-
随着互联网的发展，各种数据呈指数型增长，Web上的数据量以exabytes(1018)和zettabytes(1021)为单位进行衡量，到2025年预测互联网的数据量将超过全世界人口的大脑容量，数据的快速增长是由于数字传感器、通信、计算和存储方面的进步造成了巨大的数据集[1-2].大数据的特征体现在4V方面，即体积、速度、品种和准确度，而提取有用的知识和信息变得越来越困难，因此对于大数据的分类分析越来越重要[3-5].
决策树是数据挖掘中使用最广泛的分类方法之一，能够达到良好的精度水平.决策树的一个特殊优点是与归纳有关，这通常需要对有限数量的参数进行操作[5].处理不确定数据时引入模糊决策树，模糊决策树中的每个节点都是由模糊集来表征的，因此每个实例可以激活不同的分支并到达多个叶子[6].但是，决策树的缺点是对轻微噪声非常敏感，因此在噪声大数据中效果并不好.
目前，随机森林被认为是最有效和最流行的分类工具之一[7-8].随机森林的基本算法包含2个随机元素：bagging(即不同的数据集，从整个数据集中取而代之，用于学习每个不同的树)以及随机属性选择.在森林中的每个树中选择可用属性的子集，并确定相对最佳分割[9].模糊随机森林具有更高的预测精度和更少的参数方差，比模糊规则的系统更准确，并且比清晰的随机森林更能容忍噪声[10].
现有普通分类方法有卷积神经网络、支持向量机、K-最近邻、直方图条件熵、堆叠自编码器和粒子群优化算法等[11-12]，但是这些方法对于大数据普适性并不好，需要利用分布式计算重新设计支持算法来处理这样具有挑战性的数据集.在这种情况下，MapReduce框架被证明是一个非常好的选择，但是其他分类算法在MapReduce框架中的分布式实现对大数据的噪声属性却没有较好的效果.文献[13]中提出一种基于改进Tri-Training算法的健康大数据分类模型，该方法通过更改扩充样本训练集选取方式，剔除可能提高分类误差的样本，解决了随机选取基础分类器的扩充训练样本集会引入噪声这一问题.但是这种方法是避免训练过程引入噪声问题，对于含噪声的大数据处理效果并不好.文献[14]提出一种新的分布式最近邻分类中的原型简化分类方法，旨在将原始训练数据集表示为减少的实例数，加快分类过程并降低最近邻规则的存储要求和对噪声的敏感性，但是该方法对噪声大数据的分类精度并不高.
现有数据分类方法具有无法适应大数据分类及噪声大数据分类精度不高的问题.针对这些问题，本文提出了一种在MapReduce中实现的高度随机模糊森林算法，并给出了MapReduce下的分布式实现.模糊随机森林的生成需要一个初步的bagging步骤，在整个学习数据集上应用采样，以便得到与森林中模糊树的数量一样多的单个学习数据集.在C4.5决策树上构建模糊树的连续属性分区，并在节点创建时生成模糊分区.该算法能够更好地分配计算工作量，优化并节省计算费用，同时不会破坏整体集合的准确性.实验结果表明，在训练数据存在属性噪声的情况下，所提出的算法比现有方法更有效.
HTML
-
Mapreduce是一个分布式运算程序的编程框架，其核心功能是在hadoop集群中分布式并行运行用户的业务代码. Mapreduce框架具有以下几个优点：①突破大数据硬件资源限制；②降低了集群上分布式运行的开发难度和复杂度；③将用户工作重点由计算复杂度转移至业务开发上. Mapreduce程序完整运行需要3个进程，如表 1所示.
MapReduce分布式运行完成一个任务代码，需要经过4个部分，分别是程序启动、Maptask进程、MRAppMaster过程和Reducetask进程，其核心部分是Maptask进程和Reducetask进程. Maptask过程如图 1所示.
由图 1可知Maptask的过程为：经过对输入文件划分，得到大小固定的多个InputSplit，解析InputSplit中的记录为键值对〈key，value〉，根据〈key，value〉对调用map，结果输出0或多个〈key，value〉对.对于输出的〈key，value〉对按照一定的key规则进行分区，得到分区的数量即为Reducer任务数量，之后对分区中〈key，value〉对进行排序，最终对数据进行归约处理，并将处理后的数据输出. 图 2给给出了Reducer任务的过程图.
由图 2可知Reducer任务的过程为：复制多个Mapper任务〈key，value〉对到Reducer本地，对所有复制〈key，value〉对数据进行合并与排序，之后每个〈key，value〉对调用reduce，将每次调用reduce的输出〈key，value〉对输出到HDFS文件中.
-
① 用于生成模糊随机森林的模糊决策树学习算法，②高度随机模糊森林(highly random fuzzy forest，HRFF)算法，③MapReduce框架下HRFF算法的分布式实现.
-
模糊决策树生成方法是基于最佳想法来选择最佳属性，在给定训练样例组每个节点处的分割.为了测量一组例子中的杂质，首先需要确定模糊集的基数，清晰集的基数只是其元素的数量，模糊集S的基数是其中所有元素隶属度值的总和，可表示为
其中，μS(e)表示e到S的隶属度值.通过上式可以来计算模糊集S的模糊熵.
符号S→c表示包含c类所有样本集合S的子集，S中的样本越不纯，熵值越高.此外，根据该属性对样本进行排序，将属性的模糊信息增益定义为模糊熵的减少.假设在属性x的模糊划分方面将集合S分成模糊子集S1，S2，…，属性x相对于S的模糊信息增益可写为
其中，Hf(S)表示S的模糊熵.在每个子节点处，选择具有最大模糊信息增益的属性，然后在所有子节点上递归调用构建过程及其相应的数据，包含数据项和相关成员隶属度的列表.根节点中的所有成员隶属度值都设置为1，这意味着根节点上的默认成员隶属函数始终返回1.
算法1中给出了构建单个模糊决策树的基本算法，构建模糊树过程通过调用find-best-attribute开始.
本算法根据模糊信息增益确定了在当前节点划分数据的最佳属性.评估遍历所有输入属性，并根据计算出的信息增益选择其中最好的属性.
当构建过程到达叶节点时，计算该节点的权重，可以将权重视为表示该节点中各种类的概率.基于隶属度和分配给叶节点数据项的类来计算权重. c类的权重是通过式(4)获得的.
使用构建模糊决策树来实现分类过程，算法2中给出了分类过程，提供给此过程的参数是分类已确定其成员隶属的新样本，由data的单个变量表示.成员隶属度值设置为1. total-weights变量通过引用传递，应该包含过程结束时每个类的权重.
对于每个子节点，当前成员隶属度值使用子成员membership-f返回的值进行t-normed，得到子节点的数据隶属度.当执行分类时必须考虑所有子节点，而不仅仅是μ≥0.5的子节点，total-weights变量也被传递给子节点以便更新.
通过树遍历一个新样本，直到抵达一个叶节点.在叶节点上将当前隶属度通过t-normed赋给每个类权重，随后这些值被添加到总权重中的适当值.通过这个过程，多叶节点可以在分类任务中被激活，每个叶节点的结果被添加到最终结果以决定不同类样本的隶属度.
-
本文提出的高度随机模糊森林(HRFF)算法遵循随机森林算法的基本思想，使用随机选择的训练样本和特征来构建集合的基础模型.这种随机数据选择有利于减轻大量数据项的计算负担，并避免高维中的特征选择问题.
HRFF算法的特性在于引入输入属性模糊分区的随机化，这会影响模糊决策树构造的结果.算法基本原则是：通过属性随机模糊划分学习的单个树不能表现出最佳性能，所有树共同补偿才能产生高的分类精度.此外，采用随机分区的计算开销降低，这在大数据处理中尤为重要.
下面给出输入属性随机模糊划分的细节，由于分类特征的划分显而易见，本文只讨论数值属性的模糊划分，指定几个模糊集隶属函数来将属性的域划分为一组模糊区域.这意味着一个样本可以遍历几个子节点，具体取决于它对模糊区域的成员隶属度值，选择梯形隶属函数，可以通过点p进行参数化.
在图 3中，可以看到使用p=4，q=0.5生成的隶属函数，属性的域为U=[0, 10]，这里仅定义了两个隶属函数，以加快决策树构建和通过非常小的子节点的遍历过程.用于确定梯形函数确切形状的点a和b被放置在各自段的特定百分比q∈[0, 1]上，即a=p－q(p－Umin)，b=p+q(Umax－p).为了减少学习算法的运行时间，如果该样本具有相对于相关模糊区域μ≥0.5的隶属度值，只对子节点传递一个样本.
原则上，有可能通过寻找参数p的最佳值来优化模糊分区，但是当数据集很大时，会导致非常高的计算成本.另一方面，随机森林的关键思想是即使单个决策树可能无法正确分类，基础模型的组合也会产生统计上准确的结果.同样，可以应用类似想法来支持在属性的模糊分区中随机选择参数p的值.尽管在大多数情况下随机分区可能导致单个决策树的性能较差，但整体集合将通过对来自单个决策树的结果求平均来做出正确的决策.因此，在本文HRFF算法中，学习集合中的每个单个模糊决策树的同时，将随机值分配给每个节点处的参数p.
-
将本文算法扩展到大数据集上，最广泛使用的方法是在计算机上分布执行，本文选择MapReduce作为执行此操作的框架.
首先描述标准分布方法，将整个数据集分成几部分，因为整个数据集太大而无法通过树学习程序进行处理.用R表示数据部分的数量.如果数据项的原始计数是D，则每个R部分获得
$\frac{D}{R}$ 的数据项，然后利用每个R部分生成自己的随机森林.另外一个参数是每个森林中的树木数量，本文用V表示.所以，总的来说会有RV个树.在算法3中给出了mapper和reducer函数.首先，对输入数据进行了一些初步假设.输入文件中的每一行都标记为训练数据或验证数据，本文指定如果行以字母v开头，则该行是验证行，否则默认为训练行.本算法在建立随机模糊森林的同时对结果进行验证，这样做是为了每个工作者获得一些训练数据及所有验证数据，以便可以立即预测所有验证样本的类.
算法3中显示的mapper逐行读取文件，如果遇到训练行则会发出一个在[0，R]范围内的随机key，其中只有一个reducer得到该key，如果mapper遇到验证行，则会向所有reducers发出key.然后，reducers运行reduce函数，获取与其id相关的所有行，reducer循环遍历与之关联的所有行，并将其放入validation-data和training-data组中.使用training-data，用V树构建随机森林，其中V是算法的参数，reducer会预测每条线的隶属度.
由于每个reducer为每个数据项生成单个预测，因此对于每个单独的项总共有R个预测，为了能够组合这些预测，将使用此reducer作为下一步的mapper，然后以数据项为key进行预测，能够将所有预测组合在一个数据项下.算法4中给出了另一个reducer算法，能够将来自所有随机森林的预测组合成一个整体预测，这就为每个单独的类加上了预测，最后的决定是隶属度值最高的类.
2.1. 单个模糊决策树
2.2. 高度随机的模糊森林算法
2.3. HRFF的MapReduce分布式实现
-
本文实验的大数据集及通过在其上运行所选算法获得的结果见表 2.
表 2给出了5个大数据集，所有这些数据集都来自UCI机器学习库. 表 2中前4个数据集都是真实的数据集，最后一个是基于HIGGS数据集人工生成的，通过获取HIGGS数据集中的每个项目并生成4个新项目来生成此人工数据集.
通过运行模糊随机森林(Fuzzy Random Forest，FRF)和高度随机模糊森林HRFF算法，本文使用准确度来比较算法的性能.实验将在数据中引入一些噪声，用一定的概率分布对其进行扰动.扰动以这样的方式完成，即它增加或减去该值的某个百分比.所以，以一定的概率应用变换(1+q)x→x，实数q在[-Q，Q]范围内，其中Q∈[0, 1].参数Q确定扰动的强度，在本文实验中将Q设置为扰动的概率(表 3).
在表 3中可以看到对于大数据集的分类结果.由此可以得出，本文的算法优于FRF，在Q=0.4的干扰下，本文算法依然有较好的分类准确性.为了证明本文算法的可扩展性，选择SUSY数据集样本进行实验.理论上，本文算法应该与MapReduce可执行核的数量成线性关系.
图 4给出表 4中数据的绘制图，可以得到本文算法几乎与节点的大小成线性关系，这表明本文算法适用于具有足够计算能力的更大数据集.
-
本文提出了高度随机模糊森林算法来处理大数据分类问题，并给出了HRFF在MapReduce框架下的分布式实现.该算法的基本思想是在分割数值属性时随机化模糊分区，且能够更好地分配计算工作量，允许模糊分区的随机性用于模糊决策树的输入变量.实验结果表明，在具有属性噪声的情况下，本文HRFF算法比FRF算法分类更准确.通过改变通常的数据分布过程来改进算法的并行化功能，HRFF也可以很好地适应并行处理器的数量.未来工作将研究在噪声影响下，提高分类精度的方法.
DownLoad: