《工业控制计算机｝２０１４年第２７卷第２期 数据挖掘分类算法优化非平衡采样样本的研究与应用 吴 琼 周维民 李运田 （上海大学机电工程与自动化学院，上海２０００７２） 摘 要 主要是针对采样过程中的非平衡数据进行处理、分类，改变传统算法在其处理过程中的分类倾向性。结合数据挖掘中 多种分类算法构建的混合模型进行分类处理非平衡采样数据，并将优化的结果进行比较。 关键词：分类算法，非平衡性，Ａｄａｂｏｏｓｔ，ＲａｎｄｏｍＦｏｒｅｓｔｓ，ＳＶＭ，ＲＯＣ Ａｂｓｔｒａｃｔ Ｔｈｉｓ ｐａｐｅｒ ｉｓ ｍａｉｎｌｙ ｆｏｒ ｎｏｎ－ｅｑｕｉｌｉｂｒｉｕｍ ｓａｍｐｌｉｎｇ ｄａｔａ ｔｏ ｃｌａｓｓｉｆｙ ａｎｄ ｄｅａｌ ｗｉｔｈ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｂｉａｓ ｉｎ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏ— ｒｉｔｈｍ．Ｔｈｉｓ ｐａｐｅｒ ｃｏｍｂｉｎｅｓ ｗｉｔｈ ａ ｖａｒｉｅｔｙ ｏｆ ｄａｔａ ｍｉｎｉｎｇ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｔｏ ｃｏｎｓｔｒｕｃｔ ｈｙｂｒｉｄ ｍｏｄｅｌ ｔｏ ｃｌａｓｓｉｆｙ ｕｎｂａｌ— ａｎｃｅｄ ｓａｍｐｌｉｎｇ ｄａｔａ．ａｎｄ ｆｉｎａｌｌｙ ｃｏｍｐａｒｅｓ ｔｈｅ ｒｅｓｕｌｔ． Ｋｅｙｗｏｒｄｓ：ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ｕｎｂａｌａｎｃｅｄ ｓａｍｐｌｉｎｇ ｄａｔａ．Ａｄａｂｏｏｓｔ ＲａｎｄｏｍＦｏｒｅｓｔｓ ＳＶＭ．ＲＯＣ 非平衡采样样本的分类问题是指数据采样样本中某些类的 数量占的比重比较大，而其它类样本数量比率比较低，我们将数 量比重比较大的样本称为多数样本，数量比较少的样本称为少 数样本。虽然现有的分类研究可以取得较好的分类效果，但是它 步骤一：输入：给定训练集Ｄ＝｛（ｘ ，Ｙ ），（Ｘ２，Ｙ２），．…（Ｘ ， ｙ ）｝，ｉ＝１，２，３…ｎ其中ｘｉ∈Ｘ，Ｙ。∈Ｙ＝｛１，－１｝ 步骤二：初始化：对样本的权值进行初始化： ‘ｏ ７（ｉ）＝１／ｎ； （１） 们的缺陷在于假设训练的数据集是平衡的，这一假设往往是不 成立的。然而在数据挖掘过程中，少数样本往往对科研价值起到 了至关重要的作用。例如医疗诊断、石油泄漏等领域。 步骤三：循环ｔ＝１，２…Ｔ； １）通过权重（Ｉ） （ｉ）在Ｄ中采样得到弱分类器Ｃ 的训练集进 行训练； 鉴于非平衡分类研究的重要性，目前国内外学者进行了大 ２）对于分类器Ｃ ：×一Ｙ，计算其训练误差８ｋ： ８ｔ＝ ∞ｆ（ｆ） ≠ｈｉ（ ） （２） 量的研究，主要有下面几个方面：①改变数据的分布，常见的有 随机向上采样，随机向下采样。其中比较成熟的做法是ＳＭＯＴＥ 技术，采用少数类样本合成重采样技术将非平衡数据通过差值 来改变数据的分布情况从而影响分类效果。②主要从算法层面 上进行改进，例如在传统的分类算法的基础上引入代价敏感因 以及正确识别正样本的权值和： ｐ ＝∑∞ （『） ：１， （ ）＝７ ３）设置弱分类器Ｃ 的权值： （３） 子进行改进。③从设计新的评价准则方面进行研究，通常是通过 引入混淆矩阵如Ｆ值来进行。 本文主要是将Ａｄａｂｏｏｓｔ算法与ＲａｎｄｏｍＦｏｒｓｅｔｓ算法组 成的混合算法和Ａｄａｂｏｏｓｔ算法与ＳＶＭ组成的混合算法进行 比较，通过ＲＯＣ曲线作为评价指标得出最优化的算法。 １ Ａｄａｂｏｏｓｔ＋ＲａｎｄｏｍＦｏｒｅｓｔｓ混合算法 １．１ ＡｄａＢｏｏｓｔ算法 ； （孚）＋ 其中ｋ为一个常数，其取值满足增加分类准确率。 ４）更新训练样本权重： （４） （５） （『）＝半ｘ ｅ ａ＇ｈｔ：（ｘｊ）＝ ｙ￣＝Ｔｅｔ（ｉ）ｅ－￣＇ｈ＇（ｘ＇ｌｙ （ｘ）≠Ａｄａｂｏｏｓｔ算法的具体实现：将每个训练样本赋予一个权 重，该权重表明它被某个分量分类器训练的概率。训练样本的初 始权重相等。如果某个样本被当前的分类器分类准确则降低其 权重，那么在构造下一个分量分类器的训练集时，它被选中的概 率就会被降低。反之，分类错误时，则会相应提高其权重，它人选 下一个分量分类器的训练集的概率会增加。因此对于第ｔ次的 其中。Ｚ 为一个归一化因子，即： ∑∞，（『）ｅ ，；１ ’ （６） 循环结束。 步骤四：输出：用迭代Ｔ次得到的分类器分别对样本点进行分 类，最终分类结果经过强分类器得到，强分类器的判别函数值为： Ｔ 迭代操作，需要根据第ｔ一１次训练结果设置相应的权重来选取 新的训练集，对于第ｔ一１次分类中分类器分类正确的样本降低 Ｈ（ｘ）＝ｓｉｇｎ［ ａ，ｈ （ｘ）］ ｔ＝１ （７） 其权重，分类错误的样本提高其权重，再进行训练分类器Ｃ ，再 根据第ｔ次分类的结果训练分类器Ｃ ＋１，依次迭代下去，直到满 足结束条件程序终止。 由（４）式可知，Ｐ 是第ｔ次循环弱分类器中能正确识别的正 样本的权值和，它代表弱分类器ｈ 对正样本的识别能力，而 ｋｅｐ 是关于Ｐｔ的增函数，这样求得新的加权参数。因此只有那 些对正样本识别能力更强的分类器才会具有更大的权值。 １．２ ＲａｎｄｏｍＦｏｒｅｓｔｓ算法 具体算法步骤如下： 输入采样数据集的格式为（× ，Ｙｉ），其中Ｘｉ表示原始训练集 中的样本，ｙｉ表示各样本的类标记Ｙ．∈（１，一１），ｉ＝１，２…ｎ，ｎ表 示给定的样本数目。 （ｉ）为第ｔ次迭代样本Ｘｉ的权重。ｈｔ是分量 分类器Ｃ 的决策函数，ｈｌ（ｘ ）是由分量分类器Ｃ 给出的对样本 Ｘ，的类标记。具体步骤如下： ＲａｎｄｏｍＦｏｒｅｓｔｓ算法也叫随机森林算法，该算法是ＣＡＲＴ 算法的改进算法，ＲａｎｄｏｍＦｏｒｅｓｔｓ算法包含多个决策树分类 器，其输出的类别由个别树输出的类别的众数来决定，也就是采 用投票法得到。但因为ＲａｎｄｏｍＦｏｒｅｓｔｓ算法分类过程中采用了 数据挖掘分类算法优化非平衡采样样本的研究与应用 两个随机性，这有效避免了采样样本的过分拟合。其随机性体现 在两个方面：①采用Ｂａｇｇｉｎｇ算法随机选取样本；②随机选取 分裂属性集；假设训练样本有ｎ个属性，指定一个属性的数量为 ｍ＜ｎ或ｍ＝ｎ，对于每个内部节点，从ｎ个属性中随机抽取ｍ个 属性作为分裂属性集，以这ｍ个属性上最好的分裂方式对结点 进行分裂。 １．３ Ａｄａｂｏｏｓｔ＋ＲａｎｄｏｍＦｏｒｅｓｔｓ混合算法 混合算法主要基于Ａｄａｂｏｏｓｔ算法的实现，具体步骤以及 实现参考ＡｄａＢｏｏｓｔ算法步骤，其中Ａｄａｂｏｏｓｔ算法中的弱分类 器选用ＲａｎｄｏｍＦｏｒｅｓｔｓ分类器。 ２ Ａｄａｂｏｏｓｔ＋ＳＶＭ算法 ２．１ ＳＶＭ算法 ＳＶＭ（Ｓｕｐｐｏ￣Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅｓ）支持向量机是一个尝试 在两组数据集中建立最大间隔超平面来进行线性划分的分类 器，这个最大间隔超平面由一组小的子集来确定称为支持向量。 对于线性可分的数据集，ＳＶＭ会尝试找到一个最大间隔分类 面，最大间隔分类面将数据集中的点分为两个部分，并且使得被 划分的数据集中点距离分类面尽可能远，这样可以达到分类误 差尽可能小的目的。支持向量机也可以对线性不可分数据进行 分类，通过核函数将低维空间中向量转换到高维空间中，从而在 高维空间中求出最大间隔超平面。 ２．２ ＡｄａＢｏｏｓｔ＋ＳＶＭ混合算法 根据ＡｄａＢｏｏｓｔ算法流程，其中弱分类器采用ＳＶＭ分类 器，ＳＶＭ分类器中核函数采用参数为 的径向基函数。 在混合算法中ＡｄａＢｏｏｓｔ算法中采用级联的结构组成串行分 类器，即当训练样本进行分类时，只有当前一级的分类器判决为正 的样本时该训练样本会被送到下一级的分类器中重新进行分类， 当训练样本经过分类器被判断为负样本时就直接输出。最终的结 果是每一级都被判断为正样本的训练数据。示意图如图１： ７８ 基于ＷＳＮ的实验室环境远程监测系统 房问内部署一个协调器节点和ＧＰＲＳ模块相连。对ＺｉｇＢｅｅ网 络的距离和丢包率进行了测试，测试时每隔８００ｍｓ采集一次数 据，数据长度两个字节，分别采集温度、湿度和烟雾三项数据。在 无障碍物和有墙壁障碍物两种情况下测试了丢包率。丢包率与 距离的关系曲线如图５所示。 图２传感器终端节点框图 ／ ３系统软件设计 ／ ３．１检测节点软件设计 检测节点在整个系统中起到数据的采集和传输的作用，其工 作的主要过程为：首先对节点进行初始化，也就是初始化 ． ０ ／ ＿’—————■—一 ２０ ４０ ６０ ＣＣ２４３０，其工作包括定义系统的时钟信号、工作频率、电源管理 方式、ＺｉｇＢｅｅ网络层和ＭＡＣ层的参数及Ｉ／Ｏ接口和外设的初始 距离６ｌＩ） 图５丢包率与距离的关系 化。然后发送加入网络信号，等待网络协调器响应。若没有接收到 有测试结果可知，在无障碍条件下的数据丢包率相对较低， 但在有墙壁障碍条件下，当节点之间的距离大于１０ｍ时，数据 应答，则终端系统继续发送入网信号，若加入网络成功，则等待中 断，响应相应的中断。检测节点软件流程图如图３所示＿３ 。 ３．２网关节点模块软件设计 网关节点上电后，需要进行硬件的初始化，建立ＺｉｇＢｅｅ网 传输的丢包率大大上升，说明墙壁对无线数据的传输的影响较 大。在部署时也将分布在不同房间的两个节点距离尽量缩短。在 实验室环境中，由于面积不是很大，通过合理的部署，可以获得 可靠的数据传输率。 （２）ＧＰＲＳ的数据延迟 络。并设置网络的ＰＡＮ ＩＤ，等待节点加入网络；在有传感器节 点加入网络之后，接收传感器节点发送的传感器数据，协调器通 过ＲＳ２３２与ＧＰＲＳ模块相连，将来自协调器的数据通过短信的 方式发送到设定的手机号码上。节点中嵌人的软件流程如图４。 ６ ５ ＧＰＲＳ技术相对成熟，具有较强的数据纠错能力。能够可靠 地实现数据的远距离传输。数据延迟时间一般在２ｓ之内，在对 于数据的实时性要求不是太高的检测系统中，这个延迟时间是 可以接受的。 （３）系统综合测试 一巷糙 巾 ４ ３ ２ １ ０ 系统上电 系统Ｌ电 硬件仞始化 ◆ 螋件初始化 仞贻化网络，建 立信道。 在实验室环境中，为降低电池供电节点的功耗，将数据的采 集时间间隔设为２０ｓ，在每个房间的门后和房屋中间位置部署 三个节点。系统数据包的整体丢失率在０．５％以下，满足实验室 的检测要求。 ５ ／ＪＮＪ，．ＺｉｇＢｅｅ网络 卜一 Ｎ 有节点抽入？ 结束语 ＼／采集传感器数据 主 为新加入节点分 配地址 基于ＷＳＮ的实验室环境远程监测系统，利用传感器技术、 近距离无线网络ＺｉｇＢｅｅ技术和远程无线通信技术ＧＰＲＳ，实现 了实验室环境的远程监测，通过对温度、烟雾等环境物理参数的 检测，可以及时发现存在的安全隐患。测试结果表明，系统在丢 包率、实时性等方面满足远程监测的要求。 参考文献 ［１］李文仲，段朝玉，等ＺｉｇＢｅｅ无线网络技术入门与实践［Ｍ］．北京：北 京航空航天大学出版社，２００７ ◆ 发送数据 二二Ｅ 接收来自于传感 器节点的数据 ’ 延 ２０Ｓ 二二［发送数据 ＧＰＲＳ通过串｜］ 图３传感器节点流程图 图４协调器流程闰 ４系统运行效果及分析 ［２］韩华峰，杜克明，等．基于ＺｉｇＢｅｅ网络的温室环境远程监控系统设 计与应用［Ｊ］．农业工程学报，２００９，２５（７）：１５８－１６３ ［３］汪玉风，姜林基于ＺｉｇＢｅｅ和ＧＰＲＳ的无线抄表系统［Ｊ］．仪表技术 与传感器，２０１０（１０）：４９－５１ ［收稿日期：２０１３．１１．２］ （１）丢包率与通信距离的测试 首先测试ＺｉｇＢｅｅ网络的丢包率，将７个节点分别部署在 二个不同的房间内，每个房间中放置三个传感器节点，其中一个 （上接第６４页） Ｍｉｎｏｒｉｔｙ Ｏｖｅｒ—ｓａｍｐｌｉｎｇ Ｔｅｃｈｎｉｑｕｅ［Ｊ］Ｊｏｕｒｎａｌ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎ— 参考文献 ［１］Ｘｕｃｈｕｎ Ｌｉ，Ｌｅｉ Ｗａｎｇ，Ｅｒｉｃ Ｓｕｎｇ，ＡｄａＢｏｏｓｔ ｗｉｔｈ ＳＶＭ－ｂａｓｅｄ ｔｅｌｌｉｇｅｎｃｅ Ｒｅｓｅａｒｃｈ．２００２．１６（１）：３２１—３５７ ［５］明均仁肖凯基于Ｒ语言的面向需水预测的随机森林方法［Ｊ］．统计 与决策，２０１２（９）：８１－８３ ｃｏｍｐｏｎｅｎｔ ｃｌａｓｓｉｆｉｅｒｓ［Ｊ］．Ｅｎｇｉｎｅｅｒｉｎｇ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ２１（２００８）７８５—７９５ ［２］韩敏，朱新荣．不平衡数据分类的混合算法［Ｊ］．控制理论与应用． ２０１ １，２８（１０）：１４８５—１４８９ ［６］郭虎升，元慧，王文剑．处理非平衡数据的粒度ＳＶＭ学习算法［Ｊ］．计 算机工程，２０１０，３６（２）：１８１—１８３ ［７］Ｂａｕｅｒ，Ｅ，Ｋｏｈａｖｉ，Ｒ．，１９９９．Ａｎ ｅｍｐｉｒｉｃａｌ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｖｏｔ— ｉｎｇ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ：ｂａｇｇｉｎｇ，ｂｏｏｓｔｉｎｇ，ａｎｄ ｖａｒｉａｎｔｓ． ［３］王晓丹，孙东延一种基于ＡｄａＢｏｏｓｔ的ＳＶＭ分类器［Ｊ］．空军工程大 学学报，２００６，７（６）：５４—５７ ［４］Ｃｈａｗｌａ Ｎ Ｖ Ｂｏｗｙｅｒ Ｋ Ｗ．Ｈａｌ Ｌ Ｏ ｅｔｌ ａｌ ＳＭＯＴＥ：Ｓｙｎｔｈｅｔｉｃ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ ３６（１），１０５－１３９ ｆ收稿日期：２０１３ １１．１２］