聚類分析綜述

曹凱迪,徐挺玉,劉云,張昕

（南京醫科大學醫學信息學與管理研究所 南京醫科大學第一附屬醫院 江蘇 南京 210029）

聚類分析綜述

曹凱迪,徐挺玉,劉云,張昕*

（南京醫科大學醫學信息學與管理研究所 南京醫科大學第一附屬醫院 江蘇 南京 210029）

無監督學習是一種常用的數據挖掘方法，聚類分析是很重要的一種無監督學習方法，在醫學電子病歷的數據挖掘方面有很多應用。本文沿著數據挖掘-機器學習-無監督學習-聚類分析的路徑，闡釋了幾個概念的關系，圍繞著聚類分析的定義、算法和其在電子病歷挖掘中的應用現狀進行了詳細綜述。

數據挖掘；無監督學習；聚類分析；電子病歷

0 引言

在人類歷史上，計算機的出現使人類的生產工具發生了極大的變革，這是因為計算機的運算速度和數據存儲能力都遠遠超過人類的大腦。現代信息化的社會中，每天產生極大的數據量，這些數據有些是有用的，有些是無用的，如何從海量的數據中提取有用的信息是計算機科學家一直以來探索的難題。數據挖掘就是一種從海量的數據中通過某種算法找到隱藏于其中的信息的技術，它通常與計算機科學有關，通過統計、機器學習、模式識別、在線分析處理、情報檢索等多種方法來達到挖掘信息的目的[1]。

將挖掘出的信息用于計算機推理、學習，使計算機能夠像人類一樣進行學習，就是機器學習的領域。機器學習[2]就是計算機利用已有的數據，得出某種模型，并利用模型來預測未來的一種方法，這種方法很類似于人的思考方法。隨著計算機技術的高速發展，機器學習已經變成人工智能研究的一個重要領域。機器學習有很多種方法，包括有監督學習、無監督學習、半監督學習和強化學習。無監督學習事先沒有任何訓練樣本，需要直接對數據進行建模，計算機自己發現數據中存在的內在關系。看起來無監督學習非常困難，因為這是一個計算機自己摸索的過程，但事實上并不是所有的訓練樣本的輸入都分類正確，因此會出現問題，會導致過適合(over-fitting)，這個時候無監督學習就是適合的算法，也因此無監督學習在數據挖掘中具有相比其他方法更為廣闊的應用前景[3]。

無監督學習主要有兩種方法，關聯規則與聚類分析。聚類分析是無監督學習中的更常用的形式。本文圍繞無監督學習的聚類分析進行綜述，首先介紹聚類分析的定義，之后圍繞聚類分析的算法介紹它的具體步驟和算法以及應用現狀。

1 聚類分析的定義

所謂聚類分析，就是根據待分類模式特征的相似或相異程度將數據樣本進行分組，從而使同一組的數據盡可能相似，不同組的數據盡可能相異[3][4]。它的目的是用于知識發現而不是用于預測。評判聚類結果的標準就是：組內部的數據相似度越大，組與組之間數據的差異度越大，那么聚類效果就越好[5]。聚類分析在計算機科學方面的應用范圍非常多，包括模式識別、數據分析、文本挖掘等[6]。

2 聚類分析的算法

已知的聚類分析算法有很多種[7]，同時各種聚類方法也在被科學家不斷地提出和改進，在實際應用中聚類算法的選擇取決于待評判數據的類型和聚類的目的，不同的算法適合于不同類型的數據。根據近年來出現的各種聚類方法的特點，常用的聚類算法可用被分成四種：基于劃分的聚類算法[8]、基于層次的聚類算法、基于密度的聚類算法、基于網格的聚類算法等[9][10]。

2.1 基于劃分的聚類算法

基于劃分的聚類算法是在機器學習中應用最多的。它的原理是：假設聚類算法所使用的目標函數都是可微的，先對數據樣本進行初步的分組，再將此劃分結果作為初始值進行迭代，在迭代過程中根據樣本點到各組的距離反復調整，重新分組，最終得到一個最優的目標函數。最終的聚類結果出現在目標函數收斂的情況下[3]。

K-means算法是基于劃分的聚類算法中的經典算法之一。它的步驟可概括如下：

(1) 任意選擇k個樣本點作為初始的組中心；

(2)repeat；

(3) 根據組中樣本點的平均值，將每個樣本點(重新)賦予距離最近的組；

(4) 更新樣本點的平均值，即計算每個組中樣本點的平均值；

(5) until不再發生變化[11]。

K-means算法之所以成為經典算法，是它具有的優勢決定的：(1)時間復雜度與數據集大小呈線性關系，(2)它收斂于局部最優解。沒有一種算法是完美的，K-means算法也具有它自身的確定：(1)傳統的K-means使用歐氏距離，僅適用于球形數據，(2)對噪聲和孤立點較為敏感。

除了K-means算法之外，常用的基于劃分的聚類算法還有K-medoid[12]、K-modes和K-prototypes[13]等算法。

2.2 基于層次的聚類算法

