搜索
聚类分析主要内容聚类基于分割的聚类层次聚类基于密度的聚类聚类分析(ClusteringAnalysis)发现对象簇(Cluster)，使得同一个簇内的对象尽量相似，不同簇间的对象尽量不同。Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized簇的概念可能会模糊Howmanyclusters?FourClustersTwoClustersSixClusters聚类无监督的学习(Unsupervisedlearning):与分类不同，没有事先定义的类别标记。聚类的用途：•作为单独的数据分析工具•可作为其它方法的预处理手段聚类分析的应用理解(Understanding)•相关文档的组,有相似功能的基因和蛋白质组,或有相似价格波动的股票等。概括(Summarization)•减小数据集的规模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-UPClusteringprecipitationinAustralia用聚类做数据预处理数据概括(Summarization):•服务于回归(regression),主成分分析(PCA),分类(classification),关联分析(associationanalysis)压缩(Compression):•图像处理(Imageprocessing)寻找K-最近邻居(K-nearestNeighbors)•在一个簇或几个簇内进行局部搜索聚类质量的评价高质量的聚类：•高簇内相似性(highintra-classsimilarity)•低簇间相似性(lowinter-classsimilarity)聚类的质量不但依赖于所使用的方法，而且也依赖于实现方式。聚类质量最主要的评价标准还是用户的满意程度。聚类质量的度量相似性度量:•一般通过距离函数来描述:d(i,j)•针对不同数据，如区间值数据、布尔数据、类别数据、顺序数据等，会有不同的距离函数•根据不同应用和数据的语义，变量会被赋予不同的权重。聚类的质量:•通常会有明确的质量函数来度量聚类质量的好坏。•很难定义“足够好”•这类问题的答案往往具有明显的主观色彩。聚类中常用的数据结构数据矩阵差别矩阵距离函数（1）通常距离函数须具备如下性质：•d(i,j)0，非负性•d(i,i)=0•d(i,j)=d(j,i)，对称性•d(i,j)d(i,k)+d(k,j)，三角不等式距离函数（2）假设每条记录有n个属性,两个元组(xi1,…,xin)和(xj1,…,xjn)的相似性可通过如下方式来度量：Minkowski距离：若属性具有不同的权重，此时的距离可定义为：通常使用的是Minkowski距离的特殊形式：数值型属性可使用Minkowski距离及其特殊形式使用距离函数之前，要对属性的值进行规范化，如z-值规范化：使用平均绝对偏差(MeanAbsoluteDeviation,MAD)，而不用标准差的原因：•前者比后者抗噪声能力更强•用前者更容易检测到噪声顺序属性顺序属性(ordinalattribute)可以是连续的，也可以是离散的•可通过离散化把连续属性转换为顺序属性顺序比实际的值更重要转换后可看作是连续属性•将实际的值xiA用其排序(rank)riA来代替,riA{1,…,MA}•将排序映射到[0,1]•再使用Minkowski距离二值属性(BinaryVariables)使用列联表(contingencytable)对称属性(symmetricattribute)的距离:非对称属性(asymmetricattribute)的距离:Jaccard系数：1-d(i,j)dcbacbjid),(cbacbjid),(pdbcasumdcdcbabasum0101ObjectiObjectj二值属性的相异性•性别是对称属性，其余均是非对称属性•设Y和P代表1，N代表0•相异性只由非对称属性计算NameGenderFeverCoughTest-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackd名词性属性(NominalVariables)二值数型的泛化,可取两个以上的值,如red,yellow,blue,green方法1:简单匹配•m:#ofmatches,p:total#ofvariables方法2:转化为二值属性pmpjid),(混合型属性将不同类型的属性转换到[0,1]不同的属性可被赋予不同的权重向量对象(VectorObjects)向量对象:文档中的关键字等.应用广泛:信息检索,生物信息学等.Cosinemeasure(,)XYsXYXY聚类的类型聚类就是要得到一系列的簇主要分为分割聚类和层次聚类分割聚类(PartitionalClustering)•将数据对象分割为不重叠的子集，使得每个数据对象只属于其中的一个子集。层次聚类(Hierarchicalclustering)•将数据对象分割为一系列嵌套的、树状的簇分割聚类OriginalPointsAPartitionalClustering层次聚类p4p1p3p2p4p1p3p2p4p1p2p3p4p1p2p3TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram聚类的类型排它的与非排它的•非排它聚类中，对象可能属于多个簇模糊与非模糊的•模糊聚类中，每个点与每个簇都有一个0到1之间的隶属度•这些隶属度的和必须是1部分与完全的•在某些情况下，可能只对一部分数据进行聚类同构与异构的•可能对不同类型的对象进行聚类聚类的类型良分割聚类(Well-separatedclusters)基于中心的聚类(Center-basedclusters)邻近聚类(Contiguousclusters)基于密度的聚类(Density-basedclusters)基于概念的聚类(Concept-basedclusters)基于目标函数的聚类(ObjectiveFunctionclusters)良分割聚类每个点到簇内其它点的距离都小于到簇外其它点的距离。3well-separatedclusters基于中心的聚类每个点与其所在簇中心的距离都小于与其它簇中心的距离。簇的中心可以是质心(centroid),即簇内所有点的均值；或是medoid,即簇内最有代表性的点。（它到其他所有（当前cluster中的）点的距离之和最小）4center-basedclusters基于密度的聚类簇是密度超过一定阈值的点的集合，簇与簇之间被一些低密度度区域分开。适用于簇不规则(irregular)、或相互纠缠(intertwined),及存在噪声和孤立点(outlier)的情况。7density-basedclusters基于目标函数的聚类（1）用目标函数来定义簇•构建簇，使目标函数最大或最小。•枚举所有可能的把对象点构成簇的方式，并使用目标函数对这些簇进行评价，评价结果最好的作为最终的聚类方式。(NPHard)•可以有全局和局部目标•层次聚类通常是局部目标•分割聚类通常是全局目标基于目标函数的聚类（2）可将聚类问题映射到不同的域，并在这些域内求解问题：•相关矩阵(Proximitymatrix)定义了一个加权图，其中结点是用于聚类的点，加权的边代表结点间的相关性。•聚类等价于将图分割为互连的子图，每个子图代表一个簇。•目标是使簇间的权重和最小，簇内的权重和最大。主要内容聚类基于分割的聚类层次聚类K-平均聚类分割聚类方法每个簇都有一个中心点(centroid)每个点最终都归属于一个与其距离最近的中心点所决定的簇。簇的数目K需要事先给定基本的算法非常简单K-平均聚类的细节初始中心点是随机选择的•每次迭代之后簇往往会发生变化.中心点一般是该簇的均值.“相似性”一般是通过Euclidean距离,cosine相似性等来度量的.在以上这些相似性度量标准下，K-平均聚类一般都会收敛.复杂性O(n*K*I*d)•n=numberofpoints,K=numberofclusters,I=numberofiterations,d=numberofattributes两个不同的K-平均聚类-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xySub-optimalClustering-2-1.5-1-0.500.511.5200.511.522.53xyOptimalClusteringOriginalPointsK-平均聚类演示-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.53xyIteration6K-平均聚类演示-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.53xyItera