圖松弛優(yōu)化聚類的快速近似提升方法*

謝　磊，王士同

江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122

1　引言

聚類是數(shù)據(jù)挖掘、統(tǒng)計(jì)機(jī)器學(xué)習(xí)和科學(xué)發(fā)現(xiàn)的首要問題。在過去幾十年中，已經(jīng)開發(fā)了各種各樣的方法來解決聚類問題[1-4]。例如在完成一些圖像分割任務(wù)時(shí)，其中的數(shù)據(jù)聚類問題便是通過高階相關(guān)聚類[5]來解決。作為解決NP-hard組合優(yōu)化問題的替代方案，半定規(guī)劃松弛被提出?；诎攵ㄒ?guī)劃松弛的方法相比于光譜/特征向量方法具有一定優(yōu)勢(shì)[6-7]，因?yàn)樵摲椒ǖ母郊蛹s束迫使優(yōu)化過程找到效果更好的解決方案。然而，這一約束也帶來了很大的負(fù)面效果：迭代終止標(biāo)準(zhǔn)對(duì)聚類結(jié)果有顯著影響。與之相比，基于圖松弛優(yōu)化聚類（graph-based relaxed clustering，GRC）[8]算法表現(xiàn)出很好效果。通過歸一化剪切改進(jìn)[6]中引入的歸一化目標(biāo)，簡化了計(jì)算，使得聚類任務(wù)可以作為二次規(guī)劃解決。聚類效果在處理復(fù)雜的集群時(shí)有所改善，且實(shí)現(xiàn)也非常簡單。

雖然GRC算法有許多優(yōu)點(diǎn)，但其并不能和經(jīng)典算法相媲美，例如層次聚類以及k-means算法，它們都在大規(guī)模數(shù)據(jù)挖掘中得到很好的應(yīng)用。原因很簡單，此算法由于計(jì)算矩陣的逆會(huì)消耗多項(xiàng)式計(jì)算時(shí)間，在計(jì)算高維大數(shù)據(jù)時(shí)會(huì)顯得非常吃力甚至不可行。

本文主要專注于設(shè)計(jì)對(duì)GRC算法的快速近似改進(jìn)算法，即主要對(duì)GRC算法做速度提升。正如在涉及計(jì)算瓶頸的數(shù)據(jù)挖掘中的許多情況一樣，本文的目標(biāo)是找到一種有效的預(yù)處理器，減少輸入到該瓶頸的數(shù)據(jù)結(jié)構(gòu)的大?。▍⒁娢墨I(xiàn)[9-10]）。此預(yù)處理步驟可以考慮許多方式，例如，可以對(duì)數(shù)據(jù)進(jìn)行多種形式的二次采樣，隨機(jī)選擇數(shù)據(jù)點(diǎn)或根據(jù)某種形式進(jìn)行分層選取。另一個(gè)選擇是用少量點(diǎn)（即“代表點(diǎn)”）替換原始數(shù)據(jù)集，目的是捕獲數(shù)據(jù)相關(guān)結(jié)構(gòu)。本文主要提供了兩個(gè)這樣的預(yù)處理方式。第一個(gè)是將k-means應(yīng)用于對(duì)初始數(shù)據(jù)的縮減步驟，第二個(gè)是使用文獻(xiàn)[11]中的隨機(jī)投影樹（random projection tree，RPTree）。實(shí)驗(yàn)顯示，通過這兩種預(yù)處理，彌補(bǔ)了GRC算法的不足，尤其在速度方面有顯著改進(jìn)。同樣，在處理一些較大規(guī)模數(shù)據(jù)時(shí)性能得到了提高。

2　相關(guān)準(zhǔn)備

2.1　GRC算法

給定n個(gè)數(shù)據(jù)點(diǎn)X1,X2,…,Xn，每個(gè)Xi∈Rd。令鄰接圖G=(V,E)定義為無向圖，其中第i個(gè)頂點(diǎn)對(duì)應(yīng)于數(shù)據(jù)點(diǎn)Xi。對(duì)于每個(gè)邊緣(i,j)∈E，本文用權(quán)重aij來表示數(shù)據(jù)點(diǎn)Xi和Xj的親和度（或相似度）。并將矩陣作為鄰接矩陣。

