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