基于Hadoop的邻域粗糙集快速属性约简方法

摘要

本发明公开了一种基于Hadoop的邻域粗糙集快速属性约简方法，包括a)建立基于Hadoop的分布式平台、b)邻域粗糙集定义、c)生成候选集、d)计算每个属性的重要度、e)选择重要度最大的属性加入到候选集、f)判断是否满足停止条件、g)保存特征选择的状态等步骤。本发明基于Hadoop分布式平台对并行的数据挖掘算法并行化进行分析，实现了邻域粗糙集属性约简算法的并行化，并行后的属性约简大大降低了时间复杂度，执行中间过程大大减少了中间结果的输出，提高了大规模数据的分析效率，从而将纷繁多样的海量数据转换成具有信息和商业价值的可用数据，进而完成数据挖掘和分析优化。

主权项

1.基于Hadoop的邻域粗糙集快速属性约简方法，其特征在于：包括以下步骤：a)建立基于Hadoop的分布式平台：建立HDFS分布式文件系统和MapReduce并行编程模型；所述HDFS分布式文件系统采用主从结构体系，由一个管理者和多个工作者构成，管理者管理文件系统的命名空间，维护文件系统树及整棵树内所有的文件和目录，工作者是文件系统的工作节点，根据需要存储并检索数据块，并且定期向管理者发送“心跳”报告，如果管理者在指定的时间段内没有收到工作者的“心跳”报告，则管理者启动容错机制对其进行处理；所述MapReduce并行编程模型将任务分成若干小任务去执行，每个小任务对集群节点本地存储的数据块进行处理；b)邻域粗糙集定义：在混合属性的数据库中，将一个邻域信息系统表示为：NIS＝＜U,A,V,f＞，式中：U是样例的集合，A是属性的集合，V是属性的值域，f是信息函数：U×A→V；设B是一个数值特征子集，则对于B，x的邻域是${\delta }_B\left(x\right)=\left\{x_i\right|x_i\in {\delta }_a\left(x\right),\forall a\in B\};$c)生成候选集：采用搜索策略生成一组待评价特征子集作为候选集，最初的候选集是空集或者特征全集或者随机产生的一组特征子集；d)计算每个属性的重要度：建立一个Mapper类和一个Reducer类，Mapper类读入样本数据，并将样本集合按照已选的属性集合为每个待评价的属性分配对应的样本集合作为Reducer类的输入，每个reducer只接受一个属性的所有样本子集，并在一个reducer之内通过组合键数据进行分区，Reducer任务的个数就是待评价的属性个数，对应的样本集合将以不同的属性编号输入到对应的Reducer任务中，多个Reducer任务并行执行，给定一个邻域决策系统NDT＝＜U,AUD,V,f＞，定义属性a的重要度计算为SIG(a,B,D)＝γ_B(D)-γ_B-a(D)，SIG(a,B,D)反应了属性a对决策属性D的重要程度，用来评价每个属性的重要度；e)选择重要度最大的属性加入到候选集：将d)步骤中的输出作为本步骤的输入，与之前最大的重要度值进行比较，如果当前属性的重要度值更高，则把当前的属性作为最好的特征子集添加到候选集中；f)判断是否满足停止条件：采用特征产生过程和评价过程作为停止条件，特征产生过程的停止条件有两种：一种是判断是否已经选择了预先定义的特征个数，另一种是判断是否已经达到预先定义的迭代个数；评价过程的停止条件有两种：一种是判断是否添加或剔除了一个特征将产生一个更好的特征子集，另一种是判断是否最优特征子集已经得到；g)保存特征选择的状态：分别保存已选择的特征集合和未选择的特征集合，d)步骤中对未选择的特征集合计算重要度，f)步骤中已选择的特征集合和未选择的特征集合进行更新，最后将已选择的特征集合和未选择的特征集合作为结果输出。