多源异构数据集下的改进挖掘算法设计

吴文波，吴昌钱，胡 永

(1. 闽南科技学院计算机信息学院，福建 泉州 362000；2. 西藏民族大学信息工程学院，陕西 咸阳 712082)

1 引言

当下随着信息时代的深入发展，导致各类数据急剧增长，同时数据结构类型也逐渐繁多，海量的多源异构数据集存在于多领域中；该类数据集的特性，导致数据的可利用率较低[1]。为实现该类数据集中的数据的有效利用，对其进行智能挖掘是主要手段。基于此，本文依据随机森林理念，提出基于随机森林的频繁项集智能挖掘算法，对该类数据集进行挖掘分类，实现数据集的充分利用。

频繁项集指的是数据集中出现频率较高的相关变量，可通过对该项集的挖掘得出，挖掘结果可作为目标处理的依据[2]。数据分类作为数据挖掘的重要步骤或者目标，对于数据处理和应用具有重要意义。随机森林是一种通过分类器完成数据挖掘分类的模型，数个FP-tree树是其实现挖掘目的的依据，同时参与模型训练，且模型输出类别需以其类别为依据[3]。因此，模型性能的优劣，与各个FP-tree树的性能优劣存在直接且较大关联。该算法的运算依据是统计学理论，充分结合引导聚集和随机子空间两种算法，通过样本抽取和FP-tree树建模，形成多颗FP-tree树，最终结果的输出需依据投票完成[4]。

2 基于随机森林的频繁项集智能挖掘算法

2.1 基于改进FP-tree的频繁项集挖掘算法

2.1.1 频繁项集

以数据频繁项集为出发点，设计基分类器，其与各个类别相对应，并在该设计过程中，需确定优先类别，该过程为随机选择。分类器的差异导致其针对的数据类别存在差异，同时，使形成的FP-tree树结构也存在差异，以此保证基分类器的多样性[5]。由于随机森林算法是通过构建FP-tree树完成算法运行，FP-tree树则是完成频繁项集挖掘的典型算法。

如果项集合用I={i1，i2，…，in}表示，事物的集合用D表示，其属于数据库；项集合则构成各个事物T，且保证T∈I，以所有的T∈I为参照，仅在该条件下，T中包含项集X。X在D中的事物数量用于表示计数，且属于X的支持度。X在D中的事物比例用于表示X的支持度，当n表示T的数量，且属于D，则X/n获取的百分比即为X的支持度。在任意个给定的支持度小于X的支持度时，X即为频繁项集，此时给定的支持度为最小。

频繁模式树也称为FP-tree树，由3个域可构成其中的一个节点，分别为项名item、支持度计数sup-count和链node-link，后两者均属于节点。为保证遍历的便捷性，完成项头表的建构，其用Header-tabie表示，其中包含2个域，分别为项名item、链头head of node-link。

FP-tree的构建主要依据FP-growth算法完成，需对数据集进行扫描，且次数为2次，每一次扫描的内容分别如下：

1)为形成全部频繁1-项集及其支持度，对D进行扫描得出，按照获取的结果由高至低顺序，向Header-tabie中插入。

2)完成根节点null的构建，且属于T，采取手段对D中的各个T进行处理，分别为：第一，对项头表执行第一次扫描，获取其中的频繁项集，且扫描标准为按照顺序完成[6]；[p|P]表示排列后的结果，其中两个参数均表示项目，前者对应第一个，后者对应剩余的。第二，使用insert-tree[p|P]，当子女N存在于T中时，则N.item=p，同时N的数量加1；反之，需创建新节点，其名称用p表示，sup-count则设为1，确定其父节点，并进行链接，相同的项名节点可利用node-link完成链接，在p不是空的情况下，采用insert-tree[p|P]完成递归。

2.1.2 基于FP-数组技术的频繁项集挖掘算法

由于T具备base、header和FP-数组三种属性，因此，采用T作为程序的参数，T在三种属性下，分别包含X、项头表以及FP-数组Ax。该算法对频繁项集进行挖掘的详细步骤如下所述：

输入：FP-array

输出：属于T中的全部频繁项集

1)if T′ only contains a single branch B