GRC算法的目的同樣是將數(shù)據(jù)分為多個(gè)類，使得每一數(shù)據(jù)樣本屬于且僅屬于某一類。各種聚類算法用不同的方式將這種分割問題形式化。作為解決NP-hard組合優(yōu)化問題的一個(gè)替代方案，文獻(xiàn)[12]提出了半定規(guī)劃松弛方法。同樣的，Lee等人在文獻(xiàn)[8]中提出了基于圖松弛優(yōu)化算法，需要注意的是，其中歸一化剪切（normalized cut，NC）[13]被寬限到廣義特征值系統(tǒng)：

其中e′=(1,1,…,1),L=D-A作為拉普拉斯矩陣。e的維度為數(shù)據(jù)點(diǎn)的數(shù)目，D、A分別為圖的度矩陣和鄰接矩陣。

式（1）中的兩個(gè)約束將最優(yōu)解限制在二進(jìn)制分區(qū)上。為了克服這個(gè)短缺，Lee等人進(jìn)一步松弛式（1）得：

其中Q=e′，ζ為常數(shù)，這就是所謂的GRC算法。式（2）是它的二次規(guī)劃（quadratic programming，QP）形式。作者通過使用拉格朗日乘數(shù)法又進(jìn)一步將其簡化為如下形式：

本文聚類問題的優(yōu)化以封閉形式求解，無需任何迭代即可找到L的特征屬性。但如果L是半正定，會(huì)出現(xiàn)一些問題，所以通過在L中的對(duì)角線項(xiàng)添加正值α來近似替代L，以此來保證L是正定的。當(dāng)然，在式（3）之前還可以根據(jù)對(duì)數(shù)據(jù)的了解做更多約束條件，增強(qiáng)對(duì)聚類的區(qū)分。通過y，可以很容易地知道有多少個(gè)聚類存在，直觀地區(qū)分它們。為了最后方便對(duì)比，可以對(duì)y進(jìn)行k-means運(yùn)算得到比較統(tǒng)一的聚類標(biāo)簽?？梢姡珿RC算法是自適應(yīng)的（即它不需要預(yù)先設(shè)定聚類的數(shù)量）和直接的（即所有聚類的區(qū)分可以僅通過一次單一的計(jì)算完成）。但是此方法在計(jì)算矩陣的逆時(shí)，消耗多項(xiàng)式時(shí)間，不難想象，隨著數(shù)據(jù)量的增多，矩陣維度的增大，時(shí)間消耗將逐漸變得不可接受。因此，在下節(jié)將給出快速近似提升方面的內(nèi)容。

關(guān)于GRC算法具體過程詳解如下所示。需要注意的是，在σ的選值方面，不同數(shù)據(jù)集則選值不同，一般可對(duì)各維度計(jì)算標(biāo)準(zhǔn)差后求均值得出。本文方法則是在循環(huán)計(jì)算每一維度時(shí)，根據(jù)所得數(shù)據(jù)實(shí)時(shí)運(yùn)算求出標(biāo)準(zhǔn)差。

算法1基于圖松弛優(yōu)化（GRC）算法

輸入：n個(gè)數(shù)據(jù)點(diǎn)

輸出：輸入數(shù)據(jù)的簇標(biāo)記。

1.計(jì)算出鄰接矩陣A：

2.2　快速近似方法介紹

文獻(xiàn)[17]巧妙地選擇以與其規(guī)范成比例的值對(duì)Gram矩陣的列進(jìn)行采樣的方案，從而代替均勻采樣這一步驟。因?yàn)檫@對(duì)Gram矩陣在近似誤差的約束上做出讓步，所以該方法可能需要選擇較多的列以實(shí)現(xiàn)較小的近似誤差。其誤差界限可由如下公式表示：

