数据挖掘和27_W18A

1、聚类分析2014.12.23 第十八周数据挖掘和分析什么是聚类分析？ Cluster Analysis 将数据划分成有意义或有用的组（簇） 捕获数据的自然结构（旨在理解） 解决其他问题的起点（旨在实用）根据在数据中发现的描述对象及其关系的信息，将数据分组 目标：组内相似性（同质性、相关性）越大、组间的越小、聚类就越好簇间距离最大化簇内距离最小化聚类分析的应用 旨在理解 将对象划分成组或类（聚类） 指派特定对象到组或类（分类） 簇：潜在的类 旨在实用 个别数据对象到簇的抽象 刻画簇特征的簇原型（代表簇中其他对象的数据对象） 生物学 信息检索 气候 心理学和医学 商业 汇总：降维 压缩：向量量化

2、有效的发现近邻什么是簇？Notion of a Cluster can be AmbiguousHow many clusters?4个簇 2个簇 6个簇以下是否是聚类分析？ 监督分类 Supervised classification 已有类别标号 （聚类有时也称作非监督分类） 简单分组Simple segmentation 按照学生姓名分组 查询结果Results of a query 基于外部条件的查询结果 图的划分Graph partitioning聚类的方式 Clusterings 聚类(clustering) : 整个簇集合 层次的 hierarchical 与 划分的 parti

3、tional 划分的聚类 Partitional Clustering 数据对象被划入不重叠的子集 (簇，clusters) ，使得每个数据对象仅属于一个子集 层次的聚类 Hierarchical clustering 簇有子簇，簇之间存在树形的层次嵌套关系 划分的聚类 Partitional Clustering初始数据点初始数据点A Partitional Clustering层次聚类 Hierarchical Clusteringp4p1p3p2 p4 p1 p3 p2 p4p1p2p3p4p1 p2p3Traditional Hierarchical ClusteringNon-tra

4、ditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram不同的聚类类型 互斥的 Exclusive versus non-exclusive In non-exclusive clusterings, points may belong to multiple clusters. Can represent multiple classes or border points 模糊的 Fuzzy versus non-fuzzy In fuzzy clustering, a point bel

5、ongs to every cluster with some weight between 0 and 1 Weights must sum to 1 Probabilistic clustering has similar characteristics 完全的与部分的 Partial versus complete In some cases, we only want to cluster some of the data Heterogeneous versus homogeneous Cluster of widely different sizes, shapes, and de

6、nsities簇的类型 明显分离的 Well-separated clusters 基于原型（中心）的Center-based clusters 基于临近的 Contiguous clusters 基于密度的 Density-based clusters 共同性质的（概念簇）Property or Conceptual簇的类型: 明显分离的 Well-SeparatedA cluster is a set of points such that any point in a cluster is closer (or more similar) to every other point in

7、the cluster than to any point not in the cluster. 3 well-separated clusters簇的类型: 基于中心（原型）的A cluster is a set of objects such that an object in a cluster is closer (more similar) to the “center” of a cluster, than to the center of any other cluster The center of a cluster is often a 质心 centroid, the

8、average of all the points in the cluster, or a 中心点 medoid, the most “representative” point of a cluster 4 center-based clusters簇的类型: 基于临近的簇中的每个对象到该簇的某个对象的距离比到不同簇的任意点更近A cluster is a set of points such that a point in a cluster is closer (or more similar) to one or more other points in the cluster th

9、an to any point not in the cluster.8 contiguous clusters簇的类型: 基于密度的簇是对象的稠密区域 A cluster is a dense region of points, which is separated by low-density regions, from other regions of high density. 适用于簇形状不规则、或有噪声或离群点时 Used when the clusters are irregular or intertwined, and when noise and outliers are

10、present. 6 density-based clusters簇的类型: 共同性质的（概念簇）Finds clusters that share some common property or represent a particular concept. . 2 Overlapping Circles聚类算法 K均值 K-means and its variants 基于原型和划分的 （凝聚的）层次聚类 Hierarchical clustering 基于密度的聚类（DBSCAN）Density-based clusteringK均值基于划分 每个簇有一个质心 centroid (cen

11、ter point) 每个点被分配给最近的质心需指定簇的数量K 另：K中心点聚类（中心点必须是一个实际数据点）K均值K均值聚类初始质心通常随机设置质心 (通常) 是簇内所有点的均值.最近：欧几里得距离、余弦相似性、相关性、等等.对于某些临近性函数和质心类型，K均值总是快速收敛到某个状态：质心不变/所有点不会改变簇的归属较弱的条件，如“直到只有1%的点发生改变”K均值聚类：1 指派点到最近的质心 “最近”：临近性度量 欧式空间的点：欧几里得距离（L2），曼哈顿距离(L1) 文档：余弦相似性，Jaccard度量K均值聚类：2 质心和目标函数 第4步：“重新计算每个簇的质心” 质心可能随邻近性度量和

12、聚类目标不同而改变 欧几里得空间的数据 误差平方和 Sum of Squared Error (SSE) （散布：scatter） x, Ci, ci, mi, m, K 使得簇的SSE最小的质心是什么？ One easy way to reduce SSE is to increase K, the number of clusters A good clustering with smaller K can have a lower SSE than a poor clustering with higher K21(c , )iKiix CSSEdistxK均值聚类：2 质心和目标函数

13、文档数据 最大化簇中文档与簇的质心的相似性 簇的凝聚度（cohesion） 曼哈顿距离 L1绝对误差和 SAE1cos(x,c )iKiix CTotalCohesionine111( , )|iKLiix CLiSAEdistc xdistcxK均值聚类：3 选择初始质心-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最优聚类最优聚类初始点初始点K均值聚类：初始质心的选择的重要性-2-1.5-1-0.500

14、.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6K均值聚类：初始质心的选择的重要性-2-1.5-1-0.500.

15、511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6K均值聚类：初始质心的选择的重要性-2-1.5-1-0.500.5

16、11.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5K均值聚类：初始质心的选择的重要性-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.51

17、1.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5随机初始化的局限在每个“真正”的簇中选择一个初始点的几率很小特别是当K很大时假设簇的大小相同为 nFor example, if K = 10, then probability = 10!/1010 = 0.00036Sometimes the initi

18、al centroids will readjust themselves in right way, and sometimes they dontConsider an example of pairs of clusters初始质心问题的解决方案 重复运行 帮助有限 对样本进行层次聚类技术，提取K个簇的质心作为初始质心 后处理 Postprocessing 二分K均值 Bisecting K-means 对初始化问题不敏感K均值聚类的附加问题：处理空簇 简单 K均值算法可能产生空簇（没有点被指派到某个簇），需要选择替补质心 解决方法 选择一个距离当前任何质心最远的点 从最大 SSE的簇中选择一个点 If there are several empty clusters, the above can be repeated several times.K均值聚类的附加问题：预处理 离群点 预处理：标准化数据 离群点可能过度影响所发现的簇 导致原型不够有代表性，SSE较高 可以删除 但是，离群点有可能有趣 数据压缩，异常点 识别离群点后聚类 可能需删除很小的簇（常常代表离群点的组）K均值聚类的附加问题：后处理 删除小的簇（可能是离群点的组） 分裂簇（高SSE的） 合并簇（相近且低SSE）K均值聚类的附加问题：增量的更新