第6章 数据聚类

第六章聚类分析刘辉数据仓库与数据挖掘1/31/2023主要内容6.1聚类的基本概念6.2相似度的计算6.3划分聚类方法6.3.1k-means算法6.3.2PAM算法6.4层次聚类方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚类方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于网格的聚类方法6.6.1STING算法6.6.2CLIQUE算法上机实验：使用KNIME进行聚类分析1/31/20232数据仓库与数据挖掘物以类聚人以群分1/31/20233数据仓库与数据挖掘聚类分析示例1/31/20234数据仓库与数据挖掘6.1聚类的概念聚类的定义聚类分析是将物理的或者抽象的数据集合划分为多个类别的过程，聚类之后的每个类别中任意两个数据样本之间具有较高的相似度(距离较小)，而不同类别的数据样本之间具有较低的相似度(距离较大)。分类与聚类的区别与联系监督学习非监督学习半监督学习1/31/20235数据仓库与数据挖掘6.1聚类的概念样本序号描述属性1描述属性2…x113…x216.5…x31.54…x44.57.5…x548.5…x65.59…x74.58…聚类分析的数据集没有类别属性AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1………描述属性类标识聚类分类1/31/20236数据仓库与数据挖掘6.1聚类的基本概念6.2相似度的计算6.3划分聚类方法6.3.1k-means算法6.3.2PAM算法6.4层次聚类方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚类方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于网格的聚类方法6.6.1STING算法6.6.2CLIQUE算法上机实验：使用KNIME进行聚类分析1/31/20237数据仓库与数据挖掘6.2相似度计算连续型属性的相似度计算方法二元离散型属性的相似度计算方法多值离散型属性的相似度计算方法混合类型属性的相似度计算方法1/31/20238数据仓库与数据挖掘数据矩阵数据样本通常用矩阵来表示单个数据样本可用d-维向量表示相似度矩阵对称的距离度量会得到对称的相似度矩阵数据样本的表示n个样本，d个属性1/31/20239数据仓库与数据挖掘6.2.1连续型属性的相似度(距离)计算欧氏距离（Euclideandistance）曼哈顿距离（Manhattandistance）明考斯基距离（Minkowskidistance）马哈拉诺比斯距离（Mahalanobisdistance）1/31/202310数据仓库与数据挖掘相关系数衡量两个变量之间的相关程度，反映了两个变量之间的变化方向ρ落在[-1，1]之间ρ>0表示正相关，两个变量具有相同的变化方向（类似的表现模式）ρ=0表示不相关ρ<0表示负相关，两个变量具有相反的变化方向（相反的表现模式）1/31/202311数据仓库与数据挖掘cosine距离xyθ优点：计算方便，值在0与1之间1/31/202312数据仓库与数据挖掘KL距离（KL散度）衡量两个概率分布之间的差异度假设p,q是两个概率分布，则KL距离为：如何将两个样本数据转换为两个分布呢？p,q两种将两个向量进行规范化，使得每个分量的值落在(0,1)之间，且分量之和等于1注意：KL距离是非对称的！1/31/202313数据仓库与数据挖掘6.2.2二元属性的相似度计算数据样本的二值离散型属性的取值情况数据样本xi10合计数据样本xj1a11a10a11+a100a01a00a01+a00合计a11+a01a10+a00a11+a10+a01+a001/31/202314数据仓库与数据挖掘二元属性的相似度计算对称的二值离散型属性不对称的二值离散型属性1/31/202315数据仓库与数据挖掘二元属性的相异度示例设Y与P置为1,N的值置为01/31/202316数据仓库与数据挖掘6.2.3多值离散型属性的相似度计算假设d为数据集中的属性个数，u为样本xi和xj取值相同的属性个数样本序号年龄段学历收入X1青年研究生高X2青年本科低X3老年本科以下中X4中年研究生高1/31/202317数据仓库与数据挖掘6.2.4混合型属性的相似度计算对于包含混合类型属性的数据集的相似度通常有两种计算方法：将属性按照类型分组，每个新的数据集中只包含一种类型的属性；之后对每个数据集进行单独的聚类分析把混合类型的属性放在一起处理，进行一次聚类分析，需要将连续型属性离散化。1/31/202318数据仓库与数据挖掘主要内容6.1聚类的基本概念6.2相似度的计算6.3划分聚类方法6.3.1k-means算法6.3.2PAM算法6.4层次聚类方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚类方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于网格的聚类方法6.6.1STING算法6.6.2CLIQUE算法上机实验：使用KNIME进行聚类分析1/31/202319数据仓库与数据挖掘聚类算法的性能评价指标数据挖掘技术对聚类算法的要求：可伸缩性处理不同类型属性的能力发现任意形状聚类的能力减小对先验知识和用户自定义参数的依赖性处理噪声数据的能力可解释性和实用性与分类评价指标对比1/31/202320数据仓库与数据挖掘6.3划分聚类的基本概念划分方法:把具有n个数据样本划分成具有k个簇的集合给定k，找出有k个簇的一个划分使得所选择的划分准则最优全局最优:穷举所有可能的划分启发式方法:k-平均算法和k-中心点算法k-means算法(MacQueen’67):每个簇用簇的中心表示k-medoids算法或围绕中心点的划分PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每一个簇用接近聚类中心的一个数据样本表示1/31/202321数据仓库与数据挖掘6.3.1k-means聚类算法1/31/202322数据仓库与数据挖掘6.3.1k-means算法步骤1/31/202323数据仓库与数据挖掘k-means算法例题假设数据集D含有9个数据对象（用2维空间的点表示）：A1(3,1),A2(3,9),A3(8,6),B1(2,5),B2(2,4),B3(3,6),C1(2,6),C2(2,6),C3(2,2)采用k-均值方法进行聚类，距离函数采用欧几里德距离，取k=3，假设三个簇的初始分别为A1,B1,和C1，求第一次循环结束时的三个簇的质心，要求写出计算过程。1/31/202324数据仓库与数据挖掘K-means算法的优缺点优点

