第7章基于核熵成分分析的量子聚類算法PPT課件

1、人工智能學院 School of Artificial Intelligence1提綱第 7 章 基于核熵成分分析的量子聚類算法人工智能學院 School of Artificial Intelligence7.4 結論與討論7.2 基于核熵成分分析的量子聚類算法2提綱第 7 章 基于核熵成分分析的量子聚類算法7.1 量子聚類算法7.3 實驗結果及分析人工智能學院 School of Artificial Intelligence7.4 結論與討論7.2 基于核熵成分分析的量子聚類算法3提綱第 7 章 基于核熵成分分析的量子聚類算法7.1 量子聚類算法7.3 實驗結果及分析人工智能學院 Sch

2、ool of Artificial Intelligence47.1量子聚類算法 為了實現量子力學在聚類分析中的應用，David Horn和Assaf Gottlieb提出了量子聚類的概念。他們將聚類問題看作一個物理系統(tǒng)，構建粒子波函數表征原始數據集中樣本點的分布。通過求解薛定諤方程式獲得粒子勢能分布情況，而勢能最小的位置可以確定為聚類的中心點。 隨著現代科技的迅猛發(fā)展，聚類所面對的數據的規(guī)模也越來越大，結構也越來越復雜。此時，量子聚類也面臨著不小的挑戰(zhàn)。為了更加精確且高效地實現數據的聚類，本章參考并結合了核聚類、信息熵、譜聚類以及K近鄰的一些思想，來優(yōu)化量子聚類算法。本章提出了一種新的量子聚

3、類方法利用核熵成分分析的量子聚類（KECA-QC）。該方法可分為兩個子步驟：預處理和聚類。在數據預處理階人工智能學院 School of Artificial Intelligence57.1量子聚類算法段，結合核熵主成分分析替代原來簡單的特征提取方式，將原始數據映射至高維特征空間，使非線性可分的數據在特征空間變得線性可分。并用熵值作為篩選主成分的評價標準，提取核熵主成分。預處理能夠有效解決數據間復雜的非線性關系問題，尤其對于高維數據，還能夠同時達到降維的目的。在聚類階段，在傳統(tǒng)量子聚類算法的基礎上，引入K近鄰法來估計量子波函數及勢能函數。這種局部信息的引入既降低了算法運行時間，又提高了聚類的

4、精度。為了進一步驗證該方法的有效性，本章通過與四種對比算法KM（K均值法）、NJW（著名的譜聚類方法）、QC（傳統(tǒng)量子聚類算法）和KECA-KM（核熵成分分析聚類方法）作比較，對8個人工合成數據集和10個UCI數據集進行實驗結果的統(tǒng)計，分析這五種算法的性能。人工智能學院 School of Artificial Intelligence67.1量子聚類算法 量子力學描述了微觀粒子在量子空間的分布，而這同聚類是研究數據樣本在尺度空間中的分布情況是等價的。波函數是粒子量子態(tài)的描述1，波的強度決定了粒子出現在空間某處的概率。薛定諤提出的波動方程描述了微觀粒子的運動，其目的是求解波函數，即有勢場約束的

5、粒子的分布狀況。換句話說，粒子量子態(tài)的演化遵循薛定諤方程。本章使用不顯含時間的薛定諤方程，其方程式可以表述為：(7-1)其中， 為波函數； 為勢能函數； 為Hamilton算子； 為算子 的能量特征值； 為劈形算子； 為波函數寬度調節(jié)參數。 量子力學理論的研究發(fā)現，微觀粒子自身所具有的勢能影響著粒子在能量場中的分布。從式(7-1)也容易看出，勢能相同，則粒子的狀 22-2HVE p p V pkecaHqc人工智能學院 School of Artificial Intelligence77.1量子聚類算法態(tài)分布相同。勢能函數相當于一個抽象的源，隨著勢能趨近于零或者比較小時，在一定寬度的勢阱中往

6、往分布有較多的粒子。當粒子的空間分布縮變到一維無限深勢阱時，粒子則聚集在勢能為零的勢阱中。 從量子力學角度出發(fā)，對于樣本分布已知的數據，等價描述為粒子分布的波函數已知。聚類過程相當于：在波函數已知時，利用薛定鍔方程反過來求解勢能函數，而這個勢能函數決定著粒子的最終分布。這就是量子聚類2-4的物理思想依據。在量子聚類中，本章使用帶有Parzen窗的高斯核函數估計波函數（即樣本點的概率分布），即：(7-2)上式對應于尺度空間中的一個觀測樣本集 ， 高斯函數可以看作是一個核函數5，它定義了一個由輸入空間到Hilbert空間的非線性映射。因此也可以認為 是一個核寬度調節(jié)參數。 2221iNiep pp

