作者：錢烽

三、合并聚類算法

基于定義2所提出的相似度定義,我們在圖2中給出最小化局部邊際的合并聚類算法詳細(xì)執(zhí)行過程.首先,針對數(shù)據(jù)集中可能存在的噪聲數(shù)據(jù),我們對所有樣本點進(jìn)行孤立點檢測.然后,作為ACMOM算法的主要過程,我們采用基于MkNN關(guān)系的相似度對檢測結(jié)果為非孤立的樣本點進(jìn)行合并聚類.接著,為了構(gòu)建完整的系統(tǒng)樹圖,我們將其余孤立樣本點賦予距離它最近的類簇.最后,對于不存在任何MkNN連接的少數(shù)剩余類簇集合,我們使用ALINK算法進(jìn)行合并操作并輸出系統(tǒng)樹圖形式的聚類結(jié)果.

該算法的具體執(zhí)行步驟如下:

(1) 初始化基本類簇(第1~6行): 算法首先初始化類簇集合GS和孤立點集合OS為空集,然后遍歷數(shù)據(jù)集中的樣本點.為了避免噪聲數(shù)據(jù)的影響,ACMOM算法對于每一個樣本點都使用了LOF技術(shù)[28]來檢測其是否為孤立點.其中,由于LOF檢測也涉及樣本點的最近k鄰居計算,我們使用了相同的最近鄰參數(shù)k值.對于檢測結(jié)果為孤立點的樣本點,我暫時將其加入孤立點集合OS中.而對于其余樣本點,我們初始化每個樣本點自成一類,并將它們加入到類簇集合GS中,使之成為系統(tǒng)樹圖的葉子節(jié)點.

(2) 合并最相似類簇對(第7~11行): 接著,算法開始執(zhí)行合并操作.在每次合并操作開始時,ACMOM算法首先根據(jù)定義2更新所有可能的類簇間相似度,并從中找出最大值.對于滿足相似度最大值的類簇對和,我們將其合并為一個新的類簇,并在系統(tǒng)樹圖中將其賦為和的父親節(jié)點.最后,我們在類簇集合中用新類簇替換原來的子類簇和.ACMOM算法將不斷重復(fù)上述合并操作直至任意類簇間相似度都為0或所有樣本點都合并至同一類簇為止。

(3) 合并孤立樣本點(第12~15行): 對于剩余的每個孤立樣本點,ACMOM算法首先找到距離其最近的非孤立點鄰居,然后將其合并至該鄰居所在的類簇中.

(4) 返回合并聚類結(jié)果(第16、17行): 上述算法流程執(zhí)行完畢后,如果所有的樣本點都已合并至類簇集合GS中的唯一類簇,我們直接將其作為系統(tǒng)樹圖的根節(jié)點返回給用戶.否則,我們使用ALINK算法對集合GS中的剩余類簇做進(jìn)一步合并操作并返回最終的系統(tǒng)樹圖結(jié)果.為了保證一致性,我們使用類簇間的樣本間距均值來記錄所返回系統(tǒng)樹圖中的節(jié)點高度。

四、復(fù)雜度分析

本節(jié)中,我們將更加具體地描述ACMOM算法的實現(xiàn)細(xì)節(jié),從而詳細(xì)分析其時間復(fù)雜度和空間復(fù)雜度.4時間復(fù)雜度分析

準(zhǔn)備工作: 為了計算類簇間相似度以及使用LOF技術(shù)對樣本點進(jìn)行孤立點檢測,我們需要事先為每個樣本點計算其最近k鄰居集合.ACMOM算法通過構(gòu)建k-d樹結(jié)構(gòu)來實現(xiàn)這一操作.根據(jù)文獻(xiàn)[29,30]的描述,構(gòu)建k-d樹的時間復(fù)雜度為O(nlogn),而為任意樣本點查找k個最近鄰居需要O(dn1-1/d+k)時間.其中,n表示數(shù)據(jù)集中樣本點的個數(shù),表示樣本點的維度.因此,為數(shù)據(jù)集中的n個樣本點構(gòu)建k最近鄰列表的總體時間復(fù)雜度為O(dn2-1/d+kn).

