1、* 高级人工智能 史忠植 1知识发现（数据挖掘) 第五章 史忠植中国科学院计算技术研究所聚类分析Clustering Analysis * 高级人工智能 史忠植 2内容提要一、概述二、相似性度量三、 划分方法四、 层次聚类方法五、 基于密度的聚类六、 基于网格方法七、 基于模型方法八、 蚁群聚类方法十、粒度计算十一、实例分析与计算机实现概 述l 无监督学习不要求对数据进行事先标定，在数据的分类结构未知时，按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内相似性尽量大。利用无监督学习期望能够发现数据集中自身隐藏的内蕴结构信息。l 无监督学习也称 聚类分析 。 无监督学习源于许多研究领
2、域，受到很多应用需求的推动。例如，l 在复杂网络分析中，人们希望发现具有内在紧密联系的社团l 在图像分析中，人们希望将图像分割成具有类似性质的区域l 在文本处理中，人们希望发现具有相同主题的文本子集l 在有损编码技术中，人们希望找到信息损失最小的编码l 在顾客行为分析中，人们希望发现消费方式类似的顾客群，以便制订有针对性的客户管理方式和提高营销效率。这些情况都可以在适当的条件下归为聚类分析。概 述l “ 物以类聚，人以群分 ” 。l 一般的聚类算法是先选择若干个模式点作为聚类的中心。每一中心代表一个类别，按照某种相似性度量方法（如最小距离方法）将各模式归于各聚类中心所代表的类别，形成初始分类。
3、然后由聚类准则判断初始分类是否合理，如果不合理就修改分类，如此反复 迭代 运算，直到合理为止。与监督学习不同，无监督法是边学习边分类，通过学习找到相同的类别，然后将该类与其它类区分开。聚类分析l 聚类分析 (cluster analysis)是将样品个体或指标变量按其具有的特性进行分类的一种统计分析方法。o 对样品进行聚类，称为样品 (Q型 )聚类分析。其目的是将分类不明确的样品按性质相似程度分成若干组，从而发现同类样品的共性和不同类样品间的差异。o 对指标进行聚类，称为指标（ R型）聚类分析。其目的是将分类不明确的指标按性质相似程度分成若干组，从而在尽量不损失信息的条件下，用一组少量的指标来
4、代替原来的多个指标（主成分分析？因子分析？）典型的数据聚类基本步骤如下：l (1)对数据集进行表示和预处理，包括数据清洗、特征选择或特征抽取；l (2)给定数据之间的相似度或相异度及其定义方法；l (3)根据相似度，对数据进行划分，即聚类；l (4)对聚类结果进行评估。聚类分析相似性度量 如何刻画样品 /（指标）变量间的亲疏关系或相似程度？样品相似性的度量变量相似性的度量相似系数度量相似系数体现对象间的相似程度，反映样本之间相对于某些属性的相似程度。确定相似系数有很多方法，这里列出一些常用的方法，可以根据实际问题选择使用。设 为被分类对象的全体，以 表示每一对象 的特征数据。令 xi, xjO, rij是 xi和 xj之间的相似系数，满足以下条件：l rij=1 xi= xjl xi, xj, rij 0,1l xi, xj, rij= rji相似系数度量 其中， M为正数，满足相似系数度量2、夹角余弦两变量 Xi与 Xj看作 p维空间的两个向量，这两个向量间的夹角余弦可用下式进行计算显然 ， cos ij 1。
