数据挖掘中聚类算法比较及在武警网络中的应用研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇数据挖掘中聚类算法比较及在武警网络中的应用研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：聚类算法是数据挖掘的核心技术,根据评价聚类算法优劣的几个标准,对数据挖掘中常用聚类算法做了比较分析,根据各自特点,加以改进,并应用于武警部队数据挖掘项目中。通过运用改进型Kmeans算法,取得了较好的挖掘结果,为进一步信息的智能化检索、信息的过滤、分拣提供依据。

关键词：数据挖掘;代表点聚类算法;基于密度的聚类算法;Kmeans聚类算法;指挥自动化

中图分类号：TP274文献标识码：A文章编号：1004-373X(2008)08-115-03オ

Comparison of Clustering Method in Data Mining and Application of Armed Police Force Network

TIAN Jie,ZHOU Xiaojuan,LV Jianxin

(Engineering College of Armed Police Force,Xi′an,710086,China)オ

Abstract：Clustering method is the core of data mining technology.In this paper,several standards are used to evaluate these clustering methods.Finally the author elicits an advanced Kmeans clustering algorithms to the armed police actual network,obtaining good result,which will provide basis for further information on intelligent retrieval,information filtering,sorting,and so on.

Keywords：data mining;DBSCAN;CURE;Kmeans;command automation

1 引 言

数据挖掘的历史虽然较短,但从20世纪90年代以来,他的发展速度很快,是多学科综合的产物。虽然目前还没有一个完整的定义,但这里认为：数据挖掘就是从海量的数据中挖掘出可能有潜在价值的信息的技术。这些信息是可能有潜在价值的,支持决策,可以有效利用指挥自动化网,为进一步研究寻找突破口。

数据挖掘综合了各个学科技术,其任务一般可分为2类：描述和预测。描述性挖掘任务刻划数据库中数据的一般特性。预测性挖掘任务在当前数据上进行推断,以进行预测\[1\]。主要功能有分类和预测、聚类分析、关联规则和序列模式的发现、偏差的检测等。

把数据库中的对象分类是数据挖掘的基本操作,根据最大化类内的相似性、最小化类间的相似性的原则进行聚类或分组,从而使属于同一类的个体间距离尽可能小,而不同类个体间距离尽可能大,为了找到效率高、通用性强的聚类方法人们从不同角度提出近百种聚类方法,典型的有Kmeans方法、Kmedoids方法、CLARANS方法,BIRCH方法等,这些算法适用于特定的问题及用户。

聚类算法一般分为分割和分层2种。分割聚类算法通过优化评价函数把数据集分割为K个部分,他需要K作为输人参数。典型的分割聚类算法有Kmeans算法：Kmedoids算法、CLARANS算法。分层聚类由不同层次的分割聚类组成,层次之间的分割具有嵌套的关系。他不需要输入参数,这是他优于分割聚类算法的一个明显的优点,其缺点是终止条件必须具体指定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和CURE算法等。根据评价聚类算法优劣的几个标准\[2\],对常用的聚类算法进行比较分析。

(1) 是否适用于大数据量,算法的效率是否满足大数据量高复杂性的要求;

(2) 是否能应付不同的数据类型,能否处理符号属性;

(3) 是否能发现不同类型的聚类;

(4) 是否能应付噪声数据或异常数据;

(5) 是否对数据的输入顺序不敏感。

2 数据挖掘常用聚类算法比较分析

2.1 BIRCH算法

BIRCH算法即平衡迭代削减聚类法,其核心是用一个聚类特征3元组表示一个簇的有关信息,从而使一簇点的表示可用对应的聚类特征,而不必用具体的一组点来表示。他通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有2个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数,而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类,非叶子结点为他的子女的最大关键字,可以根据这些关键字进行插人索引,他总结了其子女的信息。

聚类特征树可以动态构造,因此不要求所有数据读人内存,而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T,则把该叶子节点分裂。其他叶子结点也需要检查是否超过分枝因子来判断其分裂与否,直至该数据插入到叶子中,并且满足不超过类直径,而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小,控制其占内存容量。

BIRCH算法通过一次扫描就可以进行较好的聚类,由此可见,该算法适合于大数据量。BIRCH算法只适用于类的分布呈凸形及球形的情况,并且由于BIRCH算法需提供正确的聚类个数和簇直径限制,对不可视的高维数据不可行。

2.2 CURE算法

CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类,然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的表示方法进行改进,回避用所有点或用中心和半径来表示一个类；而是从每一个类中抽取固定数量、分布较好的点作为描述此类的代表点,并将这些点乘以一个适当的收缩因子,使他们更靠近类的中心点。将一个类用代表点表示,使得类的外延可以向非球形的形状扩展,从而可调整类的形状以表达那些非球形的类。另外,收缩因子的使用减小嗓音对聚类的影响。CURE算法采用随机抽样与分割相结合的办法提高算法的空间和时间效率,并且在算法中用堆和Kd树结构来提高算法效率。

2.3 DBSCAN算法

DBSCAN算法即基于密度的聚类算法。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是：对于一个类中的每个对象,在其给定半径的领域中包含的对象不能少于某一给定的最小数目。在DBSCAN算法中,发现一个类的过程是基于这样的事实：一个类能够被其中的任意一个核心对象所确定。为了发现一个类,DBSCAN先从对象集D中找到任意对象P,并查找D中关于关径Eps和最小对象数Minpts的从P密度可达的所有对象。如果P是核心对象,即半径为Eps的P的邻域中包含的对象不少于Minpts,则根据算法,可以找到一个关于参数Eps和Minpts的类。如果P是一个边界点,则半径为Eps的P邻域包含的对象少于Minpts,P被暂时标注为噪声点。然后,DBSCAN处理D中的下一个对象。