基于層次的聚類算法也是一種非常常用的算法，它使用數據的聯接規則，通過層次式的架構方式，不斷地將數據進行聚合或分裂，用來形成一個層次序列的聚類問題的解[14]。在層次聚類中，組間距離的度量方法選擇很重要，廣泛使用的組間距離度量方法包括：最小距離、最大距離、平均值的距離、平均距離。

按照層次分解的兩種順序，自頂向下和自底向上，層次聚類算法可以被分為兩類，一類是凝聚的層次聚類算法另一類是分裂的層次聚類算法[15]。目前，凝聚的層次聚類算法有Karypis等[16]提出的CHAMELEON、Guha等提出的ROCK[17]和CURE[18]等；分裂層次聚類算法有Steinbach等[19]提出的bisecting K-means、Boley等[20]提出的PDDP等。

基于層次的聚類算法是一種很優秀的算法，它的優勢在于用戶不用預先指定聚類分組的數目，而且能夠清晰的表達組與組之間的層次關系。同樣，它也有自身的缺點，包括兩個方面，一個是在層

次聚類過程中，上一層次的組形成后，不能在后續的聚類過程中對其進行調整，即不能回溯[21]：第二點是大多數層次聚類算法的計算復雜度至少為O(N2)（其中N是數據點的數量），這導致層次聚類算法在處理大規模數據時十分低效。

2.3 基于密度的聚類算法

基于密度的聚類算法，是用密度取代數據的相似性，按照數據樣本點的分布密度差異，將樣本點密度足夠大的區域聯結在一起，以期能發現任意形狀的組[6]。這類算法的優點在于能發現任意形狀的組，還能有效地消除噪聲[3]。基于密度算法常用的有包括DBSCAN[22]，OPTICS，DENCLUE 等。

2.4 基于網格的聚類算法

基于網格的聚類算法，它的原理是把量化的網格空間進行聚類法，這個算法一般與數據集的大小沒有關系，計算時間復雜度只取決于網格單元的數量。基于網格的聚類算法的優點在于它可以大幅提高計算效率；而缺點在于它很難檢測到斜側邊界的聚類，只能針對垂直或水平的聚類。常見的基于網格的聚類算法有STING[23]、WaveCluster[24]、CLIQUE[25]等。

3 無監督學習在電子病歷挖掘中的應用現狀

電子病歷是指醫務人員在整個病人的診療過程中，使用專門的醫院信息系統產生的針對每一個患者個體的數字化的診療記錄[26]。通過計算機手段對電子病歷中的信息進行提取和分析，從中得到有助于構建臨床決策支持系統和個性化醫療服務的數據在醫療大數據的時代有重要意義[27]。目前針對電子病歷主流的挖掘方法是基于詞典的方法和基于有監督學習的方法，前者過于依賴詞典后者需要人工標注語料作為訓練數據，而無監督學習克服了上述兩種問題，因此基于無監督學習-聚類分析的電子病歷挖掘得到了廣泛的應用。

自動分詞是分析和挖掘中文電子病歷的關鍵基礎，張立邦等[28]提出了一種基于無監督學習的中文電子病歷分詞方法，在3000份電子病歷上面的實驗結果證明了該方法的有效性。史柏語等[29]運用無監督學習的方法，對甲狀腺腫瘤的手術情況進行了建模，分析得出手術范圍隨病灶淋巴結轉移而擴大，但不受病灶本身大小的影響。丁衛平等[30]提出了一種基于約束關系的改進核聚類算法，用來解決電子病歷中圖像切割的問題，該算法通過引入約束關系 在圖像分割前進行修正，提高圖像分割效果。栗偉等[31]提出了一種自適應的文本聚類方法，用來解決電子病歷中疾病診斷文本同義詞識別和命名標準化問題，該算法能夠自動確定類簇個數，并且提升了聚類的準確性。張煥君等[32]提出了一種模糊聚類分析方法，用來解決醫療信息的復雜性和不確定性，對電子病歷數據進行綜合處理分析。他采用了減法聚類產生初始聚類中心，再進行模糊C均值聚類算法，以實現模糊C均值聚類過程中的聚類中心。

4 總結

當今社會，計算機互聯網技術飛速發展，各行各業中的各種形式的數據海量涌現，這是一個數據大爆炸的時代。所有的數據都有各自的結構特點，在處理使用這些數據的時候人們遇到了很大的挑戰。無監督學習能夠幫助人們在對數據一無所知的情況下，發現數據之間的內在聯系和區別，從而找到其中內在的結構和規律。聚類分析作為無監督學習方法中很重要的一種形式，具有很多經典的算法，它在許多關鍵的領域尤其是在中文電子病歷挖掘中，引起了科學家廣泛的關注和興趣，具有強大的應用。

[1] 數據挖掘.百度百科. http：//baike.baidu.com/.

[2] Mitchell T M．Machine Learning．New York：McGraw-Hill,1997.

[3] 王駿. 無監督學習中聚類和閾值分割新方法研究D. 南京理工大學,2010.

[4] 王敏.分類屬性數據聚類算法研究[D]. 江蘇大學, 2008.

