第7章聚类分析析

聚类（簇）：数据对象的集合◦在同一个聚类（簇）中的对象彼此相似◦不同簇中的对象则相异聚类分析◦将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程聚类是一种无指导的学习：没有预定义的类编号聚类分析的数据挖掘功能◦作为一个独立的工具来获得数据分布的情况◦作为其他算法（如：特征和分类）的预处理步骤模式识别空间数据分析◦在GIS系统中，对相似区域进行聚类，产生主题地图◦检测空间聚类，并给出它们在空间数据挖掘中的解释◦图像处理商务应用中，帮市场分析人员发现不同的顾客群万维网◦对WEB上的文档进行分类◦对WEB日志的数据进行聚类，以发现相同的用户访问模式一个好的聚类分析方法会产生高质量的聚类◦高类内相似度◦低类间相似度作为统计学的一个分支，聚类分析的研究主要是基于距离的聚类；一个高质量的聚类分析结果，将取决于所使用的聚类方法◦聚类方法的所使用的相似性度量和方法的实施◦方法发现隐藏模式的能力可扩展性(Scalability)◦大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率处理不同数据类型的能力◦数字型；二元类型，分类型/标称型，序数型,比例标度型等等发现任意形状的能力◦基于距离的聚类算法往往发现的是球形的聚类，其实现实的聚类是任意形状的用于决定输入参数的领域知识最小化◦对于高维数据，参数很难决定，聚类的质量也很难控制处理噪声数据的能力◦对空缺值、离群点、数据噪声不敏感对于输入数据的顺序不敏感◦同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果高维性◦高维的数据往往比较稀松，而且高度倾斜基于约束的聚类◦找到既满足约束条件，又具有良好聚类特性的数据分组可解释性和可用性◦聚类要和特定的语义解释和应用相联系许多基于内存的聚类算法采用以下两种数据结构◦数据矩阵：用p个变量来表示n个对象也叫二模矩阵，行与列代表不同实体◦相异度矩阵：存储n个对象两两之间的临近度也叫单模矩阵，行和列代表相同的实体npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x0...)2,()1,(:::)2,3()...ndnd0dd(3,10d(2,1)0许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。相异度d(i,j)的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括：◦区间标度变量◦二元变量◦标称型、序数型和比例标度型变量◦混合类型的变量区间标度度量是一个粗略线性标度的连续度量，比如重量、高度等选用的度量单位将直接影响聚类分析的结果，因此需要实现度量值的标准化，将原来的值转化为无单位的值，给定一个变量f的度量值，可使用以下方法进行标准化：◦计算平均的绝对偏差◦其中◦计算标准化的度量值(z-score)◦使用平均的绝对偏差往往比使用标准差更具有健壮性.)...211nffffxx(xnm|)|...|||(|121fnffffffmxmxmxnsffififsmxz对象间的相似度和相异度是基于两个对象间的距离来计算的◦Euclidean距离i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维数据对象◦Manhattan距离)||...|||(|),(2222211ppjxixjxixjxixjid||...||||),(2211ppjxixjxixjxixjid◦Manhattan距离和Euclidean距离的性质d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)◦Minkowski距离上式中，q为正整数，如果q=1则表示Manhattan距离，如果q=2则表示Euclidean距离qqppqqjxixjxixjxixjid)||...|||(|),(2211一个二元变量只有两种状态：0或1；◦e.g.smoker来表示是否吸烟一个对象可以包含多个二元变量。二元变量的可能性表：◦如何计算两个二元变量之间的相似度？pdbcasumdcdcbabasum0101ObjectiObjectj对称的VS.不对称的二元变量◦对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g.性别◦基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度：◦不对称的二元变量中，变量的两个状态的重要性是不同的；e.g.HIV阳性VSHIV阴性◦基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相异度dcbacbjid),(cbacbjid),(NameGenderFeverCoughTest-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackdP228例8.1二元变量之间的相异度（病人记录表）Name是对象标识gender是对称的二元变量其余属性都是非对称的二元变量如过Y和P（positive阳性）为1，N为0，则：标称变量是二元变量的推广，它可以具有多于两个的状态值。比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序是不重要的。计算标称变量所描述的对象（一个对象可以包含多个标称变量）i和j之间的相异度◦方法一：简单匹配方法m:匹配的数目，即对象i和j取值相同的变量的数目(也可加上权重)◦方法二：对M个标称状态中的每个状态创建一个新的二元变量，并用非对称的二元变量来编码标称变量pmpjid),(红绿蓝黄取值0100绿0010蓝。。。。。。一个序数型变量可以是离散的或者是连续的序数型变量的值之间是有顺序关系的，比如：讲师、副教授、正教授。假设f是描述n个对象的一组序数型变量之一，f的相异度计算如下：◦1.设第i个对象的f值为xif，则用它在值中的序rif代替◦2.将每个变量的值域映射到[0,1]的空间◦3.采用区间标度变量的相异度计算方法计算f的相异度11fififMrz},...,1{fifMr一个比例标度型变量xif是在非线性的标度中所取的正的度量值，例如指数标度，近似的遵循以下公式：AeBtorAe-Bt计算比例标度型变量描述的对象之间的相异度◦采用与区间标度变量同样的方法——标度可能被扭曲，效果往往不好◦对比例标度型变量进行对数变化之后进行与区间标度变量的相似处理yif=log(xif)◦将xif看作连续的序数型数据，将其秩作为区间标度的值来对待在真实的数据库中，数据对象不是被一种类型的度量所描述，而是被多种类型（即混合类型）的度量所描述，包括：◦区间标度度量、对称二元变量，不对称二元变量，标称变量，序数型变量合比例标度变量计算混合型变量描述的对象之间的相异度◦将变量按类型分组，对每种类型的变量进行单独的聚类分析在每种聚类分析导出相似结果的情况下可行◦所有变量一起处理，进行一次聚类分析，可以将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间[0,1]之内聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的，常用的聚类算法包括：◦划分方法◦层次的方法◦基于密度的方法◦基于网格的方法◦基于模型的方法实际应用中的聚类算法，往往是上述聚类方法中多种方法的整合给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k=n。◦每个组至少包含一个对象◦每个对象属于且仅属于一个组划分准则：同一个聚类中的对象尽可能的接近或相关，不同聚类中的对象尽可能的原理或不同簇的表示◦k-平均算法由簇的平均值来代表整个簇◦k中心点算法由处于簇的中心区域的某个值代表整个簇对给定数据对象集合进行层次分解◦自底向上方法（凝聚）：开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件。◦自顶向下方法（分裂）：开始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，直到最终每个对象在一个单独的簇中，或达到一个终止条件◦缺点：合并或分裂的步骤不能被撤销基于距离的聚类方法的缺点：只能发现球状的簇，难以发现任意形状的簇。基于密度的据类：只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类。◦优点：可以过滤掉“噪声”和“离群点”，发现任意形状的簇。把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类都在这个网格结构上进行。◦优点：处理数度快（因为处理时间独立于数据对象数目，只与量化空间中每一维的单元数目有关）为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。◦一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类◦这种方法同时也用于自动的决定数据集中聚类的数目通过统计学的方法，考虑噪声和离群点，从而产生健壮的聚类方法给定n个对象的数据集，以及要生成的簇的数目k，划分算法将对象组织为k个划分（kn）每个划分代表一个簇◦通常通过计算对象间距离进行划分典型的划分方法◦k均值◦k中心点◦以上两种方法的变种簇的相似度是关于簇中对象的均值度量，可以看作簇的质心（centroid）k均值算法流程1.随机选择k个对象，每个对象代表一个簇的初始均值或中心2.对剩余的每个对象，根据它与簇均值的距离，将他指派到最相似的簇3.计算每个簇的新均值4.回到步骤2，循环，直到准则函数收敛常用准则函数：平方误差准则21iCpkimpEi(p是空间中的点，mi是簇Ci的均值)012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2随机选择2个对象，作为簇的中心将每个对象指派到最相似的簇更新每个簇的均值更新每个簇的均值重新分派重新分派…可扩展性较好，算法复杂度为O(nkt)，其中n为对象总数，k是簇的个数，t是迭代次数。经常终止于局部最优解缺点◦只有当簇均值有定义的情况下，k均值方法才能使用。（某些分类属性的均值可能没有定义）◦用户必须首先给定簇数目◦不适合发现非凸形状的簇，或者大小差别很大的簇◦对噪声和离群点数据敏感k均值方法有些变种，他们的区别在于◦不同的初始k个均值的选择◦不同的相异度计算◦不同的计算簇均值的策略聚类分类数据的方法：k众数（mode）方法◦用众数来替代簇的均值◦采用新的相异性度量处理分类对象◦采用基于频率的方法更新簇的众数◦可以集成k均值和k众数方法，对具有数值和分类值的数据进行聚类k均值方法对于离群点敏感◦一个具有很大极端值的对象可能显著的扭曲数据的分布◦平方误差函数将进一步严重恶化这种影响k中心点方法：采用簇的中心点，即最靠近中心的对象来代表簇◦降低算法对离群点的敏感度012345678910012345678910012345678910012345678910k中心点方法仍然基于最小化所有对象与其对应的参照点之间的相异度之和原则，使用的是绝对误差标准(p是空间中的点，代表簇Cj中一个给定对象；oj是簇Cj中的代表对象)通常该算法重复迭代，直到每个代表对象都成为它的簇的实际中心点◦首先随意选择初始代表对象◦只要能够提高结果聚类质量，迭代过程就使用非代表对象替换代表对象聚类结果的质量用代价函数评估，该函数度量对象与其簇的代表对象之间的平均差异度jCpkjopEj1为了确定非代表对