2)for each subset y of the set of items in B

3)output itemset Y∪Tbase with count-min-count of nodes in Y；

4)else for each i in T header do begin

5)output Y=T base ∪{i}with i count；

6)if T FP-array is define

7)construct a new header table foe Y′s FP-tree fromT FP-array ；

8)else construct a new header table from T；

9)construct Y′s conditional FP-tree Ty and possibly its FP-arry AY；

10)ifTY≠φ

11)call FP-growth+(TY)；

12)end

样本x在测试阶段的预测通过产生的FP-tree树完成，且数量为L，在随机森林算法中，一颗FP-tree树可完成一个结果挖掘，基于此，可得出L个挖掘结果，为T1(x)，T2(x)，….，TL(x)；x的最终频繁项集类别标签为y，该结果的获取通过投票的方式完成，其计算公式为

(1)

式中：指示函数用I(·)表示；在Ti(x)=ωj的情况下，I(Ti(x)=ωj)结果为1，反之其结果为0。

通过上述步骤，获取最终的频繁项集输出结果，其类别判断标准为得出的投票数量的高低，票数多的作为频繁项集类的确定结果。

2.2 基于优化随机森林算法的频繁项集分类

由于随机森林算法需要构建大量FP-tree树，因此会导致内存被大量占用；同时，该算法结合引导聚集和随机子空间两种算法，两者均会对分类精度和多样性造成影响[7]。因此，为保证算法分类精度对随机森林算法进行改进，主要从两个方面完成，一是获取精度较高的部分FP-tree树，且由随机森林形成；二是对选取出的FP-tree树进行聚类，且树的选取标准为精度较高、相对程度较低[8]。改进后的随机森林算法流程见图1。

图1 改进后的算法流程

2.2.1 高精度子森林选取

(2)

式中：A表示AUC的平均值，属于森林中全部FP-tree树；如果F的数量低于SubF数量的三分之一，则待聚类子森林为SubF，反之需要将选取标准降低。σ表示AUC值的标准差，属于森林中全部FP-tree树，获取该值后，完成子森林构成，其由FP-tree树组成[10]，且AUC≥A-σ。组成的子森林公式为

(3)

依据上述内容，完成待聚类子森林的构成，其过程如下所述：

输入：训练集和测试集

输出：高精度子森林

1)抽取训练子集，且数量为K，从训练集D中抽取得出。

2)基分类器的训练，采用FP-tree树生成算法完成，其属于各个训练子集中。

3)为获取AUC的值，输入待测样本，完成所有FP-tree树的分类。

4)对获取的A和σ进行统计，以AUC≥A-σ或者AUC≥A作为标准，选取FP-tree树，形成SubF。

2.2.2 聚类选择多样性子森林

通过2.2.1小节获取SubF后，对其进行聚类，获取数据点，为相同测试点上的多颗FP-tree树分类结果。P表示数量，属于FP-tree树，为SubF中，因此可获取的待聚类样本数量也用P表示。

对聚类后的簇进行划分，使其形成数个类簇，相似度较低、精度较高的随机森林的组成是由其中典型的树完成，其步骤如下所述：

输入：聚类数量Q

输出：改进的随机森林模型

1)选取SubF作为数据集，获取其中的初始聚类中心，数量为Q。

2)完成所有数据遍历，计算距离，其属于对各个数据至聚类中心两者之间；并对数据属性进行划分处理，将距离中心簇的距离远近作为划分依据。

3)对各个聚类中心进行重复计算。

4)重复上述两个步骤，当满足最大迭代次数为止。

5)随机森林的组成由分类精度高的FP-tree树完成，该FP-tree树属于Q中。

为避免Q的选择对聚类结果造成影响，聚类中心的选择通过最大最小距离完成，详细步骤如下所述：

1)聚类中心z1为平均多样性最佳的FP-tree树，该多样性即可表示平均值，属于森林中全部树，其计算公式为

(4)

(5)

2)z2表示第二个聚类中心，其确定标准为距离z1最近。

3)获取距离，属于剩余的样本和已经确定的全部聚类中心，确定其中的最小距离。

4)选取最大距离，新增的聚类中心为与其对应的样本。

