聚类分析中的数据类型.ppt

《聚类分析中的数据类型.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、聚类报告人：熊赟内容提要符号说明及定义相似性度量聚类分析中的数据类型聚类的准则函数聚类分析的过程聚类方法与算法符号说明1.数据样本X，由d个属性值组成：X＝（x1,x2,…,xd），其中xi表示样本中的各属性，d是样本或样本空间的维数（或属性个数）。2.数据样本集记为X｛X1,X2,…,Xn｝，第i个样本记为Xi＝｛xi1,…,xid｝，许多情况下聚类的样本本集看成是一个n×d(n个样本×d个属性)的数据矩阵：符号说明3.簇Ci：数据样本集X分成k个簇，每个簇是相应数据样本的集合，相似样本在同一簇中，相异样本

2、在不同簇中。簇Ci（i=1,2,…,k）中样本的数量ni。簇记为Ci＝｛Xj1i,Xj2i,…,Xjnii｝，Ci（i＝1,…,k）是X的子集，如下所示：C1∪C2∪…∪Ck＝X且Ci∪Cj＝ф，i≠j符号说明用下面的特征来描述簇：①簇的质心（centroid）：（样本的平均值）是簇的“中间值”（middle），但并不需要是簇中实际点。令ni表示簇Ci中样本的数量，mi表示对应样本的均值：centroid＝②簇的半径，是簇中两个点间的均方差的平方根。定义定义（聚类）：给定一数据样本集X｛X1,X2,…,Xn｝

3、，根据数据点间的相似程度将数据集合分成k簇：｛C1,C2,…,Ck｝的过程称为聚类，∪i=1kCi＝X，Ci∪Cj＝ф，i≠j。相似样本在同一簇中，相异样本在不同簇中。关于同一簇中的样本比来自不同簇的样本更为相似的判断问题主要涉及以下两个独立的子问题：a.怎样度量样本之间的相似性；b.怎样衡量对样本集的一种划分的好坏。相似性度量相异度矩阵（dissimilaritymatrix）用来存储n个样本两两之间的相似性，表现形式是一个n×n维的矩阵：d(Xi，Xj)是样本Xi和样本Xj间相异性的量化表示。最明显的相似

4、性度量是样本之间的距离。相似性度量Xi｛xi1,…,xid｝和Xj｛xj1,…,xjd｝是两个具有d个属性的两个样本。距离度量标准d（Xi，Xj）表示第i个样本与第j个样本间的距离。在聚类分析中，最常用的距离定义如下：最著名的距离度量标准是d维空间中的欧几里德距离：d（Xi，Xj）＝（2）1/2相似性度量更广义的d维空间中的度量为明考斯基距离度量Lk（Xi，Xj）＝（k）1/k通常也被称为Lk范数，欧几里德距离即L2范数。而L1范数则常被称为曼哈坦距离或城区距离相似性度量例：对于一个4维向量X1＝｛1,0,1

5、,0｝和X2＝｛2,1,-3,-1｝，这些距离的度量标准L1（X1，X2）＝1+1+4+1＝7，L2（X1，X2）＝（1+1+16+1）1/2＝4.36L3（X1，X2）＝（1+1+64+1）1/3＝4.06。Lk（Xi，Xj）＝（k）1/k聚类算法即是先定义一个合适的度量，然后计算任意两个样本之间的距离。当两个样本之间的欧几里德距离小于某个阈值d0时，这两个样本就属于同一类。距离阈值d0影响簇的数量和大小，d0越小，每个簇就越小，簇的数目就越多。如果d0太大，则所有样本将会被分为同一簇；如果d0太小，每个样

6、本又会单成一类。聚类分析中的数据类型1.区间标度变量（interval-valuedvariables）2.二元变量（BinaryVariables）样本Xj10样本Xi1n1,1n1,00n0,1n0,03.标称型、序数型、比例标度型变量4.混合型变量二元变量的相似度计算简单匹配系数（simplematchingcoefficient，SMC）评价这样的两个样本Xi和样本Xj之间的相异度评价系数是Jaccard系数例：样本Xi和样本Xj具有8个二元类型变量：Xi＝｛0,0,1,1,0,1,0,1｝和Xj＝｛

7、0,1,1,0,0,1,0,0｝则n1.1＝2，n1.0＝2，n0.1＝1，n0.0＝3Ssmc(Xi,Xj)=3/8，Sjc(Xi,Xj)=3/5簇间的距离度量标准用于簇Ci和簇Cj之间的距离度量标准是：1)最小距离：其中Xi∈Ci和Xj∈Cj2)最大距离：其中Xi∈Ci和Xj∈Cj3)中间距离：其中mi和mj是Ci和Cj的质心4)平均距离：其中Xi∈Ci和Xj∈Cj，且ni和nj是类Ci和Cj间的样本数。簇间的距离度量标准聚类的准则函数误差平方和准则（sum-of-squared-errorcriteri

8、on）：其中X∈Ci，mi是Ci的质心Je即所有样本的平方误差和。聚类的分析过程聚类技术概览划分的方法层次的方法基于密度的方法基于网格的方法基于模型的方法划分方法（partitioningmethod）划分方法的基本思想是，给定一个n个样本的数据库，划分方法将数据划分为k个划分（k<=n），每个划分表示一个簇，同时满足：a.每个簇至少包含一个样本；b.每个样本必须属于且仅属于一个簇。基于质心的k－m