一种AP算法的改进:M-AP聚类算法

Affinity Propagation(AP)聚类算法将所有数据点作为潜在的聚类中心,在相似度矩阵的基础上通过消息传递进行聚类.与传统聚类方法相比,对于大规模数据集,AP是一种快速、有效的聚类方法.但是AP算法在聚类结构复杂的(非团状)数据集上得到的效果并不是很好.因此,在AP的基础上加入一个merge过程,将AP算法改进为M-AP算法,可以有效地解决这种问题.而当样本数目比较大时,将CVM压缩算法融入其中,可以有效地解决大样本问题.     

MapReduce框架下并行知识约简算法模型研究

面向大规模数据进行知识约简是近年来粗糙集理论研究热点。经典的知识约简算法是一次性将小数据集装入单机主存中进行约简,无法处理海量数据。深入剖析了知识约简算法中的可并行性;设计并实现了数据和任务同时并行的Map和Reduce函数,用于计算不同候选属性集导出的等价类和属性重要性;构建了一种MapReduce框架下并行知识约简算法模型,用于计算基于正区域、基于差别矩阵或基于信息熵的知识约简算法的一个约简。在Hadoop平台上进行了相关实验,实验结果表明,该并行知识约简算法模型可以高效地处理海量数据集。     

基于MapReduce的并行k-modes算法

k-modes是一种代表性的分类数据的聚类算法.首先对k-modes聚类算法的实现过程进行了改进:通过在分配数据对象到簇时更新这个簇中各个属性项的次数,使得在遍历一次全部数据对象就能计算出新的簇中心.为了使k-modes能够处理大规模分类数据,在Hadoop平台上用MapReduce并行计算模型实现了k-modes算法.实验表明:在处理大量数据时,并行k-modes比串行k-modes极大地缩短了聚类时间,取得了较好的加速比.     

基于近邻传播算法的半监督聚类

提出了一种基于近邻传播(affinity propagation,简称AP)算法的半监督聚类方法.AP是在数据点的相似度矩阵的基础上进行聚类.对于规模很大的数据集,AP算法是一种快速、有效的聚类方法,这是其他传统的聚类算法所不能及的,比如:K中心聚类算法.但是,对于一些聚类结构比较复杂的数据集,AP算法往往不能得到很好的聚类结果.使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整,进而达到提高AP算法的聚类性能.实验结果表明,该方法不仅提高了AP对复杂数据的聚类结果,而且在约束对数量较多时,该方法要优于相关比对算法.     

基于属性排斥矩阵的约简方法

针对启发式算法难以获得最小约简的问题,研究最小约简约束下属性之间的排斥特性,提出了针对部分最小约简必要条件的属性排斥矩阵.在此基础上,分别结合典型加法类和减法类启发式约简算法提出两种改进的基于属性排斥矩阵的启发式属性约简算法,采用UCI(加州大学欧义分校)机器学习数据集所进行的测试结果表明,属性排斥矩阵能够全面提高启发式属性约简算法的性能,有利于获得最小约简.     

云计算环境下知识约简算法

知识约简是粗糙集理论的重要研究内容之一.经典的知识约简算法是假设所有数据一次性装入内存中,这显然不适合处理海量数据.为此,从属性(集)的可辨识性和不可辨识性出发,给出了可辨识和不可辨识对象对的概念及其性质,并阐述了它们与差别矩阵的关系.利用MapReduce设计了并行计算等价类的方法,提出了面向大规模数据的数据并行知识...     

一种改进的集成算法RSCA在医学领域中的应用

首次将粗糙集和聚类算法结合起来用于医学领域,取得很好效果.先用粗糙集去除数据集中无用的、干扰性的属性进行约简,然后利用一种改进的基于密度的聚类算法对处理后的数据集进行有效的聚类.从结果可以发现用粗糙集处理后的结果比处理前的分类准确度提高很多.此外,算法的时间复杂度低,适合对大规模数据库的挖掘.最后,通过仿真实验,证明了算法确实具有上述优点.     

基于聚类粒化和簇间散度的属性约简算法

属性约简是粗糙集理论中的研究热点,对连续值数据进行属性约简的算法大多基于优势关系或邻域关系。然而连续值数据集的属性不一定具有优势关系;而基于邻域关系的属性约简算法虽然可以通过邻域半径调整粒化程度,不过由于各属性量纲不同且半径参数为连续值使半径难以统一,导致整个参数粒化过程计算量较大。为解决此问题,提出一种基于聚类粒化的多粒度属性约简策略。首先,利用聚类方法将相似样本归类,并提出了基于聚类的近似集、相对正域及正域约简概念;其次,根据JS（Jensen-Shannon）散度理论对簇间各属性数据分布进行差异性度量,并选择出具有代表性的特征用以区分不同类簇;最后,利用可辨识矩阵设计了属性约简算法。所提算法不要求属性具有序关系,且不同于邻域半径,聚类参数为离散值,调节此参数就能够对数据集形成不同粒化程度的划分。在UCI与Kent Ridge数据集上进行的实验结果表明,该属性约简算法可以直接处理连续值数据,且该算法在较小范围内离散地调节聚类参数便能在保持甚至提高分类精度的前提下去除数据集中的冗余特征。     

基于MapReduce的分布式近邻传播聚类算法

随着信息技术迅速发展,数据规模急剧增长,大规模数据处理非常具有挑战性.许多并行算法已被提出,如基于MapReduce的分布式K平均聚类算法、分布式谱聚类算法等.近邻传播(affinity propagation,AP)聚类能克服K平均聚类算法的局限性,但是处理海量数据性能不高.为有效实现海量数据聚类,提出基于MapReduce的分布式近邻传播聚类算法——DisAP.该算法先将数据点随机划分为规模相近的子集,并行地用AP聚类算法稀疏化各子集,然后融合各子集稀疏化后的数据再次进行AP聚类,由此产生的聚类代表作为所有数据点的聚类中心.在人工合成数据、人脸图像数据、IRIS数据以及大规模数据集上的实验表明:DisAP算法对数据规模有很好的适应性,在保持AP聚类效果的同时可有效缩减聚类时间.     

云计算环境下差别矩阵知识约简算法研究

知识约简是粗糙集理论的重要研究内容之一。经典的差别矩阵知识约简算法只能处理小数据集,而已有的任务并行的知识约简算法是假设所有数据一次性装入内存中,这显然不适合处理海量数据。为此,剖析了差别矩阵元素的特性,根据属性(集)的不可辨识性和云计算技术MapRcducc设计了适合数据并行的差别矩阵,并首次提出了面向大规模数据的差别矩阵知识约简算法。实验结果表明该知识约简算法是有效可行的,且具有较好的可扩展性。