其中，Gk是G秩為k的最佳近似，這形成了用于近似Gram矩陣的約束。由于來自G的數(shù)量為n的采樣列，數(shù)量級(jí)為且該算法具有級(jí)的計(jì)算復(fù)雜度。從式（4）的右側(cè)可看出，為了獲得較小的近似誤差則需要非常小的ε，這也使得將要選擇的行數(shù)變大。例如，當(dāng)使用高斯內(nèi)核時(shí)會(huì)按照O(n)的量級(jí)增長，因此預(yù)期采樣列數(shù)為O(n)。本文的快速近似方法則做了相對(duì)改進(jìn)，避免像Nystro?m方法的較高內(nèi)存需求，且在處理平衡性較低的數(shù)據(jù)集時(shí)，因較小聚類被遺漏所導(dǎo)致的數(shù)值穩(wěn)定性問題也得到較好解決。

3　GRC算法的快速近似改進(jìn)

本章將介紹對(duì)GRC算法的快速近似提升的算法框架。對(duì)于這一算法的改進(jìn)，重點(diǎn)放在其建立鄰接矩陣和矩陣求逆的時(shí)間優(yōu)化上。對(duì)于此問題的解決，最為直接有效的方式便是通過縮小數(shù)據(jù)量來實(shí)現(xiàn)。文中算法主要是由預(yù)處理步驟和GRC算法步驟組成。根據(jù)GRC算法輸出的錯(cuò)誤聚類率與輸入失真之間的量化關(guān)系，便可在執(zhí)行GRC算法之前，選取合適的預(yù)處理方式，使得調(diào)用原始數(shù)據(jù)的失真最小化。本文給出兩種處理方法：第一種是基于k-means的數(shù)據(jù)預(yù)處理方式，第二種則基于RPTree。此外，這兩種方式主要具有有利的計(jì)算性質(zhì)和實(shí)現(xiàn)簡單等優(yōu)點(diǎn)。算法過程可簡單概括為圖1所示。

3.1　k-means對(duì)GRC算法的快速提升

矢量量化是為了在最小化失真度量的情況下，選出表示數(shù)據(jù)集的最佳代表點(diǎn)集合[22]。當(dāng)失真測量使用均方誤差時(shí)，矢量量化中最常用的算法是kmeans，因其具有理論支持以及簡單等多方面的優(yōu)點(diǎn)。k-means算法采用迭代過程，在每次迭代時(shí)，算法將每個(gè)數(shù)據(jù)點(diǎn)分配給最近的質(zhì)心，并重新計(jì)算聚類質(zhì)心。當(dāng)均方誤差的總和穩(wěn)定時(shí)，則程序停止，以此可得到很好的聚類中心作為數(shù)據(jù)代表點(diǎn)。使用kmeans作為聚類的預(yù)處理器，選出數(shù)據(jù)代表點(diǎn)來進(jìn)行之后的GRC運(yùn)算。以此，提出了一種“基于k-means的快速近似GRC算法”（KAGRC）算法。算法過程如下所示。

算法2KAGRC：(x1,x2,…,xn,k)

輸入：n個(gè)數(shù)據(jù)點(diǎn)k個(gè)代表點(diǎn)。

2017年，我國甘薯總產(chǎn)量7 057.1萬t,按照55%的加工比例和20%的產(chǎn)品原料比,當(dāng)年我國甘薯加工品產(chǎn)量約為780萬t．戴起偉等[5]估算結(jié)果顯示,當(dāng)前我國國內(nèi)甘薯加工產(chǎn)品消費(fèi)量約在500萬t以上,因此，粗略估算,我國甘薯加工品的年出口水平應(yīng)在200～280萬t之間．

輸出：輸入數(shù)據(jù)的聚類標(biāo)簽label。

1.將x1,x2,…,xn數(shù)據(jù)類別定義為k，進(jìn)行k-means計(jì)算。

（1）計(jì)算得出的聚類中心為y1,y2,…,yk，將其作為k個(gè)代表點(diǎn)。

（2）構(gòu)建一個(gè)對(duì)應(yīng)表，將每個(gè)xi與最近的聚類質(zhì)心yi相關(guān)聯(lián)。

2.對(duì)聚類質(zhì)心y1,y2,…,yk進(jìn)行GRC算法運(yùn)算，從而得到每一yi對(duì)應(yīng)的聚類簇標(biāo)記y，于是可直觀得到聚類情況，了解聚類數(shù)目以及大體數(shù)量。