7、,d,12iNpppp12,Tdiiiidpppp人工智能學院 School of Artificial Intelligence87.1量子聚類算法 因此，當波函數 已知時，若輸入空間只有一個單點 ，即 通過求解薛定諤方程，勢能函數表示為： (7-3) 根據量子理論可知，式(7-3)是粒子在諧振子中的調和勢能函數的表達形式，此時 算子的能量特征值為 ，其中 為算子 的可能的最小特征值，可以用樣本的數據維數來表示4。 對于一般情況，本章進一步把式(7-2)帶入(7-1)，得到樣本服從高斯分布的勢能函數的計算公式： (7-4) 本章假定 非負且確定，也就是說 的最小值為零， 可以通過求解式(7-

8、4)得到： p1p1N 212TV11ppppp2EddH 22222221exp222iiidVEE ppppp人工智能學院 School of Artificial Intelligence97.1量子聚類算法 (7-5) 根據量子力學理論可知，當粒子具有較低勢能時，其振動較小，相對來說比較穩(wěn)定。這從聚類的角度看，就相當于勢能最小或者為零的樣本周圍也會有比較多的樣本存在。由于樣本的勢能函數值是可以被確定計算的，因此可以利用勢能來確定聚類中心。當樣本數據符合歐氏分布時，利用梯度下降法找到勢能函數的最小點作為聚類的中心。其迭代公式3-5為： (7-6)其中，初始點設為 ； 為算法的學習速率；

9、為勢能的梯度。最終，粒子朝勢能下降的方向移動，即數據點將逐步朝其所在的聚類中心的位置移動，并在聚類中心位置處停留。因此，可以利用量子222minE iiittttVtyyy 0iiyp tV人工智能學院 School of Artificial Intelligence107.1量子聚類算法方式確定聚類的中心點。距離最近的某些點被歸為一類。 從整體來看，在QC算法中勢能函數就相當于量子聚類的價值函數，其聚類中心不是簡單的幾何中心或隨機確定，而是完全取決于樣本自身的潛在信息；且聚類不需要預先假定任何特別的樣本分布模型和聚類類別數；是一種基于劃分的無監(jiān)督聚類算法。人工智能學院 School of

10、Artificial Intelligence7.4 結論與討論7.2 基于核熵成分分析的量子聚類算法11提綱第 7 章 基于核熵成分分析的量子聚類算法7.1 量子聚類算法7.3 實驗結果及分析人工智能學院 School of Artificial Intelligence127.2基于核熵成分分析的量子聚類算法(1) 核熵成分分析方法核熵成分分析方法 一個純粹的量子聚類方法不是在所有的實例中都是很有效的，尤其是當數據集的維數較高時。究其原因，一是數據之間存在著一定量的冗余信息，這極有可能過度強化某一屬性的信息，而忽略某些有用的特征，阻礙了尋找數據間真實的潛在結構；二是隨著數據量或者維度增加，

11、直接對原始數據集進行處理會給算法運行帶來很高的計算代價。為了解決上述問題，David Horn和Inon Axel等人認為在執(zhí)行量子聚類之前，應該對原始數據集進行一個預處理的步驟。在文獻3-4中，這個預處理指的是用奇異值分解（SVD）的方法實現由原始數據空間到特征空間的轉換。這種利用SVD的量子聚類方法就是最經典的量子聚類方法，后續(xù)的實驗中仍用QC來表示它。然而SVD也存在著人工智能學院 School of Artificial Intelligence137.2基于核熵成分分析的量子聚類算法比較明顯的缺點：SVD是一個線性變換。雖然線性變換計算方便，并且容易推廣到新的數據上，但是在實際的生產

12、中，數據間往往呈現復雜的非線性關系，因此線性變換在許多實際問題中并不適用。主成分分析法（PCA）也存在著同樣的問題。因此，在很多情況下，這種線性變換方法不能達到較好的效果?；诖耍S多學者將其推廣到核空間中去解決，以適應非線性的情況，如核主成分分析法（KPCA）6-7。 給定一個數據集 ，其中 。本章同樣使用高斯核矩陣做空間變換： (7-7)其中， 是高斯核的唯一參數。 為一個 的核矩陣，其維度等于12N,Xx xx,1,2,diji jNx xR222,ijijGexxx xGNN人工智能學院 School of Artificial Intelligence147.2基于核熵成分分析的量子

13、聚類算法樣本點的個數。 核矩陣可以分解為 ，其中 為由特征值 （ ）組成的對角矩陣， 為對應的特征向量 作為列向量構成的矩陣。 如圖7-1，本章使用兩個合成數據集（a-1和b-1）作為例子展示數據的預處理結果。（a-2, a-3，b-2和b-3）都代表著數據變換空間的二維映射?？梢院苊黠@的看出線性變換和非線性變換的顯著差別。SVD不能將不同的類分開，KPCA則很容易抓住相對較為復雜數據結構。尤其對Synthetic2尤為明顯：KPCA完全將兩個類分隔開，而SVD沒有。TGQ Q12,N 12NQ12,Nq qq人工智能學院 School of Artificial Intelligence15

