论文部分内容阅读
聚类分析是模式识别与人工智能中发现知识的重要途径之一,传统的聚类分析是一种硬划分。大数据时代出现了高维海量数据,它们往往具有不完备性、不精确性、不一致性等特征,传统聚类算法很难满足这些数据的聚类需求。粒度计算是不确定信息处理的重要工具,是当前计算智能领域中模拟人类思维和解决复杂问题的新方法。粒度计算的兴起将聚类分析拓展到了软计算领域,实用价值进一步提高,理论意义更加贴近现实。通过粒度的变换,聚类可以在不同层次、不同角度进行,使得“亦此亦彼”的聚类有了研究的理论基础和实践方法,弥补了传统聚类的不足,有利于问题的解决。本文将粒度计算与聚类分析融合在一起,对粒度聚类方法做了深入研究。将粒度的思想贯穿到聚类的数据预处理与聚类分析的整个过程,同时将聚类作为属性粒化与样本粒化的手段,用聚类的目标函数、参数的值来描述粒化的角度和层次。本文主要工作有以下几个方面:1.针对聚类分析预处理中属性约简时间、空间复杂度高的问题,采用聚类的方法对属性并行粒化。基于属性区分能力和AP聚类的属性粒化方法利用AP聚类算法将属性分为若干簇类后在每个簇类中依据信息熵、属性重要度等指标选取代表属性构成最后的属性集合,从而完成属性粗粒化的要求。对大数据集的特征降维,这种算法比传统的属性约简算法大大提高了运算效率,在属性粒化精度要求不是很严格的情况下,算法优势明显。基于AP聚类的并行属性约简算法可以在保持分类能力不变的情况下提高传统属性约简算法的效率,但是由于并行约简中仍然采用的是传统的算法,所以对规模特别大的数据集,算法的时效性有一定的局限性。2.将粒度计算与聚类算法相结合,一般只是将粒度计算的模型应用到聚类算法中去。聚类结果之间仍然无法自由转换。由于所有聚类算法统一在粒度的思想下,提出基于聚合网络的变粒度二次聚类方法,通过粒度计算将两种聚类算法融合在一起,首次聚类的目的并不是完成对整个数据集的聚类操作,而是找到合适的聚合粒层,是在较细的粒度上进行,用以寻找数据局部结构,并依据粒度的粗细形成聚合网络中的某一聚合粒层,二次聚类在此基础之上完成对论域的聚类操作。提出基于K均值与层次聚类的变粒度自适应二次聚类方法,可以同时解决K均值算法易受初始聚类中心的影响而聚类错误、不能识别任意形状数据集和层次聚类速度较慢的问题。提出的基于AP聚类的变粒度二次聚类方法首次聚类采用AP聚类,效果稳定,一次聚类粒度较细,正确率高,寻找合适粒度时间少。3.为了解决AP聚类不能适用于子空间聚类的问题,提出了两种改进算法。一种是属性样本同步粒化的AP熵加权软子空间聚类算法去除冗余属性后,在每次聚类算法的迭代过程中增加一步修改属性权重。迭代终止时,就得到了兴趣度子空间的准确的属性集的粒化结果。另一种属性样本异步粒化的AP子空间聚类方法是一种异步软子空间聚类算法,首先通过计算属性的基尼值与联合基尼值得到属性的关系矩阵,然后将子空间的查找转换成查找矩阵的极大全1子矩阵,降低了时间复杂度,最后在各兴趣度子空间使用AP算法聚类,完成子空间聚类的任务。算法既保留了AP聚类算法的优点,又克服了AP算法不能进行子空间聚类的不足。4.对并行程序的粒化方法做了研究,在细粒度并行思想的指导下,提出基于改进属性约简的细粒度并行AP聚类算法。算法将粒度思想引入到并行计算中,首先分析了程序并行计算中的粒度原理,对传统的基于差别矩阵的属性约简算法做了改进与并行化处理,降低了它的时间空间复杂度,然后对AP算法做了细粒度并行化处理,提高了算法的效率。整个算法将任务划分到多个线程同时处理。