5)重复上述两个步骤，停止条件为获取聚类中心，且数量为Q。

6)完成聚类中心计算后，向相应的类别中划分样本集，属于聚类中心，且以最小距离为划分标准。

综上所述，完成算法优化，使算法在构建大量FP-tree树进行挖掘时性能得到提升，完成数据集中频繁项智能挖掘和数据分类。

3 测试分析

选取某机器学习数据库中的4个数据集，作为测试本文方法应用性能和应用效果的测试对象，数据集信息详情见表1。

表1 测试对象数据信息

在进行测试时，测试环境为：64位Windows10操作系统，Intel(R) Core(TM) i7-7700HQ，CPU 3.09GHz，安装内存为16GB。构建初始随机森林，数量和深度分别为100颗和10。依据文中方法步骤得出预测结果。在此基础上，生成随机森林，其标准为精度较高、相似程度较低。选取测试集，将其用于测试改进前后算法的性能，测试结果通过分类评估指标完成对比分析。本文采用的评估指标为Kappa系数，该指标计算公式为

(6)

式中：P1和P2均表示概率，属于两个分类器，前者表示两者获取结果一致，后者表示两者偶然相同。其中

(7)

(8)

式中：mk，s表示概率，位于ωk和ωs类中，且由Ti和Tj划分完成。该系数的取值为[-1，1]，值越大，说明一致性越佳，测试指标用于评估本文方法挖掘结果与实际结果的一致性程度。

算法在运算过程中，生成的FP-tree树数量L和类别数量K对于算法的运算存在直接关联，因此需确定最佳的两者取值，测试在不同L和K数量下，本文算法的挖掘AUC值和预测准确率，结果见图2。AUC值越高，表示算法真实性越高，其取值范围[0.5，1]。

图2 最佳取值测试结果

分析图2测试结果可得：FP-tree树数量的增加，AUC值随之变化，呈现上升、下降、上升的循环状态，当FP-tree树数量达到60时，AUC值最佳，为0.984；并且类别数量为30个时，预测准确率最佳，0.977。因此为保证算法的最佳效果和性能，L和K的取值分别为0.984和0.977。

为测试本文算法对于多样性子森林的聚类效果，测试本文算法在差异化最佳聚类数量时，算法每次获取的子森林集成准确率，结果见图3。为了最大程度保证测试结果的可靠性，测试结果为5次结果的平均值。

图3 聚类准确率测试结果

分析图3测试结果可知：聚类数量越多，聚类正确率则随之提升，但是当其达到饱和后，则不再上升，聚类数量为30个时，聚类正确率达到99.1%，聚类数量继续增加至35后，聚类正确率平稳，不再发生变化。

频繁项集的挖掘效果是体现算法应用性能的直观标准，将4种数据集中的属性数量和频繁项集数量分别作为挖掘目标，用于进一步衡量本文算法的挖掘效果。测试本文算法对4个数据集中的属性数量和频繁项集数量分别进行挖掘，获取挖掘结果，以此分析本文算法的挖掘效果，结果见图4。

图4 挖掘测试结果

根据图4测试结果可知：本文算法在对四种数据集进行挖掘后，可较为准确完成数据集中频繁项集数量以及属性数量的挖掘，其中只有在挖掘数据集2中的属性数量挖掘时，挖掘结果与实际结果存在一个数量的差异，其它数据集的频繁项集数量以及属性数量挖掘结果均与实际结果相同，可在整体挖掘误差较低的情况下完成数据集挖掘。

4 结论

数据的信息化发展，促使数据的应用需求极大增加，也导致对于各类数据的处理需求显著增加，频繁项集作为数据集中可体现数据中变量情况的一种项集，其对于数据的处理和应用具有重要作用。频繁项集的准确、有效挖掘，可使数据集中的各类数据利用率极大程度提升，但是频繁项集的智能挖掘一直面临诸多问题。本文以随机森林理论为依据，对其进行改进，提升数据集中频繁项集的挖掘效果，研究基于随机森林的频繁项集智能挖掘算法。通过测试表明：本文算法改进后具备良好的挖掘性能，挖掘正确率越高，可在极低的误差下完成数据集中的频繁项集挖掘。