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

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

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

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