数据挖掘中的聚类分析方法.doc

数据挖掘中的聚类分析方法 随着计算机应用的普及，信息系统产生的数据量日益增大，如何有效地利用巨量的原始数据分析现状和预测未来，己经成为人类面临的一大挑战。由此数据挖掘技术应运而生并得以迅猛发展，这是快速增长的数据量和日益贫乏的信息量之间矛盾运动的必然结果。 数据挖掘（Data Mining)，又称为数据库中的知识发现(简称 KDD)，是从大量数据中提取可信的、新颖的、有效的并能被人们理解的模式的处理过程。数据挖掘是一门新兴的技术，它以数据库技术作为基础，把逻辑学、统计学、机器学习、模糊学、可视化计算等多门学科的成果综合在一起，进行如何从数据库中得到有用信息的研究。数据挖掘技术得到了人们的普遍关注，广泛应用于银行金融、保险、公共设施、政府、教育、远程通讯、软件开发、运输等各个企事业单位及国防科研上。 聚类分析是数据挖掘中的一个重要研究领域。所谓聚类，就是把没有类别标记的样本集按某种准则划分成若干类，使类内样本的相似性尽可能大，而类间样本的相似性尽量小，是一种无监督的学习方法。聚类分析通常是在没有先验知识支持的前提下进行的，它所要解决的就是在这种前提下，实现满足要求的类的聚合。聚类分析的研究主要集中在聚类算法上，产生性能好而且实用的聚类算法是其终极目的。聚类是一个富有挑战性的研究领域，采用基于聚类分析方法的数据挖掘在实践中己取得了较好的效果，在实际操作中往往不是采用单一的手段，而是采用多种手段和方法相结合根据潜在的各项应用，数据挖掘对聚类的典型要求有以下9个方面:(1) 可伸缩性 可伸缩性是指算法不论对于小数据集还是对于大数据集，都应是有效的在很多聚类算法当中，对于数据对象小于200个的小数据集合性很好，而对于包含成千上万个数据对象的大规模数据库进行聚类时，将会导致有不同的偏差结果。此外，可伸缩性算法应该随着数据库大小的变化，其运行时间应该线性变化。 (2)处理不同字段类型的能力 算法不仅要能处理数值型数据，还要有处理其它类型字段的能力，包括分类标称类型(catalog流Viminal)，序数型(ordinal)，二元类型(binary)，或者这些数据类型的混合。 (3)能够发现任意形状的聚类 (4)用于决定输入参数的领域知识最小化 在聚类分析当中，许多聚类算法要求用户输入一定的参数，如希望簇的数目聚类结果对于输入参数很敏感，通常参数较难确定，尤其是对于含有高维对象的数据集更是如此。要求用人工输入参数不但加重了用户的负担，也使得聚类质量难以控制。 (5)处理高维数据的能力 既可处理属性较少的数据，又能处理属性较多的数据很多聚类算法擅长处理低维数据，一般只涉及两到三维，通常最多再加二维的情况下能够很好地判断聚类的质量聚类数据对象在高维空间是非常具有挑战性的，尤其是考虑到这样的数据可能高度偏斜并且非常稀疏。例如，考虑包含不同地区的温度测量的数据集如果温度在一个相当长的时间周期内重复地测量，则维度的增长正比于测量的次数为低维数据开发的传统的数据分析技术通常不能很好地处理这样的高维数据。 (6)能够处理噪声数据 现实世界中的数据库常常包含了孤立点空缺未知数据或有错误的数据一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果所以我们希望算法可以在聚类过程中检测代表噪声和离群的点，然后删除它们或者消除它们的负面影响。 (7)结果对于输入记录顺序不敏感 一些聚类算法对于输入数据的顺序是敏感的对于同一个数据集合犷以不同的顺序提交给同一个算法时，可能产生差别很大的聚类结果，这是我们不希望的研究和开发对数据输入顺序不敏感的算法具有重要的意义。 (8)基于约束的聚类 在实际应用当中可能需要在各种约束条件下进行聚类找到既要满足特定的约束，又要具有良好聚类特性的数据分组是一项具有挑战性的任务我们希望聚类算法可以在考虑这些限制的情况下，仍具有较好的表现。 (9)可解释性和可用性 聚类的结果最终都是要面向用户的，用户期望聚类得到的信息是可理解和可应用的，但是在实际挖掘中有时往往不能令人满意。这就要求聚类算法必须与一定的语义环境语义解释相关联。领域知识对聚类分析算法设计的影响是一个很重要的研究方面。聚类分析方法分类 1、基于划分的方法 根据对象在划分之间移动的衡量参数和簇的表示方法不同，基于划分的方法主要包括有k一平均值算法，k一中心点算法。 k一means算法的相似度计算根据一个簇中对象的平均值即簇的质心来进行，它的处理过程如下首先，随机地选择k个对象作为初始的k个簇的质心;然后对剩余的每个对象，根据其与各个质心的距离，将它赋给最近的簇;再后重新计算每个簇的质心这个过程不断重复，直到准则函数收敛通常采用的准则函数为平方误差和准则函数这里的SSE是数据库中所有对象的平方误差总和，p为数据对象，m，是簇C的平均值这个准则函数使生成的结果尽可能的紧凑和独立。 k一means算法对于孤立点敏感，一个极大值的对象可能在相当大的程度上扭曲数据的分布选用类中位置最中心的对象，即中心点能够很好的处理异常点k中心点算法的基本策略是:首先为每个类随意选择一个代表对象;剩余对象根据其与表对象的距离分配给最近的一个类然后反复地用非代表对象来替代代表对象，以改进聚类的质量聚类结果的质量用一个代价函数来估算，该函数度量对象与其参照对象之间的平均相异度。 2、基于层次的方法 层次的方法按数据分层建立簇，形成一棵以簇为节点的树根据层次如何形成，层次的方法可以分为凝聚的和分裂的凝聚的方法，也称自底向上的方法，该方法从数据点作为个体簇开始，每一步合并两个最接近的簇，直到所有的簇合并为一个分裂的方法，也称为自顶向下的方法，它与凝聚的方法正好相反，该方法从包含所有点的一个簇开始，每一步分裂一个簇，最终每个对象在单独的一个簇中，或者达到一个终止条件，比如达到某个希望的簇数目，或者两个最近的簇之间的距离超过了某个闭值在这种情况下，我们需要确定每一步分裂哪一个簇，以及如何分裂。 3、基于网格的方法 基于网格的聚类方法 采用多分辨率的网格数据结构，把对象空间量化为有限数目的单元，形成一个网格结构，所有操作都在这个网格结构上进行这种方法的主要优点是处理速度快，处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关代表性的是STING算法。 STING(Information Grid )是基于网格方法的一个非常典型的例子该算法基于网格的多分辨率聚类技术，它将要聚类的空间区域划分为矩形单元针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构:高层的每个单元被划分为多个低一层的单元关于每个网格单元属性的统计信息(例如平均值最大值最小值)被预先计算和存储，以便于进行查询处理该算法的主要优点是它的网格结构有利于并行处理和增量更新而且效率非常的高，主要不足是由于它采用了一个多分辨率的方法来进行聚类分析，它的聚类的质量取决于网格结构最低层的粒度，如果粒度比较细，处理的代价会显著的增加，但如果最低层的粒度太粗将会降低聚类分析的质量;而且STING在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，所以其聚类边界只能是水平的或竖直的，没有对角的边界因此尽管该技术有快速的处理速度，但可能降低簇的质量和精确性描述对每个簇，它确定覆盖相连的密集单元的最大区域，然后确定最小的覆盖。 4、基于密度的方法基于密度的方法很多算法中都使用距离来描述数据对象之间的相似性，前面提到的两种聚类方法就是基于这种相似性进行聚类，这样的聚类方法对于大部分的球形簇聚类效果较好，但往往对任意形状的簇聚类结果较差，甚至无法进行有效聚类，因此提出了基于密度的聚类方法2这类方法将簇看作是数据空间被低密度区域分割开的高密度区域该类算法除了可以发现任意形状的类，还能够有效