聚類分析研究的挑戰性問題范文

本站小編為你精心準備了聚類分析研究的挑戰性問題參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《廣東工業大學學報》2014年第二期

聚類分析是一個富有挑戰性的任務，尤其是在大數據時代，隨著微博、微信等新型社會化媒體的出現，不同來源的數據一方面使數據呈現出TB級／天的增長趨勢，另一方面使數據的類型變得更加多樣化，使數據的結構變得更為繁雜，這些變化給聚類分析研究帶來了新的困難和挑戰，具體挑戰包括處理多樣化數據類型的能力、處理超高維數據的能力、處理不均衡數據的能力、聚類算法的可拓展能力和聚類效果評價的指標選擇問題．這些挑戰有的是自聚類算法產生以來就已存在，有的則是新時代產生的新問題．

1處理多樣化數據類型的能力

隨著信息技術的發展，數據的類型變得越來越復雜，同一個研究對象中可能會同時包含著多種不同類型的數據．針對不同的數據類型，研究者們提出了不同的聚類算法．不過在聚類算法產生初期，人們最先關注的是比較容易理解和處理的數值型數據．早在1967年MacQueen就針對數值型數據集提出了非常經典的Kmeans聚類算法，該算法以歐氏距離作為數值屬性差異性的度量方法［13］．Kmeans算法實現簡單，計算速度快，處理效率高，但不能處理分類型數據．對于分類屬性的數據，通常存在兩種不同的處理方式，一種是將分類屬性轉換成多個取值為0和1的數值屬性，再利用Kmeans算法進行處理；另一種是由Huang，JoshuaZhexue教授提出的適用于純分類屬性的Kmodes算法，該算法采用匹配差異法度量分類屬性之間的差異程度，但這種表示難以準確反映出類中對象的取值情況，導致差異性度量不準確，并且當某個屬性取值頻度最大的屬性值多于一個時，mode不唯一，不同的mode選擇可能得到完全相反的結論．事實上，在許多實際應用中，需要處理的數據中往往既含有數值型屬性又包含分類型屬性，此時使用Kmeans或Kmodes算法都不能有效地解決問題．針對該問題，Huang結合Kmeans和Kmodes算法提出了能夠處理混合型屬性的Kprototypes聚類算法，但是該方法存在著與Kmodes算法一樣的缺點．隨后，蔣盛益針對Kprototypes聚類算法的不足，以統計頻度作為分類型屬性的差異性度量指標并提出了Ksummary算法，該算法很好地提高了聚類效率，但是時間開銷較Kprototypes有所增加．為了進一步提高聚類效率，在混合屬性差異性度量的基礎上又提出了一種基于最小距離原則的聚類算法（也稱一趟聚類算法），其基本思想就是將對象依次被并入到與其差異度最小的簇中．一趟聚類算法只需掃描數據集一遍，具有近似線性的時間復雜度、聚類精度高的優點，可拓展性高，適用于劃分大規模數據集．所以在處理大數據集時，將一趟聚類算法與其他聚類算法結合而形成的混合聚類算法或聚類融合算法則可以提高聚類效率和質量．另外，謝岳山等為解決聚類融合算法對混合屬性數據處理效果不佳的問題，提出了一種基于圖論的加權聚類融合算法，在聚類的基礎上利用預設的融合函數對數據對象進行權重賦值，同時通過設置各個數據對間邊的權重來確定數據之間的關系，并得到加權最近鄰圖，然后再用圖論的方法進行聚類．實驗表明，該算法的聚類精度和穩定性優于其他聚類融合算法．上述算法都是將一個對象劃分到一個簇中，屬于硬聚類．但是在實際領域中，有許多對象往往同時屬于多個類，所以目前有許多研究工作對上述算法進行改進形成軟聚類以解決實際應用中的現實問題．盡管Kprototypes、Ksummary和一趟聚類算法能夠處理混合型屬性，但是它們在兩種不同類型屬性差異性度量和比較方面的有效性還值得商榷．換句話說，在特征空間上，分類屬性的取值頻度與數值屬性的絕對偏差在理論上是不能直接進行大小比較的．因此，如何改進不同類型屬性差異度的可比性或提出更有效的混合屬性差異度度量方法是未來研究的一個重要挑戰．

2處理超高維數據的能力

