聚类分析基本概念和算法

《聚类分析基本概念和算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、聚类分析：基本概念和算法第8章聚类分析：基本概念和算法什么是聚类分析?聚类分析将数据划分成有意义或有用的组（簇）。聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类

2、方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式；聚类的复杂性Howmanyclusters?FourClustersTwoClustersSixClusters不同的聚类类型划分聚类（PartitionalClustering）层次聚类（HierarchicalClustering）互斥（重叠）聚类（exclusiveclustering）非互斥聚类（non-exclusive）模糊聚类（fuzzyclustering）完全聚类（completeclustering）部分聚类（partialclustering）划分聚类（PartitionalClustering）O

3、riginalPointsAPartitionalClustering划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。层次聚类（HierarchicalClustering）TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram层次聚类是嵌套簇的集族，组织成一棵树。互斥的、重叠的、模糊的互斥的（Exclusive）每个对象都指派到单个簇.重叠的（overlapping）或非互

4、斥的（non-exclusive）聚类用来反映一个对象.同时属于多个组（类）这一事实。例如：在大学里，一个人可能既是学生，又是雇员模糊聚类（Fuzzyclustering）每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。部分的（Partial）部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。完全的（complete）完全聚类将每个对象指派到一个簇。不同的簇类型明显分离的基于原型的基于图的基于密度的概念簇簇类型:明显分离的（Well-Separated）每个点到同簇中任一点的距离比到不同簇中所有点的距

5、离更近。3well-separatedclusters簇类型:基于原型的每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。基于中心的（Center-Based）的簇：每个点到其簇中心的距离比到任何其他簇中心的距离更近。4center-basedclusters簇类型:基于图的如果数据用图表示，其中节点是对象，而边代表对象之间的联系。簇可以定义为连通分支（connectedcomponent）：互相连通但不与组外对象连通的对象组。基于近邻的（Cont

6、iguity-Based）：其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8contiguousclusters簇类型:基于密度的（Density-Based）簇是对象的稠密区域，被低密度的区域环绕。6density-basedclusters簇类型:概念簇（ConceptualClusters）可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。.2OverlappingCirclesK均值聚类基本K均值算法1.选择k个点作为初始的质心2.r

7、epeat3.将每个点指派到最近的质心，形成k个簇4.重新计算每个簇的质心5.until质心不发生变化数据对象之间的相异度EuclideanDistance明可夫斯基距离（MinkowskiDistance）MinkowskiDistancer=1.城市块(曼哈顿,出租车,L1范数)距离.r=2.欧氏距离（L2范数）r.上确界(Lmax或L范数)距离.二元数据的相似性度量两个仅包含二元属性的对象之间的相似性度量也称相似系数两个对象的比较导致四个量f00=x取0并且y取0的属性个数f01