一种基于条件熵的决策表属性约简并行算法*

本文以分类为基础提出了一种基于条件熵的决策表属性并行约简算法。该算法通过条件熵的计算在属性约简的同时将原决策表逐层分解为相对于决策属性来说尽量均匀的子决策表,从而实现了属性约简的并行计算。本文随后对该算法的时间复杂度进行了分析,实验表明,该算法在效率方面优于传统算法。     

一种并行的信息系统属性约简算法*

属性约简是信息系统中的一个重要操作,而分类是属性约简的基础,且直接在大数据集上进行属性约简往往存在效率低下的问题。故以分类为基础提出了一种基于信息熵的信息系统并行属性约简算法。该算法通过信息熵的计算,在属性约简的同时对原信息系统逐层分解成尽量均匀的子表,从而实现了属性约简的并行计算并缩小了搜索空间。对该算法的时间复杂度进行了分析,实验表明,该算法在效率方面优于传统算法。     

基于模糊关联规则并行挖掘算法的飞行数据处理

针对顺序的模糊关联规则算法在处理海量飞行数据时,由于算法可扩展性低、响应时间过长而带来数据处理的不便,本文采用模糊关联并行挖掘算法,先使用并行的模糊c-2均值算法将数量型属性划分成若干个模糊集,并借助模糊集软化属性的划分边界:在用改进的布尔型关联规则的并行挖掘算法来发现频繁模糊属性集.通过飞行数据库进行算法验证,证明了并行算法具有好的可扩展性、规模增长性和加速比性能.     

基于弱相关化特征子空间选择的离散化随机森林并行分类算法

随着大数据时代的到来,数据信息呈几何倍数增长。传统的分类算法将面临着极大的挑战。为了提高分类算法的效率,提出了一种基于弱相关化特征子空间选择的离散化随机森林并行分类算法。该算法在数据预处理阶段对数据集中的连续属性进行离散化。在随机森林抽取特征子空间阶段,利用属性向量空间模型计算属性间的相关性,构造弱相关化特征子空间,使所构建的决策树之间相关性降低,从而提高随机森林的分类效果;并通过研究随机森林的并行化策略,结合MapReduce框架,改进并实现了随机森林模型构建过程的双重并行化,进一步改善了算法的计算效率。     

基于云计算的层次粗糙集模型约简算法研究

传统的并行属性约简算法通过利用抽样技术获取小数据样本进行知识约简,但对于大数据集来说,样本数据不具有一般性且无法代表整个数据集.为了弥补传统并行属性约简算法只能用来计算最小属性约简、处理小数据集的缺陷,论文通过分析了先验知识在粒计算中的重要性,结合云计算技术处理海量数据的优势,以粗糙集理论为背景,从不同角度、层次出发建立层次粗糙集模型,提出基于云计算的层次粗糙集模型约简算法,讨论并实现了知识约简算法中的可并行化操作,利用Hadoop在普通计算机集群上进行试验,从运行时间、加速比、可扩展性三个方面对所提出基于正区域、信息熵、边界域算法的重要性进行评价.实验证明：基于云计算的层次粗糙集模型约简算法可以有效处理大数据集.     

基于并行处理机制的数据复用策略研究

针对频繁出现的数据冗余、数据复用效率低下等问题,将列存储方式结合并行处理机制对数据复用策略进行优化。构建了基于MapReduce的数据复用并行化处理模型,利用改进型CSM模式匹配算法结合数据挖掘过程中的数据筛选算法,提出并行化数据复用算法。该算法利用数据属性的模式匹配确定属性列之间的对应关系,使用数据检测方式验证属性列数据复用的可行性,从而进行属性列数据筛选,实现并行化的数据复用策略。在大数据环境下的数据仓库中,对大规模基准数据属性集SSB和TPCH中提取的数据实证分析,实验结果分析中存储量和处理时间分别减少了17%和35%,实验结果验证了并行化数据复用策略在数据存储量、数据处理时间等方面比普通数据复用策略更具高效性。     

改进的并行fp-growth算法在工业设备故障诊断中的应用研究

如今,工业设备不断向智能化、大型化发展,伴随着设备故障日益复杂多样,如何快速、准确地诊断故障成为一个难题。通过研究,提出以大数据技术Hadoop为平台,基于兴趣属性列的改进的fp-growth算法作为数据挖掘方法,来实现工业设备的故障诊断。实验以工业齿轮箱为例,首先选取两部分数据分别作为训练数据和测试数据,在预处理阶段对训练数据进行空值处理、维度相关性分析以及抽样离散化数据;其次提出基于兴趣属性列的改进的并行fp-growth算法,从训练数据中挖掘出属性列与故障之间的关联规则;最后通过测试数据验证关联规则,证明了改进方法的可行性。实验结果表明,基于兴趣属性列改进的并行fp-growth算法能够在保证准确率的情况下进行快速故障诊断。     