3.通過建立的對(duì)應(yīng)表以及yi對(duì)應(yīng)的聚類簇標(biāo)記得到每一xi所對(duì)應(yīng)的聚類簇標(biāo)記label。

在KAGRC算法中，第一步k-means的計(jì)算復(fù)雜度是O(knt)，其中t表示迭代次數(shù)。第二步的復(fù)雜度不小于O(k3)，第三步復(fù)雜度為O(n)，則可知KAGRC的復(fù)雜度為O(k3)+O(knt)。

3.2　RPTree對(duì)GRC算法的快速提升

在這一方法中，則是用RPTree對(duì)k-means進(jìn)行替代，即通過隨機(jī)投影這一方式來減少失真[11]。RPTree給出了數(shù)據(jù)空間的分區(qū)，分區(qū)的每個(gè)單元格中的中心點(diǎn)作為該單元格中大量數(shù)據(jù)點(diǎn)的代表點(diǎn)。RPTree是基于k維樹（k-dimensional tree，k-d樹）的，這種空間數(shù)據(jù)結(jié)構(gòu)[23]是通過每次沿著一個(gè)坐標(biāo)遞歸地分割數(shù)據(jù)空間所得到，并非沿著坐標(biāo)方向分割，其根據(jù)選擇的方向進(jìn)行隨機(jī)投影分割。當(dāng)前單元格中的所有點(diǎn)都沿隨機(jī)方向投影，然后被分割開來。雖然古典kd樹由于對(duì)軸平行分裂的限制而縮小了數(shù)據(jù)空間的維度，但RPTree在處理數(shù)據(jù)的固有維度方面更加適合，故使用RPTree作為局部失真最小化變換不失為一種不錯(cuò)的選擇。由此可見，本文的第二種算法將KAGRC算法的步驟1替換為如下的部分內(nèi)容：

在x1,x2,…,xn上構(gòu)建一個(gè)h級(jí)隨機(jī)投影樹；將各單元格中數(shù)據(jù)點(diǎn)的質(zhì)心y1,y2,…,yk作為k個(gè)代表點(diǎn)。

得到本文的第二種改進(jìn)算法“基于RPTree的快速近似GRC算法”（RAGRC）。

該算法的時(shí)間消耗主要是RPTree在進(jìn)行數(shù)據(jù)預(yù)處理時(shí)的建樹部分以及GRC部分，算法的復(fù)雜度為O(k3)+O(hn)，其中O(hn)是建立h級(jí)隨機(jī)投影樹所需的復(fù)雜度。

至此，以上內(nèi)容即為本文算法的主要內(nèi)容，首先通過k-means或者RPTree對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理，再通過GRC算法對(duì)預(yù)處理所得的代表點(diǎn)進(jìn)行聚類，之后再映射到各點(diǎn)，從而得到數(shù)據(jù)標(biāo)簽的快速近似提升方法。

4　實(shí)驗(yàn)分析

實(shí)驗(yàn)中，主要使用兩個(gè)量來評(píng)估聚類性能：運(yùn)行時(shí)間，以及通過每個(gè)數(shù)據(jù)集的真實(shí)簇標(biāo)記和算法所得簇標(biāo)記計(jì)算出的聚類精度。運(yùn)行時(shí)間即對(duì)某一數(shù)據(jù)集運(yùn)行一次聚類算法所用時(shí)間（在此使用計(jì)算機(jī)時(shí)間）。則在同樣數(shù)據(jù)集及環(huán)境的情況下，耗時(shí)越短且聚類精度越高表明算法性能越好。聚類精度的計(jì)算方法很多，本文采用較為通俗的做法，這里需要搜索類的排列，則可令表示類情況，和分別表示數(shù)據(jù)點(diǎn)的真實(shí)簇標(biāo)記和采用聚類算法后所得簇標(biāo)記?？捎霉綄⒕垲惥圈露x為：

其中，Ι表示指標(biāo)函數(shù)；Πz是z上的所有置換集合?？紤]到當(dāng)聚類數(shù)量較多時(shí)，式（5）在計(jì)算方面受到限制，在這種情況下，從集合Πz中采樣，逐一計(jì)算后取出最佳結(jié)果使之作為β的最終估計(jì)值。在實(shí)驗(yàn)中，如果k<8，窮舉Πz，否則就從中取10 000個(gè)樣例。

