一种不精确数据的聚类挖掘方法.doc
《一种不精确数据的聚类挖掘方法.doc》由会员分享,可在线阅读,更多相关《一种不精确数据的聚类挖掘方法.doc(11页珍藏版)》请在三一文库上搜索。
1、一种不精确数据的聚类挖掘方法 (1.湖南商学院 计算机与电子工程系, 长沙 410205; 2.中南大学 信息科学与工程学院, 长沙 410083) ?丶?词:非精确数据; K平均算法; FK聚类算法; 密度概率函数 Algorithm in clustering location datafor uncertain data mining LI Qingfeng1,2, ZHOU Xiancheng1,2, WANG Li1,2, ZHOU Weilin1 (1.Dept. of Computer& Electronic Engineering, Hunan Business College
2、, Changsha 410205, China; 2.School of Information Science & Engineering,Central South University, Changsha 410083, China) Abstract:To consider data uncertainty in the clustering process, this paper proposed a FKmeans clustering algorithm that enhanced the Kmeans algorithm tothe goal of minimizing th
3、e expected sum of squared errors E(SSE). Specially noted that a data object xi was specified by an uncertainty region with an uncertainty pdf f(xi). This paper applied FKmeans to the particular pattern of movingobject uncertainty. Experimental results show that by considering uncertainty, the cluste
4、ring algorithm can produce more accurate results. Key words:data uncertainty; Kmeans algorithm ; FKmeans clustering algorithm; pdf ? 现实生活中数据的不精确性是固定存在的,如距离测量数据、传感器检测数据等。由于测量偏差、取样精度及非实时性等往往使得到的数据出现一定的误差,这种数据称为噪声数据。对噪声数据处理已经有了多种较成熟的方法,但对不确定数据的挖掘工作做得还比较少。由于不确定性,数据不再具有确定值的粒子特性,传统的数据挖掘技术多是对确定数据的分析处理,因此采用
5、这些技术之前应平滑数据、去掉噪声。对噪声数据处理的方法不同,将对数据挖掘的结果有较大的影响。图1描述了不确定性位置的运动物体的一种聚类算法,如果仅仅考虑表面记录的数值,许多物体将可能被划入错误的类,甚至有可能会改变各类的聚类质心,导致一系列的错误。对这种问题通常采用的技术是归纳不确定的数据信息,例如用统计概率密度函数,这样能使数据挖掘的结果更接近现实的情况。本文研究了怎样对不确定数据进行归纳合并,以便使聚类挖掘结果更准确,同时提出了一种基于K中心点聚类的新算法。 图1(a)中现实的数据由三个聚类点(a, b, c)构成;(b)中分析记录的数据时,可能会推导出四个聚类(a,b,c and c);
6、(c)中当运用线性不确定性进行分析时,推导的结果是a, b and c三个聚类,显而易见,这个结果与(b)中分析相比更接近真实的数据聚类(a)。 1 相关的工作 近年来不确定数据的分析处理研究逐渐引起了人们的关注和兴趣。很多研究致力于非精确数据的查询,以便发现可信度比效高的结果。例如,在文献1中, Cheng等人提出了在序列范围内查询非精确数据的解决思想, 他们在文献2中又提出了在最邻近序列查询聚类序列的方法。 现在这些研究结果主要是应用在单一数据库序列的非精确数据管理领域,还没有涉及到更复杂数据库的分析和挖掘等问题的研究。聚类在数据挖掘中的作用是很大的,但在对非精确数据的聚类分析和数据挖掘的
7、研究工作还进行得比较少。 Hamdan等人3用EM算法对混合型高密度数据库的非精确数据聚类进行了探索,然而EM算法的约束条件多、局限性大,在其他环境条件下的使用受到了限制。与此相关的另一种探索是模糊聚类,在模糊聚类中一簇表示成模糊数据集,每个对象根据不同的属性或分类等级可能聚类到不同的簇。目前,K平均模糊聚类算法是应用较广泛的方法。 K平均算法以K为参数,把n个对象分为k个簇,以使簇内具有较高的相似度,而簇间的相似度较低。相似性的计算根据一个簇中对象的平均值(被看做簇的重心)来进行。其算法处理流程如下:a)随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象,根据其与
8、各个簇中心的距离,将它赋予最近的簇。b)重新计算每个簇的平均值,不断重复这个过程,直到准则函数收敛。通常,采用平方误差准则,其定义为 E=ki=1pci?Op-mi?O2。其中:E是数据库中所有对象的平方误差的总和;p是空间中的点,表示给定的数据对象;mi是簇ci的平均值(p和mi均是多维的)。这个准则试图使生成的结果簇尽可能地紧凑和独立。 算法描述:K平均。划分的K平均算法基于簇中对象的平均值。 输入:簇的数目k和包含n个对象的数据库。 输出:k个簇,使平方误差准则最小。 方法: a)任意选择k个对象作为初始的簇中心; b)repeat; c)根据簇中对象的平均值,将每个对象(重新)赋予最类
9、似的簇; d)更新簇的平均值,即计算每个簇中对象的平均值; e)until不再发生变化。 该算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的,而簇与簇之间区别明显时,它的效果较好。对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度是O(nkt)。其中:n是所有对象的数目;k是簇的数目;t是迭代的次数。通常k 2 对不确定数据的聚类算法分析 2.1 问题的分析 本文介绍基于密度分布函数的聚类算法。该算法主要基于下面的思想: a)每个数据点的影响可以用一个数学函数来形式化地模拟,它描述了一个数据点在邻域内的影响,被称为影响函数(influence function); b)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 不精确 数据 挖掘 方法
链接地址:https://www.31doc.com/p-1591926.html