一种面向数据流贝叶斯分类的显露模式挖掘方法

李志杰，刘基旺，廖旭红，江华

（湖南理工学院信息科学与工程学院，岳阳 414006）

0 引言

基于模式的数据流贝叶斯分类方法，利用事务中项之间的相互关系计算贝叶斯联合概率，是一种有效的数据挖掘模型［1-2］。然而，现有的频繁模式挖掘算法面向事务数据流，与实际应用场景不完全吻合。大量的关系表型数据需要转换为带类值约束的事务数据流，才能用作有监督学习的训练数据［3-4］。

数据流本质上是非平稳的，除了有用信息外，大部分是一些无用的冗余信息，往往还包含噪声。然而，如果从原始数据流中挖掘频繁模式，则可以清除冗余信息和噪声的影响，比单个项值包含更多的信息［5］。不过，直接挖掘高密度数据流频繁模式，常常会产生大量超过需求数量的频繁模式。因此，实际应用中改为挖掘频繁闭合模式，它是频繁模式的无损压缩［6］。

挖掘频繁闭合模式用于数据流分类，这种模式必须带有类标约束才有意义［7］。在挖掘频繁闭合模式之前，大量的关系表型数据集要转换成带类值约束的事务数据集，这种预处理是批量进行的。文献［8］等开发的挖掘事务数据集闭合频繁项集算法，不适用于关系表型数据集的批量挖掘，需要增加预处理环节。

影响贝叶斯模型分类性能的的另一重要因素在于，大多数基于模式的贝叶斯分类器没有综合考虑模式在各个类数据集中的支持度，仅仅只计算了模式在目标类数据集中的支持度［9］。这样的模式挖掘方式难以进一步提升贝叶斯分类模型的性能［10］。

本文基于IncMine［5］算法，提出一种面向数据流贝叶斯分类的显露模式挖掘方法EPBIM，用于数据流贝叶斯分类。MOA 平台上的实验结果验证了本文提出方法的有效性。

1 相关工作

1.1 频繁项集与频繁闭合项集

定义1 事务型数据。设A={a1，a2，…，an}表示属性集，项为属性的整型取值。一个事务是项的集合，其中，项集的长度不大于属性集长度。每个事务只包含每个属性的最多一个项。事务型数据由多个事务Tid组成。

定义2 频繁项集。假设一个数据集最小支持度阈值为σ，如果项集在数据集中的支持度大于σ，则称之为频繁项集。

定义3 频繁闭合项集。假设X是频繁项集，Y是X的任一超项集。如果对于所有的Y，其支持度均低于X的支持度，则称X为频繁闭合项集。

定义4 关系表型数据。对于关系表型数据的条件属性值，本文采用“属性名∶属性值∶类别值”格式替换后，再扫描数据集得到各个项值id，构成事务型数据。带类标属性值与项存在一个映射关系。

定义5 约束频繁闭合项集。带有类别值的频繁闭合项集，称为约束频繁闭合项集。

1.2 数据流频繁项集挖掘方法

现有的数据流频繁项集挖掘算法，如Moment、FP-Stream、IncMine 等，都是面向事务型数据。根据分类标准不同，数据流频繁项集挖掘有多种划分方法。①挖掘频繁闭合项集，还是所有频繁项集。②是否引入滑动窗口或时间衰减机制。③按每个事务、还是按批次更新频繁项集。④挖掘结果是精确解还是近似解。

以IncMine［5］为例，是一种引入滑动窗口机制、按批次增量更新的、挖掘频繁闭合项集近似算法，有可控且少量的漏报，但比精确解算法Moment、FP-Stream快得多。

IncMine 在MOA 实现时，使用Charm［6］作为批处理挖掘器。Charm 的数据结构本质上是一种Apriori 层次结构，每个节点表示为（项集×事务集）键值对，子节点的事务集是父节点事务集的子集。

对于挖掘出来的FCI，IncMine 按长度把它们分别存储在不同的列表中。同时，IncMine把这些FCI组织成IF（IInverted FCI Index）数据结构。基于IFI，算法可以高效实现查询、更新FCI等操作。

1.3 贝叶斯分类与显露模式

贝叶斯分类器关键是计算各类值联合概率，这是一种被广泛研究的分类模型。经典的朴素贝叶斯计算公式为：

然而现实中这种条件独立性假设模型是很少成立的，于是出现了基于模式的贝叶斯分类算法，通过在数据集中抽取频繁模式来近似计算联合概率的乘积值：