14、7.2基于核熵成分分析的量子聚類算法圖7-1 利用SVD和KPCA的數據變換和聚類類別數；是一種基于劃分的無監(jiān)督聚類算法。人工智能學院 School of Artificial Intelligence167.2基于核熵成分分析的量子聚類算法 在數據的預處理過程中，本章總是選擇前 個最大的特征值所對應的特征向量。然而，這并不能保證能夠很好的提取數據集的結構信息。如圖7-2，以synthetic1為例，展示了前6個特征向量（ ）。在所有特征向量中，均各有一段曲線對應的樣本值不為零，而其他部分為零。如果使用KPCA進行數據的特征提取，按照特征值的大小會選取前3個特征向量（ ）。 中不為零的樣本與

15、基本相同，均沒有體現第1和第3類的特征。因此可以得出這樣的結論： 和 提供給的類的信息是相同的。因此，應該采用更有效的方式提取不同類樣本的差異。16qq13qq2q1q1q2q人工智能學院 School of Artificial Intelligence177.2基于核熵成分分析的量子聚類算法圖7-2 按降序排列前6個最大的特征值所對應的特征向量人工智能學院 School of Artificial Intelligence187.2基于核熵成分分析的量子聚類算法 假設待聚類數據集是一個系統(tǒng)，聚類算法實際上就是將這個系統(tǒng)從無序（各模式隨機放置）到有序（各模式按相似性聚集在一起）的過程。而熵可

16、以作為系統(tǒng)有序性的度量。從信息論的角度，Jenssen等人將熵與核方法數據映射結合起來，提出核熵主成分分析法（KECA）8。在計算熵的時候用到帶有高斯核函數的Parzen窗作為概率分布模型，很自然地將熵的計算化為核矩陣的計算，構造成為一個核空間里的優(yōu)化問題。 設 是數據的 概率密度函數，則該數據的信息熵為 。由于對數函數是單調函數，所以只需考慮 即可。為了估計 ，需要進行Parzen窗的密度估計 ，這就將熵的計算和高斯核矩陣聯系在一起。 的值可通過數學推導得出：( )p x12 ,.,NXx xx2log( )px dx2( )rpx dxr1( )( ,)iip xK x xNr人工智能學院

17、 School of Artificial Intelligence197.2基于核熵成分分析的量子聚類算法 (7-8)其中， 為每個元素均取1的 的向量； 是第 個特征值和特征向量對應的熵的貢獻值。 以熵值大小為度量標準，降序排列特征值及其對應的特征向量。令 為一個包含前 個對應的特征值的對角矩陣， 為一個以前 個對應特征向量為列的矩陣，則利用KECA得到特征空間中的變換數據為： (7-9) 為一個 的核熵主成分矩陣，將其作為輸入數據用于下一步的量子聚類，其每一行都對應著原始數據集中的一個點。 圖7-3展示了利用KECA的Synthetic1和Synthetic2的預處理結果。2Tiiir1

18、q11N1,2,ir iNkeca_llkeca_lQl12Tkecakeca_lkeca_lQ kecaNl人工智能學院 School of Artificial Intelligence207.2基于核熵成分分析的量子聚類算法對于Synthetic1，KPCA選取前2個特征值及其對應的特征向量，而圖7-3(a)中，KECA則選擇第一個和第三個主成分。對比圖7-1(a-3)和圖7-3(a)，加入熵選擇的數據呈現的結構更加清晰。對于Synthetic2亦是如此。KECA可以更好的保留數據集的聚類結構信息，擴大類與類之間的差異。尤其對線性不可分的數據集，表現出更好的優(yōu)越性。此外，利用KECA的預

19、處理為量子聚類奠定了基礎，同時提高了聚類效率。圖7-3 利用KECA的數據變換人工智能學院 School of Artificial Intelligence217.2基于核熵成分分析的量子聚類算法 總的來說，通過KECA預處理，將原始數據映射到高維特征空間，提取特征并用熵作為度量選擇主成分。可以說，KECA是一個先升維后降維的過程。KECA去除了數據的冗余信息，獲得更加緊湊和經濟的數據表示形式，同時更加有效地表達數據的潛在結構。此外，KECA將一個非線性可分的問題轉變?yōu)橐粋€線性可分的問題，在結構更為復雜的數據上也能夠獲得較好的處理效果。這些都有助于聚類準確度的提高。對于那些維度較高的數據，采

20、用KECA還能夠同時達到降維的目的。應當指出的是，預處理變換后的數據維度有可能大于原始數據的維度，尤其是對那些低維原始數據。盡管如此，變換處理后的數據仍是有利于聚類分析的。不論原始數據維度的高低，變換后的數據維度都會維持在一個較低的水平。雖然數據的預處理需要花費人工智能學院 School of Artificial Intelligence227.2基于核熵成分分析的量子聚類算法一定的時間，但是這對于后期聚類運行的效率和聚類的精度提高，付出的代價是值得的。(2) K近鄰的量子聚類近鄰的量子聚類 在QC算法中， 的每一行都可以看做是一個粒子對應著原始數據的一個數據點。從式(7-2)中可以看出，要

