论文部分内容阅读
近年来，信息技术发展极其迅速，数据库技术也随之快速发展，人类获得数据的手段越来越多样化，使得人类所拥有的数据量急剧增加。人们需要从这些数据中获得更多有价值的信息，数据挖掘在此背景下得到广泛关注。聚类是数据挖掘重要的分支，因其是无监督分类而颇具研究和实用价值。在实际应用中，我们经常会遇到大量的类别型数据。由于类别型数据没有数值型数据所具有的几何性质，传统的聚类方法不能直接用来处理类别型数据，需要专门针对类别型数据提出相应的聚类方法。近年来，针对类别型数据的聚类方法引起了广泛关注，并出现了K-modes、Fuzzy K-modes等聚类算法。现有的针对类别型数据的聚类算法还存在很多问题，例如，距离度量不合理、缺乏有效的机制来选择初始中心等。为了解决现有的方法所存在的问题，本文利用粗糙集理论来研究面向类别型数据的聚类，作为一种处理不确定和不完备数据的有效工具，粗糙集理论在数据挖掘的很多领域中都可以发挥重要的作用。我们在传统重叠距离的基础上提出了一种新的距离度量标准，并且提出了两种新的初始中心选择算法。本文所做的工作主要包括以下三个部分：(1)提出一种新的距离度量——加权重叠距离，并由此提出一种基于加权重叠距离的K-modes聚类算法WODKM。在WODKM算法中，我们使用粗糙集理论中的属性重要性和粗糙熵等概念来计算每个属性的重要性，并且在计算对象之间的加权重叠距离时，不同的属性将根据其重要性的大小被赋予不同的权重，从而可以有效地体现出不同属性之间的差异性。实验充分证明了该算法的有效性。(2)将基于距离的离群点检测方法应用于K-modes聚类，利用该方法来选择初始类中心，并由此提出一种新的初始中心选择算法Ini_Distance。为了避免将离群点选为初始中心，我们将传统的基于距离的离群点检测技术引入到K-modes聚类中，通过计算每个对象的离群程度值以及对象之间的加权距离来选择中心点，从而使得离群程度低的对象更有可能成为中心点。另外，通过考虑任意两个初始中心点之间的距离，我们同样可以避免多个中心点来自同一个类的问题。(3)由于基于距离的离群点检测方法存在计算开销大、过于依赖相关的参数等问题，本文进一步提出一种基于信息熵的离群点检测方法，并基于该方法来为聚类选择初始类中心，并由此提出一种新的初始中心选择算法Ini_Entropy。相对于Ini_Distance算法，Ini_Entropy算法具有更少的计算开销，而且不需要预先设置相关参数。