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

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

聚類分析綜述

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

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

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

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

0 引言

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

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

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

1 聚類分析的定義

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

2 聚類分析的算法

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

2.1 基于劃分的聚類算法

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

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

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

(2)repeat；

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

(4) 更新樣本點(diǎn)的平均值，即計(jì)算每個(gè)組中樣本點(diǎn)的平均值；

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

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

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

2.2 基于層次的聚類算法

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

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

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

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

2.3 基于密度的聚類算法

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

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

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

3 無監(jiān)督學(xué)習(xí)在電子病歷挖掘中的應(yīng)用現(xiàn)狀

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

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

4 總結(jié)

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

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

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

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

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

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

[6] 陳黎飛.高維數(shù)據(jù)的聚類方法研究與應(yīng)用[D]. 廈門大學(xué), 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] 賀玲,吳玲達(dá),蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述J．計(jì)算機(jī)應(yīng)用研究，2007，24(1)：10-13．

[10] 孫吉貴,劉杰,趙連宇.聚類算法研究J．軟件學(xué)報(bào)，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] 張雪. 可能性聚類有效性評(píng)價(jià)研究[D]. 哈爾濱理工大學(xué), 2014.

[15] 馮曉蒲, 張鐵峰. 四種聚類方法之比較[J]. 微型機(jī)與應(yīng)用, 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. 電子設(shè)計(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)督學(xué)習(xí)的中文電子病歷分詞和名實(shí)體挖掘[D]. 哈爾濱工業(yè)大學(xué),2014.

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

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

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

[31] 栗偉,許洪濤,趙大哲,等. 一種面向醫(yī)學(xué)短文本的自適應(yīng)聚類方法J. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版),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