4.1　實(shí)驗(yàn)平臺(tái)及數(shù)據(jù)集

本文實(shí)驗(yàn)中，所有實(shí)驗(yàn)均使用單一機(jī)器作為實(shí)驗(yàn)平臺(tái)，同時(shí)保證CPU在進(jìn)行運(yùn)算時(shí)，嚴(yán)格控制其他程序?qū)ζ滟Y源的消耗。實(shí)驗(yàn)平臺(tái)的詳細(xì)信息如表1所示。本文共9個(gè)實(shí)驗(yàn)數(shù)據(jù)集，分別為5個(gè)人造平面數(shù)據(jù)集DS1、DS2、DS3、DS4、DS5以及4個(gè)選自UCI（http://archive.ics.uci.edu/ml/datasets.html）的復(fù)雜數(shù)據(jù)集 mGamma、musk、sensorreadings和 PokerHand。數(shù)據(jù)集的具體信息如表2所示。需要說明的是，PokerHand數(shù)據(jù)集由10個(gè)類別組成，共有100萬個(gè)實(shí)例。然而，原始數(shù)據(jù)集是非常不平衡，其中有6類的總量少于總樣本的1%。本文將較小類別合并在一起，同時(shí)保持其中較大類別不變。操作之后，數(shù)據(jù)集共分為3類，分別對(duì)應(yīng)于樣本總數(shù)的50.12%，42.25%和7.63%。

Table 1　Experimental platform表1　實(shí)驗(yàn)平臺(tái)

Table 2　Experimental datasets表2　數(shù)據(jù)集

4.2　速度提升實(shí)驗(yàn)

本節(jié)將使用人造數(shù)據(jù)集DS1、DS2、DS3、DS4，DS5來進(jìn)行實(shí)驗(yàn)。需要注意的是，本節(jié)用到的5個(gè)數(shù)據(jù)集為了在時(shí)間上形成對(duì)比，都采取了較多數(shù)據(jù)點(diǎn)。此外，為了證明算法的普遍適用性，這些數(shù)據(jù)集也具有不同聚類形式，從簡單到復(fù)雜，覆蓋面較為廣泛，選取具有代表性。

首先，圖2～圖6給出了原圖及運(yùn)行GRC算法后和KAGRC算法后的圖解。

從圖中可以看出，相對(duì)于GRC算法，KAGRC算法對(duì)于各種圖形數(shù)據(jù)集聚類的效果都非常好。在運(yùn)行KAGRC算法時(shí)，其所對(duì)應(yīng)的縮減率γ為1/8，即各數(shù)據(jù)集的代表點(diǎn)k為3 750、812、1 250、750和525，其運(yùn)行時(shí)間分別為12 s、0.8 s、1.3 s、0.7 s和0.5 s。相對(duì)于直接使用GRC的259 s、8 s、28 s、6.4 s和3 s，速度都有顯著提升。本文實(shí)驗(yàn)具體的情況如表3至表7所示。

Fig.2　Original graph and experimental graph of DS1圖2　DS1原圖及實(shí)驗(yàn)圖

Fig.3　Original graph and experimental graph of DS2圖3　DS2原圖及實(shí)驗(yàn)圖

Fig.4　Original graph and experimental graph of DS3圖4　DS3原圖及實(shí)驗(yàn)圖

Fig.5　Original graph and experimental graph of DS4圖5　DS4原圖及實(shí)驗(yàn)圖

Fig.6　Original graph and experimental graph of DS5圖6　DS5原圖及實(shí)驗(yàn)圖

Table 3　Experimental results on dataset DS1表3　數(shù)據(jù)集DS1的實(shí)驗(yàn)結(jié)果

Table 4　Experimental results on dataset DS2表4　數(shù)據(jù)集DS2的實(shí)驗(yàn)結(jié)果

Table 5　Experimental results on dataset DS3表5　數(shù)據(jù)集DS3的實(shí)驗(yàn)結(jié)果

