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

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

聚類分析綜述

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

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

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

數(shù)據(jù)挖掘；無監(jiān)督學習；聚類分析；電子病歷

0 引言

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

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

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

1 聚類分析的定義

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

2 聚類分析的算法

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

2.1 基于劃分的聚類算法

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

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

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

(2)repeat；

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

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

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

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

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

2.2 基于層次的聚類算法

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

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

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

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

2.3 基于密度的聚類算法

基于密度的聚類算法，是用密度取代數(shù)據(jù)的相似性，按照數(shù)據(jù)樣本點的分布密度差異，將樣本點密度足夠大的區(qū)域聯(lián)結(jié)在一起，以期能發(fā)現(xiàn)任意形狀的組[6]。這類算法的優(yōu)點在于能發(fā)現(xiàn)任意形狀的組，還能有效地消除噪聲[3]?；诿芏人惴ǔＳ玫挠邪―BSCAN[22]，OPTICS，DENCLUE 等。

2.4 基于網(wǎng)格的聚類算法

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

3 無監(jiān)督學習在電子病歷挖掘中的應用現(xiàn)狀

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

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

4 總結(jié)

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

[1] 數(shù)據(jù)挖掘.百度百科. http：//baike.baidu.com/.

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

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

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

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

[6] 陳黎飛.高維數(shù)據(jù)的聚類方法研究與應用[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] 賀玲,吳玲達,蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述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] 龔賢靜.基于電子病歷的醫(yī)療缺陷管理方法[J]. 中國衛(wèi)生信息管理雜志,2010,7(3)：22-25.

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

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

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

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

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

[32] 張煥君,楊小寧.基于模糊聚類分析的臨床路徑?jīng)Q策研究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