算法步驟(1): 根據(jù)文獻(xiàn)[28]的描述,在已知k最近鄰列表的前提下對n個樣本點進(jìn)行LOF檢測的時間復(fù)雜度為O(n).而將數(shù)據(jù)集中的所有樣本點加入基本類簇集合GS或孤立點集合OS的時間復(fù)雜度也是O(n).因此,算法步驟(1)的總體時間復(fù)雜度是O(n).

算法步驟(2): 算法從O(n)個基本類簇開始,每次選擇兩個現(xiàn)有類簇合并為一個新類簇,執(zhí)行過程最多包含O(n)次合并操作.在此之前,ACMOM算法通過掃描樣本點的k最近鄰列表來構(gòu)建數(shù)據(jù)集的MKNN連接集.這需要O(kn)的時間復(fù)雜度.基于所得的連接集,我們?yōu)槊總€基本類簇保存一個哈希表結(jié)構(gòu)[31],其中存儲了與其相鄰的類簇序號.與序號一起保存的還有參與類簇之間MKNN連接的邊界樣本點集合(即定義2中的PK和PL).這些操作可以通過掃描一遍MKNN連接集完成,因而時間復(fù)雜度也是O(kn).在每次進(jìn)行合并操作時,我們需要找到滿足相似度最大的類簇對.為了加速算法執(zhí)行,我們將與每個類簇最相似的類簇序號以及對應(yīng)相似度存儲在一個最大堆結(jié)構(gòu)[32]中.構(gòu)建最大堆結(jié)構(gòu)的時間復(fù)雜度是O(nlogn),而每次從其中查找滿足最大相似度的類簇對僅需要常數(shù)項時間.在進(jìn)行合并操作時,除了使用常數(shù)項時間將原有類簇的樣本點合并至新的類簇外,我們還需要將原有類簇的鄰居列表進(jìn)行合并,并且更新其最相似鄰居.由于這一列表存儲在哈希表結(jié)構(gòu)中,而類簇的平均鄰居數(shù)為O(k),因而所需的時間復(fù)雜度也是O(k).此外,我們還需要更新與被合并類簇相鄰的其他類簇.假設(shè)這些相關(guān)類簇的平均數(shù)量為個,則對它們的鄰居列表進(jìn)行更新的時間復(fù)雜度為.最后,在最大堆結(jié)構(gòu)中更新這些相關(guān)類簇以及新合并類簇的最近鄰信息需要時間.綜上所述,對數(shù)據(jù)集進(jìn)行O(n)此合并操作的時間復(fù)雜度為,這也是算法步驟(2)的總體時間復(fù)雜度.

算法步驟(3): 為了對每個孤立樣本點查找其最近非孤立點鄰居,我們首先在它的最近k鄰居列表中進(jìn)行搜索,這需要最多O(kn)時間.而對于剩余的孤立樣本點,我們通過進(jìn)一步查詢k-d樹進(jìn)行判斷.設(shè)這些剩余樣本點的個數(shù)為,查詢的最壞時間復(fù)雜度為.之后,將所有孤立樣本點合并至最近類簇的時間復(fù)雜度為O(n).因而算法步驟(3)的總體時間復(fù)雜度為.

算法步驟(4): 假設(shè)類簇集GS中還剩余個未被合并的類簇,使用ALINK算法對其進(jìn)行合并的時間復(fù)雜度為,這也是算法步驟(4)的總體時間復(fù)雜度.

綜上所述,ACMOM算法的時間復(fù)雜度為.根據(jù)第五節(jié)中的實驗結(jié)果,在實際算法執(zhí)行過程中的值都要遠(yuǎn)遠(yuǎn)小于樣本點個數(shù)n.因此,在高維數(shù)據(jù)中ACMOM算法的時間復(fù)雜度主要集中于k最近鄰樣本點的查詢操作O(dn2-1/d)。

