云计算环境下的分类规则挖掘方法

摘要

本发明公开了一种云计算环境下的分类规则挖掘方法，其特征在于：采用由一个控制中心和多个从属服务器构成的主从式组织结构，首先由控制中心将待分类数据集划分为训练样本和测试样本，并将训练样本均匀划分为相同大小的各数据块分配到各处理单元上；然后由处理单元采用遗传算法训练数据块，得到分类的原子规则；最后由分类器约简原子规则，并选择满足分类精度要求的约简结果作为分类规则挖掘的最终结果。本发明适用于云计算环境下分布式数据存储上的数据分类，可进行云计算环境下数据分类任务的分布式并行处理，对云计算环境下海量数据的分类处理问题起到了积极的效果。

说明书

技术领域

本发明属于云计算环境下数据分析技术领域，具体涉及一种云计算环境下的分类规则挖 掘方法。

背景技术

分类技术研究是云计算环境下数据分析与管理的重要研究领域。一方面，分类是数据挖 掘重要的任务类型，云计算环境下的数据具有海量性、分布性和动态性等特征，这些特征给 云计算环境下的数据管理带来了挑战，通过分类规则挖掘对这些数据进行分析，有助于提高 云计算环境下海量数据分析与管理的效率。另一方面，云环境具有超大规模的存储和计算能 力，资源和结构具有动态伸缩性，并且通过虚拟化技术和庞大的资源池按需提供服务，使得 高效的数据分类成为可能。分类规则挖掘是数据分析管理中的重要任务，有助于更好地理解 云计算环境下的海量数据，辅助云计算环境下的运营决策；同时，云计算高性能的计算和存 储能力，为分类规则挖掘提供了高效运行的保障。因此，分类规则挖掘是云计算环境下的数 据分析处理的重要技术，其理论和应用的研究具有重要意义。

在分类规则挖掘技术的研究中，国内外学者提出了诸多解决方案，包括以贝叶斯法为代 表的统计学方法、以决策树法和规则归纳法为代表的及其学习方法，以及神经网络方法等， 这些方法应用于小规模静态数据集的分类规则挖掘时，具有较高的分类精度。然而这些方法 仍存在瓶颈问题，包括需要对数据集进行多次的扫描和排序，导致算法的低效；对噪声和确 实数据比较敏感，易出现过拟合；对于大训练集的可伸缩性不是很好等。特别在云计算环境 下，分布式海量数据集的大规模性和动态性，导致数据分类过程搜索空间和维度的激增，增 加了分类的计算复杂性，降低了传统分类方法的效率，因而现有的分类规则挖掘方法无法直 接应用于云计算环境中。

发明内容

为了解决上述问题，本发明克服现有技术的局限性，提供一种云计算环境下的分类规则 挖掘方法。本发明适用于云计算环境下分布式数据存储上的数据分类，可进行云计算环境下 数据分类任务的分布式并行处理，对云计算环境下海量数据的分类处理问题起到了积极的效 果。利用云计算环境下大规模计算节点的规模计算效应，有效提高云计算环境下海量数据分 类规则挖掘的效率；并通过主从式的组织结构和基于遗传算法的规则训练过程，解决分类规 则挖掘在云计算环境下的分布式实现。

本发明为解决技术问题采用如下技术方案：

本发明云计算环境下的分类规则挖掘方法的特点是：

所述云计算环境由多个分布式的服务器构成；在所述云计算环境下实施分类规则挖掘时， 采取主从式组织结构，所述主从式组织结构为设置一台服务器为控制中心，其它服务器为从 属服务器；由所述控制中心安排部署整个挖掘任务的执行、调度管理并协调各从属服务器的 操作；所述各从属服务器是任务的具体执行单元，所述分类规则挖掘方法按如下步骤进行：

a、由控制中心将待分类的数据集划分为训练样本和测试样本，对所述训练样本进行均匀 划分，得到相同大小的各数据块，为每个数据块指定一个执行分类挖掘任务的从属服务器作 为处理单元，将所述各数据块分配到对应的各处理单元上；

b、由所述处理单元采用遗传算法对分配得到的数据块实施用于分类的原子规则的训练， 将训练得到的原子规则存入缓冲区；

c、由所述控制中心对缓冲区内的原子规则进行划分，选择闲置的从属服务器作为分类器， 安排分类器进行原子规则的冗余约简，并检测约简结果的分类精度，筛选出满足分类精度要 求的约简结果，作为分类规则挖掘的最终结果。

本发明云计算环境下的分类规则挖掘方法的特点也在于：

所述步骤a的执行过程是：

控制中心在接到分类挖掘任务的请求后，将待分类的数据集划分为训练样本和测试样本， 根据用户所提出分类挖掘任务的要求以及训练样本的特征，搜索合适的从属服务器作为处理 单元，并将训练样本均匀划分成大小相同的数据块；设满足条件的处理单元数量为N，训练 样本大小为M，则所划分的数据块大小为M/N；