[5] 張靜.數據挖掘中聚類分析綜述[J]. 價值工程, 2014(15)：226-227.

[6] 陳黎飛.高維數據的聚類方法研究與應用[D]. 廈門大學, 2008.

[7] XU Rui, Donald Wunsch 1 1.survey of clustering algorithmJ.IEEE.Transactions on Neural Networks, 2005,16(3)：645-67 8.

[8] YI Hong, SAM K． Learning assignment order of instances for the constrained K-means clustering algorithmJ．IEEE Transactions on Systems, Man, and Cybernetics, Part B：Cybernetics,2009,39 (2)：568-574.

[9] 賀玲,吳玲達,蔡益朝.數據挖掘中的聚類算法綜述J．計算機應用研究，2007，24(1)：10-13．

[10] 孫吉貴,劉杰,趙連宇.聚類算法研究J．軟件學報，2008，19(1)：48-61．

[11] 四類clustering方法比較 - LXS的專欄 - http：//blog.csdn.net.

[12] Kaufman L, Rousseeuw P J．Finding Groups in Data： An Introduction to Cluster Analysis．John Wiley,1990.

[13] Huang Z．Extensions to the K-means algorithm for clustering large data sets with categorical values．Data Mining and Knowledge Discovery,1998,2(3)：283304.

[14] 張雪. 可能性聚類有效性評價研究[D]. 哈爾濱理工大學, 2014.

[15] 馮曉蒲, 張鐵峰. 四種聚類方法之比較[J]. 微型機與應用, 2010, 29(16)：1-3.

[16] Karypis G, Hart E H, Kumar V CHAMELEON：A hierarchical clustering algorithm using dynamic modeling．IEEE Computer,1999,32(8)：68-75.

[17] Guha S, Rastogi R, Shim K．ROCK：A robust clustering algorithm for categorical attributes．Sydney： Proceedings of the15th ICDE．1999,512-521.

[18] Guha S, Rastogi R, shim K．CURE： An efficient clustering algorithm for large databases．In： Procedings of the ACM SIGMOD Conference．1998,73-84.

[19] Steinbach M, Karypis G, Kumar V A comparison of document clustering techniques．In KDD Workshop on Text Mining. 2000.

[20] Boley D L．Principal direction divisive partitioning. Data Mining and Knowledge Discovery,1998,2：325-344.

[21] 趙向梅, 王艷君, 劉林.聚類算法及聚類融合算法研究J. 電子設計工程, 2011, 19(1 5) ：4-5.

[22] Ester M，Kriegel H-P，Sander J，Xu X：A density-based algorithm for discovering clusters in large spatial databases with noise．In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining．AAAI Press，1996：226-231.

[23] Wang W, Yang J，Muntz R R. STING：A statistical information grid approach to spatial data mining. In Proceedings of 23rd International Conference on very Large Data Bases, Morgan Kaufnann, 1997：1 86-195.

[24] Sheikholeslami G,Chaaeljee S,Zhang A：WaveCluster：A multi-resolution clustering approach for very large spatial databases．Proceedings of 24rd International Conference on Very Large Data Bases，Morgan Kaufrnann,1998：428-439.

[25] Agrawal R, Gehrke J,Gunopulos D,Raghavan P. Automatic subspace clustering of high dimensional data for data mining applications.In Proceedings of the 1998 ACM SIGMOD international conference on Management of Data.ACM Press,1998：94-105.

[26] 龔賢靜.基于電子病歷的醫療缺陷管理方法[J]. 中國衛生信息管理雜志,2010,7(3)：22-25.

[27] 張立邦.基于半監督學習的中文電子病歷分詞和名實體挖掘[D]. 哈爾濱工業大學,2014.

[28] 張立邦,關毅,楊錦峰.基于無監督學習的中文電子病歷分詞J. 智能計算機與應用,2014(2)：68-71.

[29] 史柏語,戚譯天,白昕成,等.基于電子病歷的甲狀腺腫瘤數據挖掘J. 電子技術與軟件工程,2013(6)：50-52.

[30] 丁衛平,鄧偉.一種基于約束關系的電子病歷圖像分割核聚類算法J. 計算機應用,2007,27(8)：2066-2068.

[31] 栗偉,許洪濤,趙大哲,等. 一種面向醫學短文本的自適應聚類方法J. 東北大學學報(自然科學版),2015,36(1)：19-23.

[32] 張煥君,楊小寧.基于模糊聚類分析的臨床路徑決策研究J. 控制工程,2013,20(6).

Review of Clustering Analysis

CAO Kai-di, XU Ting-yu, LIU Yun, ZHANG Xin
(Institute of Medical Informatics and Management, Nanjing Medical University, The First Affiliated Hospital of Nanjing Medical University, Nanjing 210029, China)

Unsupervised learning is a method of machine learning commonly used as data mining method. Cluster analysis is an important unsupervised learning method. It has many applications in electronic medical records. In this paper, they explained the concepts of data mining, machine learning and unsupervised learning. The definition and algorithms of clustering analysis, and the application of it in electronic medical record mining are reviewed.

Data mining; Unsupervised learning; Clustering analysis; Electronic medical record