显露模式是从一个目标类数据集到另一个对立类数据集的支持度有明显差异的模式，基于显露模式的贝叶斯分类方法，能够捕获不同类型数据之间的明显趋势，分类精度高，易于理解。

2 基于IncMine的显露模式挖掘方法

2.1 基于批次的FCI增量更新算法

Charm 挖掘出最新批次的FCI，需要增量更新滑动窗口中的FCI。IncMine 增量更新算法如算法1所示。

2.2 关系表型数据流半懒惰学习

2.2.1 估计联合概率

假设事务的类属性C有属性值c和cˊ，T={a1，a2，a3，a4，a5，a6}为待分类事务。为了估计联合概率P（T，c）i的值，需要在窗口的频繁项队列链表A和Aˊ中抽取显露模式。

如图1 所示，假定事务T抽取的类c的显露模式为{{a1,a2},{a3,a4}}，属性A5和A6是未被覆盖的属性，则联合概率的估计值为：

图1 基于显露模式未被覆盖的弱条件独立模型

2.2.2 数据流贝叶斯分类

EPBIM 是基于显露模式的贝叶斯数据流分类器，采用半懒惰式学习策略［10］进行分类。在训练阶段，其主要任务是挖掘当前滑动窗口的频繁闭合项集C和C′，当有新的批次数据生成时，更新滑动窗口及相应的数据结构。对于一个待分类样本S，EPBIM在每个类标对应的频繁闭合项集中，利用边界运算方法选取S在该类标的显露模式集合，用来计算待分类样本在每个类标下的联合概率。

3 实验结果与分析

本文的实验平台是MOA（massive online analysis）［1］，主要使用真实数据集，以及MOA数据生成器生成的合成数据集对算法的性能进行评价。实验采用分类精度性能指标，对本文分类器与MOA平台上的多种类型分类器进行对比。实验在2.60 GHz、Intel（R）Core（TM）i7-6700HQ CPU、内存16 GB、操作系统Windows 10的计算机上进行。

3.1 数据集

为了评价EPBIM 算法的性能，本文使用的数据集分别是原始数据集及其挖掘模式形成的数据集。

3.1.1 原始数据集

实验中采用了三个实际数据集：iris-2D.arff，cpu.with.vendor.arff，credit-g.arff 和两个合成数据流：AgrawallGenerator，RandomTreeGenerator。数据集具体参数见表1。

表1 数据集基本信息

3.1.2 挖掘模式形成的数据集

表1 所示的五个原始数据集，划分为训练集和测试集，占比分别为0.7 和0.3。通过Charm 挖掘出训练集的频繁闭合模式，并选择输出最长的显露模式，如表2所示。

表2 原始数据集挖掘的最长模式

3.2 抽取显露模式对实际数据集分类

3.2.1 显露模式与原始数据集贝叶斯分类

将原始数据集与显露模式分别应用WEKA 贝叶斯分类，分类准确度的结果如表3所示。

表3 原始数据集与显露模式分类准确度比较

从表3 可看到，应用显露模式的贝叶斯分类相对于只用原始数据集，分类准确度都得到提升。只有iris-2D的分类准确度维持不变。

3.2.2 多种分类器性能比较

对于MOA 平台上的rotatingHyperplane 数据流，表4 比较EPBIM 算法与朴素贝叶斯分类器（nb）、多数分类器（mc）、装袋分类器（oz）、杠杆袋装分类器（lb）、霍夫丁树分类器（ht）等在线分类器的准确度结果。

表4 rotatingHyperplane 分类准确度比较

显然，rotatingHyperplane 数据流经过模式挖掘之后再对其进行基于显露模式的数据流分类，其分类准确率最高。朴素贝叶斯分类器准确率其次，多数分类器最低。所以，显露模式挖掘工作是有意义的，贝叶斯与显露模式结合的EPBIM 分类器在以上几种分类器中准确度最高。

4 结语

朴素贝叶斯是一个理想模型，假设所有输入数据具有独立性。朴素贝叶斯作为一个增量算法，十分适合数据流的场景。不过，现实数据集往往包含大量噪声或无用信息，在分类前加一个模式挖掘的环节很有必要。挖掘频繁模式预处理可以去除冗余信息和噪声，频繁模式比单个属性更有区分力，基于模式的贝叶斯分类具有更高的准确度。