基于聚类分析的图像分割研究毕业论文

基于聚类分析的图像分割研究毕业论文内容摘要：

变划分内容。 一个好的划分衡量标准通常就是同一个组中的对象彼此相近或相 关，而不同组中的对象较远或差距较大。 主要的划分方法有： Kmeans 聚类法和 Kmedoid 聚类法。 Kmeans 聚类法在处理海量数据库方面较有效，特别是对数 南京邮电大学通达学院 2020 届本科生毕业设计 (论文 ) 8 值属性处理，它对异常数据很敏感。 PAM（围绕中心对象进行划分）方法是最初 提出的 Kmedoid 聚类 算法之一。 Kmedoid 聚类算法比 Kmeans 聚类算法在 处理异常数据和噪声数据方面更为鲁棒，但是前者的处理时间要比后者更大。 2．层次方法 层次方法就是通过分解所给定的数据对象集来创建一个层次。 根据层次分解 形成的方式，可以将层次方法分为自下而上（也称凝聚方式）和自上而下（也称 分割方式）两种类型。 自下而上的层次方法从每个对象均为一个单独的组开始 , 逐步将这些组进行合并，直到组合并到了层次顶端或满足终止条件为止。 自上而 下层次方法从所有对象均属于一个组开始，每一次循环将其分解为更小的组，直 到每个 对象构成一组或满足终止条件为止。 BIRCH 和 CURE 算法就是层次方法的实例。 3．基于密度方法 基于密度的聚类方法就是不断增长所获得的聚类直到邻近密度小于一定阈 值为止。 这种方法可以用于消除数据中的噪声（异常数据）。 DBSCAN 就是一个 典型的基于密度的方法，该方法根据密度阈值不断增长聚类。 4．基于网格方法 基于网格方法将对象空间划分为有限数目的单元以形成网格结构。 所有聚 类操作均是在这一网格结构上进行的。 这种方法主要优点就是处理事件由于与数 据对象个数无关而仅与划分对象空间的网格数相关，从而显得 相对较快。 STING 就是一个典型的基于网格的方法。 5．基于模型方法 基于模型的方法就是为每个聚类假设一个模型，再去发现符合相应模型的 数据对象。 一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函 数来确定具体聚类。 它根据标准统计方法并考虑到“噪声”或异常数据，可以自 动确定聚类个数，因此它可以产生很鲁棒的聚类方法。 如神经网络方法。 聚类分析中的数据类型 数据挖掘的一个重要步骤是数据准备，这包括对选定的数据进行规范化、 整合和预处理等等，这是进行数据挖掘的前提，也同样是聚类算法能 正常实施的 必要前提。 要对数据对象进行聚类，基于统计方法，其最重要的前提是要计算各 个数据对象之间的距离 — 即相异度，针对不同的数据类型有不同的相异度计算方 法。 许多基于内存的聚类算法常使用以下两种有代表性的数据结构：数据矩阵和 相异度矩阵。 数据矩阵与相异度矩阵 设聚类问题中有 n 个对象 :ix (i=1,2,...,n)，对每个对象选择了 P 个变量， 南京邮电大学通达学院 2020 届本科生毕业设计 (论文 ) 9 用间隔尺度测定后，第 i 个对象的第 j 个变量的观测值用ijx表示，则这 n 个对象所有P 个变量的观测值可以看成是如下的 n p 矩阵 : 11 11pnpnxxxx （ ） 矩 阵 ()常被称为数据矩阵，它是对象－变量结构的数据表达方式，其中 第 i个对象的 P个变量的观测值可以记为向量 : ix =  1, 2,...i i ipx x x T () 聚类中常用的另外一种数据结构是相异度矩阵，它存储的是 n 个对象两两之间的 近似性，表现形式为一个 n n 矩阵 : () 其中 d(i,j) , 是对象 i 与对象 1 之间相异性的量化表示，通常它是一个非负的数值，当对象 i 和对象 j 越相似和越“接近”， d(i,j) , 的值就越接近。 反之，如果两个对象越不同或相距“越远”， d(i,j) , 的值就越大。 显然 d(i,j) ,＝ d(i,j) ，且 d(i,j) , =0，因此可以得到形如 ()的矩阵。 相异度矩阵是对象－ 对象结构的一种数据表达方式。 聚类分析的典型要求 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。 数据挖掘对聚类的典型要求如下。 1) 可伸缩性 许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类又可能会导致偏南京邮电大学通达学院 2020 届本科生毕业设计 (论文 ) 10 差的结果。 我们需要具有高度可伸缩性的算法。 2）处理不同类型属性的能力 许多算法被设计用来聚类数值类型的数据。 但是，应用可能要求聚类其他类型的数据，如二元类型（ binary），分 类 /标称类型（ categorical/nominal），序数型（ ordinal）数据，或者这些数据类型的混合。 3）发现任意形状的聚类 许多聚类算法基于欧几里的距离或者曼哈坦距离度量来决定聚类。 基于这样的距离度量的算法趋向于发现具有相近尺度合密度的球状簇。 但是，一个簇可能是任意形状的。 提出能发现任意形状簇的算法是很重要的。 4）处理噪声数据的能力 绝大多数现实世界中的数据库都包含了孤立点，空缺，未知数据或者错误的数据。 一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。 5）对于输入记录的顺序不敏感 一些聚类算法对于输入数据的顺序是敏感的。 例如，同一个数据集合，当以 不同的顺序提交同一个算法时，可能生成差别很大的聚类结果。 开发对数据输入 顺序布敏感的算法具有重要的意义。 6）高维性（ high dimensionality） 一个数据库或者数据仓库可能包含若干维或者属性。 许多聚类三算法擅长处 理低维数据，可能只涉及两到三维。 人类最多在三维的情况下能够很好地判断聚 类的质量。 在高维空间中聚类数据对象时非常有挑战性的，特别是考虑到这样的 数据可能非常稀疏，而且高度偏斜。 聚类分析的一般步骤 在实际应用聚类分析中，根据有无领域知识参与可将整个过程分解为三个环 节，每个环节都有其明确的任务，这样对于整个聚类分析的过程就会有更清晰的 认识，如图 所示。 南京邮电大学通达学院 2020 届本科生毕业设计 (论文 ) 11 图 聚类的一般步骤 第一步是特征抽取。 它的输入是原始样本，由领域专家决定使用哪些特征来深刻地刻画样本的本 质性质和结构。 它的结果输出是一个矩阵，矩阵的每一行是一个样本，每一列是 一个特征指标变量。 选取特征的优劣将直接影响以后的分析和决策。 如果第一步 就选择了和聚类意图根本无关的特征变量，那企图得到良好的聚类结果则无异于 缘 木求鱼。 合理的特征选取方案应当使得同类样本在特征空间中相距较近，异类 样本则相距较远。 在有些应用场合还需要将得到的样本矩阵进行一些后处理工 作。 比如为了统一量纲就对变量进行标准化处理，这样采用不同量纲的变量才具 有可比性；有些场合可能选择的特征变量太多，不利于以后的分析和决策，这时 可以先进行降维处理；仅凭经验和领域知识选择的特征变量有可能是相关的，进 行主成分分析就可以消除变量间的相关性，从而得到一些相互独立的特征变量。 第二步是执行聚类算法，获得聚类谱系图。 它的输入是一个样本矩阵，它把一个样 本想象成特征变量空间中的一个点。 聚类 算法的目的就是获得能够反映 X 维空间中这些样本点之间的最本质的“簇成一 团”性质。 这一步没有领域专家的参与，它除了几何知识外不考虑任何的领域知 识，不考虑特征变量在其领域中的特定含义，仅仅认为它是特征空间中一维而己。 南京邮电大学通达学院 2020 届本科生毕业设计 (论文 ) 12 聚类算法的输出一般是一个聚类谱系图，由粗到细地反映了所有的分类情况；或 者直接给出具体的分类方案，包括总共分成几类，每类具体包含那些样本点等等。 第三步是选取合适的分类阈值。 在得到了聚类谱系图之后，领域专家凭借经验和领域知识，根据具体的应用场合， 决定阈值的选取。 选定阈值之后，就能够从聚类谱系图上直接看出分类方案。 领 域专家还可以对聚类结果结合领域知识进行进一步的分析，从而加深样本点和特 征变量的认识。 总之，实际应用聚类分析是一个需要多方参与的过程，它无法脱离开领域专 家的参与，聚类算法仅仅是整个聚类流程中的一环而己，光依靠聚类算法一般不 会得到令人满意的效果。 常见的聚类算法 Kmeans 算法 Kmeans 聚类算法是给定类的个数 K，利用距离最近的原则，将 N 个对象 分到 K 个类中去，聚类的结果由 K 个聚类中心来表达，基于给定的聚类目标函数（或称聚类效果判别函数），算法采用迭代更新的方法，每一次迭代过程都是向目标函数值减少的方向进行；在每一轮中，依据 k 个参照点将其周围的点分别组成 k 个簇，而每个簇的几何中心将被作为下一轮迭代的参照点，迭代使得选取的参照点越来越接近真实的簇几何中心，使得类内对象之间的相似性最大，类之间的相似性最小。 聚类效果的好坏用目标函数 J表示 :11( , )ik ij j iijnj d x c  ， () 其中 ( , )ij j id x c是jx与 ic 之间的距离函数，如欧氏距离。 目标函数 J 其实就是每个数据点与所在 簇的质心的距离之和，所以， J 值越小，簇就越紧凑，相对越独立。 因此，算法 通过不断优化 J 的取值来寻求好的聚类方案，当 J 取极小值时，对应的聚类方案 即是最优方案。 根据聚类结果的表达方式可以将聚类算法划分为：硬 Kmeans （ HCM）算法、模糊 Kmeans（ FCM）算法和概率 Kmeans 算法（ PCM）。 Kmeans 算法描述如 下： 南京邮电大学通达学院 2020 届本科生毕业设计 (论文 ) 13 步骤 1) 随机选取 k 个对象作为初始的簇的质心。 步骤 2) 计算对象与各个族的质心的距离，将对象划分到距离其最近的簇。 步骤 3) 重新计算每个新簇的均值，即质心。 步骤 4) 若簇的质心不再变化，则返回划分结果，否则转步骤 2） . kmeans 算法尝试找出使平方误差函数值最小的 k 个划分。 当结果簇是密集 的，而簇与簇之间区别明显时，它的效果较好。 面对大规模数据集，该算法是相对可扩展的，并且具有较高的效率。 算法的复杂度为 O(nkt),其中， n 为数据集中对象的数目， k 为期望得到的簇的数目， t 为 迭代的次数。 通常情况下，算法可以终止于局部最优解。 但是， k－ means 算法只有在簇的平均值被定义的情况下才能使用。 这可能不适用于某些应用，例如涉及有分类属性的数据。 其次，这种算法要求事先给出要生成的簇的数目 k，显然，这在某些应用中是不实际的。 另外， kmeans 算法不适用于发现非凸面形状的簇，或者大小差别很大的簇。 还有，它对于噪音和孤立点数据是敏感的。 k－ means 算法有很多变种，例如， k模算法用模代替簇的平均值，用新的相异性度量方法来处理分类对象，用基于频率的方法来修改聚类的模。 而 k－平均算法和 k－ 模算法相结合，用来处理有数值类型和分类类型属性的数据，就产生了 k原型算法。 2 .2. 2 D BSCAN 算法 DBSCAN 算法可以将足够高密度的区域划分为簇 , 并可以在带有 “噪声” 的空间数据库中发现任意形状的聚类。 DBSCAN 通过检查数据库中每个点的 E 2邻域来寻找聚类。 如果一个点 P 的 E 2 邻域包含多于 M inP ts 个点 , 则创建一个以 P 作为核心对象的新簇。 然后反复地寻找从这些核心对象直接密度可达的对象 , 当没有新的点可以被添加到任何簇时 , 该过程结束。 如果 采用空间索引 , DBSCAN 的计算复杂度是 O(n log n )。 STING 算法 STING（ Statistical Information Grid)算法是一种基于网格的多分辨率聚 类方法，它将空间区域划分为若干矩形网格单元。 针对不同级别的分辨率，通常 存在多个级别的矩形单元，这些单元形成了一个层次结构，高层的每个单元被划 分为多个低一层的单元。 关于每个网格单元属性的统计信息，如平均值、最大值、 最小值等，被预先计算和存储。 高层单元的统计参数可以很容易地从低层单元的计算得到。 这 些统计参数包括 :属性无关的参数 count；属性相关的参数 m(平均值 )， s(标准方差 )，min(最小值 )， max(最大值 )，以及该单元中属性值遵循的分布 (distribution)类型，例南京邮电大学通达学院 2020 届本科生毕业设计 (论文 ) 14 如正态分布、平均分布、指数分布或无 (如果分布未知 )。 当数据被装载进数据库时，底层单元的参数 count、 m、 s, min 和 max 直接进行计算。 如果分布的类型事先知道，distribution 的值可以由用户指定，也可以通过假设检验来获得。 统计参数的使用可以按。