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

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

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

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

多粒度粗糙集模型下的矩阵属性约简算法

随着网络和通信技术的快速的发展,社会进入了大数据时代。如何能够快速地从海量大数据中找到属性约简是目前研究的一个热点。由于传统属性约简的方法在计算大数据属性约简时,需要消耗巨大的计算时间,不能有效地处理日益积累的大数据属性约简的问题。为了提高传统属性约简算法的效率,针对较大决策信息系统属性约简更新问题,利用多粒度粗糙集理论,提出了基于多粒度粗糙集模型的矩阵属性约简算法,通过2组UCI数据集对所提出的多粒度矩阵属性约简算法的性能进行测试,结果验证了该多粒度矩阵属性约简算法是合理且有效的。     

深度AWB结合改进DIT的高效大数据分类

针对传统数据分类属性模型中存在的较为复杂且大数据分类效率低等问题,基于云计算环境,提出利用深度属性加权贝叶斯(deep attribute weighting Bayesian,AWB)算法结合改进差别信息树(differential information tree,DIT)的大数据高效分类方法.利用AWB算法构建大数据训练集的模糊知识库,提高大数据分类精度;采用改进DIT进行模糊粗糙集属性约简,以并行方式利用映射函数对信息进行分区,将洗牌算法融入模糊分类器的设计中,提高大数据分类效率;利用CloudSim仿真器在大型网络数据集对所提方法的性能进行实验论证.实验结果表明,所提方法提高了分类准确度,降低了计算时间,提高了计算效率.     

云计算下保持边界域划分的知识约简算法研究

知识约简是数据挖掘应用中知识获取的重要步骤。经典的知识约简算法是一次性将小数据集装入内存中进行知识约简,而传统的并行知识约简仅仅利用任务并行来提高约简算法效率,都无法处理海量数据。通过分析经典的知识约简算法,构建了不可辨识的对象对,提出了保持边界域划分的知识约简算法,并探讨了保持边界域划分的知识约简算法之间的关系。深入剖析了知识约简算法中数据和任务同时并行的可行性,提出了云计算环境下保持边界域划分的知识约简算法框架模型,在Hadoop平台上构建了云计算环境并进行了相关实验。实验结果表明该知识约简算法可以处理海量数据集。     

F-邻域粗糙集及其约简

邻域粗糙集可以直接处理数值型数据, F- 粗糙集是第一个动态粗糙集模型. 针对动态变化的数值型数据, 结合邻域粗糙集和F- 粗糙集的优势, 提出了F- 邻域粗糙集和F- 邻域并行约简. 首先, 定义了F- 邻域粗糙集上下近似、边界区域; 其次, 在F- 邻域粗糙集中提出了F- 属性依赖度和属性重要度矩阵; 根据F- 属性依赖度和属性重要度矩阵分别提出了属性约简算法, 证明了两种约简方法的约简结果等价; 最后, 比对实验在UCI数据集、真实数据集和MATLAB生成数据集上完成, 实验结果显示, 与相关算法比较, F- 邻域粗糙集可以获得更好的分类准确率. 为粗糙集在大数据方面的应用增加了一种新方法.     

粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).     

一种基于并行遗传算法的粗糙集属性约简

指出现有粗糙集属性约简算法的不足,考虑并行遗传算法在处理大型数据库上的特有优势,将粗糙熵作为粗糙集不确定性的度量,给出一种求解信息系统约简集的三群体并行遗传算法.最后通过实例计算表明该算法能快速有效求解属性约简,而且对大规模数据样本的信息系统效果更为明显.     

基于知识粒度特征的多目标粗糙集属性约简算法

针对多知识粒度粗糙集在条件属性权重计算及约简过程中易忽略单个属性序列产生的等价划分的问题,引入帕累托最优思想,同时考虑基于等价关系的知识依赖分辨度以及属性的重要性程度,将多粒度粗糙集属性约简问题转化为离散多目标优化问题.针对该问题的结构设计具有集群智能优化思想及复杂网络拓扑结构的优化算法,在算法中引入基于个体的非支配解集以平衡局部最优与全局最优的关系,引入基于“均值-方差”的遗传算子增加种群多样性.以UCI中的测试数据集作为算例构建粗糙集决策表进行优化计算,引入多种智能算法进行性能比较,依据约简结果,利用多层感知机对数据集中的对象进行分类,验证约简方法的有效性.研究结果表明:所提出方法具有更强的多目标属性挖掘性能;基于帕累托最优思想的多目标属性约简方法能较好地综合知识分辨度与知识粒度建模方式的优点,提升数据集的分类精度.     