在高維空間中聚類數據對象是非常有挑戰性的，因為數據可能分布非常稀疏，而且會高度偏斜．例如，“雙十一購物狂歡節”的背后隱藏著商品品牌銷售量和賣家客戶數量分布的不平衡性以及用戶購買數據的稀疏性．傳統聚類算法在處理低維數據時能夠表現出較好的性能，但對于高維數據，由于屬性數量過多引起的稀疏性問題和屬性差異性度量的偏差問題，這往往會導致聚類效果變差．維度災難是一個非常普遍的現象，若直接采用傳統聚類算法往往不能得到所期望的結果．為了更好地滿足現實需求，研究者們提出了許多針對高維數據的聚類方法．綜觀當前研究成果，在面對高維數據時通常都是先對特征空間進行處理，采用特征變換或特征選擇的方式來降低特征維度以提高聚類算法的性能．特征變換是根據合適的方法尋求與高維數據等價的低維空間表示，通過將原始特征空間進行變換，重新生成一個維數更小、各維度之間的獨立性更強的空間，從而使降維之后的數據所包含的信息與降維之前盡可能地相同或相近［28］．最常用的特征變換方法有小波變換、PCA、LPP和NPE［31］．特征選擇是在不同任務需求下選取那些符合要求且彼此之間關聯程度較小的最優特征子集的過程，其目的是通過剔除與任務需求不相關和弱相關的特征以降低維度，從而提高學習算法的效率和性能．特征選擇算法在尋找最優特征子集時，需要對特征之間的相關性進行評價．對于相同類型的特征一般采用線性相關系數、信息增益、互信息、可分性等指標來度量特征的相關性．而對于混合類型特征的相關性度量而言，通常采用的方法是將連續特征進行離散化，將混合特征之間的相關度計算轉化為兩個離散特征之間相關性的度量問題．離散化策略一方面會增加額外的時間開銷，另一方面也可能會造成信息丟失，從而降低數據的處理效率與質量．為避免這些問題，文獻［35］用均方差性質提出了一種混合特征相關性度量方法CMMF，但是如何更有效地將混合特征相關度與同類型特征間相關度進行比較也是當前需要解決的一個重要問題．特征選擇的另一種形式是子空間聚類，利用聚類算法在不同子空間中搜索簇群．目前用于處理高維數據的方法大多采用軟子空間聚類，其基本思想是：在聚類時將類別看成是模糊的，即每個對象在一定程度上可以看成屬于某一簇，在一定程度上又可以看成屬于另一個簇，通過對數據集中的各類別賦予不同的特征權重向量，并以此來表示聚類過程中各維特征對此類別貢獻的大小．在聚類過程中，不同的特征在不同的類別上有不同的貢獻，因此不同的特征在不同類別有不同的特征權重向量，從而形成了若干個“軟子空間”．典型軟子空間聚類算法子空間方法多采用劃分類型的聚類算法，但是這類方法一直存在著聚類個數難以確定的問題．另外，在處理混合類型數據時，子空間聚類該如何更好地分配權重向量也是一個非常難以解決的問題．

3處理不均衡數據的能力

隨著信息技術的廣泛應用，無論是科學研究還是社會生活的各個領域中都積累了大量的數據，這些數據中可能會存在某類數據對象的數量遠遠多于其他類別數據，或是很大部分是沒有標記，只有少量是有標記的，造成數據分布出現不平衡性．在缺乏類別信息情況下，采用聚類方法就是一種有效的處理方式．而在現實生活中，大多數對象并沒有嚴格的類別，它們在狀態和類別方面存在著模糊性，因而進行軟劃分可能會更加真實和合理，這種現象在不均衡數據集上表現尤為突出．從大量聚類算法的實驗中可以看出，相對來說，聚類算法在不均衡數據集上的性能要比在均衡數據集上的性能差．現有的劃分聚類算法或層次聚類算法等在處理不均衡數據時，其聚類性能大幅度下降；部分圖論聚類算法，如DBSCAN、Chameleon等能有效識別任意大小和不同形狀的簇，在處理不均衡數據方面效果相對較好，但它們的時間復雜度都很高，難以處理大規模的數據集．文獻［41］結合一趟聚類算法改進了DBSCAN算法，其聚類性能有了較大的提高，在處理不均衡數據方面更有優勢，同時也可以應用于大規模數據集．文獻［42］和［43］提出的兩階段混合聚類策略能比較有效地處理不均衡文檔數據，文獻［42］在聚類第二個階段采用文檔權重調整技術，根據文檔被錯誤劃分的次數調整文檔的權值，以減少文檔不平衡分布造成的影響．由于METIS圖劃分技術對不均衡數據處理效果欠佳，文獻［43］提出使用Graclus代替METIS對不均衡數據構成的圖進行圖劃分處理，以提高算法處理不均衡數據的性能．李志華等針對分類屬性數據樣本間的分布不平衡性、樣本的分布與空間距離無關的特點，提出一種基于量子機制的分類屬性數據模糊聚類算法．文獻［44］和［45］通過修改傳統聚類算法目標函數和加入權重系數來提高算法的魯棒性以及在不均衡數據上的聚類性能．文獻［46］和［47］在聚類過程中，考慮了屬性的不平衡分布，對不同的分類屬性賦予不同的權值以提高聚類算法的擴展性．另外，集成學習和數據抽樣也是解決不均衡數據聚類的有效方式，它們通過投票機制或抽樣訓練的方式改進原始數據的分布結構以降低不均衡性［48，49］．雖然在不均衡數據的處理問題上存在著多種解決方式，但是在對待具體大規模數據時，其算法的效率和效果都有待進一步分析和驗證．所以，針對不均衡數據的高性能聚類算法研究也是一個有待深入研究的問題．

