半監(jiān)督AP聚類算法的并行計算

1、半監(jiān)督ap聚類算法的并行計算聚類算法概述v聚類分析是研究數(shù)據挖掘技術的有效手段，聚類分析是研究數(shù)據挖掘技術的有效手段，是一種無監(jiān)督的分類方法。聚類的目標是將是一種無監(jiān)督的分類方法。聚類的目標是將相似的對象劃分到同一個簇中，將不相似的相似的對象劃分到同一個簇中，將不相似的對象劃分到不同的簇中。聚類可分為對象劃分到不同的簇中。聚類可分為:v基于劃分的聚類方法基于劃分的聚類方法 如如k-means，k中心等中心等v基于層次的聚類方法基于層次的聚類方法 如凝聚和分裂方法如凝聚和分裂方法v基于網格和密度的聚類方法基于網格和密度的聚類方法 v基于模型的聚類方法基于模型的聚類方法聚類算法的數(shù)學描述v設模式樣

2、本集為 , 其中 為d 維模式向量, 聚類問題就是要找到一個劃分 , 滿足 v并且使得總的類間離散度和 達到最小, 其中 為第k 個聚類的中心, 為樣本到對應聚類中心距離, 聚類準則函數(shù)j即為各類樣本到對應聚類中心距離的總和。這里 為歐氏空間的距離, 即 。, 2 , 1,nixxiix,m21cccc);, 2 , 1,(), 2 , 1(jimjiccmiccxjiiimi mkcxkikizxdj1),(kz),(kizxd),(kizxdkikizxzxd),(ap聚類算法v以往的很多聚類算法都是通過選取類代表點來完成聚類的。傳統(tǒng)的尋找類代表點的方法是，隨機地選擇初始類代表點集合，然后

3、迭代調整類代表點，直到類代表點不再發(fā)生明顯改變時結束，其聚類結果會受到初始類代表點選擇的影響。v2007年，frey 等人提出了一種近鄰傳播（affinity propagation，ap）算法，該算法將信任傳播思想用于數(shù)據點之間的信息交換，為每個數(shù)據點找到類代表點，從而完成聚類。近鄰傳播算法以數(shù)據點對之間的相似度為基礎，將所有的數(shù)據點都看作是潛在的類代表點，通過數(shù)據點之間交換信息，得到一個較為理想的類代表點的集合。該算法快速、有效，引起了學者的廣泛關注。v2008年，軟件學報的一篇文章中提出了半監(jiān)督的近鄰傳播聚類算法（semi-supervised clustering based on a

4、ffinity propagation，sap），該算法在ap算法的基礎上引入半監(jiān)督思想，利用成對點約束信息對相似度矩陣進行調整，然后利用ap算法進行聚類。半監(jiān)督聚類半監(jiān)督聚類v 半監(jiān)督聚類是利用樣本先驗知識，利用有標簽的樣本來指導無標簽的樣本的聚類方法，由于在數(shù)據挖掘中獲得少量有標簽的樣本相對比較容易，故半監(jiān)督聚類算法成為機器學習中重要內容之一。半監(jiān)督聚類半監(jiān)督聚類 主要方法：基于成對約束的方法 must-link cannot-link 基于距離的方法 利用成對約束來學習距離度量 基于約束和距離的方法 兩種方法的綜合成對限制先驗信息v用must-link和cannot-link來輔助聚類搜

5、索，must-link規(guī)定兩個樣本必須在同一聚類中，cannot-link規(guī)定兩個樣本不能在同一聚類中。v傳遞性： sap聚類算法v分析sap 算法，發(fā)現(xiàn)算法的時間復雜度較高，為o（n3）。隨著數(shù)據集的增大，運行時間增加很快。因此給出了半監(jiān)督近鄰傳播聚類算法的并行計算方法（ psap ），實驗發(fā)現(xiàn)該并行算法的運行時間約為原算法的1/81/4。psap聚類算法v其基本思想是將待測數(shù)據集隨機分成兩部分，然后分別在每部分中采用sap 算法獲取相應的類代表點集合，最后將兩個類代表點集合合并成新的數(shù)據集再運行一次sap算法。v假設待測數(shù)據集的規(guī)模為n，sap 算法的時間復雜度為o（n3），而psap算法

6、由于數(shù)據規(guī)模減半，因此所耗時間約為原計算時間的1/8，從而降低了時間的消耗。psap聚類算法v采用數(shù)據劃分的psap 算法與未劃分數(shù)據的sap 算法的約束信息應一致，由于約束信息是以數(shù)據點在數(shù)據集中的序號表示的，因此psap算法必須將原來的約束信息傳遞到數(shù)據子集上。psap 算法主要解決待測數(shù)據集分開計算和最后的合并計算時約束信息和數(shù)據點序號的轉換問題。約束信息的轉換發(fā)生在數(shù)據集的分割、部分數(shù)據集的sap聚類、聚類結果的合并以及每個原始數(shù)據點最后確定類代表點的各個時刻。約束信息的轉換和數(shù)據點的序號轉換是同時進行的。psap聚類算法步驟v（1）以數(shù)據點的序號對表示成對點約束信息。以ml=（xi，

7、xj）表示must-linked 約束，cl=（xi，xj）表示cannot-linked約束。v（2）將待測數(shù)據集（data）隨機地分成兩部分，分別為firstdb和seconddb。v（3）ml中的約束信息分成三部分，兩個數(shù)據點都被分到firstdb 中的約束信息，記為ml1；兩個數(shù)據點都被分到seconddb中的約束信息，記為ml2；一個在firstdb 中，另一個在seconddb中，此時的約束信息記為part_ml。同樣地，cl也被分成了三部分，cl1、cl2以及part_cl。v（4）以ml1和cl1分別作為firstdb 數(shù)據集的must-linked 和cannot-linke

8、d 約束，在firstdb 上進行sap算法，得到firstdb 數(shù)據集的類代表點坐標信息cp1。v（5）以ml2和cl2分別作為seconddb 數(shù)據集的must-linked和cannot-linked 約束，在seconddb 上進行sap算法，得到seconddb數(shù)據集的類代表點坐標信息cp2。v（6）將cp1和cp2合并，作為新的待測數(shù)據集merge。v（7）將part_ml 和part_cl 中的每對約束信息進行轉換整合后在merge數(shù)據集上作為約束運行sap算法。v（8）為原始數(shù)據集data中的每個點確定最后的類標號。psap聚類算法v下面以一個包含40 個數(shù)據點的交叉形數(shù)據集為

9、例說明psap算法的運行過程，如圖1 所示。psap聚類算法v其中的相似性約束為：ml=（14，23），（8，40），（10，35），cl=（8，14），（14，35），（23，35）。這里的數(shù)值均為數(shù)據點序號。圖1 中3 條連線為3 個must-linked，兩個黑色的圓點是并行聚類算法（psap）最終得出的類代表點；兩個標有+號的點是非并行聚類算法（sap）得出的類代表點。在當前約束下，正確的聚類結果應為左上角的10 個數(shù)據點和右下的10 個數(shù)據點為一簇，而左下角的10個數(shù)據點和右上角的10個數(shù)據點為一簇。psap聚類算法v將data 隨機分成firstdb、seconddb，其中8、14

10、、35、40 分到firstdb中，10、23 分到seconddb中，如圖2 所示。psap聚類算法v經過數(shù)據集的分割，每個數(shù)據點在子數(shù)據集中都有了新的序號。為了使子數(shù)據集能獨立運行sap 算法，必須將約束信息轉換到子數(shù)據集上。本例中有1 個ml約束和2 個cl約束轉換到firstdb 中了，而seconddb 沒有得到約束信息。在firstdb 中約束信息轉換過程為：vml1=（8，40）ml1=（3，19）vcl1=（8，14），（14，35）cl1=（3，6），（6，17）psap聚類算法v此時兩個數(shù)據集及其上的約束信息已經轉換完畢，可以分別獨立地運行sap 算法了。由于是并行計算，這

11、個步驟所需的時間應為兩個運行時間中的較大者。每個數(shù)據集都得出自己的類代表點集合，將這兩個類代表點集合合并，注意在合并之后seconddb提供的類代表點序號依次下移。psap聚類算法psap聚類算法vpart_ml 和part_cl 約束所涉及到的數(shù)據點分別被劃分在兩個數(shù)據集上，只有在合并之后才能起到約束作用。具體情況如下：vpart_ml 中的約束（14，23），序號為14 的數(shù)據點被分到firstdb 中，新序號為6； 在firstdb 上進行sap算法，得到6 的類代表點為2。 序號為23 的數(shù)據點被分到seconddb中，新序號為12。在seconddb 上進行sap算法，得到12 的類

12、代表點為4，在兩個類代表點集cp1和cp2合并后，cp2中的4對應合并后的7。所以，兩個類代表點集合合并后約束（14，23）轉換為（2，7）。其余類似。vpart_ml=（14，23），（10，35）part_ml=（2，7），（5，3）vpart_cl=（23，35）part_cl=（7，3）psap聚類算法v如此轉換約束后運行sap，得出最后的類代表點集合，如圖4所示。psap聚類算法v考慮原始數(shù)據集中的點，如10（2.2，1.4），在seconddb 中標號為7，sap 得出的類代表點為2。該類代表點在合并后的序號為5，經過sap 得出的類代表點為3（5.2，4.5）。從圖1 中可以看出

13、這樣的類代表點是正確的。同理可以為每個原始數(shù)據點確定最終所屬的類標號。在約束ml、cl 下，用sap 算法對原始數(shù)據集進行聚類，得出的類代表點的坐標分別為（2.1，1.3）和（5.2，1.2），在圖1 中用+號標出。從圖1 中不難看出，雖然兩個算法得出的類代表點不同，但是它們都能正確地表示聚類結果。算法對比實驗v實驗數(shù)據來自uci 數(shù)據集，測試了iris 數(shù)據集、wine 數(shù)據集、glass 數(shù)據集和heart 數(shù)據集。各數(shù)據集的基本情況下表所示。算法對比實驗v測試方案為：指定約束個數(shù)如100，給出10 組約束個數(shù)均為100 的約束集合，其中must-linked 和cannot-linked各占一半。采用相同的約束測試每個算法，