1提綱第7章基于核熵成分分析的量子聚類算法7.4結(jié)論與討論7.2基于核熵成分分析的量子聚類算法2提綱第7章基于核熵成分分析的量子聚類算法7.1量子聚類算法7.3實驗結(jié)果及分析7.4結(jié)論與討論7.2基于核熵成分分析的量子聚類算法3提綱第7章基于核熵成分分析的量子聚類算法7.1量子聚類算法7.3實驗結(jié)果及分析47.1量子聚類算法

為了實現(xiàn)量子力學(xué)在聚類分析中的應(yīng)用，DavidHorn和AssafGottlieb提出了量子聚類的概念。他們將聚類問題看作一個物理系統(tǒng)，構(gòu)建粒子波函數(shù)表征原始數(shù)據(jù)集中樣本點的分布。通過求解薛定諤方程式獲得粒子勢能分布情況，而勢能最小的位置可以確定為聚類的中心點。

隨著現(xiàn)代科技的迅猛發(fā)展，聚類所面對的數(shù)據(jù)的規(guī)模也越來越大，結(jié)構(gòu)也越來越復(fù)雜。此時，量子聚類也面臨著不小的挑戰(zhàn)。為了更加精確且高效地實現(xiàn)數(shù)據(jù)的聚類，本章參考并結(jié)合了核聚類、信息熵、譜聚類以及K近鄰的一些思想，來優(yōu)化量子聚類算法。本章提出了一種新的量子聚類方法——利用核熵成分分析的量子聚類（KECA-QC）。該方法可分為兩個子步驟：預(yù)處理和聚類。在數(shù)據(jù)預(yù)處理階57.1量子聚類算法段，結(jié)合核熵主成分分析替代原來簡單的特征提取方式，將原始數(shù)據(jù)映射至高維特征空間，使非線性可分的數(shù)據(jù)在特征空間變得線性可分。并用熵值作為篩選主成分的評價標(biāo)準(zhǔn)，提取核熵主成分。預(yù)處理能夠有效解決數(shù)據(jù)間復(fù)雜的非線性關(guān)系問題，尤其對于高維數(shù)據(jù)，還能夠同時達(dá)到降維的目的。在聚類階段，在傳統(tǒng)量子聚類算法的基礎(chǔ)上，引入K近鄰法來估計量子波函數(shù)及勢能函數(shù)。這種局部信息的引入既降低了算法運行時間，又提高了聚類的精度。為了進(jìn)一步驗證該方法的有效性，本章通過與四種對比算法KM（K均值法）、NJW（著名的譜聚類方法）、QC（傳統(tǒng)量子聚類算法）和KECA-KM（核熵成分分析聚類方法）作比較，對8個人工合成數(shù)據(jù)集和10個UCI數(shù)據(jù)集進(jìn)行實驗結(jié)果的統(tǒng)計，分析這五種算法的性能。67.1量子聚類算法

量子力學(xué)描述了微觀粒子在量子空間的分布，而這同聚類是研究數(shù)據(jù)樣本在尺度空間中的分布情況是等價的。波函數(shù)是粒子量子態(tài)的描述[1]，波的強度決定了粒子出現(xiàn)在空間某處的概率。薛定諤提出的波動方程描述了微觀粒子的運動，其目的是求解波函數(shù)，即有勢場約束的粒子的分布狀況。換句話說，粒子量子態(tài)的演化遵循薛定諤方程。本章使用不顯含時間的薛定諤方程，其方程式可以表述為：(7-1)其中，

為波函數(shù)；

為勢能函數(shù)；

為Hamilton算子；

為算子

的能量特征值；

為劈形算子；

為波函數(shù)寬度調(diào)節(jié)參數(shù)。

量子力學(xué)理論的研究發(fā)現(xiàn)，微觀粒子自身所具有的勢能影響著粒子在能量場中的分布。從式(7-1)也容易看出，勢能相同，則粒子的狀77.1量子聚類算法態(tài)分布相同。勢能函數(shù)相當(dāng)于一個抽象的源，隨著勢能趨近于零或者比較小時，在一定寬度的勢阱中往往分布有較多的粒子。當(dāng)粒子的空間分布縮變到一維無限深勢阱時，粒子則聚集在勢能為零的勢阱中。

從量子力學(xué)角度出發(fā)，對于樣本分布已知的數(shù)據(jù)，等價描述為粒子分布的波函數(shù)已知。聚類過程相當(dāng)于：在波函數(shù)已知時，利用薛定鍔方程反過來求解勢能函數(shù)，而這個勢能函數(shù)決定著粒子的最終分布。這就是量子聚類[2-4]的物理思想依據(jù)。在量子聚類中，本章使用帶有Parzen窗的高斯核函數(shù)估計波函數(shù)（即樣本點的概率分布），即：(7-2)上式對應(yīng)于尺度空間中的一個觀測樣本集

，

高斯函數(shù)可以看作是一個核函數(shù)[5]，它定義了一個由輸入空間到Hilbert空間的非線性映射。因此也可以認(rèn)為

是一個核寬度調(diào)節(jié)參數(shù)。87.1量子聚類算法

因此，當(dāng)波函數(shù)

已知時，若輸入空間只有一個單點

，即

通過求解薛定諤方程，勢能函數(shù)表示為： (7-3)

根據(jù)量子理論可知，式(7-3)是粒子在諧振子中的調(diào)和勢能函數(shù)的表達(dá)形式，此時

算子的能量特征值為

，其中

為算子

的可能的最小特征值，可以用樣本的數(shù)據(jù)維數(shù)來表示[4]。

對于一般情況，本章進(jìn)一步把式(7-2)帶入(7-1)，得到樣本服從高斯分布的勢能函數(shù)的計算公式： (7-4)

本章假定

非負(fù)且確定，也就是說

的最小值為零，

可以通過求解式(7-4)得到：97.1量子聚類算法

(7-5)

根據(jù)量子力學(xué)理論可知，當(dāng)粒子具有較低勢能時，其振動較小，相對來說比較穩(wěn)定。這從聚類的角度看，就相當(dāng)于勢能最小或者為零的樣本周圍也會有比較多的樣本存在。由于樣本的勢能函數(shù)值是可以被確定計算的，因此可以利用勢能來確定聚類中心。當(dāng)樣本數(shù)據(jù)符合歐氏分布時，利用梯度下降法找到勢能函數(shù)的最小點作為聚類的中心。其迭代公式[3-5]為： (7-6)其中，初始點設(shè)為

