数据挖掘概念与技术原书第2版第7章聚类分析析课件说课材料

《数据挖掘概念与技术原书第2版第7章聚类分析析课件说课材料》由会员分享，可在线阅读，更多相关《数据挖掘概念与技术原书第2版第7章聚类分析析课件说课材料（38页珍藏版）》请在金锄头文库上搜索。

1、聚类分析,聚类（簇）：数据对象的集合 在同一个聚类（簇）中的对象彼此相似 不同簇中的对象则相异 聚类分析 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程 聚类是一种无指导的学习：没有预定义的类编号 聚类分析的数据挖掘功能 作为一个独立的工具来获得数据分布的情况 作为其他算法（如：特征和分类）的预处理步骤,什么是聚类分析？,模式识别 空间数据分析 在GIS系统中，对相似区域进行聚类，产生主题地图 检测空间聚类，并给出它们在空间数据挖掘中的解释 图像处理 商务应用中，帮市场分析人员发现不同的顾客群 万维网 对WEB上的文档进行分类 对WEB日志的数据进行聚类，以发现相同的用户访问模式

2、,聚类分析的典型应用,一个好的聚类分析方法会产生高质量的聚类 高类内相似度 低类间相似度 作为统计学的一个分支，聚类分析的研究主要是基于距离的聚类；一个高质量的聚类分析结果，将取决于所使用的聚类方法 聚类方法的所使用的相似性度量和方法的实施 方法发现隐藏模式的能力,什么是好的聚类分析？,对于输入数据的顺序不敏感 同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果 高维性 高维的数据往往比较稀松，而且高度倾斜 基于约束的聚类 找到既满足约束条件，又具有良好聚类特性的数据分组 可解释性和可用性 聚类要和特定的语义解释和应用相联系,数据挖掘对聚类分析的要求 (2),许多基于内存的聚类算

3、法采用以下两种数据结构 数据矩阵：用p个变量来表示n个对象 也叫二模矩阵，行与列代表不同实体 相异度矩阵：存储n个对象两两之间的临近度 也叫单模矩阵，行和列代表相同的实体,聚类分析中的数据类型,许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。 相异度d(i,j)的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括： 区间标度变量 二元变量 标称型、序数型和比例标度型变量 混合类型的变量,相异度计算,区间标度度量是一个粗略线性标度的连续度量，比如重量、高度等 选用的度量单位将直接影响聚类分析的结果，因此需要实现度量值的标准化，将原来的值转

4、化为无单位的值，给定一个变量f的度量值，可使用以下方法进行标准化： 计算平均的绝对偏差 其中 计算标准化的度量值(z-score) 使用平均的绝对偏差往往比使用标准差更具有健壮性,区间标度变量,对象间的相似度和相异度(1),对象间的相似度和相异度是基于两个对象间的距离来计算的 Euclidean距离 i=(xi1,xi2,xip)和j=(xj1,xj2,)是两个p维数据对象 Manhattan距离,对象间的相似度和相异度(2),Manhattan距离和Euclidean距离的性质 d(i,j) 0 d(i,i) = 0 d(i,j) = d(j,i) d(i,j) d(i,k) + d(k,j

5、) Minkowski距离 上式中，q为正整数，如果q=1则表示Manhattan距离，如果q=2则表示Euclidean距离,一个二元变量只有两种状态：0或1； e.g. smoker来表示是否吸烟 一个对象可以包含多个二元变量。 二元变量的可能性表： 如何计算两个二元变量之间的相似度？,二元变量 (1),Object i,Object j,对称的 VS. 不对称的 二元变量 对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g. 性别 基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度： 不对称的二元变量中，变量的两个状态的重要性是不同的；e.g. H

6、IV阳性 VS HIV阴性 基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相异度,二元变量 (2),二元变量的相异度示例,P228 例8.1 二元变量之间的相异度 （病人记录表）,Name是对象标识 gender是对称的二元变量 其余属性都是非对称的二元变量 如过Y和P（positive阳性）为1，N为0，则：,标称变量,标称变量是二元变量的推广，它可以具有多于两个的状态值。比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序是不重要的。 计算标称变量所描述的对象（一个对象可以包含多个标称变量）i和j之间的相异度 方法一：简单匹配方法 m: 匹配的数目，

7、即对象i和j取值相同的变量的数目 (也可加上权重) 方法二：对M个标称状态中的每个状态创建一个新的二元变量，并用非对称的二元变量来编码标称变量,红绿蓝黄取值 0100绿 0010蓝 。,序数型变量,一个序数型变量可以是离散的或者是连续的 序数型变量的值之间是有顺序关系的，比如：讲师、副教授、正教授。 假设f是描述n个对象的一组序数型变量之一，f的相异度计算如下： 1. 设第i个对象的f值为xif，则用它在值中的序rif代替 2. 将每个变量的值域映射到0,1的空间 3. 采用区间标度变量的相异度计算方法计算f的相异度,一个比例标度型变量xif是在非线性的标度中所取的正的度量值，例如指数标度，近

8、似的遵循以下公式： AeBt or Ae-Bt 计算比例标度型变量描述的对象之间的相异度 采用与区间标度变量同样的方法标度可能被扭曲，效果往往不好 对比例标度型变量进行对数变化之后进行与区间标度变量的相似处理 yif = log(xif) 将xif看作连续的序数型数据，将其秩作为区间标度的值来对待,比例标度变量,在真实的数据库中，数据对象不是被一种类型的度量所描述，而是被多种类型（即混合类型）的度量所描述，包括： 区间标度度量、对称二元变量，不对称二元变量，标称变量，序数型变量合比例标度变量 计算混合型变量描述的对象之间的相异度 将变量按类型分组，对每种类型的变量进行单独的聚类分析 在每种聚类