基于改进属性约简的细粒度并行AP聚类算法

Affinity Propagation(AP)聚类算法将所有数据点作为潜在的聚类中心,在相似度矩阵的基础上通过消息传递进行聚类.与传统聚类方法相比,对于规模很大的数据集,AP是一种快速、有效的聚类方法.正是这样,属性约简对于AP算法非常重要.另外,在大规模并行系统的设计中,细粒度并行是实现高性能的基本策略.提出了一种基于改进属性约简的细粒度并行AP聚类算法(IRPAP),将粒度思想引入到并行计算中.首先分析了并行计算中的粒度原理.然后用改进的属性约简算法对数据集预处理.此算法并行计算并选择差别矩阵元素,降低了时间空间复杂度,最后用AP算法聚类.整个IRPAP算法将任务划分到多个线程同时处理.实验证明,对于大规模数据集的聚类,IRPAP算法比AP算法效率更高.     

基于MapReduce的Bagging决策树优化算法

针对经典C4.5决策树算法存在过度拟合和伸缩性差的问题,提出了一种基于Bagging的决策树改进算法,并基于MapReduce模型对改进算法进行了并行化。首先,基于Bagging技术对C4.5算法进行了改进,通过有放回采样得到多个与初始训练集大小相等的新训练集,并在每个训练集上进行训练,得到多个分类器,再根据多数投票规则集成训练结果得到最终的分类器;然后,基于MapReduce模型对改进算法进行了并行化,能够并行化处理训练集、并行选择最佳分割属性和最佳分割点,以及并行生成子节点,实现了基于MapReduce Job工作流的并行决策树改进算法,提高了对大数据集的分析能力。实验结果表明,并行Bagging决策树改进算法具有较高的准确度与敏感度,以及较好的伸缩性和加速比。     

基于Hadoop的并行共享决策树挖掘算法研究

共享知识挖掘是指通过学习不同事物之间的共享知识,将学习到的知识应用到未知事物来加快认知未知事物。针对大数据集中串行共享知识挖掘算法效率低下的问题,结合云计算技术,提出了一种基于Hadoop的并行共享决策树挖掘算法(PSDT)。该算法采用传统的属性表结构实现并行挖掘,但 其I/O操作过多,影响算法性能,为此,进一步提出了一种混合并行共享决策树挖掘算法(HPSDT)。该算法采用混合数据结构,在计算分裂指标阶段使用属性表结构,在分裂阶段采用数据记录结构。数据分析表明,HPSDT算法简化了分裂过程,其I/O操作是PSDT的0.34左右。实验结果表明,PSDT和HPSDT都具有良好的并行性和扩展性;HPSDT比PSDT性能更好,并且随着数据集的增大,HPSDT的优越性更加明显。     

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

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

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

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

基于并行约简的网络安全态势要素提取方法

网络安全态势要素选取的质量对网络安全态势评估的准确性起到至关重要的作用,而现有的网络安全态势要素提取方法大多依赖先验知识,并不适用于处理网络安全态势数据。为提高网络安全态势要素提取的质量与效率,提出一种基于属性重要度矩阵的并行约简算法,在经典粗糙集基础上引入并行约简思想,在保证分类不受影响的情况下,将单个决策信息表扩展到多个,利用条件熵计算属性重要度,根据约简规则删除冗余属性,从而实现网络安全态势要素的高效提取。为验证算法的高效性,利用Weka软件对数据进行分类预测,在NSL-KDD数据集中,相比利用全部属性,通过该算法约简后的属性进行分类建模的时间缩短了16.6%;对比评价指标发现,相比现有的三种态势要素提取算法（遗传算法（GA）、贪心式搜索算法（GSA）和基于条件熵的属性约简（ARCE）算法）,该算法具有较高的召回率和较低的误警率。实验结果表明,经过该算法约简的数据具有更好的分类性能,实现了网络安全态势要素的高效提取。     

基于SPMD的C4.5并行决策树加速分析