；

為算法的學(xué)習(xí)速率；

為勢能的梯度。最終，粒子朝勢能下降的方向移動，即數(shù)據(jù)點將逐步朝其所在的聚類中心的位置移動，并在聚類中心位置處停留。因此，可以利用量子107.1量子聚類算法方式確定聚類的中心點。距離最近的某些點被歸為一類。

從整體來看，在QC算法中勢能函數(shù)就相當(dāng)于量子聚類的價值函數(shù)，其聚類中心不是簡單的幾何中心或隨機確定，而是完全取決于樣本自身的潛在信息；且聚類不需要預(yù)先假定任何特別的樣本分布模型和聚類類別數(shù)；是一種基于劃分的無監(jiān)督聚類算法。7.4結(jié)論與討論7.2基于核熵成分分析的量子聚類算法11提綱第7章基于核熵成分分析的量子聚類算法7.1量子聚類算法7.3實驗結(jié)果及分析127.2基于核熵成分分析的量子聚類算法(1)核熵成分分析方法

一個純粹的量子聚類方法不是在所有的實例中都是很有效的，尤其是當(dāng)數(shù)據(jù)集的維數(shù)較高時。究其原因，一是數(shù)據(jù)之間存在著一定量的冗余信息，這極有可能過度強化某一屬性的信息，而忽略某些有用的特征，阻礙了尋找數(shù)據(jù)間真實的潛在結(jié)構(gòu)；二是隨著數(shù)據(jù)量或者維度增加，直接對原始數(shù)據(jù)集進(jìn)行處理會給算法運行帶來很高的計算代價。為了解決上述問題，DavidHorn和InonAxel等人認(rèn)為在執(zhí)行量子聚類之前，應(yīng)該對原始數(shù)據(jù)集進(jìn)行一個預(yù)處理的步驟。在文獻(xiàn)[3-4]中，這個預(yù)處理指的是用奇異值分解（SVD）的方法實現(xiàn)由原始數(shù)據(jù)空間到特征空間的轉(zhuǎn)換。這種利用SVD的量子聚類方法就是最經(jīng)典的量子聚類方法，后續(xù)的實驗中仍用QC來表示它。然而SVD也存在著137.2基于核熵成分分析的量子聚類算法比較明顯的缺點：SVD是一個線性變換。雖然線性變換計算方便，并且容易推廣到新的數(shù)據(jù)上，但是在實際的生產(chǎn)中，數(shù)據(jù)間往往呈現(xiàn)復(fù)雜的非線性關(guān)系，因此線性變換在許多實際問題中并不適用。主成分分析法（PCA）也存在著同樣的問題。因此，在很多情況下，這種線性變換方法不能達(dá)到較好的效果。基于此，許多學(xué)者將其推廣到核空間中去解決，以適應(yīng)非線性的情況，如核主成分分析法（KPCA）[6-7]。

給定一個數(shù)據(jù)集

，其中

。本章同樣使用高斯核矩陣做空間變換： (7-7)其中，

是高斯核的唯一參數(shù)。

為一個

的核矩陣，其維度等于147.2基于核熵成分分析的量子聚類算法樣本點的個數(shù)。核矩陣可以分解為

，其中

為由特征值

（

）組成的對角矩陣，

為對應(yīng)的特征向量

作為列向量構(gòu)成的矩陣。

如圖7-1，本章使用兩個合成數(shù)據(jù)集（a-1和b-1）作為例子展示數(shù)據(jù)的預(yù)處理結(jié)果。（a-2,a-3，b-2和b-3）都代表著數(shù)據(jù)變換空間的二維映射。可以很明顯的看出線性變換和非線性變換的顯著差別。SVD不能將不同的類分開，KPCA則很容易抓住相對較為復(fù)雜數(shù)據(jù)結(jié)構(gòu)。尤其對Synthetic2尤為明顯：KPCA完全將兩個類分隔開，而SVD沒有。157.2基于核熵成分分析的量子聚類算法圖7-1利用SVD和KPCA的數(shù)據(jù)變換和聚類類別數(shù)；是一種基于劃分的無監(jiān)督聚類算法。167.2基于核熵成分分析的量子聚類算法

在數(shù)據(jù)的預(yù)處理過程中，本章總是選擇前

個最大的特征值所對應(yīng)的特征向量。然而，這并不能保證能夠很好的提取數(shù)據(jù)集的結(jié)構(gòu)信息。如圖7-2，以synthetic1為例，展示了前6個特征向量（

）。在所有特征向量中，均各有一段曲線對應(yīng)的樣本值不為零，而其他部分為零。如果使用KPCA進(jìn)行數(shù)據(jù)的特征提取，按照特征值的大小會選取前3個特征向量（

）。

中不為零的樣本與

基本相同，均沒有體現(xiàn)第1和第3類的特征。因此可以得出這樣的結(jié)論：

和

提供給的類的信息是相同的。因此，應(yīng)該采用更有效的方式提取不同類樣本的差異。177.2基于核熵成分分析的量子聚類算法圖7-2按降序排列前6個最大的特征值所對應(yīng)的特征向量187.2基于核熵成分分析的量子聚類算法

假設(shè)待聚類數(shù)據(jù)集是一個系統(tǒng)，聚類算法實際上就是將這個系統(tǒng)從無序（各模式隨機放置）到有序（各模式按相似性聚集在一起）的過程。而熵可以作為系統(tǒng)有序性的度量。從信息論的角度，Jenssen等人將熵與核方法數(shù)據(jù)映射結(jié)合起來，提出核熵主成分分析法（KECA）[8]。在計算熵的時候用到帶有高斯核函數(shù)的Parzen窗作為概率分布模型，很自然地將熵的計算化為核矩陣的計算，構(gòu)造成為一個核空間里的優(yōu)化問題。

設(shè)

是數(shù)據(jù)的

概率密度函數(shù)，則該數(shù)據(jù)的信息熵為

。由于對數(shù)函數(shù)是單調(diào)函數(shù)，所以只需考慮

即可。為了估計

，需要進(jìn)行Parzen窗的密度估計

，這就將熵的計算和高斯核矩陣聯(lián)系在一起。

的值可通過數(shù)學(xué)推導(dǎo)得出：197.2基于核熵成分分析的量子聚類算法

(7-8)其中，