4.1空間復(fù)雜度分析

從上面的分析可以得出,ACMOM算法實際執(zhí)行過程中需要存儲如下一些結(jié)構(gòu):(1) 包含有n個樣本點的k-d樹結(jié)構(gòu),空間復(fù)雜度為;(2) 所有樣本點的最近k鄰居列表,空間復(fù)雜度為;(3) 所有樣本點的MkNN連接集,空間復(fù)雜度為;(4) 最多n個相鄰類簇列表,空間復(fù)雜度為;(5) 包含所有類簇的最相似類簇信息的最大堆結(jié)構(gòu),空間復(fù)雜度為.

綜上所述,ACMOM算法的空間復(fù)雜度為,主要集中于存儲所有樣本點的最近k鄰居列表以及與此相關(guān)的其他結(jié)構(gòu)中。

4.2實驗結(jié)果與分析

本節(jié)中,我們將從聚類有效性和算法運(yùn)行效率兩個方面詳細(xì)比較ACMOM算法與其他兩類合并聚類算法.對于經(jīng)典合并聚類技術(shù),我們選取滿足單調(diào)遞減特性的CLINK算法、SLINK算法、ALINK算法和WARD算法作為其代表方法.對任意形狀的合并聚類技術(shù),我們選取目前公認(rèn)表現(xiàn)最好的CHAMELEON算法作為其代表方法.此外,我們還將具體分析算法參數(shù)k值的變化對于聚類有效性和算法運(yùn)行效率的影響.

在算法實現(xiàn)方面,我們通過調(diào)用Matlab軟件中的linkage等函數(shù)來使用CLINK算法、SLINK算法、ALINK算法和WARD算法.另外,我們還通過調(diào)用算法作者所提供的CLUTO軟件包(C++語言)[33]來使用CHAMELEON算法.CHAMELEON算法的主要參數(shù)采用作者建議的-clmethod=graph、-sim=dist、-agglofrom=30 (其他參數(shù)采用軟件默認(rèn)設(shè)置).最后,我們的ACMOM算法采用C++語言編寫實現(xiàn).所有的實驗程序都運(yùn)行在一臺Intel i7-2.8GHz包含有8G內(nèi)存和安裝有Windows 7操作系統(tǒng)的計算機(jī)上。

4.3有效性實驗

4.3.1任意形狀聚類分析

第一組實驗中,我們考察ACMOM算法對于任意形狀類簇的聚類能力。所采用的數(shù)據(jù)集是文獻(xiàn)[16]中用于測試CHAMELEON算法的數(shù)據(jù)集DS1.1-1.4[33]。其中,數(shù)據(jù)集DS1.1-1.3各包含有8000個樣本點,數(shù)據(jù)集DS1.4包含有10000個樣本點.根據(jù)文獻(xiàn)[16]的實驗結(jié)果展示和分析,采用標(biāo)準(zhǔn)參數(shù)設(shè)定的CHAMELEON算法能夠較好地聚類上述數(shù)據(jù)集,而CURE算法對于這幾個數(shù)據(jù)集都出現(xiàn)了較大程度的錯誤劃分.圖3展示了原始數(shù)據(jù)集以及ACMOM算法的聚類結(jié)果,表明其對于任意形狀類簇具有良好的聚類效果。本組實驗中,我們設(shè)置ACMOM算法參數(shù)k = 28,圖3中具體描述了展示所截取的類簇數(shù)目C.

另外,Linkage Metric算法的測試結(jié)果對于上述幾個數(shù)據(jù)集都出現(xiàn)了明顯的錯誤劃分,這來自于其嚴(yán)格單調(diào)遞減的理論特性。限于篇幅原因,我們省略了對其聚類結(jié)果的展示.

4.3.2聚類質(zhì)量分析

