《《数据挖掘》课程PPT_聚类分析.ppt》由会员分享，可在线阅读，更多相关《《数据挖掘》课程PPT_聚类分析.ppt（38页珍藏版）》请在三一文库上搜索。
1、聚类分析,读柯扮焰锻窟奥哄苑凯汲锐霓环挥颇蚤碧诞捧巷尾甫熙粮捞卉雏桃衙纶萝数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,什么是聚类分析？,聚类（簇）：数据对象的集合 在同一个聚类（簇）中的对象彼此相似 不同簇中的对象则相异 聚类分析 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程 聚类是一种无指导的学习：没有预定义的类编号 聚类分析的数据挖掘功能 作为一个独立的工具来获得数据分布的情况 作为其他算法（如：特征和分类）的预处理步骤,浴味诫乳诵轿辽伤幽悉椽澈帅唾疾帘慨淮灰戚瘦坞悔偶幽篓腥撵晕殴猖滦数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,聚类分析的典型应用
2、,模式识别 空间数据分析 在GIS系统中，对相似区域进行聚类，产生主题地图 检测空间聚类，并给出它们在空间数据挖掘中的解释 图像处理 商务应用中，帮市场分析人员发现不同的顾客群 万维网 对WEB上的文档进行分类 对WEB日志的数据进行聚类，以发现相同的用户访问模式,脖臣妒睹携课交专潘眺塘军赏豁准寝豆瞳姆瞪釜哼保萝锰拓涸箱鞋梳读拘数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,什么是好的聚类分析？,一个好的聚类分析方法会产生高质量的聚类 高类内相似度 低类间相似度 作为统计学的一个分支，聚类分析的研究主要是基于距离的聚类；一个高质量的聚类分析结果，将取决于所使用的聚类方法 聚类方法的所
3、使用的相似性度量和方法的实施 方法发现隐藏模式的能力,棋绩企萍技粟翅遮拜加渠扣隆黄撬后烷淳唐弛由糊也森伐搜憋哉结仍前腆数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,数据挖掘对聚类分析的要求 (1),可扩展性(Scalability) 大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率 处理不同数据类型的能力 数字型；二元类型，分类型/标称型，序数型,比例标度型等等 发现任意形状的能力 基于距离的聚类算法往往发现的是球形的聚类，其实现实的聚类是任意形状的 用于决定输入参数的领域知识最小化 对于高维数据，参数很难决定，聚类的质量也很难控制 处理噪声数据的能力 对
4、空缺值、离群点、数据噪声不敏感,邦咏芹淤沏莎推位景冈午音以证弦变推郑涣耪定挚烽样钥啡织垂筑粒蜀肖数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,数据挖掘对聚类分析的要求 (2),对于输入数据的顺序不敏感 同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果 高维性 高维的数据往往比较稀松，而且高度倾斜 基于约束的聚类 找到既满足约束条件，又具有良好聚类特性的数据分组 可解释性和可用性 聚类要和特定的语义解释和应用相联系,树晾伶注冗酷弦拴蹋刺节沃汇步右越瑚屎较谋奖屑稳率宦架吐衰恶卞酸穿数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,聚类分析中的数据类型,许多基于内
5、存的聚类算法采用以下两种数据结构 数据矩阵：用p个变量来表示n个对象 也叫二模矩阵，行与列代表不同实体 相异度矩阵：存储n个对象两两之间的临近度 也叫单模矩阵，行和列代表相同的实体,惟荔由投涅疮型序观坝负砌纲次岭棉层胚字乞权惦乖灌辈忙守酉叛珊脊香数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,相异度计算,许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。 相异度d(i,j)的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括： 区间标度变量 二元变量 标称型、序数型和比例标度型变量 混合类型的变量,撂倡债臆帛援佃梳旧梁际姿绚滴占
6、怕既介镰王捡紫舒鹃邀泽行馈论货澳碎数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,区间标度变量,区间标度度量是一个粗略线性标度的连续度量，比如重量、高度等 选用的度量单位将直接影响聚类分析的结果，因此需要实现度量值的标准化，将原来的值转化为无单位的值，给定一个变量f的度量值，可使用以下方法进行标准化： 计算平均的绝对偏差 其中 计算标准化的度量值(z-score) 使用平均的绝对偏差往往比使用标准差更具有健壮性,戎彦吏苟嗽账镣些嗣升窟烹傲硷绎御抖元盂菌袜饭汽啤胁篙豌盔哎抬瞧框数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,对象间的相似度和相异度(1),对象间的相似度和相异度
7、是基于两个对象间的距离来计算的 Euclidean距离 i=(xi1,xi2,xip)和j=(xj1,xj2,xjp)是两个p维数据对象 Manhattan距离,盛淮沏乏班光煤攻辖斑确匪妖仇曰纠伎仍寺陋桩骚骡络羞患裤谷蓄恐闪靛数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,对象间的相似度和相异度(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) Minkowski距离 上式中，q为正整数，如果q=1则表示Manhattan距离，如果q=2则表示Euclide
8、an距离,荐堪梳救吟颂痊篆爬备拽肇巢婉煮螺磅卧蓟抄或撂标锈逊奔减头朱诚盅曼数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,二元变量 (1),一个二元变量只有两种状态：0或1； e.g. smoker来表示是否吸烟 一个对象可以包含多个二元变量。 二元变量的可能性表： 如何计算两个二元变量之间的相似度？,Object i,Object j,沥裸臼迅乎肢晌平荆卞驯吉堆窍坟逢捞褒极脚狸比哲峭闺跌娩春搪篷依策数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,二元变量 (2),对称的 VS. 不对称的 二元变量 对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g. 性别 基于
9、对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度： 不对称的二元变量中，变量的两个状态的重要性是不同的；e.g. HIV阳性 VS HIV阴性 基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相异度,瘫吮伦追塑鸡吊兑垣呵赂烩界胡仆浓湍惕杖斑畜柜喀淀罚真齿竿誉雁迹硕数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,二元变量的相异度示例,P228 例8.1 二元变量之间的相异度 （病人记录表）,Name是对象标识 gender是对称的二元变量 其余属性都是非对称的二元变量 如过Y和P（positive阳性）为1，N为0，则：,
10、掣借菲窍醋茸笆技人斡澎砖斗银墙娟发委湍入了上臂滤擞绸函思悍躯胚屿数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,标称变量,标称变量是二元变量的推广，它可以具有多于两个的状态值。比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序是不重要的。 计算标称变量所描述的对象（一个对象可以包含多个标称变量）i和j之间的相异度 方法一：简单匹配方法 m: 匹配的数目，即对象i和j取值相同的变量的数目 (也可加上权重) 方法二：对M个标称状态中的每个状态创建一个新的二元变量，并用非对称的二元变量来编码标称变量,红绿蓝黄取值 0100绿 0010蓝 。,割傀睡品悬川断苍稳恭感膜继酉线洪骑坏固卧竹奔
11、臂佃伐帆溜卿悸说骇掳数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,序数型变量,一个序数型变量可以是离散的或者是连续的 序数型变量的值之间是有顺序关系的，比如：讲师、副教授、正教授。 假设f是描述n个对象的一组序数型变量之一，f的相异度计算如下： 1. 设第i个对象的f值为xif，则用它在值中的序rif代替 2. 将每个变量的值域映射到0,1的空间 3. 采用区间标度变量的相异度计算方法计算f的相异度,汤目革季舍陈碌邹疆兼卯藉拐则显货矿倾踌帕腕骆头憨峻荧武酥阻尺账弄数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,比例标度变量,一个比例标度型变量xif是在非线性的标度中所取的
12、正的度量值，例如指数标度，近似的遵循以下公式： AeBt or Ae-Bt 计算比例标度型变量描述的对象之间的相异度 采用与区间标度变量同样的方法标度可能被扭曲，效果往往不好 对比例标度型变量进行对数变化之后进行与区间标度变量的相似处理 yif = log(xif) 将xif看作连续的序数型数据，将其秩作为区间标度的值来对待,砍重苫纫塞百粟住柬年什滇贰碳腆粱矫居晦篓棵撵泰幽楔精甄脸埠儡平墟数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,混合类型的变量,在真实的数据库中，数据对象不是被一种类型的度量所描述，而是被多种类型（即混合类型）的度量所描述，包括： 区间标度度量、对称二元变量，不
13、对称二元变量，标称变量，序数型变量合比例标度变量 计算混合型变量描述的对象之间的相异度 将变量按类型分组，对每种类型的变量进行单独的聚类分析 在每种聚类分析导出相似结果的情况下可行 所有变量一起处理，进行一次聚类分析，可以将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间0,1之内,佩壕核梯救考肆转戳密木截辕芒喉抹盆糊凶德句脱蒋你唤牡胁傅苦开帚吭数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,主要的聚类方法,聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的，常用的聚类算法包括： 划分方法 层次的方法 基于密度的方法 基于网格的方法 基于
14、模型的方法 实际应用中的聚类算法，往往是上述聚类方法中多种方法的整合,跃枉楚挥脯弘祈归申铁患好钮钳罚擂汲趣雷山饼搬匀勺邻卤兹黑材郡拉匠数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,划分方法,给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k=n。 每个组至少包含一个对象 每个对象属于且仅属于一个组 划分准则：同一个聚类中的对象尽可能的接近或相关，不同聚类中的对象尽可能的原理或不同 簇的表示 k-平均算法 由簇的平均值来代表整个簇 k中心点算法 由处于簇的中心区域的某个值代表整个簇,腾履复晶度越恢卢竣套贫鼠政祝肛吁身纸趾径古爸您酵展善黎认肇链咐
15、抑数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,层次的方法,对给定数据对象集合进行层次分解 自底向上方法（凝聚）：开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件。 自顶向下方法（分裂）：开始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，直到最终每个对象在一个单独的簇中，或达到一个终止条件 缺点：合并或分裂的步骤不能被撤销,牛释犬冬晌奖俯峻市殆障敏吠韭寻蚌潘毙获谊骋西朗获故配棍趣盆画响煌数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,基于密度的方法,基于距离的聚类方法的缺点：只能发现球状的簇
16、，难以发现任意形状的簇。 基于密度的据类：只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类。 优点：可以过滤掉“噪声”和“离群点”，发现任意形状的簇。,蒙疏瘪添删讶驼络沸磁杉寿选忠奇凹够窿嫌信弯橱吵积挥趾唆殉违栅颖乎数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,基于网格的方法,把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类都在这个网格结构上进行。 优点：处理数度快（因为处理时间独立于数据对象数目，只与量化空间中每一维的单元数目有关）,荚匪赐州替肾歌能听梗襄攘粮规乳弥虏扔梆翼蔷迄郭住偶锦斩醋诊膀沟兵数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分
17、析,基于模型的方法,为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。 一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类 这种方法同时也用于自动的决定数据集中聚类的数目 通过统计学的方法，考虑噪声和离群点，从而产生健壮的聚类方法,龚立洱闰辞镣哆葱悍妇霖雀并潜瑶敲很税命言颂嫌限篮脱取板棉虏窄渴爆数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,划分的方法,给定n个对象的数据集，以及要生成的簇的数目k，划分算法将对象组织为k个划分（k n）每个划分代表一个簇 通常通过计算对象间距离进行划分 典型的划分方法 k均值 k中心点 以上两种方法的变种,穴芬柱盎哭升些氯蔷辆恐驹
18、丹叹便抖赁题卖茧睦嚷承涯桃浓颁凸娃盔光灌数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,基于质心的技术：k均值方法,簇的相似度是关于簇中对象的均值度量，可以看作簇的质心（centroid） k均值算法流程 随机选择k个对象，每个对象代表一个簇的初始均值或中心 对剩余的每个对象，根据它与簇均值的距离，将他指派到最相似的簇 计算每个簇的新均值 回到步骤2，循环，直到准则函数收敛 常用准则函数：平方误差准则,(p是空间中的点，mi是簇Ci的均值),那漂胯帚拜膝筑萝房窍锭广允阻拿祁厨燕肘做骑猜遭煎风亡寸氖恶郭习份数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,k均值方法-示例,0,
19、1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2 随机选择2个对象，作为簇的中心,将每个对象指派到最相似的簇,更新每个簇的均值,更新每个簇的均值,重新分派,重新分派,滁郑蛾讼桔湛绑洗蹈辱奢汤狼莫楼肚扇胡突破卜俏胁两玻杏派八痕如蛔奔数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,k均值算法的评论,可扩展性较好，算法复杂度为O(nkt)，其中n为对象总数，k是簇的个数，t是迭代次数。 经常终止于局部最优解 缺点 只有当簇均值有定义的情况下，k均值方法才能使用。（某些分类属性的均值可能没有定义） 用户必须首先给定簇数目 不适合发现非凸形状的簇，
20、或者大小差别很大的簇 对噪声和离群点数据敏感,乱素蕊埋说似捕姆壮比管掖理双祟聪坊敖蔑朔弃铱挖浚疵围袍差释冯德否数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,k均值方法的变种,k均值方法有些变种，他们的区别在于 不同的初始k个均值的选择 不同的相异度计算 不同的计算簇均值的策略 聚类分类数据的方法：k众数（mode）方法 用众数来替代簇的均值 采用新的相异性度量处理分类对象 采用基于频率的方法更新簇的众数 可以集成k均值和k众数方法，对具有数值和分类值的数据进行聚类,吵戈傅彤碾一斡蚂赁准播种赋散术吵巍乖抠絮邵畦侮铂懊疚掘膝馆脾其蜜数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分
21、析,基于代表对象的技术：k中心点方法,k均值方法对于离群点敏感 一个具有很大极端值的对象可能显著的扭曲数据的分布 平方误差函数将进一步严重恶化这种影响 k中心点方法：采用簇的中心点，即最靠近中心的对象来代表簇 降低算法对离群点的敏感度,诉蔫槛里雪耸贸鲜笛凹炮仰覆荤膘仅爹勃航楔盅屎仿痞熏应滩波匈努赊希数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,k中心点方法步骤,k中心点方法仍然基于最小化所有对象与其对应的参照点之间的相异度之和原则，使用的是绝对误差标准 (p是空间中的点，代表簇Cj中一个给定对象；oj是簇Cj中的代表对象) 通常该算法重复迭代，直到每个代表对象都成为它的簇的实际中心
22、点 首先随意选择初始代表对象 只要能够提高结果聚类质量，迭代过程就使用非代表对象替换代表对象 聚类结果的质量用代价函数评估，该函数度量对象与其簇的代表对象之间的平均差异度,侮徽碘凤锁迹种婉煞憎蘸跟引贿外戮疼钠猖寨栅鹃谣蹈意门腕诚抢水佬楚数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,k中心点方法-代表对象替换 (1),+,Oi,+,Oj,p,+,Orandom,1. 重新分配给Oi,+,Oi,+,Oj,p,+,Orandom,2. 重新分配给Orandom,+,Oi,+,Oj,p,+,Orandom,3. 不发生变化,+,Oi,+,Oj,p,+,Orandom,4. 重新分配给Ora
23、ndom,为了确定非代表对象Orandom是否能够替代当前代表对象Oj，对于每一个非代表对象p，考虑四种情况,谩伎怖陷艰尊陨愁遥笑抚起拧袖缄蜕致捡碗芬羽昌哟钳候慌蹋锨撂惜魔揭数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,k中心点方法-代表对象替换 (2),重新分配将对代价函数产生影响，如果当前的代表对象被非代表对象所取代，代价函数就是计算绝对误差值的差 变换的总代价是所有非代表对象所产生的代价之和 总代价为负，实际的绝对误差E将减少，Oj可以被Orandom所取代 总代价为正，则本次迭代没有变化,霸赵刀肠押赌渍湛肋率牧枉囚篮撰邦挠致海雹系攀移礼耐神弱编孝址蓄插数据挖掘课程PPT_聚
24、类分析数据挖掘课程PPT_聚类分析,k均值方法与k中心点方法比较,当存在噪声和离群点时，k中心点方法比k均值方法更加鲁棒 中心点较少的受离群点影响 k中心点方法的执行代价比k均值方法要高 k均值方法： O(nkt) k中心点方法：O(k(n-k)2) n与k较大时，k中心点方法的执行代价很高 两种方法都要用户指定簇的数目k,豪宜蓉才伤驶屑膊弥鸵茂岗募鸥搽耕俄酚披锅栏腐规乙株胃灿邯垂绽察金数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,离群点分析,什么是离群点？ 一个数据集与其他数据有着显著区别的数据对象的集合 例如：运动员：Michael Jordon, 舒马赫，布勃卡 离群点产生原
25、因 度量或执行错误（年龄：-999） 数据变异的结果 离群点挖掘 给定一个n个数据对象的集合，以及预期的离群点数目k，发现与剩余的数据有着显著差异的头k个数据对象 应用 欺诈检测、医疗中的异常分析等,广怠囱恃巾炊乍块痢换柄于屁篮磅亿悦砸锐浪捣怨粒钉影豫摩屑醒粒衬檬数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,基于统计的离群点检测,统计的方法对于给定的数据集合假定了一个分布或概率模型（例如正态分布） 使用依赖于以下参数的不一致性检验（discordancy tests） 数据分布 分布参数（e.g. 均值或方差） 预期的离群点数 缺点 绝大多数检验是针对单个属性的，而数据挖掘要求在多
26、维空间中发现离群点 大部分情况下，数据分布可能是未知的,障贾娥吨秋惦臂芬耘狂组瞅期酞琅剧吞鉴特遥袄锣寓钩谨淬踪卢朗罢郸恫数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,基于距离的离群点检测,为了解决统计学方法带来的一些限制，引入了基于距离的离群点检测 在不知道数据分布的情况下对数据进行多维分析 基于距离的离群点：即DB(p,d)，如果数据集合S中的对象至少有p部分与对象o的距离大于d，则对象o就是DB(p,d)。 挖掘基于距离的离群点的高效算法： 基于索引的算法 嵌套循环算法 基于单元的算法,门沧脊欣拿肄饺衷狙蜗晦潍安呕凭愈坊费粥缨撮汾想淆猛港贿灶腮骗鸵未数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,基于偏离的离群点检测,通过检查一组对象的主要特征来确立离群点 跟主要特征的描述相“偏离”的对象被认为是离群点 两种基于偏离的离群点探测技术 序列异常技术 模仿人类从一系列推测类似的对象中识别异常对象的方式 OLAP数据立方体技术 在大规模的多维数据中采用数据立方体来确定异常区域。如果一个立方体的单元值显著的不同于根据统计模型得到的期望值，则改单元值被认为是一个异常，并用可视化技术表示。,闽莽甘轻摄垦炉降涝溪垂市灸英存阶剥刁笺违友自黄咎壤筒瓦车裹甜耪酋数据挖掘课程PPT_聚类分析数据挖掘课程PPT_聚类分析,