聚类数据挖掘技术.docxVIP

2.1聚类数据挖掘近些年，随着Web技术的大规模普及及应用，社会的发展越来越依赖于信息，日常生活产生了海量的数据，但人们却难以从这些海量数据中获取有用信息，人们越来越陷入数据丰富而知识贫乏的陷阱。数据挖掘（Data Mining）于20世纪80年代为解决这个问题应运而生。数据挖掘又称知识发现（Knowledge Discovery in Database），其目的就是为了从海量的数据集中提取人们感兴趣的、事先未知的、或潜在有用的信息或模式。聚类挖掘技术是数据挖掘算法中非常重要的研究内容，旨在将样本数据按其自身的属性聚成若干类，以保证类内样本相似度尽可能高，而类间样本相似度尽可能低。随着数据分析技术近些年的蓬勃发展，进而成为许多计算应用的基础，数据分析技术可分为两种：一种是探索性数据分析，一种是验证性数据分析。而聚类就是探索性数据分析最常用的技术，同验证性数据分析中的分类技术有着本质的区别：分类是通过参考已知类别的训练数据，通过学习对未知的数据进行分类的过程，因此是一种监督的学习机制；而聚类技术刚好相反，聚类是一种无监督的学习机制，主要是把没有类别标记的数据分成有意义的组。一般说来，聚类分析包括以下几个阶段：预处理阶段：即决定用什么样的特征来表示聚类数据。该阶段还包括特征选择和特征抽取。特征选择是指在所有的数据属性集合中选择一组合适的属性来表示数据集，而特征抽取则是由现有的数据属性产生新的数据属性。相似度定义阶段：确定不同类别数据之间的相似度标准，一般通过预定义一个距离函数来量化类间的相似程度。聚类阶段：通过各种聚类算法得到不同的聚类结果。结果评估阶段：对聚类的输出结果进行评估。2.2聚类数据挖掘方法分类一般聚类算法可以分为通用聚类算法和特殊聚类算法，通用聚类算法又可分为参数和非参数的方法。参数的方法试图最小化代价函数或优化标准来进行聚类，非参数方法即定义一个距离函数进而完成聚类。特殊聚类算法是针对一些特殊数据集和要求的聚类算法。聚类算法的具体分类如图。其分类标准并不严格，某一算法可能同时属于多个分类。聚类算法分类中常用的有划分的聚类算法、层次的聚类算法、基于网格的聚类算法、基于密度的聚类算法以及基于模型的聚类算法，下面对这几种聚类算法进行介绍。2.2.1层次的聚类算法基于层次的聚类算法主要包括凝聚的层次聚类算法和分裂的层次聚类算法。其中凝聚的层次聚类算法采用自底向上的聚类策略，首先将每个样本作为一个类簇，其次合并这些类簇以形成更大的类簇，减少类簇数目，直到样本都聚到同一个簇中或满足某种聚类终止条件。而分裂的层次聚类算法恰恰相反，其采用自顶向下的聚类策略，先将所有的样本作为一个类簇，其次将样本逐步分裂到不同的类簇中以形成越来越小的类簇，直到每个样本分别自成一个簇或满足某种聚类终止条件，比如两个类簇间的距离超过了预先设定的阈值。尽管基于层次的聚类算法思想简单，但经常会遇到的一个问题就是如何选择合并或分裂点。合并或分裂点的选择非常关键，因为下一步的合并或分裂处理均是基于上一组对象的合并或分裂结果上进行的，并且已经做出的处理不会被撤销，聚类间的对象也不能被交换。如果没有选择好合并或分裂点，则会导致低质量的聚类结果。而且，基于层次的聚类算法没有很好的可伸缩性，因为确定合并或分裂点需要进行大量的对象或类检查与估算。BIRCH（Balance Iterative Reducing and Clustering using Hierarchies）是基于层次聚类算法中的典型代表算法。它先对聚类数据集进行一种紧凑的压缩处理，造成特定的数据格式，然后在压缩的数据集而非原始数据集上进行聚类，因此其输入输出成本与数据集的大小呈线性关系。对于大数据集，BIRCH有很好的聚类效果，并支持增量聚类和动态聚类。该算法对数据集进行第一遍扫描便可生成较好的聚类结果，并通过增加扫描次数可以对聚类结果进行进一步修正。在聚类过程中，BIRCH引入用于描述簇信息的两个概念，即聚类特征（Clustering Feature）和聚类特征树（Clustering Feature Tree）。其中聚类特征是一个三元组，给出了对象聚类信息的特征描述，如某聚类中有个维对象，该聚类的聚类特征CF定义为：（2-1）其中是聚类中对象的个数，是个对象的线性和，而是对象的平方和。从统计学的角度来看，聚类特征描述了聚类的统计信息，即聚类的阶矩，阶矩以及阶矩。CF记录了计算聚类和有效利用存储的关键度量，汇总了关于子聚类的信息，而非所存储的对象。而CF树是一个高度平衡的树，存储了基于层次聚类的聚类特征。BIRCH采用多阶段聚类技术：对数据集进行单遍扫描生成一个基本聚类，多遍额外扫描可以进一步改进聚类结果的质量。算法的时间复杂度为，其中是聚类对象的数目。BIRCH算法对对象的数目有很好的伸缩性，并具