SCMDFC算法研究與應(yīng)用

趙雙柱

（蘭州文理學(xué)院電子信息工程學(xué)院 甘肅 730000）

0 引言

DBSCAN算法[1]是聚類分析中最經(jīng)典的基于密度的聚類分析算法，但算法存在一些問題：聚類質(zhì)量對參數(shù)敏感；不能處理多密度數(shù)據(jù)集。針對DBSCAN缺點(diǎn)，學(xué)者們提出了改進(jìn)算法，如GDBSCAN算法[2]，KNNCLUST算法，這些算法在執(zhí)行過程中不能獲得任何關(guān)于數(shù)據(jù)項(xiàng)的類屬信息，因而通常被看作是一種無監(jiān)督學(xué)習(xí)。

1 半監(jiān)督聚類算法SCMD

1.1 SCMD 算法概述

半監(jiān)督聚類算法SCMD[3]是Yangqiang Yu等人針對多密度數(shù)據(jù)集提出的。算法中的先驗(yàn)信息以成對約束（must-link 和cannot-link）形式給出。算法中涉及到兩個定義：k最近鄰距離和k最近鄰列表，分別用P-Kdistance和P-Kneighbor表示。

SCMD算法主要包括三部分內(nèi)容：首先根據(jù)must-link集計(jì)算出參考Eps列表；然后根據(jù)cannot-link條件從參考Eps列表中選擇不同密度分布的代表Eps；最后，以這些代表Eps為參數(shù)的多階段DBSCAN算法運(yùn)行于數(shù)據(jù)集，得到最終聚類結(jié)果。

1.2 SCMD算法存在的缺點(diǎn)

SCMD算法在一些數(shù)據(jù)集上確實(shí)有著良好的性能，但是仍存在兩個問題。

（1）先驗(yàn)約束不充分時不能檢測到所有的簇

SCMD 算法在聚類過程中用到的所有Eps都是從must-link約束中計(jì)算而來，所以，如果有一個簇不包含must-link約束，則這個簇可能不會出現(xiàn)在最終的聚類結(jié)果中。尤其是當(dāng)這個不包含must-link約束的簇是數(shù)據(jù)集中最稀疏的簇的時候，它一定會被丟失，而簇中的所有點(diǎn)被分配成噪聲。而實(shí)際情況是，專家或者用戶并不總能提供出數(shù)據(jù)集中所有簇的must-link約束。

（2）不能處理簇內(nèi)多密度數(shù)據(jù)集

SCMD算法不能處理簇內(nèi)密度不均的情況。而實(shí)際存在的數(shù)據(jù)集合中，簇中間密集而邊緣稀疏的情況又是很常見的，這也是一種多密度表現(xiàn)形式。對于簇之間密度不同的數(shù)據(jù)集，SCMD 算法有良好的性能，因?yàn)樗軌蛴?jì)算不同密度的不同Eps。而同理，對于一個密度不均的簇，用SCMD 算法可以得到兩個或多個Eps，這樣這個簇會被分割成幾個小的子簇。

2 基于極少約束的多密度半監(jiān)督聚類算法SCMDFC

2.1 算法主要思想

針對SCMD算法的不足，本文提出了一種改進(jìn)的半監(jiān)督聚類算法SCMDFC。該算法的主要思想是：在原算法的基礎(chǔ)上添加對這兩種問題的處理；問題一的解決方法是：充分利用給定的先驗(yàn)知識，從約束條件集合中挖掘與可能會被丟失的簇的相關(guān)信息，從中提取其密度信息，從而查找出所有的簇。問題二的解決方法是：簇內(nèi)密度不均勻時，該簇會被聚為多個子簇，但在這些子簇中，有一個較大的簇是原來簇的主體部分，通過一定的再分配準(zhǔn)則將周圍的小的子簇合并到較大的簇中，從而獲得自然的簇結(jié)構(gòu)。

2.2 算法詳細(xì)描述

具體來說，SCMDFC算法主要增添了兩種方法來彌補(bǔ)SCMD 算法的不足。

（1）查找可能會丟失的簇，添加Eps

由 SCMD算法可知，如果一個簇中不包含有提供的must-link約束，則這個簇可能不會出現(xiàn)在聚類結(jié)果中，因?yàn)樗腅ps沒有被計(jì)算出來。所以本文試圖添加它的Eps到參考Eps列表中來解決這個問題，關(guān)鍵是如何查找這樣的簇。這里，假定這個簇雖然不包含must-link約束，但是包含cannot-link約束中的點(diǎn)。根據(jù)約束的傳遞性，（A，B）屬于must-link 集表明數(shù)據(jù)點(diǎn)A和B屬于同一個簇，（B，C）也是一樣，我們可以得出數(shù)據(jù)點(diǎn)A和C屬于同一個簇。屬于cannot-link集，表明數(shù)據(jù)點(diǎn)A和B不可能在同一個簇中。如果（A，C）是一個must-link 約束，則數(shù)據(jù)點(diǎn)B和C也不可能在同一個簇中，我們可以從約束集合中得到傳遞閉包，則只包含一個數(shù)據(jù)點(diǎn)P的閉包就屬于在聚類結(jié)果中可能會被丟失的簇，也就是SCMDFC算法要檢測的簇。然后，把P-Kdistance定義為該簇相應(yīng)的Eps，并將其加入到參考Eps列表中，這樣，簇結(jié)構(gòu)將不會丟失。

（2）分配邊界簇，解決簇內(nèi)多密度問題

定義1：（邊界簇）一個簇C中的數(shù)據(jù)點(diǎn)數(shù)目小于K時，這個簇是邊界簇。即，|C|< K。