表中，γ為縮減率，k為代表點(diǎn)數(shù)。對(duì)DS1、DS3等數(shù)據(jù)樣本量大于10 000的數(shù)據(jù)集分別進(jìn)行KAGRC和RAGRC算法實(shí)驗(yàn)。需要注意的是，在隨機(jī)投影樹建樹選取代表點(diǎn)時(shí)，不能做到和KAGRC算法中所選代表點(diǎn)數(shù)目完全相同。因此，RAGRC算法在代表點(diǎn)選取時(shí)選擇與KAGRC算法代表點(diǎn)相近數(shù)量。在實(shí)驗(yàn)中，由于選點(diǎn)時(shí)存在隨機(jī)的情況，則會(huì)造成每次實(shí)驗(yàn)結(jié)果出現(xiàn)小范圍內(nèi)波動(dòng)。為此，實(shí)驗(yàn)數(shù)據(jù)則選取均值作為數(shù)據(jù)結(jié)果，以上每組實(shí)驗(yàn)所記錄數(shù)據(jù)都是在運(yùn)行數(shù)十次之后計(jì)算均值得到。從實(shí)驗(yàn)數(shù)據(jù)可以明顯看出，同預(yù)想一樣，本文提出的KAGRC算法及RAGRC算法同GRC算法相比較，在準(zhǔn)確率幾乎不變的情況下，速度明顯提高。當(dāng)然，隨著縮減率γ逐漸地減小，其代表點(diǎn)隨之增多，算法在時(shí)間消耗上也會(huì)相應(yīng)增加。從以上實(shí)驗(yàn)來看，本文算法在保證精度情況下，速度有了非常大的提升，完全達(dá)到期望值。

下面的內(nèi)容主要針對(duì)來自UCI的3個(gè)真實(shí)數(shù)據(jù)集mGamma、sensorreadings及musk進(jìn)行實(shí)驗(yàn)。對(duì)于sensorreadings數(shù)據(jù)集，本文選取其中24維度的數(shù)據(jù)樣本進(jìn)行實(shí)驗(yàn)，并對(duì)其字符進(jìn)行數(shù)字化地處理。實(shí)驗(yàn)中也都對(duì)GRC以及k-means算法進(jìn)行詳細(xì)的比較。詳細(xì)的實(shí)驗(yàn)結(jié)果在表8～表10中分別給出。

Table 6　Experimental results on dataset DS4表6　數(shù)據(jù)集DS4的實(shí)驗(yàn)結(jié)果

Table 7　Experimental results on dataset DS5表7　數(shù)據(jù)集DS5的實(shí)驗(yàn)結(jié)果

Table 8　Experimental results on dataset mGamma表8　數(shù)據(jù)集mGamma的實(shí)驗(yàn)結(jié)果

從表中數(shù)據(jù)可看出，本文算法對(duì)于真實(shí)數(shù)據(jù)集，相對(duì)于GRC算法在速度上顯著改善。對(duì)于不同的縮減率，耗時(shí)方面會(huì)隨著代表點(diǎn)增加而增加，但速度也都遠(yuǎn)快于GRC。相對(duì)于k-means算法，KAGRC在精度方面同樣表現(xiàn)得非常優(yōu)秀。

musk數(shù)據(jù)集的維度為166維，相比于文中的其他數(shù)據(jù)集，在維度上有所提升。接下來的實(shí)驗(yàn)中，為了進(jìn)一步展現(xiàn)本文算法的優(yōu)秀性能，在musk數(shù)據(jù)集分別對(duì)KAGRC、RAGRC以及GRC、k-means等算法的運(yùn)行結(jié)果進(jìn)行比較。詳細(xì)的實(shí)驗(yàn)情況如表10所示。

Table 9　Experimental results on dataset sensorreadings表9　數(shù)據(jù)集sensorreadings的實(shí)驗(yàn)結(jié)果

Table 10　Experimental results on dataset musk表10　數(shù)據(jù)集musk的實(shí)驗(yàn)結(jié)果