复杂度:O(tkn),其中n是对象的数目,k是簇的数目,t是迭代的次数.通常k,t<<n.通常以局部最优结束.使用遗传算法或模拟退火可以达到全球最优缺点只有在簇的平均值被定义的情况下才能使用，那当涉及有分类属性的数据时该怎么办?需要事先给出k，即簇的数目，这往往是最难的不能处理噪声数据和孤立点不适合发现非凸面形状的簇1/31/202325数据仓库与数据挖掘6.3.2PAM算法PAM(PartitioningAroundMedoids，围绕中心点的划分，1987)，其特点是：选择代表性样本表示类，称之为中心点(Medoids)首先随机选择一个中心点集，如果一个非中心点改善了结果聚类的整体距离，则用一个非中心点代替中心点，不断重复此过程至判别函数不再变化为止。对小数据集很有效，但对大数据集计算代价相当高1/31/202326数据仓库与数据挖掘PAM算法示例jihttihjhitjtihj总的交换花费：1/31/202327数据仓库与数据挖掘PAM算法步骤使用实际样本点表示簇任意选择k个代表样本对每一对没有选择的样本h和选择的样本j计算完全交换花费TCih对每一对i和h如果TCih<0,则i被h所替代接着把每个没选择的样本赋给最相似的代表对象重复步骤2和3直到不发生变化1/31/202328数据仓库与数据挖掘主要内容6.1聚类的基本概念6.2相似度的计算6.3划分聚类方法6.3.1k-means算法6.3.2PAM算法6.4层次聚类方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚类方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于网格的聚类方法6.6.1STING算法6.6.2CLIQUE算法上机实验：使用KNIME进行聚类分析1/31/202329数据仓库与数据挖掘6.4层次聚类使用距离矩阵作为聚类的标准.这种方法不需要簇的数目k作为输入,但需要一个中止条件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)1/31/202330数据仓库与数据挖掘6.4.1AGNES算法AGNES(AgglomerativeNesting)使用单链接方法和相异矩阵合并最小相异的结点以一个非下降的模式进行最终所有的结点属于同一个簇1/31/202331数据仓库与数据挖掘层次聚类－簇合并示例1/31/202332数据仓库与数据挖掘层次聚类相似性度量层次聚类方法最常用的相似性度量有：最小距离最大距离均值距离平均距离1/31/202333数据仓库与数据挖掘层次聚类算法步骤凝聚型层次聚类的操作步骤1/31/202334数据仓库与数据挖掘6.4.2DIANA算法DIANA(DivisiveAnalysis)与AGNES算法的顺序正好相反最终每一个结点形成只包含它本身的簇DIANA用到如下两个定义：簇的直径：在一个簇中的任意两个数据点都有一个欧氏距离，这些距离中的最大值是簇的直径平均相异度（平均距离）1/31/202335数据仓库与数据挖掘DIANA算法步骤输入：包含n个对象的数据库，终止条件簇的数目k输出：k个簇，达到终止条件规定簇数目将所有对象整个当成一个初始簇For(i=1;i!=k;i++)DoBegin在所有簇中挑选出具有最大直径的簇；找出所挑出簇里与其他点平均相异度最大的一个点放入splintergroup，剩余的放入oldparty中。Repeat在oldparty里找出到splintergroup中点的最近距离不大于oldparty中点的最近距离的点，并将该点加入splintergroupUntil没有新的oldparty的点被分配给splintergroup；Splintergroup和oldparty为被选中的簇分裂成的两个簇，与其他簇一起组成新的簇集合END1/31/202336数据仓库与数据挖掘其他层次聚类算法CUREClusteringUsingRepresentatives

