聚类分析综述

曹凯迪,徐挺玉,刘云,张昕

（南京医科大学医学信息学与管理研究所 南京医科大学第一附属医院 江苏 南京 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