1、机器学习基础聚类基础（）2020/12/3集群第8-1课集群基础定义和动机（）定义和动机（）数据预处理和相似度计算聚类目标聚类评价2020/12/3集群第8-2课集群基础定义和动机定义和动机寻找一组对象，使得一组中的对象彼此相似（或相关），而与其他组中的对象不同（或无关）2020/12/3集群第8-3课集群基础定义和动机一个独立的工具:探索数据分发其它算法的预处理步骤模式识别，空间数据分析，图像处理，市场研究，万维网，群集文档群集web日志数据以发现相似访问模式的组聚类共表达基因市场营销:帮助营销人员在他们的客户群中发现截然不同的群体，然后利用这些知识来制定有针对性的营销方案气候:了解地球气候
2、，发现大气和海洋的模式2020/12/3集群第8-4课集群基础定义和动机一个独立的工具:探索数据分发其它算法的预处理步骤模式识别，空间数据分析，图像处理，市场研究，万维网，两个重要方面两个重要方面输入数据的属性定义点之间的相似或相异聚类要求确定目标和方法2020/12/3集群第8-5课集群基础定义和动机数据预处理与相似性计算（）数据预处理与相似性计算（）聚类目标聚类评价2020/12/3集群第8-6课数据预处理和相似度计算数据:数据对象及其属性的集合属性是一个对象的属性或特征例如:一个人的眼睛颜色，温度等属性也称为维度，变量，字段，特性或特征属性的集合描述一个对象对象也称为记录，点，事例，样本
3、，实体或实例2020/12/3集群第8-7课数据预处理和相似度计算数据矩阵（）数据矩阵（）表示n个具有p个变量的对象2020/12/3集群第8-8课数据预处理和相似度计算相似与相异相似与相异相似性相似性两个数据对象相似程度的数值度量当物体更相似时，会更高通常落在0，1范围内相异相异两个数据对象差异的数值度量物体更相似时更低最小相异度通常为0上限各不相同2020/12/3集群第8-9课数据预处理与相似度计算Distance Matrix（距离矩阵）（距离矩阵）Represents pairwise distance in n objects An n by n matrix d(i,j):dis
4、tance or dissimilarity between objects i and j Nonnegative Close to 0:similar 2023-11-4ClusteringLesson 8-10Data Preprocessing and Similarity Computation Data Matrix-Distance Matrix 2023-11-4ClusteringLesson 8-11Data Preprocessing and Similarity Computation Types of Attributes（属性的类型）（属性的类型）Discrete（
5、离散）（离散）Has only a finite or countably infinite set of values Examples:zip codes,counts,or the set of words in a collection of documents Note:binary attributes are a special case of discrete attributes Ordinal（定序）（定序）Has only a finite or countably infinite set of values Order of values is important E
6、xamples:rankings(e.g.,pain level 1-10),grades(A,B,C,D)Continuous（连续）（连续）Has real numbers as attribute values Examples:temperature,height,or weight Continuous attributes are typically represented as floating-point variables 2023-11-4ClusteringLesson 8-12Data Preprocessing and Similarity Computation S
7、imilarity/Dissimilarity for Simple Attributes 2023-11-4ClusteringLesson 8-13Data Preprocessing and Similarity Computation Similarity/Dissimilarity for Simple Attributes Minkowski DistanceContinuous AttributeMinkowski distance:a generalization If q=2,d is Euclidean distance 欧几里德距离If q=1,d is Manhatta
8、n distance 曼哈顿距离2023-11-4ClusteringLesson 8-14Data Preprocessing and Similarity Computation Similarity/Dissimilarity for Simple Attributes Minkowski DistanceContinuous AttributeStandardizationCalculate the mean absolute deviation Calculate the standardized measurement(z-score)2023-11-4ClusteringLess
9、on 8-15Data Preprocessing and Similarity Computation Similarity/Dissimilarity for Simple AttributesMinkowski DistanceContinuous AttributeStandardizationMahalanobis Distance 马氏距离马氏距离具有相同分布的两个随机向量具有相同分布的两个随机向量x和和y与协方差矩阵与协方差矩阵S的相异测度。的相异测度。A dissimilarity measure between two random vectors x and y of th
10、e same distribution with the covariance matrix S.2023-11-4ClusteringLesson 8-16Data Preprocessing and Similarity Computation Similarity/Dissimilarity for Simple AttributesMinkowski DistanceContinuous AttributeStandardizationMahalanobis Distance Common Properties of a Distance Distances,such as the E
11、uclidean distance,have some well known properties 1.d(p,q)=0 for all p and q and d(p,q)=0 only if p=q.(Positive definiteness)2.d(p,q)=d(q,p)for all p and q.(Symmetry)3.d(p,r)Conduct preprocessing and select the appropriate dissimilarity or similarity measure 进行预处理，选择合适的相似性或相似性度量=Determine the object
12、ive of clustering and choose the appropriate method 确定聚类目标，选择合适的聚类方法2023-11-4ClusteringLesson 8-20Clustering BasicsDefinition and Motivation Data Preprocessing and Similarity Computation Objective of Clustering（聚类目标）（聚类目标）Clustering Evaluation 2023-11-4ClusteringLesson 8-21Objective of Clustering Co
13、nsiderations for Cluster AnalysisPartitioning criteria Single level vs.hierarchical partitioning(often,multi-level hierarchical partitioning is desirable)Separation of clusters Exclusive(e.g.,one customer belongs to only one region)vs.overlapping(e.g.,one document may belong to more than one topic)H
14、ard versus fuzzy In fuzzy clustering,a point belongs to every cluster with some weight between 0 and 1 Weights must sum to 1 Probabilistic clustering has similar characteristics 2023-11-4ClusteringLesson 8-22Objective of Clustering Considerations for Cluster AnalysisRequirements of ClusteringScalabi
15、lity Ability to deal with different types of attributes Minimal requirements for domain knowledge to determine input parameters Able to deal with noise and outliers Discovery of clusters with arbitrary shape Insensitive to order of input records High dimensionality Incorporation of user-specified co
16、nstraints Interpretability and usability 2023-11-4ClusteringLesson 8-23Objective of Clustering Considerations for Cluster AnalysisRequirements of ClusteringNotion of a Cluster can be Ambiguous 2023-11-4ClusteringLesson 8-24Objective of Clustering Considerations for Cluster AnalysisRequirements of Cl
17、usteringNotion of a Cluster can be AmbiguousTypes of Clusters基于中心簇是一组对象，这样簇中的一个对象比任何其他簇的中心更接近（更相似）簇的“中心”星团的中心通常是一个质心，即星团中所有点的平均值，或者是一个星团中最具代表性的点2023-11-4ClusteringLesson 8-25Objective of Clustering Considerations for Cluster AnalysisRequirements of ClusteringNotion of a Cluster can be AmbiguousTypes
18、 of ClustersCenter-based Density-based 基于密度基于密度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 present.2023-11-4ClusteringLesson 8-26Clustering Basic
19、sDefinition and Motivation Data Preprocessing and Similarity Computation Objective of Clustering Clustering Evaluation（聚类评价）（聚类评价）2023-11-4ClusteringLesson 8-27Clustering Evaluation Cluster validation Quality:“goodness”of clusters Assess the quality and reliability of clustering results Why validati
20、on?To avoid finding clusters formed by chance To compare clustering algorithms To choose clustering parameters e.g.,the number of clusters 2023-11-4ClusteringLesson 8-28Clustering Evaluation Aspects of Cluster Validation Comparing the clustering results to ground truth(externally known results)Exter
21、nal Index（外部指标）Evaluating the quality of clusters without reference to external information Use only the data Internal Index（内部指标）Determining the reliability of clusters To what confidence level,the clusters are not formed by chance Statistical framework 2023-11-4ClusteringLesson 8-29Clustering Eval
22、uation Comparing to Ground Truth（与真值比较）（与真值比较）Notation N:number of objects in the data set P=P1,Ps:the set of“ground truth”clusters C=C1,Ct:the set of clusters reported by a clustering algorithm The“incidence matrix”(关联矩阵关联矩阵)N by N(both rows and columns correspond to objects)Pij=1 if Oi and Oj belo
23、ng to the same“ground truth”cluster in P;Pij=0 otherwise Cij=1 if Oi and Oj belong to the same cluster in C;Cij=0 otherwise 2023-11-4ClusteringLesson 8-30Clustering Evaluation Comparing to Ground Truth Notation The“incidence matrix”(关联矩阵)Rand Index and Jaccard Coefficient A pair of data object(Oi,Oj
24、)falls into one of the following categories SS:Cij=1 and Pij=1;(agree)DD:Cij=0 and Pij=0;(agree)SD:Cij=1 and Pij=0;(disagree)DS:Cij=0 and Pij=1;(disagree)2023-11-4ClusteringLesson 8-31Clustering Evaluation Comparing to Ground Truth Notation The“incidence matrix”(关联矩阵)Rand Index and Jaccard Coefficie
25、nt Entropy and Purity the number of objects in both the k-th cluster of the clustering solution and j-th cluster of the groundtruth the number of objects in the k-th cluster of the clustering solution the number of objects in the j-th cluster of the groundtruth 2023-11-4ClusteringLesson 8-32Clusteri
26、ng Evaluation Comparing to Ground Truth Internal Index（内部（内部指标）指标）Use only the data to measure cluster quality Measure the“cohesion”and“separation”of clusters Calculate the correlation between clustering results and distance matrix 2023-11-4ClusteringLesson 8-33Clustering Evaluation Comparing to Gro
27、und Truth Internal Index Cohesion and Separation Cohesion is measured by the within cluster sum of squares Separation is measured by the between cluster sum of squares 2023-11-4ClusteringLesson 8-34Clustering Evaluation Comparing to Ground Truth Internal Index Cohesion and Separation Cohesion is mea
28、sured by the within cluster sum of squares Separation is measured by the between cluster sum of squares BSS+WSS=constant WSS(Cohesion)measure is called Sum of Squared Error(SSE)a commonly used measure A larger number of clusters tend to result in smaller SSE 2023-11-4ClusteringLesson 8-35Clustering
29、Evaluation Comparing to Ground Truth Internal Index Cohesion and Separation Silhouette Coefficient(轮廓系数)Silhouette Coefficient combines ideas of both cohesion and separation.For an individual point,i Calculate a=average distance of i to the points in its cluster Calculate b=min(average distance of i
30、 to points in another cluster)The silhouette coefficient for a point is then given by s=1 a/b if a b,not the usual case)Typically between 0 and 1 The closer to 1 the better Can calculate the Average Silhouette width for a cluster or a clustering 2023-11-4ClusteringLesson 8-36Clustering Evaluation Co
31、mparing to Ground Truth Internal Index（内部（内部指标）指标）Cohesion and Separation Silhouette Coefficient(轮廓系数)Correlation with Distance Matrix Distance Matrix Dij is the similarity between object Oi and Oj Incidence Matrix Cij=1 if Oi and Oj belong to the same cluster,Cij=0 otherwise Compute the correlation
32、 between the two matrices Only n(n-1)/2 entries needs to be calculated High correlation indicates good clustering 2023-11-4ClusteringLesson 8-37Clustering Evaluation Comparing to Ground Truth Internal Index Cohesion and Separation Silhouette Coefficient(轮廓系数)Correlation with Distance Matrix Given Di
33、stance Matrix D=d11,d12,dnn and Incidence Matrix C=c11,c12,cnn .Correlation r between D and C is given by 2023-11-4ClusteringLesson 8-38Clustering Evaluation Comparing to Ground Truth Internal Index Cohesion and Separation Silhouette Coefficient(轮廓系数)Correlation with Distance Matrix Using Similarity
34、 Matrix for Cluster Validation Order the similarity matrix with respect to cluster labels and inspect visually.2023-11-4ClusteringLesson 8-39Clustering Evaluation Comparing to Ground Truth Internal Index Reliability of ClustersNeed a framework to interpret any measure For example,if our measure of e
35、valuation has the value,10,is that good,fair,or poor?Statistics provide a framework for cluster validity The more“atypical”a clustering result is,the more likely it represents valid structure in the data 2023-11-4ClusteringLesson 8-40Clustering Evaluation Comparing to Ground Truth Internal Index Rel
36、iability of ClustersStatistical Framework for SSEExample Compare SSE of 0.005 against three clusters in random data SSE Histogram of 500 sets of random data points of size 100 lowest SSE is 0.0173 2023-11-4ClusteringLesson 8-41Clustering Evaluation Comparing to Ground Truth Internal Index Reliabilit
37、y of ClustersStatistical Framework for SSEDetermine the Number of Clusters Using SSE2023-11-4ClusteringLesson 8-42sklearn.metrics.pairwiseThe sklearn.metrics.pairwise submodule implements utilities to evaluate pairwise distances or affinity of sets of samples.This module contains both distance metri
38、cs and kernels.2023-11-4ClusteringLesson 8-43metricFunctioncityblockmetrics.pairwise.manhattan_distancescosinemetrics.pairwise.cosine_distanceseuclideanmetrics.pairwise.euclidean_distanceshaversinemetrics.pairwise.haversine_distancesl1metrics.pairwise.manhattan_distancesl2metrics.pairwise.euclidean_
39、distancesmanhattanmetrics.pairwise.manhattan_distancesnan_euclideanmetrics.pairwise.nan_euclidean_distancessklearn.metrics.clusterThe sklearn.metrics.cluster submodule contains evaluation metrics for cluster analysis results.There are two forms of evaluation:supervised,which uses a ground truth clas
40、s values for each sample.unsupervised,which does not and measures the quality of the model itself.2023-11-4ClusteringLesson 8-44adjusted_mutual_info_scoreAdjusted Mutual Information between two clusterings.adjusted_rand_scoreRand index adjusted for chance.fowlkes_mallows_scoreMeasure the similarity
41、of two clusterings of a set of points.homogeneity_completeness_v_measureCompute the homogeneity and completeness and V-Measure scores at once.mutual_info_scoreMutual Information between two clusterings.metrics.normalized_mutual_info_scoreNormalized Mutual Information between two clusterings.silhouette_scoreCompute the mean Silhouette Coefficient of all samples.Summary2023-11-4ClusteringLesson 8-45