ROCK1/31/202337数据仓库与数据挖掘主要内容6.1聚类的基本概念6.2相似度的计算6.3划分聚类方法6.3.1k-means算法6.3.2PAM算法6.4层次聚类方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚类方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于网格的聚类方法6.6.1STING算法6.6.2CLIQUE算法上机实验：使用KNIME进行聚类分析1/31/202338数据仓库与数据挖掘6.5基于密度聚类算法的基础（1）两个参数:Eps:邻域的最大半径MinPts:一个对象的Eps-邻域至少包含的对象数NEps(p): {qbelongstoD|dist(p,q)<=Eps}直接密度可达:一个样本点p是从对象q关于Eps,MinPts直接密度可达的，如果满足以下两个条件：

1)p属于NEps(q)2)核心对象条件：

|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm1/31/202339数据仓库与数据挖掘基于密度聚类算法的基础（2）密度可达（Density-reachable）:一个样本p从对象q关于Eps和MinPts是密度可达的，如果存在一个样本链p1,…,pn,p1=q,pn=p，pi+1是从pi关于Eps,MinPts直接密度可达 密度连通（Density-connected）如果存在一个对象o,使得对象p和q是从o关于Eps和MinPts密度可达的，那么称对象p与q关于Eps与MinPts是密度连通的.pqp1pqo1/31/202340数据仓库与数据挖掘6.5.1DBSCAN算法DBSCAN算法的思想：它定义簇为密度相连的点的最大集合在带有“噪声”的空间数据库中发现任意形状的聚类核心边界异常点Eps=1cmMinPts=51/31/202341数据仓库与数据挖掘DBSCAN算法步骤任意选择一个点p找出从对象p关于Eps和MinPts.密度可达的所有点如果是一个中心点，则一个聚类就形成了如果p是一个边界点，没有从p密度可达的对象，DBSCAN则访问数据库中的其他点继续这个过程，直到所有的点被处理1/31/202342数据仓库与数据挖掘6.5.2OPTICS算法OPTICS:通过对象排序来识别聚类结构产生数据库的一个关于基于密度聚类结构的的一个次序簇次序包含的信息，等同于从一个宽广的参数设置范围内获得基于密度的聚类对包括找出内在的聚类结构的自动和交互式聚类分析方法很有用可以用图形或使用可视化技术表示1/31/202343数据仓库与数据挖掘OPTICS:DBSCAN的扩充核心距离(core－distance)C(o)=2.8cm可达距离(reachability-distant)Dp2MinPts=5e=3cmMax(core-distance(o),d(o,p))r(p1,o)=2.8cm.r(p2,o)=4cmoop1e1/31/202344数据仓库与数据挖掘Reachability-distanceCluster-orderoftheobjectsundefined‘1/31/202345数据仓库与数据挖掘主要内容6.1聚类的基本概念6.2相似度的计算6.3划分聚类方法6.3.1k-means算法6.3.2PAM算法6.4层次聚类方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚类方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于网格的聚类方法6.6.1STING算法6.6.2CLIQUE算法上机实验：使用KNIME进行聚类分析1/31/202346数据仓库与数据挖掘6.6基于网格的聚类使用一个多分辨率的网格数据结构几种代表性的方法STING(aSTatisticalINformationGridapproach)由Wang,Yang和Muntz在1997年提出WaveCluster由Sheikholeslami,Chatterjee,和Zhang提出(VLDB’98)一个采用小波变换方法的多分辨率聚类算法CLIQUE:Agrawal,etal.(SIGMOD’98)1/31/202347数据仓库与数据挖掘6.6.1STING:统计信息网格方法由Wang,Yang和Muntz提出(VLDB’97)将空间区域划分成矩形单元针对不同级别的分辨率，通常存在不同级别的矩形单元1/31/202348数据仓库与数据挖掘STING:统计信息网格方法(2)高层的每个单元被划分成多个低一层的单元每个单元属性的统计信息被预先计算和存储，这对查询处理是有用的高层单元的统计参数很容易从低层单元的计算得到，这些参数包括：Count（计数）,mean（平均值）,s（标准差）,min（最小值）,max（最大值）分布类型－正态分布，一致分布等等使用自顶向下的方法回答空间数据的查询从一个预先选择的层次开始－通常包含少量的单元为当前层的每个单元计算置信区间1/31/202349数据仓库与数据挖掘STING:统计信息网格方法(3)不相关的单元不再考虑当