第二組實驗中,我們進(jìn)一步使用DS2.1-2.4等真實數(shù)據(jù)集來測試比較ACMOM算法與其他幾種合并聚類算法的聚類質(zhì)量.上述數(shù)據(jù)集都來自于UCI Machine Learning Repository[34],它們中的樣本點都事先貼有所屬類別標(biāo)簽.表2對這些數(shù)據(jù)集的名稱、應(yīng)用領(lǐng)域、大小、維度和真實類別數(shù)目分別做了介紹和統(tǒng)計.作為衡量標(biāo)準(zhǔn),我們選取NMI (Normalized Mutual Information)和purity兩種常用尺度進(jìn)行判斷[35].

當(dāng)算法給出聚類結(jié)果為而真實類簇集合為時, NMI衡量了這兩組劃分的信息一致性,具有如下定義.

其中I是互信息函數(shù), H是熵函數(shù).

上式中n是數(shù)據(jù)集中樣本點的總數(shù),并且和.另外, purity表示了算法輸出類簇包含真實類簇最大比例的累積程度,具有如下定義.

NMI和purity的取值范圍都是[0,1],它們的值越大則說明聚類效果越好.表3顯示了幾種合并聚類算法對于數(shù)

據(jù)集DS2.1-2.4的聚類結(jié)果.其中,我們選擇算法的目標(biāo)聚類數(shù)目為數(shù)據(jù)集包含的真實類簇數(shù),即上式中M = L. 本組實驗中,我們設(shè)置ACMOM算法的參數(shù)k = 22.

?

Table 2 ?Statistics of datasets DS2.1-2.4

表2 ?數(shù)據(jù)集DS2.1-2.4的統(tǒng)計信息

Datasets	Name	Application Domain	# of points	# of dimensions	# of real clusters
DS2.1	Iris	Biology	150	4	3
DS2.2	Breast Cancer Wisconsin	Medicine	683	9	2
DS2.3	Vehicle Silhouettes	Transportation	846	18	4
DS2.4	Image Segmentation	Image Processing	2100	16	7

?

Table 3 ?NMI/purity score of agglomerative clustering algorithms

表3 ?測試不同合并聚類算法的NMI/purity值

Algorithm	Linkage Metric				CHAMELEON	ACMOM
	SLINK	CLINK	ALINK	WARD
DS2.1	0.72/0.68	0.72/0.84	0.81/0.91	0.77/0.89	0.70/0.73	0.80/0.92
DS2.2	0.01/0.65	0.64/0.93	0.68/0.94	0.78/0.97	0.04/0.65	0.84/0.98
DS2.3	0.01/0.26	0.18/0.46	0.17/0.38	0.18/0.45	0.12/0.36	0.20/0.44
DS2.4	0.35/0.29	0.50/0.53	0.49/0.49	0.55/0.56	0.59/0.59	0.68/0.67

?

如表3中所示, ACMOM算法對于不同領(lǐng)域的真實數(shù)據(jù)集都表現(xiàn)出較好的聚類效果.特別對于數(shù)據(jù)集DS2.2和DS2.4, ACMOM算法相比其他幾種合并聚類算法表現(xiàn)出明顯優(yōu)勢.

4.3.3系統(tǒng)樹圖質(zhì)量分析

系統(tǒng)樹圖作為合并聚類算法的輸出結(jié)果,表達(dá)了具體聚類模型下樣本點間的層次性相似關(guān)系.為了衡量系統(tǒng)樹圖是否真實反映了數(shù)據(jù)集樣本點間的內(nèi)在聯(lián)系,相似矩陣P、共表矩陣Pc和共表相關(guān)系數(shù)CPCC(Cophenetic Correlation Coefficient)常被用于判斷其質(zhì)量[12,36].對于一個給定的數(shù)據(jù)集,相似矩陣P中的元素表示了樣本點和間的歐氏距離.而共表矩陣Pc中的元素表示了系統(tǒng)樹圖中樣本點和首次被合并至同一類簇時的節(jié)點高度.共表相關(guān)系數(shù)CPCC則用于衡量這兩個矩陣之間的相關(guān)程度,具有如下定義。

其中,而和分別定義為