9、分析导出相似结果的情况下可行 所有变量一起处理，进行一次聚类分析，可以将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间0,1之内,混合类型的变量,聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的，常用的聚类算法包括： 划分方法 层次的方法 基于密度的方法 基于网格的方法 基于模型的方法 实际应用中的聚类算法，往往是上述聚类方法中多种方法的整合,主要的聚类方法,给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k=n。 每个组至少包含一个对象 每个对象属于且仅属于一个组 划分准则：同一个聚类中的对象尽可能的接

10、近或相关，不同聚类中的对象尽可能的原理或不同 簇的表示 k-平均算法 由簇的平均值来代表整个簇 k中心点算法 由处于簇的中心区域的某个值代表整个簇,划分方法,对给定数据对象集合进行层次分解 自底向上方法（凝聚）：开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件。 自顶向下方法（分裂）：开始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，直到最终每个对象在一个单独的簇中，或达到一个终止条件 缺点：合并或分裂的步骤不能被撤销,层次的方法,基于距离的聚类方法的缺点：只能发现球状的簇，难以发现任意形状的簇。 基于密度的据类

11、：只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类。 优点：可以过滤掉“噪声”和“离群点”，发现任意形状的簇。,基于密度的方法,把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类都在这个网格结构上进行。 优点：处理数度快（因为处理时间独立于数据对象数目，只与量化空间中每一维的单元数目有关）,基于网格的方法,为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。 一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类 这种方法同时也用于自动的决定数据集中聚类的数目 通过统计学的方法，考虑噪声和离群点，从而产生健壮的聚类方法,基于模型的方法,给定n个对象的数

12、据集，以及要生成的簇的数目k，划分算法将对象组织为k个划分（k n）每个划分代表一个簇 通常通过计算对象间距离进行划分 典型的划分方法 k均值 k中心点 以上两种方法的变种,划分的方法,簇的相似度是关于簇中对象的均值度量，可以看作簇的质心（centroid） k均值算法流程 随机选择k个对象，每个对象代表一个簇的初始均值或中心 对剩余的每个对象，根据它与簇均值的距离，将他指派到最相似的簇 计算每个簇的新均值 回到步骤2，循环，直到准则函数收敛 常用准则函数：平方误差准则,基于质心的技术：k均值方法,(p是空间中的点，mi是簇Ci的均值),P263 图7-2,k均值方法-示例,0,1,2,3,4

13、,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2 随机选择2个对象，作为簇的中心,将每个对象指派到最相似的簇,更新每个簇的均值,更新每个簇的均值,重新分派,重新分派,可扩展性较好，算法复杂度为O(nkt)，其中n为对象总数，k是簇的个数，t是迭代次数。 经常终止于局部最优解 缺点 只有当簇均值有定义的情况下，k均值方法才能使用。（某些分类属性的均值可能没有定义） 用户必须首先给定簇数目 不适合发现非凸形状的簇，或者大小差别很大的簇 对噪声和离群点数据敏感,k均值算法的评论,k均值方法有些变种，他们的区别在于 不同的初始k个均值的选择 不同的相异度计算 不同的计算

14、簇均值的策略 聚类分类数据的方法：k众数（mode）方法 用众数来替代簇的均值 采用新的相异性度量处理分类对象 采用基于频率的方法更新簇的众数 可以集成k均值和k众数方法，对具有数值和分类值的数据进行聚类,k均值方法的变种,k均值方法对于离群点敏感 一个具有很大极端值的对象可能显著的扭曲数据的分布 平方误差函数将进一步严重恶化这种影响 k中心点方法：采用簇的中心点，即最靠近中心的对象来代表簇 降低算法对离群点的敏感度,基于代表对象的技术：k中心点方法,k中心点方法仍然基于最小化所有对象与其对应的参照点之间的相异度之和原则，使用的是绝对误差标准 (p是空间中的点，代表簇Cj中一个给定对象；oj是

15、簇Cj中的代表对象) 通常该算法重复迭代，直到每个代表对象都成为它的簇的实际中心点 首先随意选择初始代表对象 只要能够提高结果聚类质量，迭代过程就使用非代表对象替换代表对象 聚类结果的质量用代价函数评估，该函数度量对象与其簇的代表对象之间的平均差异度,k中心点方法步骤,为了确定非代表对象Orandom是否能够替代当前代表对象Oj，对于每一个非代表对象p，考虑四种情况,k中心点方法-代表对象替换 (1),+,Oi,+,Oj,p,+,Orandom,1. 重新分配给Oi,+,Oi,+,Oj,p,+,Orandom,2. 重新分配给Orandom,+,Oi,+,Oj,p,+,Orandom,3. 不

16、发生变化,+,Oi,+,Oj,p,+,Orandom,4. 重新分配给Orandom,重新分配将对代价函数产生影响，如果当前的代表对象被非代表对象所取代，代价函数就是计算绝对误差值的差 变换的总代价是所有非代表对象所产生的代价之和 总代价为负，实际的绝对误差E将减少，Oj可以被Orandom所取代 总代价为正，则本次迭代没有变化,k中心点方法-代表对象替换 (2),当存在噪声和离群点时，k中心点方法比k均值方法更加鲁棒 中心点较少的受离群点影响 k中心点方法的执行代价比k均值方法要高 k均值方法： O(nkt) k中心点方法：O(k(n-k)2) n与k较大时，k中心点方法的执行代价很高 两种方法都要用户指定簇的数目k,k均值方法与k中心点方法比较,什么是离群点？ 一个数据集与其他数据有着显著区别的数据对象的集合 例如：运动员：Michael Jordon, 舒马赫，布勃卡 离群点产生原