文档介绍：19 四月 2018
DMKD Sides By MAO
1
第五章聚类方法 内容提要
聚类方法概述
划分聚类方法
层次聚类方法
密度聚类方法
其它聚类方法
19 四月 2018
DMKD Sides By MAO
2
聚类分析研究概述
聚类分析源于许多研究领域,包括数据挖掘、统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能,聚类分析能作为一个独立的工具来获得数据分布的情况,并且概括出每个簇的特点,或者集中注意力对特定的某些簇做进一步的分析。
数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集,这对聚类分析技术提出了特殊的挑战,要求算法具有可伸缩性、处理不同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用,数据挖掘对聚类分析方法提出了不同要求。
19 四月 2018
DMKD Sides By MAO
3
聚类分析在数据挖掘中的应用分析
聚类在数据挖掘中的典型应用有:
聚类分析可以作为其它算法的预处理步骤:利用聚类进行数据预处理,可以获得数据的基本概况,在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析,以获得进一步的有用信息。
可以作为一个独立的工具来获得数据的分布情况:聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点,可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景。
聚类分析可以完成孤立点挖掘:许多数据挖掘算法试图使孤立点影响最小化,或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中,孤立点可能预示着欺诈行为的存在。
19 四月 2018
DMKD Sides By MAO
4
聚类概念
定义 5-1 聚类分析的输入可以用一组有序对(X, s) 或(X, d)表示,这里X表示一组样本,s和d分别是度量样本间相似度或相异度(距离)的标准。聚类系统的输出是一个分区若C={C1, C2,…, Ck},其中Ci(i=1,2….,K)是X的子集,且满足:
C1 C2,…, Ck=X
C1∩C2= Ø, ij
C中的成员C1, C2,…, Ck叫做类或簇(Cluster),每一个类或簇都是通过一些特征描述的,通常有如下几种表示方式:
通过它们的中心或类中关系远的(边界)点表示空间的一类点。
使用聚类树中的结点图形化地表示一个类。
使用样本属性的逻辑表达式表示类。
用中心表示一个类是最常见的方式,当类是紧密的或各向同性时用这种方法非常好,然而,当类是伸长的或向各向分布异性时,这种方式就不能正确地表示它们了。
19 四月 2018
DMKD Sides By MAO
5
聚类分析的目标
聚类分析的目标就是形成的数据簇,并且满足下面两个条件:
一个簇内的数据尽量相似(high intra-class similarity);
不同簇的数据尽量不相似(low inter-class similarity)。
衡量一个聚类分析算法质量,依靠:
相似度测量机制是否合适。
是否能发现数据背后潜在的、手工难以发现的类知识。
19 四月 2018
DMKD Sides By MAO
6
聚类分析方法的分类
按照聚类的标准,聚类方法可分为如下两种:
统计聚类方法:这种聚类方法主要基于对象之间的几何距离的。
概念聚类方法:概念聚类方法基于对象具有的概念进行聚类。
按照聚类算法所处理的数据类型,聚类方法可分为三种:
数值型数据聚类方法:所分析的数据的属性只限于数值数据。
离散型数据聚类方法:所分析的数据的属性只限于离散型数据。
混合型数据聚类方法:能同时处理数值和离散数据。
按照聚类的尺度,聚类方法可被分为以下三种:
基于距离的聚类算法:用各式各样的距离来衡量数据对象之间的相似度,如k-means、k-medoids、BIRCH、CURE等算法。
基于密度的聚类算法:相对于基于距离的聚类算法,基于密度的聚类方法主要是依据合适的密度函数等。
基于互连性(Linkage-Based)的聚类算法:通常基于图或超图模型。高度连通的数据聚为一类。
按照聚类聚类分析算法的主要思路,可以被归纳为如下几种。
划分法(Partitioning Methods):基于一定标准构建数据的划分。
属于该类的聚类方法有:k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、CLARANS等。
层次法(Hierarchical Methods):对给定数据对象集合进行层次的分解。
密度法(density-based Methods):基于数据对象的相连密度评价。
网格法(Grid-based Meth