21、計算粒子的波函數就必須統(tǒng)計該粒子到所有其他粒子的核距離，也就是說，粒子的波函數受其他粒子的共同作用，作用的大小以高斯核距離為衡量標準。距離越遠，其影響力越小。假設數據集中有 個樣本，每次迭代都需要計算 個波函數，每個波函數的獲得又需要統(tǒng)計 各高斯核距離。因此，在量子聚類中，波函數的計算復雜度為 。隨著數據樣本點的增加，每次迭代算法執(zhí)行時間會以指數形式增長。人工智能學院 School of Artificial Intelligence237.2基于核熵成分分析的量子聚類算法圖7-4 高斯核函數分布 本章提出了一種新的統(tǒng)計波函數的方法。圖7-4所示的為規(guī)模參數為1的高斯核函數的分布。橫坐標表示粒

22、子之間的距離，縱坐標表示高斯核函數值，即粒子的作用力大小?？梢院苤庇^的看出，它的作用是局部的，隨著距離的增加，它的作用效果下降的速度非?？欤敝翢o限接近于0，因此它往往用于低通濾波。這里可以做一個大膽的假設：某處粒子的波函數值僅受其周圍粒子的影響?；谶@個假設來估計波函數只需要考慮樣本的局部信息。本方法采用K近鄰策略進人工智能學院 School of Artificial Intelligence247.2基于核熵成分分析的量子聚類算法行波函數的估計。假設一個有 個樣本點的數據集， 是其中任意一個樣本， 的最近的K個鄰居的集合用 表示。根據其他樣本點 到該樣本點 的歐式距離排列樣本： (7-1

23、0)其中， ； 為 的K個近鄰的集合。 是整個數據集中距離 最近的點， 是 外其他點中距離 最近的點。本章重新估計波函數為：(7-11)用上式代替原來的波函數的估計公式（式(7-2)）。本式只需要考慮樣本的K近鄰 ，而不是所有樣本點。最終勢能函數重寫為： (7-12)Npp pKp Kk1kkk, 2 , 1,22pppppNK K21K,ppppp 1pp1Kp pK pppppKkke)(222 pK pppppppKkkkdEV22222exp212人工智能學院 School of Artificial Intelligence257.2基于核熵成分分析的量子聚類算法(3) 算法描述算法

24、描述結合上一節(jié)中QC算法，本章提出一種新的量子聚類方法利用核熵成分分析的量子聚類（KECA-QC）。該方法是一個兩階段過程，首先在數據預處理階段，結合核熵主成分分析替代簡單的特征提取方式將原始數據映射至高維特征空間，并用熵值作為篩選主成分的評價標準，提取核熵主成分。其次在聚類階段，結合量子聚類方法和K近鄰策略，通過梯度下降方法不斷迭代以獲得最終聚類結果。KECA-QC的算法流程如圖7-5所示，包含以下步驟：人工智能學院 School of Artificial Intelligence267.2基于核熵成分分析的量子聚類算法KECA-QC算法算法預處理階段預處理階段:1.輸入一個數據集數據集

25、，建立高斯核矩陣 。2.通過非線性數據映射，在特征空間計算 的特征值和特征向量，并根據熵值 的大小重新排列所對應的特征值和特征向量。3.設置主成分個數選擇參數 ，得到核熵主成分矩陣 ，其每一行都可看作量子聚類中的一個粒子，并與原始數據中的數據點相對應。聚類階段聚類階段:1.計算波函數 ，勢能函數 及其梯度下降方向 ，同時統(tǒng)計每個粒子 的K個最近的鄰居，即 。2.利用梯度下降方法不斷迭代尋找量子勢能的最小值，直到達到設定的最大迭代次數。最終特征空間中的每個點都會聚縮在其所在的聚類中心的位置附近。3.根據每個粒子點距離聚類中心的遠近劃分其至不同的類中，完成聚類過程。N21,xxxXGGrllNke

26、caVVp pK人工智能學院 School of Artificial Intelligence277.2基于核熵成分分析的量子聚類算法圖7-5 KECA-QC算法流程 從廣義上說，任何涉及聚類特征分解的算法都可以被稱為譜聚類（Spectral Clustering, SC）9-10。從這個角度看，KECA-QC也應屬于廣義意義上的譜聚類算法。由此可見，本章的算法同樣具有譜聚類算法的一般優(yōu)勢，或者說KECA-QC在算法性能上和SC相匹敵。經典譜人工智能學院 School of Artificial Intelligence287.2基于核熵成分分析的量子聚類算法聚類算法的一般步驟如下：構建相似

27、度矩陣或者拉普拉斯矩陣，選擇前 個最大的特征值對應的特征向量組成特征矩陣，并將其中每一行看作特征空間中的一個向量，使用K-means方法進行聚類，聚類結果中每一向量所屬的類別就是對應的原數據集中數據點所屬的類別。從以上步驟可以看出，KECA-QC與譜聚類在算法框架上非常相似，為此本章在實驗部分給出KECA-QC與譜聚類的代表性算法Ng-Jordan-Weiss (NJW)的比較。人工智能學院 School of Artificial Intelligence297.2基于核熵成分分析的量子聚類算法(4) 參數設置參數設置 在KECA-QC中，有如下參數需要事先設置：核參數 （預處理KECA中）

28、和 （聚類QC中），主成分個數 ，梯度下降迭代次數 ，以及近鄰個數 。 核方法的其中一個難點就是核參數的選擇。從式(7-2)、(7-7)和(7-11)中可以看出，改變了核參數實質上隱含地改變了映射函數，從而改變了樣本數據在核空間分布的復雜程度，因此核參數的選擇會對最終的聚類效果產生直接的影響。一般來講，核參數是一個不太明確的經驗值3-4，需要通過多次實驗去篩選優(yōu)化。許多學者致力于設計用一個較為確定的方法選擇核參數，如Silverman11構建了一個以樣本集維度和大小為變量的核參數選擇函數；Varshavsky使用貝葉斯kecaqclStepsK人工智能學院 School of Artifici

29、al Intelligence307.2基于核熵成分分析的量子聚類算法信息準則選擇核參數，評估聚類的質量12；Nikolaos Nasios等人認為核參數可以從K近鄰的統(tǒng)計分布中估計13。在本章中，為了簡化核參數的選擇，本章根據文獻13中的方法定義 ： (7-13) 由上式可以看出， 的值其實就是樣本點到其K近鄰點的的平均歐氏距離。雖然這種方法無法找到最優(yōu)的 ，但可以用較小的時間復雜度找到相對優(yōu)的 ，在文獻13中已驗證。根據式(7-13)，高斯核矩陣 （式(7-7)），波函數 （式(7-11)）和勢能函數（式(7-12)）都能夠計算得到。這里設置近鄰個數 。根據量子聚類參考文獻14，設置相同的

30、參數 ，實驗也證明，量子聚類過程中梯度下降迭代10次至20次，粒子就已經基本處于穩(wěn)定狀態(tài)。核熵主成分個數 通過熵的差分方法得到，具體來說，對熵進行降序排列， ， 。 112 KNNikKkxxxxG p50K20Steps 11maxiillrrrr1, 2 , 1Ni人工智能學院 School of Artificial Intelligence7.4 結論與討論7.2 基于核熵成分分析的量子聚類算法31提綱第 7 章 基于核熵成分分析的量子聚類算法7.1 量子聚類算法7.3 實驗結果及分析人工智能學院 School of Artificial Intelligence327.3實驗結果及分

31、析 為了進一步測試KECA-QC的有效性，本章對18個數據集進行實驗（包括8個計算機合成數據集和10個UCI數據集15）。對比算法有：KM（K均值法）16、NJW（代表性譜聚類算法）17、QC（傳統(tǒng)量子聚類算法）3和KECA-KM（核熵成分分析聚類方法）18。在這四種對比算法中，QC不需要預設聚類的個數。以下三個指標用于評價算法的性能：Minkowski Score (MS)19，Jaccard Score (JS)3和正確率（cluster accuracy, CA）。 這里，KM是一個眾所周知的無監(jiān)督聚類算法，通過優(yōu)化目標函數獲得最終的聚類結果；在7.1.3節(jié)中，已給出了SC算法的描述，N

32、JW使用拉普拉斯矩陣的前 個特征向量將數據集劃分為 類；傳統(tǒng)的QC算法在7.1.2節(jié)已詳細給出；而KECA-KM算法的大體流程是，人工智能學院 School of Artificial Intelligence337.3實驗結果及分析首先提取前 個核熵主成分，然后利用角距離的K均值算法將數據劃分成 類。 實驗運行的PC環(huán)境為Intel(R) Core(TM) 2 Duo CPU 2.33GHz 2G RAM，在Matlab7.4(R2007a)環(huán)境下編程實現。 在接下來的實驗中，由于KM和NJW都是隨機優(yōu)化算法，為了公平比較，其實驗結果是在獨立運行100次的基礎上得到的。QC，KECA-KM和

33、KECA-QC都是確定性算法，算法運行1次即可。(1) 數據集及評價指標數據集及評價指標 表7-1為10個合成數據集基本描述，并在圖7-6中具體展示。AD_9_2 和AD_20_2均為緊湊型的簇狀數據，而data12和sizes5中的數據分布較為彌漫；data8、eyes、lineblobs和spiral是四個流形數據集。人工智能學院 School of Artificial Intelligence347.3實驗結果及分析表7-2給出了10個UCI數據集的基本描述，包括breastcancer(WBC)、german、glass、heart、ionosphere、iris、new_thyro

34、id、sonar,、vote和zoo。 在本章中，以下三個指標用于評價算法的性能： Minkowski Score（MS）： (7-14) Jaccard Score:（JS）： (7-15)其中， 表示同時屬于真實聚類標簽和通過聚類算法獲得的類別標簽的成對的樣本的數目； 表示僅屬于真實聚類標簽的成對的樣本的數目； 表示僅屬于聚類獲得的類別標簽的成對的數據數目。10111001nnnnMS10011111nnnnJS11n01n01n人工智能學院 School of Artificial Intelligence357.3實驗結果及分析 本章定義 為實際輸入的總的樣本個數； 為真實的類別數；

35、為聚類獲得的類別數； 為混淆矩陣。 Cluster accuracy（CA）：(7-16)其中，混淆矩陣中 表示同時出現在真實類別中第i類和聚類獲得的第j類的樣本點數目。由于屬于同一真實類別的樣本可能在聚類中被劃分至多個類別，因此取聚類中樣本點個數最多的那個作為統(tǒng)計輸入。 以上三個指標的返回值都在0,1區(qū)間內。MS的值越小表明聚類效果越好；而JS和CA的值越大，聚類效果越好。當取得完全正確的結果時，MS的值為0；其他兩個評價指標的值均為1。NTSon,Cfusion i jSjTijiConfusionmaxNCATi, 1;, 1,11),(jiConfusion人工智能學院 School

36、of Artificial Intelligence367.3實驗結果及分析表7-1 合成數據集基本描述數據集樣本個數樣本維數類別數AD_9_245029AD_20_21000220data1280024sizes5100024data860022eyes30023lineblobs26623spiral100022人工智能學院 School of Artificial Intelligence377.3實驗結果及分析人工智能學院 School of Artificial Intelligence387.3實驗結果及分析圖7-6 合成數據集人工智能學院 School of Artificial

37、 Intelligence397.3實驗結果及分析表7-2 UCI數據集基本描述(2) 合成數據和合成數據和UCI數據的實驗數據的實驗 表7-3給出了五種算法在合成數據集上的比較，加粗的數字表示五種算法中最好的結果。數據集樣本個數樣本維數類別數breastcancer(WBC)68392german1000242glass21496heart270132ionosphere351332iris15043new_thyroid21553sonar208602vote435162zoo101167人工智能學院 School of Artificial Intelligence407.3實驗結果及分

38、析表7-3 五種算法在合成數據集上的比較Data setKMNJWQCKECA-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

39、.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.881

40、10.10890.907500JS0.44930.93970.432611CA0.74060.96420.714311spiralMS0.982900.98440.81320JS0.348510.34720.50331CA0.592010.58800.79101人工智能學院 School of Artificial Intelligence417.3實驗結果及分析 KM和NJW分別是聚類和譜聚類的代表性算法，比較這兩種算法，顯然NJW獲得更好的聚類結果，尤其是在4個流形數據集上。由此可以得出結論，NJW不僅能處理簇狀數據，在流形數據集上還能獲得比KM有更好的聚類能力。傳統(tǒng)的QC算法在粗壯數據集

41、上表現了很好的性能，然而，此算法在流行數據集上同樣表現不佳。NJW、KECA-KM和KECA-QC都可以稱為廣義上的譜聚類算法。這三種算法在流形數據的聚類效果上明顯優(yōu)于KM和QC。KECA-QC在多數數據集上聚類效果比NJW好。KECA-QC表現最優(yōu)，在7個數據集上取得最優(yōu)值，只有在數據集data12上取得次優(yōu)結果（MS: 0.1721, JS: 0.9708, CA: 0.9925）。值得注意的是，在4個流形數據集上，KECA-QC取得了完全正確的聚類結果（MS: 0, JS: 1, CA: 1），在spiral上人工智能學院 School of Artificial Intelligenc

42、e427.3實驗結果及分析NJW取得的結果是完全正確的，在lineblobs上KECA-KM的結果是完全正確的。此外，QC和KECA-QC在簇狀數據集上的效果大致相同，因此，可以說引入核熵成分分析提高了量子聚類在復雜結構的流形數據集上的聚類能力。表7-4 五種算法在UCI數據集上的比較Data setKMNJWQCKECA-KMKECA-QCbreastcancer(WBC)MS0.37330.33070.47520.29840.3230JS0.87070.89620.79230.91430.9003CA0.96050.96920.93410.97510.9707germanMS0.86970

43、.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.6556人工智能學院 Scho

44、ol of Artificial Intelligence437.3實驗結果及分析Data setKMNJWQCKECA-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.846

45、50.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.820

46、10.82730.48940.4776JS0.47870.42310.49400.77950.7930CA0.82180.78240.77210.85150.8812人工智能學院 School of Artificial Intelligence447.3實驗結果及分析 從表7-4可以看出，在10個UCI數據集中KECA-QC有6個取得了最優(yōu)結果，KECA-KM在其他4個數據集取得最優(yōu)結果。同時，結果表明，KECA-QC在所有測試數據集上的結果都比KM、NJW以及傳統(tǒng)的QC算法好。KECA-KM取得次優(yōu)記過，這是因為該算法在聚類階段使用的基于余弦角度距離度量的K均值算法，而KECA預處理得到的

47、數據往往是帶有夾角結構的。從整體上看，KECA-QC在UCI數據集上的的優(yōu)勢表現得不如在人工合成數據集上的那么明顯。這主要是因為，UCI數據集的結構不像合成數據集的結構那么簡單，它們的結構較為多樣化，且其數據屬性也非常復雜?？偟膩碚f，本章改進的算法，相比于其他四種對比算法，仍能取得較好地聚類結果。人工智能學院 School of Artificial Intelligence457.3實驗結果及分析(3) KECA和和K近鄰對聚類的貢獻近鄰對聚類的貢獻 表7-3和表7-4表明，KECA-QC的聚類效果明顯優(yōu)于傳統(tǒng)的QC算法，這主要是由于核熵主成分預處理過程提取了有用的結構信息。由于三個評價指標

48、的一致性，本章使用CA作為唯一的評價指標比較KECA-QC和使用SVD作為預處理步驟的傳統(tǒng)QC，結果如圖7-7所示。在圖7-7中，橫軸坐標1, 2, . ,8 表示8個合成數據集，最后10個數字11, . ,18表示UCI數據集。 在圖7-7中，基于KECA預處理的QC算法在12個數據集上取得比SVD預處理的QC算法更好的效果。此外，在5個數據集上，兩種對比算法取得相同的聚類結果。因此，可以說，KECA預處理過程能夠幫助算法獲得高的聚類精度，尤其是在復雜結構的流形數據集上（5,6,7,8）。人工智能學院 School of Artificial Intelligence467.3實驗結果及分析

49、圖7-7 SVD和KECA的比較 為了確定K近鄰設置對聚類算法的貢獻，本章比較了有K近鄰的KECA-QC和沒有K近鄰的KECA-QC算法。表7-5給出了兩種算法的比較。粗體值代表兩種方法的最優(yōu)結果。在聚類正確率上，引入K近鄰的KECA-QC要比沒有K近鄰的KECA-QC略微高些，但在運行時間上，引入了K近鄰的KECA-QC大大縮短了聚類時間。為了進一步證明其優(yōu)越性，圖7-8和7-9進一步展示了對比結果。人工智能學院 School of Artificial Intelligence477.3實驗結果及分析表7-5 K近鄰對聚類的貢獻Data setKECA-QC(no K-nearest)KE

50、CA-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.

51、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.375人工智能學院 School of Artificial Intelligence487.3實驗結果及分析圖7-8 K近鄰在聚類正確率上的貢獻 由表7-5和圖7-8可以看出，在這18個數據集中，引入K近鄰

52、的算法在8個數據集上取得較優(yōu)越的聚類正確率，但這并不是非常明顯，這兩種算法在10個數據集上具有相同的聚類正確率，只有在breastcancer (WBC)上，進入K近鄰的算法效果反而沒有未引入K近鄰的聚類算法好。通過以上分析表明，在聚類正確率上，兩種對比算法的差別不大。在大多數情況下，局部信息K近鄰足以表達數據的結構人工智能學院 School of Artificial Intelligence497.3實驗結果及分析信息，冗余的信息在聚類過程中很可能發(fā)揮不了積極的作用。在某些情況下，過多的冗余信息甚至會降低聚類的精度。在所有實驗中，只有breastcancer (WBC)上的效果不是令人滿意

53、的，這主要是由于在683個樣本點中，本章只提取前50個近鄰，而這未能夠表征全部有效信息，換句話說，50個近鄰的設置對breastcancer (WBC)來說是不夠的。實驗表明，當選擇 ，聚類效果就會達到至少與引入K近鄰的聚類算法的等同的效果。圖7-9 K近鄰對運行時間的影響人工智能學院 School of Artificial Intelligence507.3實驗結果及分析 表7-5和圖7-9共同展示了算法的執(zhí)行時間?？梢钥闯觯藌oo數據集，在其他數據集上，引入K近鄰的算法的執(zhí)行時間小于未引入K近鄰的算法。數據點的個數越多，對比越明顯。當數據點個數超過500個時，引入K近鄰策略，運行時間

54、明顯縮短。例如，AD_20_2的算法執(zhí)行時間從原來的24.391s降低到5.922s；german的執(zhí)行時間從8.754s降低到4.360s。與此同時，它們的聚類正確率并沒有降低。數據點的個數少于500個時，算法執(zhí)行時間同樣有所減少，雖然這表現的并不是特別明顯。對于zoo數據集，引入K近鄰的聚類算法執(zhí)行時間比未引入K近鄰的算法執(zhí)行時間多出0.078秒，實驗證明，這主要是由于zoo僅包含101個樣本，而在統(tǒng)計50個近鄰上花費的時間比用所有101個樣本估計波函數及勢能函數略長。因此，引入K近鄰的量子聚類對樣本點較多的數據集在降低算法執(zhí)行時間上效果顯著。人工智能學院 School of Artifi

55、cial Intelligence517.3實驗結果及分析(4) 魯棒性分析魯棒性分析 為了比較這五種算法的魯棒性，本章采用文獻20中的方法。算法 在某個數據集 上的相對性能用該算法所獲得的Adjusted Rand Index（ARI）值與所有算法在求解該問題時得到的最大ARI值的比值來衡量，即：(7-17)其中， 表示Adjusted Rand Index（ARI），定義如下：(7-18)其中， 表示同時屬于類別l和類別k的數據點的個數 ，T和S分別表示真實類別和聚類劃分獲得的類別。Adjusted Rand Index也返回區(qū)間0,1之間的值。mtmtktkRbmax R,2222,12

56、22222ijiji jijijijijijnnnnR T Snnnnn ijn,k lT kS人工智能學院 School of Artificial Intelligence527.3實驗結果及分析 從式(7-17)中看出，當 時，說明算法 的在該數據集 上取得了所有算法中的最優(yōu)ARI值，而其他算法 。 為算法 在所有數據集上的獲得的比值之和，用于評價算法 的魯棒性。這個值越大，算法的魯棒性越強。 圖7-10 給出了5種算法在所有18個數據集上的 值分布的對比。結果表明，KECA-QC擁有最高的 值（16.7678）。KECA-KM取得次好的魯棒性結果（15.771），但KECA-KM需要預

57、先知道聚類的個數。如果僅考慮不需要預設聚類個數的算法QC和KECA-QC，KECA-QC的聚類魯棒性遠遠高于QC?？傊?，KECA-QC具有比其他四種算法更強的魯棒性。1mibmi*1ib mbmmmbmb人工智能學院 School of Artificial Intelligence537.3實驗結果及分析圖7-10 五種算法的魯棒性比較(5) 大規(guī)模數據集大規(guī)模數據集 在此提到的大規(guī)模主要有兩層意義：一是，數據規(guī)模大，包含的樣本點的個數多；二是，數據維度高。本章中提出的算法包含一個重要的數據預處理過程核熵主成分分析，它主要用于數據的轉換和維度的削減，尤其適用于大規(guī)模數據集。除此之外，引入K近

58、鄰策略人工智能學院 School of Artificial Intelligence547.3實驗結果及分析計算每個量子粒子的波函數，以此來減小聚類階段的時間復雜度，使之降低至線性水平。本章主要討論本方法在大規(guī)模測試集合上的性能。 所謂的高維數據所具有的的維度高達幾百甚至幾千，而表格7-2中展示的sonar, german, ionosphere三種數據集只能夠稱之為中等規(guī)模的數據集合，因此本章用計算機生成一些人工的高維度數據集合。在接下來的實驗中，隨機產生一些數據集合，每個數據集合都包含1000個數據點，數據維數分別為10, 50, 100, 500, 1000, 5000 和10000。

59、由于該數據集合是隨機產生的，所以沒辦法知道該集合的聚類準確度。本章僅僅記錄了算法運行多次運行的時間的統(tǒng)計實驗結果。 表格7-6顯示了算法在不同維度下，10個測試集合的平均運行時間。人工智能學院 School of Artificial Intelligence557.3實驗結果及分析表7-6 不同維度下的算法運行時間 如表7-6中所示，隨著數據的維數從10 到10000不斷變化，算法的運行時間也在急劇增加。即便如此，算法的時間也沒超過30秒。公式（7-7）展示了把原始數據映射到核空間的數學表示。位于核空間內任意兩個樣本點之間的核距離首先被計算出來。原始數據的維數越高，則計算相應的核矩陣需要較高

60、的時間復雜度。但是數據的維度在隨后的算法運行過程中不再被用到，因此，數據的維度僅僅影響核矩陣的計算這一單一過程。如, 在本實驗中，無論數據維度的高低，量子聚類這一過程的持續(xù)時間約為1.5秒。為了能夠測試算法KECA-QCData-dimension10501005001000500010000Time(s)4.1274.2684.5255.0286.29715.8426.88人工智能學院 School of Artificial Intelligence567.3實驗結果及分析在高維數據集合上的性能，本章選取了4組真實的數據集。表7-7 給出了數據集的一些屬性和聚類的結果。其中 是預處理過程后