论文部分内容阅读
随着科学技术的快速发展,数据量已出现爆炸式的增长。把海量数据变成可用信息,这就要求我们开发一些工具,这些工具能够从大量数据中挖掘出有效的信息。数据挖掘技术能够从海量的数据中挖掘出新颖且有规律,对决策有用的信息或者规则。聚类分析则是数据挖掘中最重要的挖掘工具之一,在众多行业中得到了极为广泛的应用。K-modes聚类算法适用于处理类别型数据集,思想易被理解且实现简单,近年来已成为人们数据挖掘和科学决策的研究热点。但是K-modes聚类算法结果的优劣对初始中心的选择尤其敏感,一旦初始中心选取不当,则容易出现各种问题而达不到应有的聚类效果。因此选择合适的初始聚类中心是K-modes算法的关键步骤。在本文中,我们从改进距离度量方式以及离群点检测的角度来研究K-modes聚类算法的初始中心选择问题,并提出了有效的K-modes聚类初始中心选择机制。本文的主要研究工作如下:(1)利用知识粒度、粗糙集中的粗糙度等相关概念,提出一种新的针对类别型数据的距离度量标准——加权重叠距离。在计算加权距离度量时,我们根据每个属性重要性的大小为不同的属性赋予不同的权值,并且为无关属性赋予较低权重,从而解决实际应用过程中不同属性贡献度不同的问题。另外,我们把新提出的加权重叠距离应用到K-modes算法中,进而提出一种基于新的加权重叠距离的K-modes算法KMGRE。我们在UCI数据集上进行了相关实验,实验结果表明,改进后的K-modes聚类算法其性能要优于传统的K-modes算法。(2)提出一种基于粒计算与粗糙集(简称GR)的离群点检测方法。由于传统K-modes聚类算法在初始中心选择过程中很有可能将离群点选作初始中心点,从而影响聚类的质量,因此,本文将对象的离群程度作为选择初始中心的一个关键因素。针对现有的离群点检测方法所存在的问题,本文提出一种基于粒计算与粗糙集的离群点检测方法。该方法采用了基于信息表的粒计算模型,对于任意对象Ux?和U上的一组不可区分关系,根据每一个不可区分关系,我们都可以获得一个包含x的颗粒g(g是一个对象子集)。为了获得论域U中每个对象x的离群程度(进而获得离群点),我们先计算颗粒g的离群程度,然后再利用颗粒g的离群程度来计算对象x的离群程度。(3)结合(1)中所提出的加权重叠距离以及(2)中所提出的离群点检测方法,进一步提出一种新的K-modes聚类初始中心选择算法Ini_WGROD。通过计算每一个对象的离群程度值以及当前对象与已有中心点之间的加权重叠距离来选择初始中心点,Ini_WGROD算法可以使得离群程度低的对象更有可能成为初始中心点,从而避免了将离群点选做初始中心点的问题,提高了K-modes算法的聚类效果。另外,通过考虑当前对象与已有中心点之间的加权重叠距离,也可以避免出现多个初始中心点来自于同一个聚类簇的现象,从而使得被选出的初始中心点能够高质量地代表不同的聚类簇。