4聚類算法的可拓展能力

許多聚類算法在小樣本數據數據集上能夠表現出很好的性能，但對包含幾百萬甚至上億個數據對象的大規模數據集進行聚類可能會產生有偏的結果．因為不同類型的聚類算法都存在著各自的問題：劃分聚類算法中聚類數目的選擇和聚類初始點的選擇是影響算法性能的關鍵和難點；層次聚類算法雖然不需要預先指定聚類數目，但是它在運行過程中不能回溯處理已經形成的簇結構，且時間復雜度非常高；基于圖論的聚類算法易于發現不規則的簇，但圖的最優劃分是一個NP難問題；基于網絡和密度的聚類算法需要預先指定較多參數．上述問題都是影響聚類算法的可擴展性的重要因素，但目前也有不少研究針對這些問題對部分聚類算法進行改進以提高其拓展性．文獻［50］提出了一種面向最小包含球問題的核心集求解算法，該算法所得核心集的大小與數據集的維數和大小均無關．文獻［51］將該技術用于譜聚類，提出了新的適用于大規模數據集的譜聚類算法．文獻［52］結合增量聚類方法對GKMeans算法進行改進，該算法需要最小化輔助聚類函數．而文獻［53］和［54］分別在聚類數目確定和聚類初始點的選擇方面給出有指導性的處理方式，并使它們能拓展至大規模數據集上．最近，Tzortzis等通過對各個簇指派不同的權重值以尋找到最優的初始聚類點，實驗證明該方法具有較好的拓展性，能夠應用于大規模數據集［55］．盡管許多聚類算法在經過改進之后能夠在一定程度上適用于大規模數據集，但是在面對超大規模的數據集時，還需要研究更有效的、拓展性更好的聚類算法．

5聚類效果評價的指標選擇問題

聚類算法產生已經有幾十年了，但是關于聚類算法的評估問題一直仍然是一個尚需突破的難題．聚類算法的常見評估指標包括外部評估指標和內部評估指標．外部評估方法是有監督的方法，與聚類算法無關．理想的聚類結果是：具有相同類別的數據對象被聚集到相同的簇中，不同類別的數據對象聚集在不同的簇中，主要的指標有聚類熵、聚類精度和召回率等．聚類熵考慮簇中不同類別數據的分布，聚類熵越小，聚類效果越好．聚類精度的基本出發點是使用簇中數目最多的類別作為該簇的類別標記．聚類召回率能夠反映被正確聚類的對象的比率．內部評估方法是利用未知結構數據集的固有特征和量值來進行評價，主要通過考察簇的分離情況和簇的緊湊情況評估聚類效果，常用的指標有SSE、Cophenetic相關系數和stability等．此外，聚類數目也是評估算法性能的一個重要指標．一般而言，SSE、stability聚類熵、聚類簇個數和召回率之間一致性較好，但不絕對，而這些指標往往都和聚類精度有沖突．特別是在進行大數據聚類時，需要聚類成多個簇，需要達到什么樣的效果才能有效解決實際問題，這些都需要結合聚類任務以及其他知識進行綜合考量．所以，在評價聚類算法的性能時，一般需要根據任務需求選擇合適的評估指標．由此可見，解決評估指標之間的矛盾也是一個大挑戰，而如何衡量聚類數目以及其他聚類效果評估指標之間的關系是未來需要加強研究的方向．

6結論

聚類分析作為典型的無監督學習方法，是探索數據規律的一種有效工具，也可作為其他學習分析方法的預處理步驟，具有非常廣泛的應用價值．本文從理解聚類分析的基本框架出發，將聚類過程分成六個步驟，然后分別就聚類分析框架中各個步驟產生的挑戰性問題及解決方法進行了歸納和總結，并提出了未來研究的方向．當然，對于大數據環境下的聚類分析而言，還有一些始終未能解決的或將會出現的挑戰性問題的存在．因此，在未來的研究工作中需要進一步解決已存在的挑戰性問題，并對新出現的問題開展更多有針對性的研究，以期進一步豐富聚類分析的研究內容和拓展聚類分析的研究方向．

作者：蔣盛益王連喜單位：廣東外語外貿大學 思科信息學院圖書館