基于屬性擴展圖的K-means聚類算法的研究.pdf

1、社團結(jié)構是社會網(wǎng)絡普遍存在的拓撲特性之一，發(fā)現(xiàn)社會網(wǎng)絡中的社團結(jié)構是復雜網(wǎng)絡研究的基礎性問題。聚類算法是發(fā)現(xiàn)社團結(jié)構的一種重要的方法。聚類分析技術在過去的許多年中得到了廣泛的研究，其中K-means聚類算法是眾多聚類算法中比較經(jīng)典的一個。K-means聚類算法由于思想簡單、時間復雜度小而被廣泛的進行了研究與運用，尤其在對大規(guī)模數(shù)據(jù)進行挖掘中，K-means聚類算法具有高效性及可伸縮性。
　　真實網(wǎng)絡中，除了數(shù)據(jù)之間存在的拓撲結(jié)構以

2、外，其數(shù)據(jù)本身存在著各種特殊屬性?，F(xiàn)存的許多聚類算法僅僅依靠數(shù)據(jù)間的拓撲結(jié)構進行聚類，而很大程度的忽略了數(shù)據(jù)所具有的特有屬性在聚類分析中的作用。本文在分析聚類算法中節(jié)點的拓撲結(jié)構及特有屬性的作用之后，對K-means聚類算法進行改進，提出了一種新的聚類算法-SAK聚類算法。本文的主要研究成果如下：
　?。?）將真實網(wǎng)絡用圖的模型表示，并根據(jù)現(xiàn)實網(wǎng)絡的實用性，將節(jié)點的屬性特性作為節(jié)點添加到圖中，并根據(jù)節(jié)點與屬性的關系添加相應的邊，從

3、而構成屬性擴展圖。在屬性擴展圖的基礎上，使用隨機行走模型對節(jié)點的結(jié)構及屬性相似性進行統(tǒng)一的測量。
　?。?）提出了一種自動更新權重值的方法，在聚類算法不斷迭代的過程中，節(jié)點邊的權重會隨之發(fā)生變化，隨著權重的改變節(jié)點間的相似度也會隨之改變，這樣，不同的屬性將會在聚類算法中起到不同的作用。這種改變將會使節(jié)點間相似度的測量更加趨于實際，趨于準確。
　?。?）提出基于屬性擴展圖的K-means聚類算法（SAK），該算法改變K-mea