基于邻域粗糙集的符号与数值属性快速约简算法

粗糙集理论被广泛应用于属性约简,算法复杂性是制约约简应用于大样本知识发现的主要问题,尤其是邻域模型下的约简问题.本文分析邻域粗糙集模型的数学性质,利用正域与属性集的单调关系,构造基于属性依赖度和前向搜索策略的快速算法.该算法降低样本比较次数,提高计算效率.实验分析表明该算法的有效性.     

云平台下基于粗糙集的并行增量知识更新算法

日益复杂和动态变化的海量数据处理,是当前人们普遍关注的问题,其核心内容之一是研究如何利用已有的信息实现快速的知识更新.粒计算是近年来新兴的一个研究领域,是信息处理的一种新的概念和计算范式,主要用于描述和处理不确定的、模糊的、不完整的和海量的信息,以及提供一种基于粒与粒间关系的问题求解方法.作为粒计算理论中的一个重要组成部分,粗糙集是一种处理不确定性和不精确性问题的有效数学工具.根据云计算中的并行模型MapReduce,给出了并行计算粗糙集中等价类、决策类和两者之间相关性的算法;然后,设计了用于处理大规模数据的并行粗糙近似集求解算法.为应对动态变化的海量数据,结合MapReduce模型和增量更新方法,根据不同的增量策略,设计了两种并行增量更新粗糙近似集的算法.实验结果表明,该算法可以有效地快速更新知识;而且数据量越大,效果越明显.     

一种基于粗糙集理论的快速并行属性约简算法

将并行计算的思想融入基于粗糙集理论的快速属性约简中,提出了一种基于粗糙集理论的快速并行属性约简算法.该算法在保证约简结果是Pawlak约简的情况下,将属性约简任务划分到多个处理器中同时处理,从而大大提高了属性约简的效率.仿真实验结果说明了该算法的高效性.     

基于邻域粗糙集下知识划分的信息表降维

Pawlak粗糙集的知识约简包括对决策表的知识约简和对信息表的知识约简。作为Pawlak粗糙集的扩展,邻域粗糙集在针对决策表的属性约简方面应用广泛,而针对信息表的属性约简方面应用鲜少。为了设计一种适用于信息表的属性约简算法,根据Pawlak粗糙集的信息表知识约简标准,首先提出一种邻域粗糙集的信息表知识约简标准,然后根据这种标准,结合贪心思想,进一步提出了一种适用于聚类任务的信息表属性约简算法。与主成分分析(principal component analysis,PCA)算法相比,实验结果表明用该算法对数据集降维后,得到的属性约简集合的属性个数较多,K-means算法根据属性集合进行聚类的精度较高。实验结果证明该算法能有效地应用于信息表的属性约简方面。     

基于最大粒的规则获取算法

粒计算是模拟人类思维和解决复杂问题的方法,它是复杂问题求解、海量数据挖掘、模糊信息处理的有效工具。文中首先分析并指出传统的规则获取方法存在的某些弊端,并从粒计算的角度分析属性约简的粒度原理,指出属性约简过程的本质是寻找决策划分空间的一个极大近似划分空间,而在极大近似划分空间上提取的规则可能不是最简规则。为此,提出一种基于最大粒的规则获取算法,该算法根据条件属性对论域形成的分层递阶的划分空间,自顶向下逐渐提取最大粒对应的规则。仿真实验表明该算法提高粗糙集的泛化能力。     

基于粒计算的属性约简算法

粒计算是一种基于问题概念空间划分的新的智能计算理论和方法,不相容决策表是粗糙集理论研究的一个重点。利用粗糙集中的等价关系来构建粒子,给出了决策表系统的粒子分解方法及在粒表示下以属性重要性作为启发信息的属性约简算法。实验结果表明该算法不仅具有高效性,而且能处理大型决策表。     

基于回溯搜索算法的决策粗糙集属性约简

属性约简是粗糙集理论的核心问题,为了获得更多更稳定的最小属性约简,根据决策粗糙集模型将最小属性约简问题转化为决策风险最小化问题,并给出了新的适应度函数计算方法;在此基础上利用回溯搜索算法较强的全局搜索性能,提出了基于回溯搜索算法的决策粗糙集属性约简算法;对UCI数据集的实验结果以及与其他约简算法的比较表明,该算法能够得到更多的最小属性约简,而且能够在多次运行中保持约简结果个数的稳定性。