数据挖掘原理与算法05

2020年3月17日星期二DMKDSidesByMAO1第五章聚类方法内容提要聚类方法概述划分聚类方法层次聚类方法密度聚类方法其它聚类方法2020年3月17日星期二DMKDSidesByMAO2聚类分析研究概述聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能，聚类分析能作为一个独立的工具来获得数据分布的情况，并且概括出每个簇的特点，或者集中注意力对特定的某些簇做进一步的分析。数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了特殊的挑战，要求算法具有可伸缩性、处理不同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。2020年3月17日星期二DMKDSidesByMAO3聚类分析在数据挖掘中的应用分析聚类在数据挖掘中的典型应用有：聚类分析可以作为其它算法的预处理步骤：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以获得进一步的有用信息。可以作为一个独立的工具来获得数据的分布情况：聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景。聚类分析可以完成孤立点挖掘：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。2020年3月17日星期二DMKDSidesByMAO4聚类概念定义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=Ø,ijC中的成员C1,C2,…,Ck叫做类或簇（Cluster），每一个类或簇都是通过一些特征描述的，通常有如下几种表示方式：通过它们的中心或类中关系远的（边界）点表示空间的一类点。使用聚类树中的结点图形化地表示一个类。使用样本属性的逻辑表达式表示类。用中心表示一个类是最常见的方式，当类是紧密的或各向同性时用这种方法非常好，然而，当类是伸长的或向各向分布异性时，这种方式就不能正确地表示它们了。2020年3月17日星期二DMKDSidesByMAO5聚类分析的目标聚类分析的目标就是形成的数据簇，并且满足下面两个条件：一个簇内的数据尽量相似（highintra-classsimilarity）；不同簇的数据尽量不相似（lowinter-classsimilarity）。衡量一个聚类分析算法质量，依靠：相似度测量机制是否合适。是否能发现数据背后潜在的、手工难以发现的类知识。2020年3月17日星期二DMKDSidesByMAO6聚类分析方法的分类按照聚类的标准，聚类方法可分为如下两种：统计聚类方法：这种聚类方法主要基于对象之间的几何距离的。概念聚类方法：概念聚类方法基于对象具有的概念进行聚类。按照聚类算法所处理的数据类型，聚类方法可分为三种：数值型数据聚类方法：所分析的数据的属性只限于数值数据。离散型数据聚类方法：所分析的数据的属性只限于离散型数据。混合型数据聚类方法：能同时处理数值和离散数据。按照聚类的尺度，聚类方法可被分为以下三种：基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如k-means、k-medoids、BIRCH、CURE等算法。基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。基于互连性(Linkage-Based)的聚类算法：通常基于图或超图模型。高度连通的数据聚为一类。按照聚类聚类分析算法的主要思路，可以被归纳为如下几种。划分法（PartitioningMethods）：基于一定标准构建数据的划分。属于该类的聚类方法有：k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、CLARANS等。层次法（HierarchicalMethods）：对给定数据对象集合进行层次的分解。密度法（density-basedMethods）：基于数据对象的相连密度评价。网格法（Grid-basedMethods）：将数据空间划分成为有限个单元（Cell）的网格结构，基于网格结构进行聚类。模型法（Model-BasedMethods）：给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集。2020年3月17日星期二DMKDSidesByMAO7常见的距离函数按照距离公理，在定义距离测度时需要满足距离公理的四个条件自相似性、最小性、对称性以及三角不等性。常用的距离函数有如下几种：明可夫斯基距离（Minkowski）二次型距离（Quadratic）余弦距离二元特征样本的距离度量2020年3月17日星期二DMKDSidesByMAO8明可夫斯基（Minkowski）距离假定x和y是相应的特征，n是特征的维数。x和y的明可夫斯基距离度量的形式如下：当取不同的值时，上述距离度量公式演化为一些特殊的距离测度:当γ=1时，明可夫斯基距离演变为绝对值距离：当γ=2时，明可夫斯基距离演变为欧氏距离：rniriiyxyxd11),(niiiyxyxd1),(2/112),(niiiyxyxd2020年3月17日星期二DMKDSidesByMAO9二次型距离二次型距离测度的形式如下：其中A是非负定矩阵。当取不同的值时，上述距离度量公式演化为一些特殊的距离测度：当A为单位矩阵时，二次型距离演变为欧氏距离。当A为对角阵时，二次型距离演变为加权欧氏距离：当为协方差矩阵时，二次型距离演变为马氏距离。21)()(),(yxAyxyxdT2112),(niiiiiyxayxd2020年3月17日星期二DMKDSidesByMAO10余弦距离余弦距离的度量形式如下：niiniiniiiyxyxyxd12121),(2020年3月17日星期二DMKDSidesByMAO11二元特征样本的距离度量对于包含一些或全部不连续特征的样本，计算样本间的距离是比较困难的。因为不同类型的特征是不可比的，只用一个标准作为度量标准是不合适的。下面我们介绍几种二元类型数据的距离度量标准。假定x和y分别是n维特征，xi和yi分别表示每维特征，且xi和yi的取值为二元类型数值{0，1}。则x和y的距离定义的常规方法是先求出如下几个参数，然后采用SMC、Jaccard系数或Rao系数。设a，b，c和d是样本x和y中满足xi=yi=1，xi=1且yi=0，xi=0且yi=1和xi=yi=0的二元类型属性的数量，则简单匹配系数（SimpleMatchCoefficient,SMC）Jaccard系数Rao系数dcbabayxSsmc),(cbaayxSjc),(dcbaayxSrc),(2020年3月17日星期二DMKDSidesByMAO12类间距离距离函数都是关于两个样本的距离刻画，然而在聚类应用中，最基本的方法是计算类间的距离。设有两个类Ca和Cb，它们分别有m和h个元素，它们的中心分别为γa和γb。设元素x∈Ca，y∈Cb，这两个元素间的距离通常通过类间距离来刻画，记为D(Ca,Cb)。类间距离的度量主要有：最短距离法：定义两个类中最靠近的两个元素间的距离为类间距离。最长距离法：定义两个类中最远的两个元素间的距离为类间距离。中心法：定义两类的两个中心间的距离为类间距离。类平均法：它计算两个类中任意两个元素间的距离，并且综合他们为类间距离：离差平方和。abCxCybaGyxdmhCCD),(1),(2020年3月17日星期二DMKDSidesByMAO13中心法中心法涉及到类的中心的概念。假如Ci是一个聚类，x是Ci内的一个数据点，那么类中心定义如下：其中ni是第i个聚类中的点数。因此，两个类Ca和Cb的类间距离为：其中γa和γb是类Ca和Cb的中心点，d是某种形式的距离公式。iCxiixnx1),(),(babaCrrdCCD2020年3月17日星期二DMKDSidesByMAO14离差平方和离差平方和用到了类直径的概念：类的直径反映了类中各元素间的差异，可定义为类中各元素至类中心的欧氏距离之和，其量纲为距离的平方：根据上式得到两类Ca和Cb的直径分别为γa和γb，类Ca+b=CaCb的直径为γa+b，则可定义类间距离的平方为：)()(1biTamiiaxxxxrbababaWrrrCCD),(22020年3月17日星期二DMKDSidesByMAO15第五章聚类方法内容提要聚类方法概述划分聚类方法层次聚类方法密度聚类方法其它聚类方法2020年3月17日星期二DMKDSidesByMAO16划分聚类算法的主要思想定义5-2给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇，kn。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：每一个簇至少包含一个对象。每一个对象属于且仅属于一个簇。对于给定的k，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。2020年3月17日星期二DMKDSidesByMAO17聚类设计的评价函数一种直接方法就是观察聚类的类内差异（Withinclustervariation）和类间差异(Betweenclustervariation）。类内差异：衡量聚类的紧凑性，类内差异可以用特定的距离函数来定义，例如，类间差异：衡量不同聚类之间的距离，类间差异定义为聚类中心间的距离，例如，聚类的总体质量可被定义为w(c)和b(c)的一个单调组合，比如w(c)/b(c)。kiCxikiiixxdCwCw121),()()(21),()(ikijjxxdCb2020年3月17日星期二DMKDSidesByMAO18k-means算法k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。算法首先随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。准则函数试图使生成的结果簇尽可能地紧凑和独立。算法5-1k-means算法输入：簇的数目k和包含n个对象的数据库。输出：k个簇，使平方误差准则最小。（1)assigninitialvalueformeans;/*任意选择k个对象作为初始的簇中心；*/(2)REPEAT(3)FORj=1tonDOassigneachxjtotheclosestclusters;(4)FORi=1tokDO/*更新簇平均值*/(5)Compute/*计算准则函数E*/(6)UNTILE不再明显地发生变化。21kiCxiixxEiCxiixCx2020年3月17日星期二DMKDSidesByMAO19k-means例子样本数据序号属性1属性2111221312422543653744854迭代次数平均值平均值产生的新簇新平均值新平均值（簇1）（簇2）（簇1）（簇2）1（1，1）（1，2）{1，2}，{3，4，5，6，7，8}（1.5，1）（3.5，3）2（1.5，1