為每個元素均取1的

的向量；

是第

個特征值和特征向量對應(yīng)的熵的貢獻(xiàn)值。

以熵值大小為度量標(biāo)準(zhǔn)，降序排列特征值及其對應(yīng)的特征向量。令

為一個包含前

個對應(yīng)的特征值的對角矩陣，

為一個以前

個對應(yīng)特征向量為列的矩陣，則利用KECA得到特征空間中的變換數(shù)據(jù)為：

(7-9)

為一個

的核熵主成分矩陣，將其作為輸入數(shù)據(jù)用于下一步的量子聚類，其每一行都對應(yīng)著原始數(shù)據(jù)集中的一個點。

圖7-3展示了利用KECA的Synthetic1和Synthetic2的預(yù)處理結(jié)果。207.2基于核熵成分分析的量子聚類算法對于Synthetic1，KPCA選取前2個特征值及其對應(yīng)的特征向量，而圖7-3(a)中，KECA則選擇第一個和第三個主成分。對比圖7-1(a-3)和圖7-3(a)，加入熵選擇的數(shù)據(jù)呈現(xiàn)的結(jié)構(gòu)更加清晰。對于Synthetic2亦是如此。KECA可以更好的保留數(shù)據(jù)集的聚類結(jié)構(gòu)信息，擴大類與類之間的差異。尤其對線性不可分的數(shù)據(jù)集，表現(xiàn)出更好的優(yōu)越性。此外，利用KECA的預(yù)處理為量子聚類奠定了基礎(chǔ)，同時提高了聚類效率。圖7-3利用KECA的數(shù)據(jù)變換217.2基于核熵成分分析的量子聚類算法

總的來說，通過KECA預(yù)處理，將原始數(shù)據(jù)映射到高維特征空間，提取特征并用熵作為度量選擇主成分?？梢哉f，KECA是一個先升維后降維的過程。KECA去除了數(shù)據(jù)的冗余信息，獲得更加緊湊和經(jīng)濟的數(shù)據(jù)表示形式，同時更加有效地表達(dá)數(shù)據(jù)的潛在結(jié)構(gòu)。此外，KECA將一個非線性可分的問題轉(zhuǎn)變?yōu)橐粋€線性可分的問題，在結(jié)構(gòu)更為復(fù)雜的數(shù)據(jù)上也能夠獲得較好的處理效果。這些都有助于聚類準(zhǔn)確度的提高。對于那些維度較高的數(shù)據(jù)，采用KECA還能夠同時達(dá)到降維的目的。應(yīng)當(dāng)指出的是，預(yù)處理變換后的數(shù)據(jù)維度有可能大于原始數(shù)據(jù)的維度，尤其是對那些低維原始數(shù)據(jù)。盡管如此，變換處理后的數(shù)據(jù)仍是有利于聚類分析的。不論原始數(shù)據(jù)維度的高低，變換后的數(shù)據(jù)維度都會維持在一個較低的水平。雖然數(shù)據(jù)的預(yù)處理需要花費227.2基于核熵成分分析的量子聚類算法一定的時間，但是這對于后期聚類運行的效率和聚類的精度提高，付出的代價是值得的。(2)K近鄰的量子聚類

在QC算法中，

的每一行都可以看做是一個粒子對應(yīng)著原始數(shù)據(jù)的一個數(shù)據(jù)點。從式(7-2)中可以看出，要計算粒子的波函數(shù)就必須統(tǒng)計該粒子到所有其他粒子的核距離，也就是說，粒子的波函數(shù)受其他粒子的共同作用，作用的大小以高斯核距離為衡量標(biāo)準(zhǔn)。距離越遠(yuǎn)，其影響力越小。假設(shè)數(shù)據(jù)集中有

個樣本，每次迭代都需要計算

個波函數(shù)，每個波函數(shù)的獲得又需要統(tǒng)計

各高斯核距離。因此，在量子聚類中，波函數(shù)的計算復(fù)雜度為

。隨著數(shù)據(jù)樣本點的增加，每次迭代算法執(zhí)行時間會以指數(shù)形式增長。237.2基于核熵成分分析的量子聚類算法圖7-4高斯核函數(shù)分布

本章提出了一種新的統(tǒng)計波函數(shù)的方法。圖7-4所示的為規(guī)模參數(shù)為1的高斯核函數(shù)的分布。橫坐標(biāo)表示粒子之間的距離，縱坐標(biāo)表示高斯核函數(shù)值，即粒子的作用力大小。可以很直觀的看出，它的作用是局部的，隨著距離的增加，它的作用效果下降的速度非?？?，直至無限接近于0，因此它往往用于低通濾波。這里可以做一個大膽的假設(shè)：某處粒子的波函數(shù)值僅受其周圍粒子的影響?；谶@個假設(shè)來估計波函數(shù)只需要考慮樣本的局部信息。本方法采用K近鄰策略進(jìn)247.2基于核熵成分分析的量子聚類算法行波函數(shù)的估計。假設(shè)一個有

個樣本點的數(shù)據(jù)集，

是其中任意一個樣本，

的最近的K個鄰居的集合用

表示。根據(jù)其他樣本點

到該樣本點

的歐式距離排列樣本： (7-10)其中，

；

為

的K個近鄰的集合。

是整個數(shù)據(jù)集中距離

最近的點，

是

外其他點中距離

最近的點。本章重新估計波函數(shù)為： (7-11)用上式代替原來的波函數(shù)的估計公式（式(7-2)）。本式只需要考慮樣本的K近鄰

，而不是所有樣本點。最終勢能函數(shù)重寫為： (7-12)257.2基于核熵成分分析的量子聚類算法(3)算法描述結(jié)合上一節(jié)中QC算法，本章提出一種新的量子聚類方法——利用核熵成分分析的量子聚類（KECA-QC）。該方法是一個兩階段過程，首先在數(shù)據(jù)預(yù)處理階段，結(jié)合核熵主成分分析替代簡單的特征提取方式將原始數(shù)據(jù)映射至高維特征空間，并用熵值作為篩選主成分的評價標(biāo)準(zhǔn)，提取核熵主成分。其次在聚類階段，結(jié)合量子聚類方法和K近鄰策略，通過梯度下降方法不斷迭代以獲得最終聚類結(jié)果。KECA-QC的算法流程如圖7-5所示，包含以下步驟：267.2基于核熵成分分析的量子聚類算法KECA-QC算法預(yù)處理階段:輸入一個數(shù)據(jù)集數(shù)據(jù)集