所述合适的从属服务器满足的条件是：存储空间不小于M/N，响应时间不大于用户所要 求的最晚时间；

控制中心访问所述训练样本，将划分所得的数据块复制到相应的处理单元上，并向处理 单元传递利用遗传算法训练原子规则的操作指令。

所述步骤b中的原子规则的训练过程是：

处理单元对构成数据块的每一条数据记录进行遗传编码，通过遗传操作的循环迭代生成 原子规则，将所述原子规则以<key，value>键值对的形式存入缓冲区，所述<key，value>键值对 中的key为类标签，value为该类标签下的原子规则；

控制中心周期性地读取缓冲区中的<key，value>键值对，生成<key，value list>键值对列表 存入缓冲区，所述<key，value list>键值对列表中的key为类标签，value list为该类标签下的原 子规则列表；

处理单元完成对数据块中所有数据记录的操作之后，向控制中心发送处理单元操作完毕 的消息。

所述步骤c按如下过程进行：

由控制中心搜索闲置的从属服务器作为分类器，分类器的个数为<key，value list>键值对列 表中key值的个数，每个分类器对应一个key值；控制中心将<key，value list>键值对列表中的 原子规则列表和测试样本中具有相同类标签的记录传送到的分类器中，并向分类器传递冗余 约简和分类精度检测的操作指令；

分类器对同一类标签下的多个相同原子规则只记录一次，删除冗余的原子规则，得到约 简后的原子规则；

分类器利用约简后的原子规则对测试样本进行分类，检测分类结果是否与测试样本的类 标签相一致，假设被原子规则a分类的测试样本中，有Y条记录的类标签与分类结果相一致， 有N条记录的类标签与分类结果不一致，则原子规则a的分类精度为Y/(Y+N)；假定用户提 出的分类挖掘任务要求中，分类精度要求为α，将所有分类精度不小于α的原子规则作为分 类规则挖掘的最终结果传送给控制中心；

控制中心汇总所有分类器生成的最终结果，再将汇总结果反馈至分类规则挖掘任务的请 求者。

与已有的数据分类方法相比，本发明的有益效果体现在：

1、本发明将海量数据的分类规则挖掘任务划分成多个子任务，分配到云计算环境中的大 规模服务器集群上处理，降低单个任务的计算复杂度，利用云计算服务器集群的规模计算效 应，显著提高整个分类规则挖掘任务的效率；

2、本发明中主从式组织结构，实现了云计算环境下任务的分配、调度与管理，为分类规 则挖掘提供了分布式的实现机制；同时，规则训练采用的遗传算法本身具有良好的并行性， 解决了常规分类技术在分布式环境中并行性差的问题。

附图说明

图1为本发明云计算环境下分类规则挖掘方法的原理图

图2为本发明中基于遗传操作循环迭代的原子规则生成的流程图

具体实施方式

在本实施例云计算环境下的分类规则挖掘方法中：

云计算环境由多个分布式的服务器构成；在云计算环境下实施分类规则挖掘时，采取主 从式组织结构，主从式组织结构为设置一台服务器为控制中心，其它服务器为从属服务器； 由控制中心安排部署整个挖掘任务的执行、调度管理并协调各从属服务器的操作；各从属服 务器是任务的具体执行单元。分类规则挖掘方法如图1所示，按如下步骤进行：

1、由控制中心将待分类的数据集划分为训练样本和测试样本，对训练样本进行均匀划分， 得到相同大小的各数据块，为每个数据块指定一个执行分类挖掘任务的从属服务器作为处理 单元，将各数据块分配到对应的各处理单元上；

2、由处理单元采用遗传算法对分配得到的数据块实施用于分类的原子规则的训练，将训 练得到的原子规则存入缓冲区；

3、由控制中心对缓冲区内的原子规则进行划分，选择闲置的从属服务器作为分类器，安 排分类器进行原子规则的冗余约简，并检测约简结果的分类精度，筛选出满足分类精度要求 的约简结果，作为分类规则挖掘的最终结果。

假设数据集由关系模式R(a₁,a₂,…,a_k)表示，其中a_i(i=1,2,…,k)为属性。将属性组<a₁,a₂,…, a_k>分为两部分，包括k-1个条件属性与1个类标签，属性a₁,a₂,…,a_k-1为条件属性，属性a_k为类标签。数据集中的每一条数据记录均为一个k维向量[c₁,c₂,…,c_k]，c_i为该数据记录中属 性a_i的取值。

原子规则的表现形式为：If(a₁=c₁)∧(a₂=c₂)∧…∧(a_k-1=c_k-1),Then a_k=c_k。

步骤1的执行过程是：

控制中心在接到分类挖掘任务的请求后，将待分类的数据集划分为训练样本和测试样本， 根据用户所提出分类挖掘任务的要求以及训练样本的特征，搜索合适的从属服务器作为处理 单元，并将训练样本均匀划分成大小相同的数据块；设满足条件的处理单元数量为N，训练 样本大小为M，则所划分的数据块大小为M/N；