CPCC的取值范圍為[-1,1],它的值越大則系統(tǒng)樹圖越能反映出數(shù)據(jù)集的真實狀況.

第三組實驗中,為了比較合并聚類算法所生成系統(tǒng)樹圖的質(zhì)量,我們采用不同類簇數(shù)目和不同維度的球形數(shù)據(jù)集DS3.1-DS3.8[37]進(jìn)行測試,并使用CPCC作為衡量標(biāo)準(zhǔn).其中,數(shù)據(jù)集DS3.1-3.3包含類簇數(shù)量不斷遞增的2維高斯分布樣本點;而數(shù)據(jù)集DS3.4-3.8則都來自于相同的高斯分布生成器,它們的樣本點維度依次遞增.這些數(shù)據(jù)集的二維或三維形狀如圖4所示,表4中描述了它們的詳細(xì)信息.

我們選擇將ACMOM算法與滿足單調(diào)遞減特性的Linkage Metric算法族進(jìn)行比較.這些算法在理論上能夠保證類簇間距離排序的嚴(yán)格保持,不易陷入局部最優(yōu)的困境,因而對于球形類簇具有良好的聚類效果.此外,由CHAMELEON不能生成完整的系統(tǒng)樹圖結(jié)構(gòu),因而無法對其計算CPCC值.本組實驗中,我們設(shè)置ACMOM算法的參數(shù)k = 22.具體的實驗結(jié)果如表5所示.

?

Table 4 ?Statistics of datasets DS3.1-3.5

表4 ?數(shù)據(jù)集DS3.1-3.5的統(tǒng)計信息

Datasets	DS3.1	DS3.2	DS3.3	DS3.4	DS3.5	DS3.6	DS3.7	DS3.8
# of points	3000	5250	7500	2026	2701	4051	5401	6751
# of dimensions	2	2	2	3	4	6	8	10
# of clusters	20	35	50	10	10	10	10	10

?

Table 5 ?CPCC of dendrograms by agglomerative clustering algorithms

表5 ?測試不同合并聚類算法下系統(tǒng)樹圖的CPCC值

Algorithm	DS3.1	DS3.2	DS3.3	DS3.4	DS3.5	DS3.6	DS3.7	DS3.8
SLINK	0.61	0.58	0.52	0.79	0.86	0.91	0.92	0.88
CLINK	0.72	0.72	0.67	0.79	0.90	0.84	0.92	0.87
ALINK	0.74	0.70	0.66	0.83	0.92	0.92	0.94	0.91
WARD	0.74	0.68	0.64	0.81	0.82	0.90	0.91	0.87
ACMOM	0.74	0.70	0.68	0.83	0.92	0.92	0.93	0.91

?

從表5中可以看出, ACMOM算法的聚類結(jié)果一直保持有幾乎最高的CPCC值.相比大部分經(jīng)典合并聚類技術(shù),它能更好地反映出樣本點間的真實距離.因而說明ACMOM算法生成的系統(tǒng)樹圖對于保證合并聚類過程中類簇之間的距離遞增順序具有一定的作用。

網(wǎng)易云產(chǎn)品免費(fèi)體驗館，無套路試用，零成本體驗云計算價值。 ?

本文來自網(wǎng)易實踐者社區(qū)，經(jīng)作者錢烽授權(quán)發(fā)布

更多網(wǎng)易研發(fā)、產(chǎn)品、運(yùn)營經(jīng)驗分享請訪問網(wǎng)易云社區(qū)。

相關(guān)文章：
【推薦】?網(wǎng)易鄭棟：數(shù)據(jù)采集與分析的那些事——從數(shù)據(jù)埋點到AB測試
【推薦】?八月暑期福利，10本Python熱門書籍免費(fèi)送！
【推薦】?數(shù)據(jù)遷移的應(yīng)用場景與解決方案Hamal

轉(zhuǎn)載于:https://www.cnblogs.com/163yun/p/9662203.html

總結(jié)

以上是生活随笔為你收集整理的最小化局部边际的合并聚类算法（中篇）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。