從表10的實(shí)驗(yàn)結(jié)果不難看出，KAGRC和RAGRC算法在精度方面已經(jīng)遠(yuǎn)遠(yuǎn)甩開k-means算法。也可注意到，兩種算法在縮減率γ減小，即代表點(diǎn)k的數(shù)量增大時(shí)，其準(zhǔn)確率也同樣是穩(wěn)步提升?？梢悦黠@看到，在KAGRC算法中，當(dāng)縮減率γ為2時(shí)，其對(duì)應(yīng)的精度已經(jīng)同GRC精度完全相同。同樣，在RAGRC算法中，當(dāng)代表點(diǎn)k為2 048時(shí)，其精度也和GRC精度非常相近。反觀時(shí)間消耗，KAGRC以及RAGRC算法無論縮減率及代表點(diǎn)如何取值，都遠(yuǎn)小于GRC算法。同樣，隨著縮減率γ減小，或者代表點(diǎn)k的數(shù)量增大時(shí)，算法的消耗時(shí)間也在合理地隨之增加。同之前實(shí)驗(yàn)相同，本節(jié)實(shí)驗(yàn)所得數(shù)據(jù)結(jié)果也是多組實(shí)驗(yàn)后取均值得到。

4.3　百萬級(jí)數(shù)據(jù)可行性實(shí)驗(yàn)

本節(jié)將對(duì)百萬量級(jí)的PokerHand數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，以說明本文算法對(duì)百萬量級(jí)數(shù)據(jù)操作的可行性。由于數(shù)據(jù)集樣本量過大，受實(shí)驗(yàn)環(huán)境的限制，無法在同等條件下進(jìn)行GRC運(yùn)算作為實(shí)驗(yàn)的對(duì)比選項(xiàng)，但是可以用其他方式來提供一個(gè)粗略的上限。在此，可將聚類問題作為一個(gè)分類問題去看待，并且選取最先進(jìn)的分類算法，即隨機(jī)森林（random forest，RF）算法[24]，以此算法所得結(jié)果來作為對(duì)比的取值。對(duì)于RF算法，選取其訓(xùn)練數(shù)據(jù)集的大小為25 010，測試數(shù)據(jù)集大小為1 000 000。同樣，在實(shí)驗(yàn)中也用k-means算法同本文算法進(jìn)行對(duì)比，其中需適量增加k-means的迭代次數(shù)，以便運(yùn)行時(shí)間與文中算法的運(yùn)行時(shí)間相同，從而保證遵循實(shí)驗(yàn)對(duì)比的單一變量原則。表11是詳細(xì)的實(shí)驗(yàn)結(jié)果。

Table 11　Experimental results on dataset PokerHand表11　數(shù)據(jù)集PokerHand的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)表明，k-means算法在增加迭代次數(shù)后并沒有顯著提高準(zhǔn)確率。同時(shí)，結(jié)果顯示，算法KAGRC和RAGRC中的數(shù)據(jù)減少并沒有嚴(yán)重降低聚類的精度，且在幾分鐘內(nèi)完成算法計(jì)算。另一方面，相對(duì)而言，KAGRC算法一定程度上稍優(yōu)于RAGRC算法。

5　結(jié)束語

本文提出了兩種對(duì)基于圖松弛優(yōu)化聚類的快速近似優(yōu)化方法。文中算法利用k-means和RPTree首先對(duì)數(shù)據(jù)點(diǎn)進(jìn)行預(yù)分組，并產(chǎn)生一組用于GRC算法的代表點(diǎn)。在實(shí)驗(yàn)階段，對(duì)多種樣本量、維度以及類別數(shù)數(shù)據(jù)集的實(shí)驗(yàn)表明，本文算法可以在聚類精度上下小范圍浮動(dòng)的情況下使GRC算法在速度上得到大幅提升。值得注意的是，本文近似算法能夠使單個(gè)機(jī)器為大型數(shù)據(jù)集運(yùn)行GRC算法。

[1]Dong Qi,Wang Shitong.Improved latent sub-space clustering algorithm and its incremental version[J].Journal of Frontiers of Computer Science and Technology,2017,11(5):802-813.

[2]Gold S,RangarajanA,Mjolsness E.Learning with preknowledge:clustering with point and graph matching distance measures[J].Neural Computation,1996,8(4):787-804.