，建立高斯核矩陣

。通過非線性數(shù)據(jù)映射，在特征空間計算

的特征值和特征向量，并根據(jù)熵值

的大小重新排列所對應(yīng)的特征值和特征向量。設(shè)置主成分個數(shù)選擇參數(shù)

，得到核熵主成分矩陣

，其每一行都可看作量子聚類中的一個粒子，并與原始數(shù)據(jù)中的數(shù)據(jù)點相對應(yīng)。聚類階段:計算波函數(shù)

，勢能函數(shù)

及其梯度下降方向

，同時統(tǒng)計每個粒子

的K個最近的鄰居，即

。利用梯度下降方法不斷迭代尋找量子勢能的最小值，直到達(dá)到設(shè)定的最大迭代次數(shù)。最終特征空間中的每個點都會聚縮在其所在的聚類中心的位置附近。根據(jù)每個粒子點距離聚類中心的遠(yuǎn)近劃分其至不同的類中，完成聚類過程。277.2基于核熵成分分析的量子聚類算法圖7-5KECA-QC算法流程

從廣義上說，任何涉及聚類特征分解的算法都可以被稱為譜聚類（SpectralClustering,SC）[9-10]。從這個角度看，KECA-QC也應(yīng)屬于廣義意義上的譜聚類算法。由此可見，本章的算法同樣具有譜聚類算法的一般優(yōu)勢，或者說KECA-QC在算法性能上和SC相匹敵。經(jīng)典譜287.2基于核熵成分分析的量子聚類算法聚類算法的一般步驟如下：構(gòu)建相似度矩陣或者拉普拉斯矩陣，選擇前

個最大的特征值對應(yīng)的特征向量組成特征矩陣，并將其中每一行看作特征空間中的一個向量，使用K-means方法進(jìn)行聚類，聚類結(jié)果中每一向量所屬的類別就是對應(yīng)的原數(shù)據(jù)集中數(shù)據(jù)點所屬的類別。從以上步驟可以看出，KECA-QC與譜聚類在算法框架上非常相似，為此本章在實驗部分給出KECA-QC與譜聚類的代表性算法Ng-Jordan-Weiss(NJW)的比較。297.2基于核熵成分分析的量子聚類算法(4)參數(shù)設(shè)置

在KECA-QC中，有如下參數(shù)需要事先設(shè)置：核參數(shù)

（預(yù)處理KECA中）和

（聚類QC中），主成分個數(shù)

，梯度下降迭代次數(shù)

，以及近鄰個數(shù)

。

核方法的其中一個難點就是核參數(shù)的選擇。從式(7-2)、(7-7)和(7-11)中可以看出，改變了核參數(shù)實質(zhì)上隱含地改變了映射函數(shù)，從而改變了樣本數(shù)據(jù)在核空間分布的復(fù)雜程度，因此核參數(shù)的選擇會對最終的聚類效果產(chǎn)生直接的影響。一般來講，核參數(shù)是一個不太明確的經(jīng)驗值[3-4]，需要通過多次實驗去篩選優(yōu)化。許多學(xué)者致力于設(shè)計用一個較為確定的方法選擇核參數(shù)，如Silverman[11]構(gòu)建了一個以樣本集維度和大小為變量的核參數(shù)選擇函數(shù)；Varshavsky使用貝葉斯307.2基于核熵成分分析的量子聚類算法信息準(zhǔn)則選擇核參數(shù)，評估聚類的質(zhì)量[12]；NikolaosNasios等人認(rèn)為核參數(shù)可以從K近鄰的統(tǒng)計分布中估計[13]。在本章中，為了簡化核參數(shù)的選擇，本章根據(jù)文獻(xiàn)[13]中的方法定義

： (7-13)

由上式可以看出，

的值其實就是樣本點到其K近鄰點的的平均歐氏距離。雖然這種方法無法找到最優(yōu)的

，但可以用較小的時間復(fù)雜度找到相對優(yōu)的

，在文獻(xiàn)[13]中已驗證。根據(jù)式(7-13)，高斯核矩陣

（式(7-7)），波函數(shù)

（式(7-11)）和勢能函數(shù)（式(7-12)）都能夠計算得到。這里設(shè)置近鄰個數(shù)

。根據(jù)量子聚類參考文獻(xiàn)[14]，設(shè)置相同的參數(shù)

，實驗也證明，量子聚類過程中梯度下降迭代10次至20次，粒子就已經(jīng)基本處于穩(wěn)定狀態(tài)。核熵主成分個數(shù)

通過熵的差分方法得到，具體來說，對熵進(jìn)行降序排列，

，

。7.4結(jié)論與討論7.2基于核熵成分分析的量子聚類算法31提綱第7章基于核熵成分分析的量子聚類算法7.1量子聚類算法7.3實驗結(jié)果及分析327.3實驗結(jié)果及分析

為了進(jìn)一步測試KECA-QC的有效性，本章對18個數(shù)據(jù)集進(jìn)行實驗（包括8個計算機合成數(shù)據(jù)集和10個UCI數(shù)據(jù)集[15]）。對比算法有：KM（K均值法）[16]、NJW（代表性譜聚類算法）[17]、QC（傳統(tǒng)量子聚類算法）[3]和KECA-KM（核熵成分分析聚類方法）[18]。在這四種對比算法中，QC不需要預(yù)設(shè)聚類的個數(shù)。以下三個指標(biāo)用于評價算法的性能：MinkowskiScore(MS)[19]，JaccardScore(JS)[3]和正確率（clusteraccuracy,CA）。

這里，KM是一個眾所周知的無監(jiān)督聚類算法，通過優(yōu)化目標(biāo)函數(shù)獲得最終的聚類結(jié)果；在7.1.3節(jié)中，已給出了SC算法的描述，NJW使用拉普拉斯矩陣的前

個特征向量將數(shù)據(jù)集劃分為

類；傳統(tǒng)的QC算法在7.1.2節(jié)已詳細(xì)給出；而KECA-KM算法的大體流程是，337.3實驗結(jié)果及分析首先提取前

個核熵主成分，然后利用角距離的K均值算法將數(shù)據(jù)劃分成

類。

實驗運行的PC環(huán)境為Intel(R)Core(TM)2DuoCPU2.33GHz2GRAM，在Matlab7.4(R2007a)環(huán)境下編程實現(xiàn)。

