数据挖掘导论-第8章-中文

数据挖掘集群分析：基本概念和算法第二章数据挖掘简介数据挖掘导论10/21/20191数据挖掘导论10/21/2019‹#›什么是集群分析？查找对象组，使得组中的对象将彼此相似（或相关），并且与其他组中的对象不同（或不相关）群间距离最大化簇内距离被最小化数据挖掘导论10/21/2019‹#›聚类分析的应用理解–用于浏览的组相关文档，具有类似功能的组基因和蛋白质，或具有相似价格波动的组股票总结–减少大型数据集的大小DiscoveredClustersIndustryGroup1Applied-Matl-DOWN,Bay-Network-Down,3-COM-DOWN,Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN,DSC-Comm-DOWN,INTEL-DOWN,LSI-Logic-DOWN,Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down,Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOWN,Sun-DOWNTechnology1-DOWN2Apple-Comp-DOWN,Autodesk-DOWN,DEC-DOWN,ADV-Micro-Device-DOWN,Andrew-Corp-DOWN,Computer-Assoc-DOWN,Circuit-City-DOWN,Compaq-DOWN,EMC-Corp-DOWN,Gen-Inst-DOWN,Motorola-DOWN,Microsoft-DOWN,Scientific-Atl-DOWNTechnology2-DOWN3Fannie-Mae-DOWN,Fed-Home-Loan-DOWN,MBNA-Corp-DOWN,Morgan-Stanley-DOWNFinancial-DOWN4Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP,Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP,Schlumberger-UPOil-UP在澳大利亚聚集降水数据挖掘导论10/21/2019‹#›什么不是集群分析？监督分类–有类标签信息简单分割–按姓氏按字母顺序将学生分成不同的注册组查询的结果–分组是外部规范的结果图分区–一些相互关联和协同，但领域不相同数据挖掘导论10/21/2019‹#›集群的概念可能是模糊的有多少个集群？四个集群两个集群六个集群数据挖掘导论10/21/2019‹#›集群类型聚类是一组聚类分层和分区集群之间的重要区别部分聚类–将数据对象划分成非重叠子集（聚类），使得每个数据对象恰好在一个子集中分层聚类–组织为分层树的一组嵌套集群数据挖掘导论10/21/2019‹#›分割聚类原始的点分割聚类数据挖掘导论10/21/2019‹#›层次聚类p4p1p3p2p4p1p3p2p4p1p2p3p4p1p2p3传统分层聚类非传统的分层聚类非传统树状图传统树图数据挖掘导论10/21/2019‹#›群集集之间的其他区别独占与非独占–在非排他性聚类中，点可以属于多个聚类–可以表示多个类或“边界”点模糊与非模糊–在模糊聚类中，一个点属于每个聚类，其权重在0和1之间–权重必须为1–概率聚类具有类似的特征部分与完整–在某些情况下，我们只想聚集一些数据非均质对均质–集群的大小，形状和密度大不相同数据挖掘导论10/21/2019‹#›集群类型分离良好的集群基于中心的集群连续簇基于密度的聚类属性或概念由目标函数描述数据挖掘导论10/21/2019‹#›集群类型：分离分离的群集：–集群是一组点，使得集群中的任何点都比集群中的任何点更接近（或更类似于）集群中的每个其他点。3well-separatedclusters数据挖掘导论10/21/2019‹#›集群类型：基于中心基于中心–群集是一组对象，使得群集中的对象比群集的“中心”更接近（更类似于）任何其他群集的中心–聚类的中心通常是质心，聚类中所有点的平均值，或聚类的最“代表性”点4个基于中心的集群数据挖掘导论10/21/2019‹#›集群类型：基于连续性连续簇（最近邻或传递）–聚类是一组点，使得聚类中的点与不在聚类中的任何点更接近（或更类似于）聚类中的一个或多个其它点。8个连续簇数据挖掘导论10/21/2019‹#›集群类型：基于密度基于密度–簇是由低密度区域与其它高密度区域分开的点的密集区域。–当集群不规则或交织，并且存在噪声和异常值时使用。6个基于密度的集群数据挖掘导论10/21/2019‹#›集群类型：概念集群共享财产或概念集群–查找共享一些共同属性或表示特定概念的集群。.2个交叉的集群数据挖掘导论10/21/2019‹#›聚类类型：目标函数由目标函数定义的集群–找到最小化或最大化目标函数的集群。–列举所有可能的方法，将点分成聚类，并通过使用给定的目标函数评估每个潜在的集群的“好”。（NP问题）–可以有全球或地方目标。分层聚类算法通常具有局部目标部分算法通常具有全局目标–全局目标函数方法的变化是将数据拟合到参数化模型。从数据确定模型的参数。混合模型假设数据是多个统计分布的“混合”。数据挖掘导论10/21/2019‹#›集群类型：目标函数…将聚类问题映射到不同的域，并解决该域中的相关问题–接近矩阵定义加权图，其中节点是被聚类的点，加权边表示点之间的近似–聚类等效于将图形分成连接的组件，每个集群一个–想要最小化群集之间的边缘权重并且最大化群集内的边缘权重数据挖掘导论10/21/2019‹#›输入数据的特性很重要接近度或密度测量的类型–这是一个派生的度量，但是聚类的中心稀疏性–说明相似性的类型–增加效率属性类型–说明相似性的类型数据类型–说明相似性的类型–其他特性，例如自相关尺寸噪声和异常值分发类型数据挖掘导论10/21/2019‹#›聚类算法K均值及其变体分层聚类基于密度的聚类数据挖掘导论10/21/2019‹#›K-means聚类分层聚类方法每个聚类与质心（中心点）相关联每个点都分配给具有最接近质心的聚类必须指定群集数K基本算法非常简单数据挖掘导论10/21/2019‹#›K-means聚类-详细信息初始质心通常是随机选择的。–生产的集群从一个运行到另一个运行。质心是（通常）集群中的点的平均值。“亲密度”通过欧几里得距离，余弦相似性，相关性等来度量。K均值将收敛用于上述的共同相似性度量。大多数收敛发生在前几次迭代中。–通常停止条件改变为“直到相对较少的点改变群集”复杂性为O(n*K*I*d)–n=点数,K=聚类数,I=迭代次数,d=属性数数据挖掘导论10/21/2019‹#›两种不同的K均值聚类-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xy次优聚类-2-1.5-1-0.500.511.5200.511.522.53xy最优聚类原始的点数据挖掘导论10/21/2019‹#›选择初始矩心的重要性-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5-2-1.5-1-0.500.511.5200.511.522.53xyIteration6数据挖掘导论10/21/2019‹#›选择初始矩心的重要性-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5-2-1.5-1-0.500.511.5200.511.522.53xyIteration6数据挖掘导论10/21/2019‹#›评估K-means集群最常见的度量是平方误差和（SSE）–对于每个点，误差是到最近群集的距离–为了得到SSE，我们计算这些误差并求和–x是簇Ci中的数据点，mi是簇Ci的代表点可以显示mi对应于集群的中心（平均）–给定两个簇，我们可以选择具有最小误差的那个–减少SSE的一个简单方法是增加K，即簇的数目具有较小K的良好聚类可以具有比具有较高K的较差聚类更低的SSEKiCxiixmdistSSE12),(数据挖掘导论10/21/2019‹#›选择初始质心的重要性...-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5数据挖掘导论10/21/2019‹#›选择初始质心的重要性...-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5数据挖掘导论10/21/2019‹#›ProblemswithSelectingInitialPointsIfthereareK‘real’clustersthenthechanceofselectingonecentroidfromeachclusterissmall.–ChanceisrelativelysmallwhenKislarge–Ifclustersarethesamesize,n,then–Forexample,ifK=10,thenprobability=10!/1010=0.00036–Sometimestheinitialcentroidswillreadjustthemselvesin‘right’way,andsometimestheydon’t–Consideranexampleoffivepairsofclusters数据挖掘导论10/21/2019‹#›10个集群示例05101520-6-4-202468xyIteration105101520-6-4-202468xyIteration205101520-6-4-202468xyIteration305101520-6-4-202468xyIteration4从每对簇的一个簇中的两个初始质心开始数据挖掘导论10/21/2019‹#›10个集群示例05101520-6-4-202468xyIteration105101520-6-4-202468xyIteration205101520-6-4-202468xyIteration305101520-6-