為什么簇內(nèi)數(shù)據(jù)點(diǎn)數(shù)目小于k的簇就是邊界簇呢？它不一定就位于某個較大的簇的邊界，也許它是遠(yuǎn)離其他簇的一個獨(dú)立的簇呢？本算法中是不可能出現(xiàn)這種情況。一個簇必然含有一個或多個核心點(diǎn)，因?yàn)榇厥怯珊诵狞c(diǎn)根據(jù)直接密度可達(dá)的規(guī)則擴(kuò)展來的。核心點(diǎn)的Eps鄰域內(nèi)至少含有M inpts（本算法中是 k）個數(shù)據(jù)點(diǎn)。如果該簇是一個獨(dú)立的簇，則它的核心點(diǎn)不可能有k個鄰居，因?yàn)榇刂袛?shù)據(jù)點(diǎn)的總數(shù)目小于k。所以該簇中沒有核心點(diǎn)。反證證得簇成員數(shù)目小于k的簇不是一個獨(dú)立的簇，而是位于某個較大的簇的邊界。

邊界簇形成的原因是真實(shí)世界中的數(shù)據(jù)集是多密度的，簇的密度不均勻，且通常是中間密度高邊界密度低。SCMD 算法的第三步，Eps值按升序排序，當(dāng)較小的Eps作為參數(shù)用于擴(kuò)展簇時，某個簇中間絕大多數(shù)點(diǎn)被分配為同一個簇標(biāo)簽，而周圍的點(diǎn)分配為噪聲。當(dāng)較大的Eps作為參數(shù)用于擴(kuò)展簇時，之前被分配為噪聲的一個或多邊界點(diǎn)變成核心點(diǎn)開始進(jìn)行簇擴(kuò)展，但這些要擴(kuò)展的點(diǎn)之前已經(jīng)被標(biāo)記，所以就形成了成員數(shù)目小于k的邊界簇。

邊界簇就是 SCMDFC算法所要查找的需要再分配的小的子簇。通過定義可以檢測邊界簇。查找到邊界簇后，算法把邊界簇分別分配給距離它們相對較近的較大的簇。

2.3 實(shí)驗(yàn)結(jié)果及分析

下面通過SCMD算法與改進(jìn)算法SCMDFC的實(shí)驗(yàn)對比，來分析SCMDFC算法的優(yōu)越性。我們選擇了兩個數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，均為多密度數(shù)據(jù)集，且含有噪聲。實(shí)驗(yàn)結(jié)果中，不同的顏色結(jié)合不同的形狀代表不同的簇，其中黑色圓點(diǎn)代表噪聲。

（1）成對約束（must-link）不充分情況

圖1 SCMD算法運(yùn)行于Data1

圖2 改進(jìn)的算法運(yùn)行于Data1

數(shù)據(jù)集Data1（如圖1和圖2所示），包含1707 個數(shù)據(jù)，具有三種密度分布、四個簇結(jié)構(gòu)，且包含噪聲。其中兩個方形的簇具有相同的密度分布，“∞”形的簇是最稀疏的。設(shè)置k=6。如果must-link約束充分，即每種密度分布的簇中都至少包含一個must-link 約束，則SCMD算法和SCMDFC 算法均能有效地發(fā)現(xiàn)簇結(jié)構(gòu)。然而，當(dāng)“∞”形的簇中的must-link約束沒有提供時，實(shí)驗(yàn)結(jié)果顯示SCMD算法只能找到三個簇，“∞”形的簇中的數(shù)據(jù)被分配成了噪聲，如圖2所示，而算法SCMDFC仍能精確地發(fā)現(xiàn)四個簇，如圖2所示。

（2）簇內(nèi)多密度情況

數(shù)據(jù)集Data2包含1938個數(shù)據(jù)。該數(shù)據(jù)集具有三個自然的簇結(jié)構(gòu)且包含噪聲，每個簇中的數(shù)據(jù)都是高斯分布的，也就是說簇中心密度高邊緣密度低。設(shè)置 K=20，實(shí)驗(yàn)結(jié)果顯示應(yīng)用SCMD算法聚類三個簇中的大部分點(diǎn)都被正確分配，但簇邊界的點(diǎn)被聚成了一些小的簇。改進(jìn)的算法可以有效地發(fā)現(xiàn)三個完整的簇，并正確的識別噪聲。

3 結(jié)論

本文提出的 SCMDFC算法充分挖掘成對約束集中所包含的信息，在must-link集不充分的條件下，仍能完整查找到所有的簇結(jié)構(gòu)，而且通過一定的再分配準(zhǔn)則解決簇內(nèi)多密度問題，但也存在不足，在must-link和cannot-link約束均不充分的條件下，不能查找到全部的簇結(jié)構(gòu)。在今后的研究工作中，希望能有進(jìn)一步的改進(jìn)。

[1]Martin Ester，Hans-Peter Kriegel，J?rgSander，et al.A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases w ith Noise[C].In Proceedings of 2nd International Conference on Know ledge Discovery and Data M ining（KDD '96）.1996：226-231.

[2]J?rg Sander， Martin Ester， Hans-Peter Kriegel， et al.Density-Based Clustering in Spatial Databases：The Algorithm GDBSCAN and Its Applications[J].Data M ining and Know ledge Discovery.1998，2（2）：169-194.

[3]Yang-QiangYu，Tian-QiangHuang，Gong-DeGuo，et al.Sem i-supervised clustering algorithm for multi-density and complex shape dataset[C].In Chinese Conference on Pattern Recognition（CCPR '08）.2008：1-6.