在接下來的實驗中，由于KM和NJW都是隨機優(yōu)化算法，為了公平比較，其實驗結(jié)果是在獨立運行100次的基礎(chǔ)上得到的。QC，KECA-KM和KECA-QC都是確定性算法，算法運行1次即可。(1)數(shù)據(jù)集及評價指標(biāo)

表7-1為10個合成數(shù)據(jù)集基本描述，并在圖7-6中具體展示。AD_9_2和AD_20_2均為緊湊型的簇狀數(shù)據(jù)，而data12和sizes5中的數(shù)據(jù)分布較為彌漫；data8、eyes、lineblobs和spiral是四個流形數(shù)據(jù)集。347.3實驗結(jié)果及分析表7-2給出了10個UCI數(shù)據(jù)集的基本描述，包括breastcancer(WBC)、german、glass、heart、ionosphere、iris、new_thyroid、sonar,、vote和zoo。

在本章中，以下三個指標(biāo)用于評價算法的性能：MinkowskiScore（MS）：

(7-14)JaccardScore:（JS）：

(7-15)其中，表示同時屬于真實聚類標(biāo)簽和通過聚類算法獲得的類別標(biāo)簽的成對的樣本的數(shù)目；表示僅屬于真實聚類標(biāo)簽的成對的樣本的數(shù)目；表示僅屬于聚類獲得的類別標(biāo)簽的成對的數(shù)據(jù)數(shù)目。357.3實驗結(jié)果及分析

本章定義

為實際輸入的總的樣本個數(shù)；

為真實的類別數(shù)；

為聚類獲得的類別數(shù)；

為混淆矩陣。Clusteraccuracy（CA）：

(7-16)其中，混淆矩陣中

表示同時出現(xiàn)在真實類別中第i類和聚類獲得的第j類的樣本點數(shù)目。由于屬于同一真實類別的樣本可能在聚類中被劃分至多個類別，因此取聚類中樣本點個數(shù)最多的那個作為統(tǒng)計輸入。

以上三個指標(biāo)的返回值都在[0,1]區(qū)間內(nèi)。MS的值越小表明聚類效果越好；而JS和CA的值越大，聚類效果越好。當(dāng)取得完全正確的結(jié)果時，MS的值為0；其他兩個評價指標(biāo)的值均為1。367.3實驗結(jié)果及分析表7-1合成數(shù)據(jù)集基本描述數(shù)據(jù)集樣本個數(shù)樣本維數(shù)類別數(shù)AD_9_245029AD_20_21000220data1280024sizes5100024data860022eyes30023lineblobs26623spiral100022377.3實驗結(jié)果及分析387.3實驗結(jié)果及分析圖7-6合成數(shù)據(jù)集397.3實驗結(jié)果及分析表7-2UCI數(shù)據(jù)集基本描述(2)合成數(shù)據(jù)和UCI數(shù)據(jù)的實驗

表7-3給出了五種算法在合成數(shù)據(jù)集上的比較，加粗的數(shù)字表示五種算法中最好的結(jié)果。數(shù)據(jù)集樣本個數(shù)樣本維數(shù)類別數(shù)breastcancer(WBC)68392german1000242glass21496heart270132ionosphere351332iris15043new_thyroid21553sonar208602vote435162zoo101167407.3實驗結(jié)果及分析表7-3五種算法在合成數(shù)據(jù)集上的比較DatasetKMNJWQCKECA-KMKECA-QCAD_9_2MS0.54380.49680.09380.09380.0938JS0.74300.78070.99120.99120.9912CA0.87100.89690.99780.99780.9978AD_20_2MS0.58360.5163000JS0.73200.7756111CA0.86340.8914111data12MS0.28570.21010.15730.15730.1721JS0.89530.93200.97560.97560.9708CA0.94500.96390.99380.99380.9925sizes5MS0.42350.22410.17990.23400.1673JS0.77710.94560.96860.94750.9722CA0.95140.96030.98500.91300.9890data8MS0.73930.72700.75710.58640JS0.57100.58200.55560.70661CA0.83670.84330.82670.90501eyesMS0.84430.15000.89480.37230JS0.52260.92050.50170.87091CA0.75330.94330.69670.96331lineblobsMS0.88110.10890.907500JS0.44930.93970.432611CA0.74060.96420.714311spiralMS0.982900.98440.81320JS0.348510.34720.50331CA0.592010.58800.79101417.3實驗結(jié)果及分析KM和NJW分別是聚類和譜聚類的代表性算法，比較這兩種算法，顯然NJW獲得更好的聚類結(jié)果，尤其是在4個流形數(shù)據(jù)集上。由此可以得出結(jié)論，NJW不僅能處理簇狀數(shù)據(jù)，在流形數(shù)據(jù)集上還能獲得比KM有更好的聚類能力。傳統(tǒng)的QC算法在粗壯數(shù)據(jù)集上表現(xiàn)了很好的性能，然而，此算法在流行數(shù)據(jù)集上同樣表現(xiàn)不佳。NJW、KECA-KM和KECA-QC都可以稱為廣義上的譜聚類算法。這三種算法在流形數(shù)據(jù)的聚類效果上明顯優(yōu)于KM和QC。KECA-QC在多數(shù)數(shù)據(jù)集上聚類效果比NJW好。KECA-QC表現(xiàn)最優(yōu)，在7個數(shù)據(jù)集上取得最優(yōu)值，只有在數(shù)據(jù)集data12上取得次優(yōu)結(jié)果（MS:0.1721,JS:0.9708,CA:0.9925）。值得注意的是，在4個流形數(shù)據(jù)集上，KECA-QC取得了完全正確的聚類結(jié)果（MS:0,JS:1,CA:1），在spiral上427.3實驗結(jié)果及分析NJW取得的結(jié)果是完全正確的，在lineblobs上KECA-KM的結(jié)果是完全正確的。此外，QC和KECA-QC在簇狀數(shù)據(jù)集上的效果大致相同，因此，可以說引入核熵成分分析提高了量子聚類在復(fù)雜結(jié)構(gòu)的流形數(shù)據(jù)集上的聚類能力。表7-4五種算法在UCI數(shù)據(jù)集上的比較DatasetKMNJWQCKECA-KMKECA-QCbreastcancer(WBC)MS0.37330.33070.47520.29840.3230JS0.87070.89620.79230.91430.9003CA0.96050.96920.93410.97510.9707germanMS0.86970.84350.89600.72850.8797JS0.49050.57130.42250.62230.4606CA0.70000.70900.70000.81000.7000glassMS1.09311.03681.08590.99211.0839JS0.31760.27770.24460.28600.3418CA0.56850.59050.56080.64020.5841heartMS0.97670.97380.96370.94690.9446JS0.36320.35600.39030.43770.4197CA0.59260.60000.62220.65180.6556437.3實驗結(jié)果及分析DatasetKMNJWQCKECA-KMKECA-QCionosphereMS0.87140.87890.94680.87140.5618JS0.43580.42830.39100.43580.7360CA0.71220.70370.64100.71220.9060irisMS0.66240.62300.58310.56660.3200JS0.65790.68190.71670.72380.9026CA0.84800.87910.90000.90670.9733new_thyroidMS0.66590.84650.62840.60370.6002JS0.63160.57780.70750.71470.7243CA0.84260.75350.86510.87440.8745sonarMS0.99210.99120.99110.91280.9462JS0.34000.35480.35700.46370.3869CA0.55290.55660.55770.70190.6586voteMS0.66870.66530.66290.65310.6379JS0.62980.63060.63270.64210.6556CA0.86160.86550.86670.87130.8782zooMS0.78270.82010.82730.48940.4776JS0.47870.42310.49400.77950.7930CA0.82180.78240.77210.85150.8812447.3實驗結(jié)果及分析