合适的从属服务器需满足如下条件：存储空间不小于M/N，响应时间不大于用户所要求 的最晚时间。

控制中心访问训练样本，将划分所得的数据块复制到相应的处理单元上，并向处理单元 传递利用遗传算法训练原子规则的操作指令。

步骤2中原子规则的训练过程是：

处理单元对构成数据块的每一条数据记录进行遗传编码，通过遗传操作的循环迭代生成 原子规则，将原子规则以<key，value>键值对的形式存入缓冲区，<key，value>键值对中的key 为类标签，value为该类标签下的原子规则；

数据记录的遗传编码过程为：每条数据记录表示为一条染色体，染色体基因值由k个属 性值的二进制码值构成。若属性值为离散值，可直接进行二进制编码；若属性值为连续值， 则要对连续属性值进行离散化后，再进行二进制编码。二进制编码过程为：设属性a_i有s个 离散属性值v₁,v₂,…,v_s，则用含s个码位的二进制数表示属性a_i的值。若a_i的值为v_j，则该 属性值二进制码的第j位值为1，其余码位的值位为0。例如，性别属性有“男”、“女”两个 值，若属性值为“男”，则该属性的二进制编码为“0 1”；若属性值为“女”，编码为“1 0”。 遗传算法中，每条染色体为一个遗传个体，所有的遗传个体构成一个种群，种群规模用遗传 个体的数量n表示，由遗传编码过程得到的种群为初始种群，一个二进制码位对应染色体的 一个基因位。

遗传操作的循环迭代过程如图2所示：第t次迭代中，首先评价第t代种群P(t)的适应度， 之后判断是否停止迭代，若满足迭代停止条件，则停止迭代，将P(t)输出作为原子规则；若 不满足迭代停止条件，则进行选择、交叉和变异操作，生成第t+1代种群P(t+1)，令t=t+1， 实施下一次迭代。

迭代停止条件为以下两个条件的任意一个：

①迭代次数t>100；

②适应度fitness>0.75。

适应度评价为：设某一遗传个体对应的数据记录为[c₁,c₂,…,c_k]，该遗传个体的适应度为 fitness=TT/n+TT/(TT+TF)，其中TT为数据块中满足“(a₁=c₁)∧(a₂=c₂)∧…∧(a_k=c_k)”的数据 记录条数，TF为数据快中满足“(a₁=c₁)∧(a₂=c₂)∧…∧(a_k-1=c_k-1)∧(a_k≠c_k)”的数据记录条数， FT为数据块中满足“┐[(a₁=c₁)∧(a₂=c₂)∧…∧(a_k-1=c_k-1)]∧(a_k=c_k)”的数据记录条数，FF为 数据块中满足“┐[(a₁=c₁)∧(a₂=c₂)∧…∧(a_k-1=c_k-1)]∧(a_k≠c_k)”的数据记录条数。

选择操作为：遗传个体X_i的选择概率复制p_i×n个 X_i的副本作为下一次遗传操作种群中的个体，fitnexss(X_i)为X_i的适应度值。

交叉操作为：按照交叉概率p_c随机选择两个遗传个体X_i和X_j，随机选择染色体上的一 个基因位w，将X_i和X_j上基因位w后面的基因段交换形成两个新的个体，作为下一次遗传 操作种群中的个体。其中，交叉概率p_c为[0.4,0.9]之间的数值，也可采用自适应的交叉概率。

变异操作为：按照变异概率p_m随机选择一个遗传个体X_i，随机选择X_i上一个基因位， 对该基因位上的二进制码进行取反。其中，变异概率p_m为[0.01,0.1]之间的数值，也可采用自 适应的变异概率。

控制中心周期性地读取缓冲区中的<key，value>键值对，生成<key，value list>键值对列表 存入缓冲区，<key，value list>键值对列表中的key为类标签，value list为该类标签下的原子规 则列表；

处理单元完成对数据块中所有数据记录的操作之后，向控制中心发送处理单元操作完毕 的消息。

步骤3按如下过程进行：

由控制中心搜索闲置的从属服务器作为分类器，分类器的个数为<key，value list>键值对列 表中key值的个数，每个分类器对应一个key值；控制中心将<key，value list>键值对列表中的 原子规则列表和测试样本中具有相同类标签的记录传送到的分类器中，并向分类器传递冗余 约简和分类精度检测的操作指令；

分类器对同一类标签下的多个相同原子规则只记录一次，删除冗余的原子规则，得到约 简后的原子规则；

分类器利用约简后的原子规则对测试样本进行分类，检测分类结果是否与测试样本的类 标签相一致，假设被原子规则a分类的测试样本中，有Y条记录的类标签与分类结果相一致， 有N条记录的类标签与分类结果不一致，则原子规则a的分类精度为Y/(Y+N)。用户提出的 分类挖掘任务要求中，分类精度要求为α，将所有分类精度不小于α的原子规则作为分类规 则挖掘的最终结果，传送给控制中心；

控制中心汇总所有分类器生成的最终结果，再将汇总结果反馈至分类规则挖掘任务的请 求者。