[3]Li Tao,Wang Shitong.Incremental fuzzy(c+p)-means clustering for large data[J].CAAI Transactions on Intelligent Systems,2016,11(2):188-199.

[4]Cheng Yang,Wang Shitong.A multiple alternative clusterings mining algorithm using locality preserving projections[J].CAAI Transactions on Intelligent Systems,2016,11(5):600-607.

[5]Kim S,Nowozin S,Kohli P,et al.Higher-order correlation clustering for image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,36(36):1761-1774.

[6]Sáez A,Serrano C,Acha B.Normalized cut optimization based on color perception findings:a comparative study[J].Machine Vision&Applications,2014,25(7):1813-1823.

[7]Sookhanaphibarn K,Thawonmas R.Exhibition-area segmentation using eigenvectors[J].International Journal of Digital Content Technology&ItsApplications,2013,7(2):533-540.

[8]Lee C H,Ane O R,Park H H,et al.Clustering high dimensional data:a graph-based relaxed optimization approach[J].Information Sciences,2008,178(23):4501-4511.

[9]Madigan D,Raghavan N,Dumouchel W,et al.Likelihoodbased data squashing:a modeling approach to instance construction[J].Data Mining and Knowledge Discovery,2002,6(2):173-190.

[10]Mitra P,Murthy C A,Pal S K.Density-based multiscale data condensation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(6):734-747.

[11]Dasgupta S,Freund Y.Random projection trees and low dimensional manifolds[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing,Victoria,May 17-20,2008.New York:ACM,2008:537-546.

[12]Keuchel J.Image partitioning based on semidefinite programming[D].Mannheim:University of Mannheim,2004.

[13]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelli-gence,2000,22(8):888-905.

[14]Deveci M,Kaya K,U?ar B,et al.Hypergraph partitioning for multiple communication cost metrics:model and methods[J].Journal of Parallel&Distributed Computing,2015,77:69-83.

[15]Karypis G,Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM Journal on Scientific Computing,2006,20(1):359-392.

[16]Bādoiu M,Har-Peled S,Indyk P.Approximate clustering via core-sets[C]//Proceedings of the 34th Annual ACM Symposium on Theory of Computing,Montréal,May 19-21,2002.New York:ACM,2002:250-257.

[17]Drineas P,Mahoney M W.On the Nystr?m method for approximating a gram matrix for improved kernel-based learning[J].Journal of Machine Learning Research,2005,6:2153-2175.

[18]Williams C K I,Seeger M.Using the Nystr?m method to speed up kernel machines[C]//Proceedings of the Neural Information Processing Systems,Denver.Cambridge:MIT Press,2001:682-688.

[19]Fine S,Scheinberg K.Efficient SVM training using low-rank kernel representations[J].Journal of Machine Learning Research,2002,2(2):243-264.

[20]Hao P,Wang L,Niu Z.Comparison of hybrid classifiers for crop classification using normalized difference vegetation index time series:a case study for major crops in North Xinjiang,China[J].PLOS One,2015,10(9):e0137748.

[21]Fowlkes C C,Belongie S J,Chung F R K,et al.Spectral grouping using the Nystr?m method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(2):214-225.

[22]Gray R M,Neuhoff D L.Quantization[J].IEEE Transactions on Information Theory,1998,44(6):2325-2383.

[23]Buaba R,HomaifarA,Kihn E.Optimal load factor for approximate nearest neighbor search under exact Euclidean locality sensitive hashing[J].International Journal of Computer Applications,2013,69(21):22-31.

[24]Breiman L.Random forest[J].Machine Learning,2001,45(1):5-32.

附中文參考文獻(xiàn)：

[1]董琪,王士同.隱子空間聚類算法的改進(jìn)及其增量式算法[J].計(jì)算機(jī)科學(xué)與探索,2017,11(5):802-813.

[3]李滔,王士同.適合大規(guī)模數(shù)據(jù)集的增量式模糊聚類算法[J].智能系統(tǒng)學(xué)報(bào),2016,11(2):188-199.

[4]程旸,王士同.基于局部保留投影的多可選聚類發(fā)掘算法[J].智能系統(tǒng)學(xué)報(bào),2016,11(5):600-607.