從表7-4可以看出，在10個UCI數(shù)據(jù)集中KECA-QC有6個取得了最優(yōu)結(jié)果，KECA-KM在其他4個數(shù)據(jù)集取得最優(yōu)結(jié)果。同時，結(jié)果表明，KECA-QC在所有測試數(shù)據(jù)集上的結(jié)果都比KM、NJW以及傳統(tǒng)的QC算法好。KECA-KM取得次優(yōu)記過，這是因為該算法在聚類階段使用的基于余弦角度距離度量的K均值算法，而KECA預(yù)處理得到的數(shù)據(jù)往往是帶有夾角結(jié)構(gòu)的。從整體上看，KECA-QC在UCI數(shù)據(jù)集上的的優(yōu)勢表現(xiàn)得不如在人工合成數(shù)據(jù)集上的那么明顯。這主要是因為，UCI數(shù)據(jù)集的結(jié)構(gòu)不像合成數(shù)據(jù)集的結(jié)構(gòu)那么簡單，它們的結(jié)構(gòu)較為多樣化，且其數(shù)據(jù)屬性也非常復(fù)雜?？偟膩碚f，本章改進(jìn)的算法，相比于其他四種對比算法，仍能取得較好地聚類結(jié)果。457.3實驗結(jié)果及分析(3)KECA和K近鄰對聚類的貢獻(xiàn)

表7-3和表7-4表明，KECA-QC的聚類效果明顯優(yōu)于傳統(tǒng)的QC算法，這主要是由于核熵主成分預(yù)處理過程提取了有用的結(jié)構(gòu)信息。由于三個評價指標(biāo)的一致性，本章使用CA作為唯一的評價指標(biāo)比較KECA-QC和使用SVD作為預(yù)處理步驟的傳統(tǒng)QC，結(jié)果如圖7-7所示。在圖7-7中，橫軸坐標(biāo)1,2,...,8表示8個合成數(shù)據(jù)集，最后10個數(shù)字11,...,18表示UCI數(shù)據(jù)集。

在圖7-7中，基于KECA預(yù)處理的QC算法在12個數(shù)據(jù)集上取得比SVD預(yù)處理的QC算法更好的效果。此外，在5個數(shù)據(jù)集上，兩種對比算法取得相同的聚類結(jié)果。因此，可以說，KECA預(yù)處理過程能夠幫助算法獲得高的聚類精度，尤其是在復(fù)雜結(jié)構(gòu)的流形數(shù)據(jù)集上（5,6,7,8）。467.3實驗結(jié)果及分析圖7-7SVD和KECA的比較

為了確定K近鄰設(shè)置對聚類算法的貢獻(xiàn)，本章比較了有K近鄰的KECA-QC和沒有K近鄰的KECA-QC算法。表7-5給出了兩種算法的比較。粗體值代表兩種方法的最優(yōu)結(jié)果。在聚類正確率上，引入K近鄰的KECA-QC要比沒有K近鄰的KECA-QC略微高些，但在運行時間上，引入了K近鄰的KECA-QC大大縮短了聚類時間。為了進(jìn)一步證明其優(yōu)越性，圖7-8和7-9進(jìn)一步展示了對比結(jié)果。477.3實驗結(jié)果及分析表7-5K近鄰對聚類的貢獻(xiàn)DatasetKECA-QC(noK-nearest)KECA-QC(K-nearest)CATime(s)CATime(s)AD_9_20.99782.8910.99781.842AD_20_2124.3915.922data120.99126.2660.99253.516sizes50.985011.670.98906.109data813.65711.734eyes10.92210.781lineblobs10.75010.625spiral110.4817.594breastcancer(WBC)0.97223.6090.97072.250german0.70008.7540.70004.360glass0.57940.6720.58410.578heart0.65180.7030.65560.625ionosphere0.90601.0310.90600.875iris0.90000.4840.97330.281new_thyroid0.87450.5470.87450.516sonar0.60460.4850.65860.469vote0.87361.4850.87821.063zoo0.87130.2970.88120.375487.3實驗結(jié)果及分析圖7-8K近鄰在聚類正確率上的貢獻(xiàn)

由表7-5和圖7-8可以看出，在這18個數(shù)據(jù)集中，引入K近鄰的算法在8個數(shù)據(jù)集上取得較優(yōu)越的聚類正確率，但這并不是非常明顯，這兩種算法在10個數(shù)據(jù)集上具有相同的聚類正確率，只有在breastcancer(WBC)上，進(jìn)入K近鄰的算法效果反而沒有未引入K近鄰的聚類算法好。通過以上分析表明，在聚類正確率上，兩種對比算法的差別不大。在大多數(shù)情況下，局部信息K近鄰足以表達(dá)數(shù)據(jù)的結(jié)構(gòu)497.3實驗結(jié)果及分析信息，冗余的信息在聚類過程中很可能發(fā)揮不了積極的作用。在某些情況下，過多的冗余信息甚至?xí)档途垲惖木?。在所有實驗中，只有breastcancer(WBC)上的效果不是令人滿意的，這主要是由于在683個樣本點中，本章只提取前50個近鄰，而這未能夠表征全部有效信息，換句話說，50個近鄰的設(shè)置對breastcancer(WBC)來說是不夠的。實驗表明，當(dāng)選擇