决策树分类方法是解决数据挖掘、模式识别中分类任务的有效方法,然而,在大规模的数据集上运行时,其运行效率受到严重影响。文中选取决策树的代表算法C4.5算法为研究对象,利用算法固有的并行性对其进行优化研究。文中利用MATLAB实现串行的C4.5决策树,并对构成该决策树的子函数进行运行时间分析,从而确定信息增益率计算的复杂性为限制算法速度的关键因素。针对此计算瓶颈,结合决策树算法在子节点分割以及最优分裂属性选择等方面的并行性,纵向划分数据,构建了并行的C4.5决策树,并利用MATLAB并行计算池功能以及SPMD设计实现。对并行后决策树运行时间验证结果表明,将C4.5决策树并行化后,并行决策树的构建时间显著缩短,实现了算法的加速。     

MapReduce框架下的朴素贝叶斯算法并行化研究

研究朴素贝叶斯算法MapReduce的并行实现方法, 针对传统单点串行算法在面对大规模数据或者参与分类的属性较多时效率低甚至无力承载大规模运算, 以及难以满足人们处理海量数据的需求等问题, 本文在朴素贝叶斯基本理论和MapReduce框架的基础上, 提出了一种基于MapReduce的高效、廉价的并行化方法. 通过实验表明这种方法在面对大规模数据时能有效提高算法的效率, 满足人们处理海量数据的需求.     

并行构件非功能属性研究

扩展了CCA并行构件体系结构,首先定义了一个并行构件非功能属性的一个最小集合,然后实现了对这些属性进行管理的非功能构件。定义了与这些非功能属性相关的接口。并行构件可以有选择地提供这些接口。并行构件向非功能构件注册自己的属性,然后通过非功能接口向非功能构件提供相关信息。为了最优化并行构件的实现,构件开发者需要实现属性管理中属于特定构件的部分,这部分内容在非功能接口中实现。非功能构件调用并行构件的非功能接口,对并行构件的非功能属性进行统一的管理。这种方法提高了并行构件运行的性能,并且为管理并行构件的执行提供了一种简便的方法。     

应用于地理信息数据自动分类的高性能聚类算法

针对现有地理信息数据分类不能体现数据归属的多类别共存性问题,提出一种使用聚类和并行计算技术提高数据分类的有效性和效率的并行地理信息数据聚类算法,并实现相应的数据自动分类系统。采用文本向量建模和抽取数据的类别特征,然后采用基于GPU的并行k-means聚类算法对数据进行类别划分。实验表明,设计的并行聚类算法体现了特征属性归属的多类别交叉性,具有较好的运行性能和扩展性。     

一种基于属性分解的FCM融合聚类算法

针对传统模糊C均值聚类算法只能发现"类球状"簇和对分量属性数据敏感的缺点,提出一种基于FCM的属性分解聚类再融合的分类算法。该算法将信息融合的思想应用于聚类算法,先在每个分量属性维度进行聚类,然后对各属性的聚类结果进行融合分析并得到聚类结果。独立对每个分量属性聚类的思想为算法的并行实现提供便利。实验结果表明,该算法不但能有效提高聚类的准确度,而且不需要提前对数据进行归一化处理,在分量属性量测数据存在偏差时仍然表现出良好的鲁棒性。     

基于Hadoop的多维关联规则挖掘算法研究及应用

传统的Apriori算法要多次扫描数据集,随着数据量的快速增长,传统的Apriori算法已经不能很好地适用于大数据分析,针对该情况设计了IPApriori算法。首先通过剪枝策略设计了一种适用于多维数据的IApriori算法,再将IApriori算法与Hadoop分布式框架相结合,实现了多维关联规则挖掘算法的并行化。将IPApriori算法运用到手机用户行为预测关联分析中,分析影响手机用户行为的一些主要因素,挖掘出手机用户行为与年龄维度、性别维度、时间维度、地点维度和手机品牌维度属性之间可能存在的某种关联。最后通过实验证明,算法的并行化和建立结构的方法可以降低系统的I/O负荷,提高算法的执行效率。     

基于属性树的并行化增量式动态属性约简算法

传统增量算法主要侧重于从更新近似的角度进行属性约简,但在处理大规模数据集时需要评估所有属性并反复计算重要度,提升时间复杂度,降低效率.针对上述问题,文中提出基于属性树的并行化增量加速策略,关键步骤是将所有属性聚类成多棵属性树进行并行化动态属性评估.首先,根据属性树相关性度量选择合适的属性树进行属性评估,降低时间复杂度.再增加分支系数至停止准则中,随着分支深度的增加进行动态增加,可使算法在达到最大阈值后自主跳出循环,有效避免原先的冗余计算,提高效率.基于上述策略,提出基于属性树的增量属性约简算法,同时与Spark并行机制结合,设计基于属性树的并行化增量式动态属性约简算法.在多个数据集上的广泛实验表明,文中算法在保持分类性能的同时,可提高动态变化数据集约简的搜索效率,具有较好的性能优势.