聚類趨勢問題的研究綜述
2009-01-01 00:00:00褚娜馬利莊王彥
計算機應用研究 2009年3期
(1.上海交通大學 電子信息與電氣工程學院 計算機科學與工程系， 上海 200240; 2.上海中醫藥大學 信息科學與技術中心， 上海 201203)
摘 要：聚類算法的性能與數據集的結構是密切相關的，雖然目前已經研究出了很多聚類算法，但沒有普遍適用的萬能聚類算法，欠缺對數據集結構的有效解釋。對聚類分析過程中重要的關鍵性問題，即聚類趨勢問題進行了系統性的研究，從統計檢驗、可視化分析等角度給予了討論，為數據集的無監督聚類分析提供了合理和有效的前期分析工具。
關鍵詞：聚類趨勢； 聚類分析； 統計檢驗； 可視化評估
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)03080103
Research for clustering tendency
CHU Na1， MA Lizhuang1，2， WANG Yan1
(1.Dept. of Computer Science Engineering， School of Electronic Information Electrical Engineering， Shanghai Jiaotong University， Shanghai 200240， China; 2.Center of Information Science Technology， Shanghai University of Traditional Chinese Medicine， Shanghai 201203， China)
Abstract:It is closely related between the performance of clustering algorithms and the structure of data sets. No methods were good enough for all types of data， nor were all methods equally applicable to all problems， and were short of reasonable interpretation to data structure. And systematic researched the clustering tendency， which was one of key problem about clustering analysis. This paper discussed it based on statistic tests， visual analysis and so on， and proved that it could present reasonable and effective analysis tools for unsupervised clustering analysis of data sets.
Key words：clustering tendency; clustering analysis; statistic tests; visual assessment
由于數據庫技術和傳感器技術的飛速發展、數據收集和數據存儲技術的快速進步，使得各組織及研究機構積累了海量數據，另一方面，網絡技術的發展也使獲得大量數據變得較容易。然而在很多實際應用中，這些海量數據由于缺少形成模式類過程的知識，都是沒有類別標簽的。聚類分析技術能解決這一類問題幫助分析數據的分布、了解各數據類的特征、確定所感興趣的數據類以便作進一步分析[1]，尋找隱藏在數據中的結構。它將一組分布未知的數據進行分類，以盡可能地使得在同一類中的數據具有相同性質，而在不同類中的數據其性質各異[2]。目前，聚類分析技術已經在很多領域得到了成功的應用，如模式識別、圖像處理、商業數據分析、市場研究、生物基因、信息安全、計算機視覺等，涉及面非常廣泛，并且提出了各種聚類算法[3~7]，如比較典型的Kmeans均值算法、FCM等等。然而，大多數聚類分析算法對輸入參數是敏感的，且都存在一個不合理的假設：待分析的數據集是可聚的[8]。事實上，現有的大多數聚類算法并不分析數據集的可聚性，只要對數據集進行聚類操作就能得到一個聚類結果。因此，這一不合理假設的存在會產生兩個問題：a)如果數據集在空間中是均勻分布的，即自然簇不存在，對數據集進行聚類操作，顯然得到的聚類結果是不合理的，且是不可解釋的；b)因某種聚類算法并不是對所有的數據類型或者數據結構的分析是適用的[9]，若不先對數據集進行聚類趨勢分析，盲目地選擇聚類算法，相當于是硬性地對數據施加一定的結構，不僅浪費了時間和精力，反而得到錯誤的結果。
為了避免聚類算法的不適當應用，也為了幫助更有效地解釋聚類結果和了解數據本身的自然屬性，并且降低將錯誤的結構強加給數據集的可能性，在應用聚類算法之前進行聚類趨勢分析是很重要的[10]。
1 聚類趨勢的定義
聚類趨勢或簇聚傾向分析就是試圖評估數據集中是否存在自然簇，即檢驗數據集是否具有類分性，而不是進行聚類[4，11]。從統計學的角度，就是檢測數據集是否是隨機或者均勻分布的[12]。在一些文獻中，也有將這個問題稱為關于模式在特征空間中分布類型的預測[4，13]或者聚類能力的檢測[14]。
2 聚類趨勢分析的原理
近年來，在聚類趨勢分析理論方面的研究已經做了很多工作，提出了許多方法，并在許多領域內得到了應用。例如，在信息檢索中應用聚類趨勢分析檢測詞匯在自然語言中的分布情況，幫助提高檢索的效率[15~17]；在化學領域，聚類分析用于尋找藥品結構之間的關系[18，19]；對綠茶中抗氧化劑成分進行采樣分析時，利用聚類趨勢分析進行孤立點的檢測[20]等。
2.1 基于統計檢驗方法的聚類趨勢分析
基于統計檢驗方法的聚類趨勢分析依賴于零假設，即數據集合在測量空間中是均勻分布的。早期的工作主要局限于低維空間中，在假設抽樣窗口已知的條件下，應用空間抽樣原理，基于最近鄰模式或最小生成樹的方法[21，22]建立統計量，如Hopkins、Holgate、CoxLewis[23，24]、T平方統計量[10]和Elberhardt統計量[25]，辨析數據集的空間結構，研究聚類趨勢問題。其中Hopkins統計量在應用稀疏數據集的情況時效果欠佳[26，27]，而且在擴充到多維空間中時也不如CoxLewis統計量檢測性能優良[28];CoxLewis統計量雖然在高維空間檢測中存在優勢，但有時得到的檢測結果是片面的、不穩定的[29]；T平方統計量是在實踐中最經常被使用的，并表現良好。根據T平方采樣原理[30，31]和k近鄰模式距離，推廣到d(d≥3)維空間中的k近鄰T平方統計量如下：
Tk=(1/M) ∑Mi=1 Udi(k)/[Udi(k)+0.5Vdi(k)]（1）
其中：M為原始采樣點O的個數；U和V分別是原始O點到P1點以及T平方采樣P2點的k近鄰距離，如圖1所示。
T平方統計量的定義中，T平方統計量不僅依賴于數據集中的模式向量與采樣窗口內選擇的抽樣始點向量之間的距離，還依賴于數據集以及采樣窗口的個數[32]，而且對抽樣窗口的設置有要求。曾廣周人等雖然在文獻[23，25]中對抽樣的矩形窗口、球形窗口以及球—矩形窗口的設置進行了分析探討，并在低維空間中取得了良好的效果，然而樣本窗的推導需要計算數據集的凸包，其計算代價很高；后來曾廣周又提出半框框架制約條件，將樣本窗定義為一個超球體，以數據集的均值點為中心，包含原來向量的一半[8]，拓寬了零假設范圍，在一定程度上減弱了抽樣窗口的設置問題。改進后的T平方統計量定義如下：
Tk={（1/M） ∑Mi=1 Udi(k)/[Udi(k)+0.5Vdi(k)]-0.5}×12M（2）
然而總體來說，這些抽樣窗口在高維空間中的設置仍然是困難的，直接影響了檢驗統計量的分布，并不能很好地發揮作用。綜合以上討論，基于統計檢驗方法的聚類趨勢分析，對于選擇正確的模型、窗口參數等是非常關鍵的，具有挑戰性。
2.2 基于圖論方法的聚類趨勢分析
如果把數據看做是多維空間中的點，整個數據集就可以看做是一個無向圖G，由一組頂點X和連接頂點的邊E構成。
G=[X，E]，X（G）={x1，x2，…，xn}
E(G)={eij=(xi，xj)｜xi，xj∈X}(3)
定義1 完全k部圖。圖G中的頂點X被劃分為k個完全不相交的子集，如果來自不同子集中的任意一對頂點在圖G中都是相鄰的，那么就稱這個圖是k部完備的，即k部完全圖。
根據著色原理，對于任意一個數據集，總是存在著一個對應著的k部圖。根據定義1可以得到聚類趨勢指數的定義：
定義2 聚類趨勢指數IC[33，34]。一個數據集的聚類趨勢指數是指使得該數據集成為k部完全圖而需要補充的邊數，即
IC=(1/2)∑ki=1 ∑x∈X[dmaxG(X)-dG(X)]=(n2-∑ki=1n2i)/2-m(4)
歸一化處理：
IG=1-m/Emax （5）
其中：m為圖G的總邊數；ni為第i個頂點子集包含的頂點個數； Emax為該數據集k部完全圖的邊數。
如果Emax=0，表示所有的頂點都是不相鄰的，完全k部圖中沒有邊存在，此時分配聚類趨勢指數為-1，著色方法得到的所有頂點顏色將是相同的，即數據集中不存在聚類；反之，如果所有的頂點都是相鄰的，即該數據集是一個完全k部圖，著色方法需要使用n種顏色來標記圖中的頂點，即數據集中每個頂點自成一類。如果上述兩種情況不存在，則該數據集具有可聚類趨勢。
2.3 基于可視化方法的聚類趨勢分析
簇數的初始化問題一直是傳統聚類方法的難點。可視化操作的目的不僅是為了顯示聚類的結果，而且也能顯式地觀察數據集是否具有可聚性，優化傳統聚類分析方法的輸入參數，如FCM、Kmeans方法的預先類別數K值的初始化。如果數據集的樣本量很大或者特征屬性很多，或者樣本之間具有強關聯性等，在這種情況下，用簡單的散點繪圖方法觀察數據的空間分布情況是不可行的。
2002年，Bezdek等人[35]提出了聚類趨勢分析的可視化評估算法VAT（visual assessment of tendency）。該方法提出基于最小支撐樹的剪枝原理對相異度矩陣R進行重排序，使得具有小相異度的數據樣本被分配相對鄰近的索引指數，再將其元素值轉換成灰度信息進行可視化，就可以明顯判斷出該數據集所具有的潛在聚類結構，即聚類趨勢信息。實驗證明[36]，VAT對低于500個小樣本的數據集有很好的效果；對大樣本數據集，其重排序操作將造成嚴重的計算負擔，具有高計算時間復雜度O(n2)，并且相異度圖像矩陣的維數也有可能超過顯示器可顯示的分辨率。為了解決對大樣本或關聯數據集進行聚類趨勢分析時遇到的問題，Huband[36]和Hathaway等人[33]分別提出了reVAT算法(revised VAT)及sVAT(scalable VAT)算法。利用偽排序和采樣技術對重排序操作過程進行改進，用相異度圖的二維剖面圖集合代替了VAT中的相異度圖矩陣，其迭代過程僅運行c次。其中c是數據集包含的類別個數，大大縮減了排序的操作次數，降低了計算時間復雜度O（cn)，具有更強的適應特征維數增加的能力和計算效率。剖面圖pi和閾值δ計算如下：
pi=[pij]∶pij=1-Rij/gM； j=1，2，…，n（6）
pi=∑nj=1 pij/n（7）
δ=(1+pi)/2（8）
其中：gM是表示相異度矩陣R中的最大值，表示數字灰度方圖里的最高灰度級。
然而，當數據集自然簇數(c＞5)變得很大時，或者當數據集的各簇沒有明顯簇內緊湊和簇間分離的特點時，使用reVAT方法得到的剖面圖是混雜的，具有部分重疊區域，于是對剖面圖的解釋將變得很困難。針對VAT以及reVAT存在的問題，Huband等人[34]提出bigVAT(VAT for large datasets)算法，其中保留了VAT以及reVAT算法具有的優勢，在建立剖面圖的基礎上進行N采樣，得到一個N×N類VAT相異度圖IbV，N值上限限制為500個采樣樣本。采樣過程如下：
IbV=Rtitj/gM」或者「Rtitj/gM（9）
ti∈T1，如果1≤i≤n1ti∈T2，如果1+n1≤i≤n1+n2…ti∈Tk，如果1+∑k-1j=1nj≤i≤∑kj=1nj(10)
其中：ti表示在剖面圖中采樣得到的相異度矩陣R中元素的下標；Ti表示剖面圖中大于閾值δ的下標集合。圖2[34]給出了40 000個樣本的集合S8的實驗結果，使用reVAT算法處理后，在第8個剖面圖出現了重疊區域，不能明確地得到聚類數是7個還是8個，還需要其他的輔助方式進行確定。而bigVAT算法對S8的處理，沿主對角線方向的黑塊顯示了聚類趨勢，可為傳統的聚類分析算法提供良好的先驗知識。
綜上所述，VAT在現有軟/硬件條件的限制下能有效地對小樣本數據集進行可視化的聚類趨勢分析，但對大樣本和關聯性數據集的處理是困難的，其改進方法reVAT、bigVAT、sVAT基本解決了這些問題。同時，bigVAT算法亦解決了隨著樣本集聚類數目增加所帶來的剖面圖難以解釋的問題。但是上述方法都只針對相異度矩陣是方陣的情況，隨后Bezdek等人[37]對此技術進行了拓展，提出基于矩形相異度矩陣的可視化聚類趨勢評估方法，提高了聚類趨勢可視化評估方法的應用范圍和能力，并有良好的應用效果，但是計算復雜度很高。
3 結束語
為避免聚類算法的不合理應用，以及為傳統聚類算法提供更多的先驗知識，聚類趨勢問題的研究已引起很多研究者的重視。本文主要討論了基于歐幾里德距離方法的聚類趨勢檢驗和可視化評估問題，對于避免聚類算法對單一類或均勻分布的數據集的不適當應用起到了良好的效果，有助于聚類結果的正確解釋。但是對于實際數據來說，其空間分布形狀和大小一般是不知道的，所以常用的距離方法未必能提供良好的模式空間分布狀態信息，因此必須注意這個問題；除此之外，對于不同領域的數據集，應根據實際應用作具體的聚類趨勢問題分析[38]。下一步筆者將致力于尋找恰當的、更低計算時間復雜度的方法，進行聚類趨勢問題的研究。
參考文獻：
[1]TAN Pangning， STEINBACH M， KUMAR V. 數據挖掘導論[M]. 范明，范宏建，譯.北京：人民郵電出版社， 2006.
[2]HAN Jiawei， KAMBER M. Data mining:concepts and techniques[M].San Fransisco:Morgan Kaufmann Publishers， 2000.
[3]JAIN A K， MUTRY M N， FLYNN P J. Data clustering: a review[J].ACM Computing Surveys， 1999， 31(3):264323.
[4]JAIN A K， DUBES R C. Algorithms for clustering data[M].New Jersey:Prentice Hall， 1988.
[5]蔡元萃，陳立潮. 聚類算法研究綜述[J]. 科技情報開發與經濟，2007，17（1）：145146.
[6]ANDERBERG M R. Cluster analysis for application[M].New York:Academic Press，1973.
[7]行小帥，焦李成. 數據挖掘的聚類方法[J]. 電路與系統學報， 2003，8(1):5967.
[8]高新波.模糊聚類分析及其應用[M]. 西安：西安電子科技大學出版社， 2004.
[9]HALKIDI M， VAZIRGIANNIS M. A data set oriented approach for clustering algorithm selection[C]//Proc of the 5th European Conference on Principles of Data Mining and Knowledge Discovery. London: SpringerVerlag， 2001:165179.
[10]曾廣周.隨機分布模式的統計檢驗[J]. 山東工業大學學報， 1986，16(4):1218.
[11]THEODORIDIS S， KOUTROUMBAS K. Pattern recognition[M]. 2nd ed. New York:Academic Press， 2003.
[12]CROSS G R， JAIN A K. Measurement of clustering tendency[C]//IFAC Symposium on Digital Control. New Delhi:[s.n.]， 1982:2429.
[13]DUBES R C， JAIN A K. Validity studies in clustering methodologies[J]. Pattern Recognition， 1979，12(11):235254.
[14]EPTER S， KRISHNAMOORTHY M， ZAKI M. Clusterability detection and initial seed selection in large data sets[EB/OL].199906 (2004).http://libra.msra.cn/papercited.aspx?id=108767.
[15]DUBIN D. Document analysis for visualization[C]//Proc of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York:ACM Press，1995:199204.
[16]DUBIN D. Structure in document browsing spaces[D]. Pittsburgh:University of Pittsburgh， 1996.
[17]DUBIN D. Clustering tendency and the cluster hypothesis in information retrieval[C]//Proc of Annual Meeting of the Classification Society of North America. 1996.
[18]LAWSON R G， JURS P C. New index for clustering tendency and its application to chemical problems[J]. Journal of Chemical Information and Computer Sciences， 1990，30(1):3641.
[19]WILLETT J. Similarity and clustering in chemical information systems[M]. New York:Wiley， 1987:138142.
[20]ZHANG M H， LUYPAERT J， FERNNDEZ PIERNA J A，et al. Determination of total antioxidant capacity in green tea by nearinfrared spectroscopy and multivariate calibration[J].Talanta，2004，62(1):2535.
[21]ZENG G， DUBES R C. A test for spatial randomness based on kNN distance[J]. Pattern Recognition Letters，1995，3(2):8591.
[22]SMITH S P， JAIN A K. Testing for uniformity in multidimensional data[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1984，6(1):7381.
[23]PANAYIRCI E， DUBES R C. Extension of the CoxLewis method for testing multidimensional data[J]. Pattern Recognition，1988，7(1):18.
[24]VINAY V， COX I J， MILICFRAYLING N， et al. On ranking the effectiveness of searches[C]//Proc of the 29th Annual International ACM SIGIR Conference on Research and Development. New York:ACM Press， 2006:398404.
[25]曾廣周.聚類趨勢的MonteCarlo檢驗[J]. 計算機應用與軟件， 1989，6（1）:3550.
[26]LAWSON R G， JURS P C. Cluster analysis of acrylates to guide sampling for toxicity testing[J]. Journal of Chemical Information and Modeling， 1990，30(2):137144.
[27]FERNANDEZ P J A， MASSART D L. Improved algorithm for clustering tendency[J]. Analytica Chimica Acta， 2000，408(12):1320.
[28]BANERJEE A， DAVE R N. Validating clusters using the Hopkins statistic[C]//Proc ofIEEE International Conference on Fuzzy Systems.Piscataway:IEEE Press， 2004:1749