，聚類效果就會達(dá)到至少與引入K近鄰的聚類算法的等同的效果。圖7-9K近鄰對運行時間的影響507.3實驗結(jié)果及分析

表7-5和圖7-9共同展示了算法的執(zhí)行時間?？梢钥闯觯藌oo數(shù)據(jù)集，在其他數(shù)據(jù)集上，引入K近鄰的算法的執(zhí)行時間小于未引入K近鄰的算法。數(shù)據(jù)點的個數(shù)越多，對比越明顯。當(dāng)數(shù)據(jù)點個數(shù)超過500個時，引入K近鄰策略，運行時間明顯縮短。例如，AD_20_2的算法執(zhí)行時間從原來的24.391s降低到5.922s；german的執(zhí)行時間從8.754s降低到4.360s。與此同時，它們的聚類正確率并沒有降低。數(shù)據(jù)點的個數(shù)少于500個時，算法執(zhí)行時間同樣有所減少，雖然這表現(xiàn)的并不是特別明顯。對于zoo數(shù)據(jù)集，引入K近鄰的聚類算法執(zhí)行時間比未引入K近鄰的算法執(zhí)行時間多出0.078秒，實驗證明，這主要是由于zoo僅包含101個樣本，而在統(tǒng)計50個近鄰上花費的時間比用所有101個樣本估計波函數(shù)及勢能函數(shù)略長。因此，引入K近鄰的量子聚類對樣本點較多的數(shù)據(jù)集在降低算法執(zhí)行時間上效果顯著。517.3實驗結(jié)果及分析(4)魯棒性分析

為了比較這五種算法的魯棒性，本章采用文獻(xiàn)[20]中的方法。算法

在某個數(shù)據(jù)集

上的相對性能用該算法所獲得的AdjustedRandIndex（ARI）值與所有算法在求解該問題時得到的最大ARI值的比值來衡量，即： (7-17)其中，

表示AdjustedRandIndex（ARI），定義如下： (7-18)其中，

表示同時屬于類別l和類別k的數(shù)據(jù)點的個數(shù)

，T和S分別表示真實類別和聚類劃分獲得的類別。AdjustedRandIndex也返回區(qū)間[0,1]之間的值。527.3實驗結(jié)果及分析

從式(7-17)中看出，當(dāng)

時，說明算法

的在該數(shù)據(jù)集

上取得了所有算法中的最優(yōu)ARI值，而其他算法

。

為算法

在所有數(shù)據(jù)集上的獲得的比值之和，用于評價算法

的魯棒性。這個值越大，算法的魯棒性越強。

圖7-10給出了5種算法在所有18個數(shù)據(jù)集上的

值分布的對比。結(jié)果表明，KECA-QC擁有最高的

值（16.7678）。KECA-KM取得次好的魯棒性結(jié)果（15.771），但KECA-KM需要預(yù)先知道聚類的個數(shù)。如果僅考慮不需要預(yù)設(shè)聚類個數(shù)的算法QC和KECA-QC，KECA-QC的聚類魯棒性遠(yuǎn)遠(yuǎn)高于QC?？傊?，KECA-QC具有比其他四種算法更強的魯棒性。537.3實驗結(jié)果及分析圖7-10五種算法的魯棒性比較(5)大規(guī)模數(shù)據(jù)集

在此提到的大規(guī)模主要有兩層意義：一是，數(shù)據(jù)規(guī)模大，包含的樣本點的個數(shù)多；二是，數(shù)據(jù)維度高。本章中提出的算法包含一個重要的數(shù)據(jù)預(yù)處理過程——核熵主成分分析，它主要用于數(shù)據(jù)的轉(zhuǎn)換和維度的削減，尤其適用于大規(guī)模數(shù)據(jù)集。除此之外，引入K近鄰策略547.3實驗結(jié)果及分析計算每個量子粒子的波函數(shù)，以此來減小聚類階段的時間復(fù)雜度，使之降低至線性水平。本章主要討論本方法在大規(guī)模測試集合上的性能。

所謂的高維數(shù)據(jù)所具有的的維度高達(dá)幾百甚至幾千，而表格7-2中展示的sonar,german,ionosphere三種數(shù)據(jù)集只能夠稱之為中等規(guī)模的數(shù)據(jù)集合，因此本章用計算機生成一些人工的高維度數(shù)據(jù)集合。在接下來的實驗中，隨機產(chǎn)生一些數(shù)據(jù)集合，每個數(shù)據(jù)集合都包含1000個數(shù)據(jù)點，數(shù)據(jù)維數(shù)分別為10,50,100,500,1000,5000和10000。由于該數(shù)據(jù)集合是隨機產(chǎn)生的，所以沒辦法知道該集合的聚類準(zhǔn)確度。本章僅僅記錄了算法運行多次運行的時間的統(tǒng)計實驗結(jié)果。表格7-6顯示了算法在不同維度下，10個測試集合的平均運行時間。557.3實驗結(jié)果及分析表7-6不同維度下的算法運行時間

如表7-6中所示，隨著數(shù)據(jù)的維數(shù)從10到10000不斷變化，算法的運行時間也在急劇增加。即便如此，算法的時間也沒超過30秒。公式（7-7）展示了把原始數(shù)據(jù)映射到核空間的數(shù)學(xué)表示。位于核空間內(nèi)任意兩個樣本點之間的核距離首先被計算出來。原始數(shù)據(jù)的維數(shù)越高，則計算相應(yīng)的核矩陣需要較高的時間復(fù)雜度。但是數(shù)據(jù)的維度在隨后的算法運行過程中不再被用到，因此，數(shù)據(jù)的維度僅僅影響核矩陣的計算這一單一過程。如,在本實驗中，無論數(shù)據(jù)維度的高低，量子聚類這一過程的持續(xù)時間約為1.5秒。為了能夠測試算法KECA-QCData-dimension10501005001000500010000Time(s)4.1274.2684.5255.0286.29715.8426.88567.3實驗結(jié)果及分析在高維數(shù)據(jù)集合上的性能，本章選取了4組真實的數(shù)據(jù)集。表7-7給出了數(shù)據(jù)集的一些屬性和聚類的結(jié)果。其中

