大数据时代,如何从数据中获取知识是一个非常重要的研究课题,数据挖掘和知识发现是从数据处理到决策支持的关键步骤。基于代表点的聚类是一种有效的无监督学习方式,它可以从不含类别标签的数据中提取知识,目前已经在客户细分、社区发现、异常消费行为检测、设施选址、医疗临床路径抽取等问题中展现出了巨大的应用价值。AP聚类是近年来提出的一种基于代表点的聚类算法,其在绝大多数数据集上都可以得到比传统聚类算法更优的聚类结果,并且在聚类过程中,无需人为设定初始代表点集合,簇的数量等等。AP聚类自提出以来,就受到了人们的青睐,目前已经在商务智能和数据挖掘中扮演了重要的角色。然而,在最近几年,数据科学得到了飞速的发展,新的数据形式层出不穷,新的数据问题不断涌现。例如电子病历数据,具有显著的动态性、多元异构性、大规模性等特征;而对电子病历的数据挖掘也从浅层问题进入深层问题,在建模分析过程中,需要考虑的因素更多,需要利用的信息更全面。标准AP聚类受到了前所未有的挑战:1)标准AP聚类只能处理静态数据,但是动态数据所占的比重却在逐年上升;2)标准AP聚类只能发现球形簇,但是随着数据形式的多样化,数据对象的分布结构正在变得越来越复杂;3)标准AP聚类算法复杂度相对较高,不适用于大规模数据聚类问题,但是在各行各业中,数据的规模正在呈指数增长。针对以上三个问题,本文分别给出了解决方案,并提出了适用于动态数据环境的增量式AP聚类,可以发现复杂形状簇的任意形状簇AP聚类,以及可以用于处理大规模数据聚类问题的快速AP聚类。本文还将以上三种聚类算法用于电子病历数据挖掘,从大量治疗记录中提取典型治疗方案,融合电子病历包含的多源信息实现治疗方案的个性化推荐。论文的主要研究工作如下:1.增量式AP聚类。分析了增量式AP聚类问题中存在的难点,并提出了两种解决方案。在此基础上,提出了两种增量式AP聚类算法:基于K中心的增式AP聚类和基于近邻赋值的增量式AP聚类。不仅从理论上分析了两种增量式AP聚类算法的合理性,还通过在真实数据集合上的计算实验验证了两种增量式AP聚类算法的有效性。2.任意形状簇AP聚类。通过对现有的两大类任意形状簇聚类算法的分析指出了局域相似度在任意形状簇聚类问题中的重要性,并讨论了从特征相似度到类别相似度转化的一般化方法。根据在类别相似度矩阵上的消息传递,提出了任意形状簇AP聚类算法。在人造数据集和真实数据集上的计算实验均表明本文所提方法可以有效发现具有复杂形状的簇。3.快速AP聚类。提出了两阶段式快速AP聚类算法。该算法首先通过选择潜在代表数据对象对因子图进行压缩,然后通过去掉不必要的消息传递对因子图进行稀疏化。最后通过在不完全因子图上的消息传递,实现对所有数据对象的聚类。计算实验表明,本文所提出的快速AP聚类算法可以在保持标准AP聚类优良的聚类性能的同时,大幅度地提高AP聚类算法的效率。4.典型治疗方案发现与推荐。首先根据电子病历中的人口统计学信息和诊断信息对病人进行聚类,以发现特定的病人群落;然后通过对药品联合使用网络划分,发现药品之间的联合使用关系;接着对电子病历中的治疗记录进行聚类,并根据聚类结果提取典型治疗方案;最后通过匹配病人群落和治疗记录的聚类结果,为指定的病人群落找到最佳的治疗方案。本研究具有重要的理论意义和应用价值:1)通过对标准AP聚类的拓展,使其具备有效分析和处理新型数据的能力,为数据科学的发展提供了新的工具;2)对标准AP聚类的改进和提升涉及到许多聚类领域中的经典问题,本文的解决思路对其他聚类算法的改进和设计同样具有启发作用;3)从大量治疗记录中提取得到的典型治疗方案,可以为医生设计和改进治疗方案提供素材;融合电子病历各部分数据的治疗方案个性化推荐,可以为医生的临床决策提供数据支持。