是預(yù)處理過程后的轉(zhuǎn)換數(shù)據(jù)的維度。從表7-7中可以觀察到，預(yù)處理過程均降低了原始數(shù)據(jù)集的數(shù)據(jù)維度，其中具有最高維數(shù)據(jù)集lung，它的維數(shù)從12600降到了8。通過這一處理，用一個低維的數(shù)據(jù)就能夠很好地表示原高維數(shù)據(jù)。在這四組數(shù)據(jù)集合中，lung的算法運行時間最長，為6.827秒，而它本身具有12600維，203個樣本點。表7-7算法在高維數(shù)據(jù)集上的測試DatasetNumberofsamplesData-dimensionNumberofclustersKECA-QCMSJSCATimes(s)spell79872550.80530.53850.73813.516ovarian541536230.55470.73700.87160.123colon622000270.52300.75260.91940.165lung20312600580.50370.78450.89166.827577.3實驗結(jié)果及分析

表7-8給出了在不同樣本點規(guī)模下，算法在10個隨機數(shù)據(jù)集上的平均運行時間。其中，每個數(shù)據(jù)集都是一個二維數(shù)據(jù)集。在研究中發(fā)現(xiàn)，KECA可能比SVD花費更長的時間，但是與傳統(tǒng)的QC相比，KECA-QC在大規(guī)模數(shù)據(jù)集上的運行時間就相當(dāng)短了。在隨機產(chǎn)生的1000個樣本點的測試集上，KECA-QC的平均運行時間僅有12.5秒，而QC的運行時間卻為27秒。對于5000個樣本點的測試集，KECA-QC的運行時間為1407秒，而QC的時間代價為8153秒，這說明本算法通過引入鄰域信息極大的減小了算法的時間代價。數(shù)據(jù)集的樣本點規(guī)模越大，KECA-QC越能發(fā)揮出快速省時的優(yōu)點。但是即使這樣，KECA-QC在具有5000個點的測試集上的運行時間也很長，將近2個小時才能得到聚類結(jié)果。

587.3實驗結(jié)果及分析表7-8算法對具有不同樣本點規(guī)模的數(shù)據(jù)集的平均運行時間

在表7-9中，本章用兩個數(shù)據(jù)集來測試算法的性能。Normal7具有7個簇狀類的合成數(shù)據(jù)集；Twonorm來自于真實數(shù)據(jù)，具有7400個樣本點和20個維度。通過表7-9得到，通過預(yù)處理，Twonorm數(shù)據(jù)集的維度從20降到了4，然而與之相反的是，Normal7的維度從2反上升至7。正如前面所說，不是所有的數(shù)據(jù)集通過預(yù)處理，數(shù)據(jù)維度都會降低，并且這種情況屢見不鮮，尤其是在數(shù)據(jù)集本身維度不高的情況下。盡管如此，KECA產(chǎn)生的變換數(shù)據(jù)對后續(xù)的聚類分析仍是有利的。Numberofsamples10050010002000300040005000Time(s)KECA-QC0.1822.49012.52112.2352.8506.81407QC0.1704.22626.98470.4188240978153597.3實驗結(jié)果及分析表7-9算法在樣本點規(guī)模大的數(shù)據(jù)集上的測試

通過上述分析，可以斷言KECA-QC適用于高維數(shù)據(jù)集合，在高維度數(shù)據(jù)集上效率極高。它可以用于處理幾萬個維度的數(shù)據(jù)集合，且運行速度很快。雖然與傳統(tǒng)的QC相比，本算法在相同的時間內(nèi)能夠處理更多的數(shù)據(jù)點，但是當(dāng)數(shù)據(jù)點個數(shù)數(shù)超過5000時，相對而言，本算法需要消耗的時間仍然是巨大的，它對于需要在線處理的實際問題的實施仍有難度。DatasetNumberofsamplesData-dimensionNumberofclustersKECA-QCMSJSCATimes(s)Normal735002770.11680.98650.9966496.7Twonorm740020240.51840.71260.836237857.4結(jié)論與討論7.2基于核熵成分分析的量子聚類算法60提綱第7章基于核熵成分分析的量子聚類算法7.1量子聚類算法7.3實驗結(jié)果及分析617.4結(jié)論與討論

本章提出了一種利用核熵成分分析的量子聚類方法，它保持了傳統(tǒng)量子聚類的優(yōu)點，是一種無監(jiān)督學(xué)習(xí)聚類算法，不需要預(yù)先假定任何特別的樣本分布模型和聚類類別數(shù)，并且聚類中心完全取決于樣本自身的潛在信息，而不是簡單的幾何中心或隨機確定。該方法可以分為兩個階段：預(yù)處理階段和聚類階段。在數(shù)據(jù)預(yù)處理階段，結(jié)合核熵主成分分析替代簡單的特征提取方式將原始數(shù)據(jù)映射至高維特征空間，并用熵值作為篩選主成分的評價標(biāo)準(zhǔn)，提取核熵主成分，為接下來的聚類打下了一個良好的基礎(chǔ)。在聚類階段，結(jié)合量子聚類方法和K近鄰策略，通過梯度下降方法不斷迭代以獲得最終聚類結(jié)果，大大降低了算法執(zhí)行時間。通過實驗分析，不論是聚類效果還是魯棒性，該算法遠(yuǎn)優(yōu)于其他對比算法，尤其是對結(jié)構(gòu)較為復(fù)雜的流形數(shù)據(jù)集。62本章參考文獻(xiàn)[1]GasiorowiczS.Quantumphysics,Wiley,NewYork,1996.[2]HornD.ClusteringviaHilbertspace[J].PhysicaAStatisticalMechanics&ItsApplications,2001,302(1-4):70-79.[3]HornD,GottliebA.TheMethodofQuantumClustering[J].2002:769--776.[4]HornD,GottliebA.Algorithmfordataclusteringinpatternrecognitionproblemsbasedonquantummechanics.[J].PhysicalReviewLetters,2002,88(1):261-268.[5]NasiosN,BorsAG.Kernel-basedclassificationusingquantummechanics[J].PatternRecognition,2007,40(3):875-889.[6]Sch?lkopfB,SmolaA,MüllerKR.Nonlinearcomponentanalysisasaker