基于频繁项集的多源异构数据并行聚类算法

赵春霞， 赵营颖， 宋学坤

(河南中医药大学信息技术学院， 河南郑州 450046)

网络技术的不断发展促使多源异构数据迅速生成，挖掘处理复杂的多源异构数据，能够有效获取数据潜在信息和规律[1]。聚类分析属于机器学习、数据挖掘以及统计学等领域的交叉性学科，不仅能够起到有效演示的作用，即确定事物的分类标准或类别准则，而且聚类的作用就是归纳，不需要确定分类的标准、分析数据对象[2]，因此对于有效地挖掘和分析复杂的多源异构数据具有重要意义。

相关领域学者对数据并行聚类进行了研究。 文献[3]中提出基于MapReduce并行化计算框架的大数据聚类算法(简称文献[3]算法)。 采用Canopy算法对聚类中心进行初始化划分， 获取粗精度聚类中心点， 利用基于MapReduce框架的并行化计算方法， 细化聚类或合并Canopy中心， 实现大数据准确聚类分析。 该算法的并行聚类处理精度较高， 但并行计算效率较低。 文献[4]中提出基于Spark框架优化的大规模数据集谱聚类并行算法(简称文献[4]算法)。 采用单向循环迭代， 对相似矩阵构建进行优化， 利用位置变换和标量乘法替换， 对Laplacian矩阵构建与正规化进行优化， 运用近似特征向量进一步计算， 实现大规模数据集谱聚类并行分析。 该算法能够有效提高运行效率， 但存在聚类处理精度低的问题。

本文中提出一种基于频繁项集的多源异构数据并行聚类算法(简称本文算法)，采用极大元法挖掘最大频繁项集，构建相异度数据结构矩阵，利用时间窗口和频繁项集挖掘出多源异构数据特征，提高多源异构数据并行聚类处理精度。运用时间反转处理以及高维相空间重构方法，实现多源异构数据并行聚类，从而缩短多源异构数据并行聚类处理时间。

1 多源异构数据频繁项集挖掘

假设事务数据库D={d1,d2, …,dn, …}(n为正整数)的项目全集为非空有限集I，其中事务dn为I的子集，即dn⊆I，由此可知，dn存在线程控制标识符(TID)，主要用来表示事务编号。I的任意子集X称为D的项集(itemset)。若dn⊆X，则称事务dn属于项集X。

D的项集X出现的频数记为Sc(X)，为了简化计算，采用支持度S(X)表示项集X出现的频率，则有

(1)

式中|D|为D中的事务个数。

当项集X的支持度S(X)大于用户设置的支持度的阈值Smin(X)时， 项集X为频繁项集； 反之， 当S(X)小于Smin(X)时，项集X为非频繁项集[5]。

当频繁项集生成时，对频繁项集进行候选剪枝，具体方法如下。

在一般的关联规则挖掘过程中，支持度的阈值Smin(X)是通过用户或相关领域专家确定的，而最小支持度为Cmin(X)=Smin(X)|D|。利用D、Smin(X)，结合挖掘得到的频繁项集，可以获取全部频繁项集。

假设X⟹Y为关联规则，项集为规则前件，项集Y为规则后件，在关联规则中，X、Y为不相交的项集，即X∩Y=○/。同时，X、Y都具有比阈值频繁项集更大的支持度。使用置信度和支持度测量规则的兴趣度，支持度用于确定数据集的频繁度，而置信度用于确定Y包含X中的频繁度。

利用支持度阈值以及置信度阈值满足关联规则的需求，那么该关联规则定义为有趣的，即

(2)

(3)

式中：Cmin(X⟹Y)为最小支持度下的关联规则；q为记录的数据条数。

假设I的任意一个子集X都能表示为m维特征向量(χX,1,χX,2,…,χX,m)，则I的全部子集都能形成幂集格P(I)的同构位置格{0, 1}m。根据频繁项集的性质和定义，如果X为频繁项集，则X的任意子集都为频繁项集，通过频繁项集所获取的集合可以作为I的幂集格[6]。

幂集格P(I)的极大元为最大频繁项集，利用I全部子集所形成的幂集格P(I)和同构位置格{0, 1}m，利用类同挖掘的极大元方法，实现多源异构数据最大频繁项集挖掘。

2 本文算法

2.1 构建相异度数据结构矩阵

通过机器学习方法对聚类分析进行观察，不需要事先了解数据集的分布，然后结合物理或抽象的集合，计算集合的相似性进行聚类。

一个簇的实体情况是作为相似性而存在的， 因此可以得到实体之间不相似的不同的簇。 对空间内的类簇聚类情况进行测试， 由于同样的类簇中任意2个点之间的距离小于不同类簇中2个点之间的距离， 因此聚类可以具体描述[7]如下： 在给定的数据集V={vi|i=1,2,…,n}中， 通过对象之间的类似程度划分数据集， 簇Ci、Cj⊆V， 其中j=1,2,…,n，i+j=n,且满足

Ci∪Cj=○/,i≠j

，

(4)

Ci∪Cj=V

。

(5)

相异度矩阵δ的存储方式是通过在n个对象中有可能出现2个对象之间的相异性实现的，具体表现形式为n×n型矩阵，所有元素d(w1,w2)即为对象w1、w2之间的相异性，即

(6)

d(w1,w2)一般为非负数，当对象w1、w2十分接近时，d(w1,w2)接近于0；d(w1,w2)越大，则对象w1、w2之间的差距越大，由此获得相异度矩阵[8]。

2.2 提取多源异构数据特征

通过构建的相异度结构矩阵，提取统计序列的特征量，实现多源异构数据并行聚类。多源异构数据的数据库检测统计特征值矩阵Φ为

Φ=δ(a,J)-1

，

(7)

式中：a为检索模糊域；J为数据的分块匹配集。

融合数据库内多源异构复合，计算聚类中心，从而获取多源异构数据的特征分布域叙述Ism，

(8)

式中：Asm为多源异构数据的并行规划聚类加权输出幅值；ρsm为多源异构数据的并行规划聚类自适应调节参数；Dsm为不等式的约束条件。

利用平均加权的方法，通过在模糊聚类中心[9]叙述数据库中多源异构数据时间窗口T,

T=Ism(T1/T2)

，

(9)

式中：T1为事件时间；T2为处理时间。

通过式(9)可以获取数据库内多源异构数据信息融合全局性的寻优返回值，把数据输入缓冲器中，得到多源异构数据链路的增益值，以此完成多源异构数据特征的提取。

2.3 融合并行聚类算法

通过在高维空间内实现多源异构数据检测，利用频繁项集挖掘[10]的多源异构数据特征进行并行聚类，从而获取数据库内多源异构数据信道的传输功率谱密度Ω，

(10)

式中：σ为信号序列；h为采样频率；G为互功率谱估计；N为时间带宽积。

利用时间反转处理以及高维相空间的重构方法，实现多源异构数据时空结构加权处理，表达式为

(11)

式中：e(n)为多源异构数据时空结构加权处理结果；y(n)为空间样点个数；x(n)为回归参数。

通过在较大规模的多重输入-多重输出(multiple input-multiple output，MIMO)信道内，对多源异构的数据平均值特征量进行提取，获取多源异构数据的并行聚类目标函数R，即

(12)

式中：f为聚类扰动的间距；κ为子带中心的频率；Wi为不同聚类中心的时间尺度；M为线性约束的参量。

多源异构数据融合聚类集为

(13)

式中w为最大聚类数。

在信息汇集的区域，只要分别满足项集数据库的压缩xi以及事务数据库的压缩xj，就能够假设多源异构数据并行融合聚类的中心ci,i-1≤minci+1,i，从而获取关联的规则集K(xi,xj)，即

K(xi,xj)=exp[(xi-xj)2/(2γ2)]

，

(14)

式中γ为采集因子。

通过上式搜索到数据聚类中心，实现多源异构数据并行聚类。

3 实验仿真分析

为了验证本文算法的有效性，选择实验环境如下：中央处理器(CPU)为Intel双核2.7 GB，内存为4 GB，硬盘容量为500 GB，操作系统为Window10，采用Visual C++编程。

3.1 多源异构数据并行聚类处理精度

实验所用的基础数据集选择某公司内部二维多源异构数据，数量为16 575条，二维多源异构数据流量的平均大小为1 474 KB，并且确保每一条多源异构数据都处于独立的状态。然后选择10台处理器，分别采用文献[3]算法、文献[4]算法和本文算法，以并行化聚类的方式对总体多源异构数据条数进行并行聚类处理，对比不同算法的多源异构数据条数并行聚类处理效果。具体对比结果如表1所示。由表可以看出， 本文算法的多源异构数据条数并行聚类处理结果与实际多源异构数据条数相差较小， 而文献[3]算法和文献[4]算法的多源异构数据条数并行聚类处理结果与实际多源异构数据条数相差较大， 由此可知， 本文算法的多源异构数据条数并行聚类处理精度较高。 由于本文算法采用极大元法挖掘最大频繁项集， 构建相异度矩阵， 利用时间窗口和频繁项集挖掘出多源异构数据特征， 因此提高了多源异构数据并行聚类处理精度。

表1 不同算法的多源异构数据并行聚类处理结果

3.2 多源异构数据并行聚类处理时间

由于多源异构数据并行聚类处理精度实验中的基础数据较少，因此很难清晰地反映不同算法在多源异构数据并行聚类处理时间的差异。将多源异构数据条数增至50 000、 100 000、 150 000、 200 000、 250 000，分别采用文献[3]算法、文献[4]算法和本文算法进行并行聚类处理，不同算法的处理时间结果如图1所示。由图可知， 随着多源异构数据条数的增加， 不同算法的多源异构数据并行聚类处理时间呈线性增长。 当多源异构数据条数为250 000时， 文献[3]算法的并行聚类处理时间为45 s， 文献[4]算法的处理时间为28 s， 而本文算法的处理时间仅为18 s。 本文算法通过引入频繁项挖掘技术， 能够找出各数据之间的关联规则并进行划分， 利用平均加权方法在模糊聚类中心叙述数据库内多源异构数据时间窗口， 因此大幅缩短了多源异构数据并行聚类处理时间。

注： 本文算法—基于频繁项集的多源异构数据并行聚类算法； 文献[3]算法—基于MapReduce并行化计算框架的大数据聚 类算法； 文献[4]算法—基于Spark框架优化的大规模数据 集谱聚类并行算法。图1 不同算法的多源异构数据并行聚类处理时间

4 结语

为了有效提高多源异构数据并行聚类处理精度， 缩短多源异构数据并行聚类处理时间， 本文中提出一种基于频繁项集的多源异构数据并行聚类算法。 通过构建相异度矩阵， 使用时间窗口和频繁项集挖掘， 提取多源异构数据特征， 利用时间反转处理以及高维相空间重构方法， 高效实现多源异构数据并行聚类。 本文算法能够有效提高多源异构数据并行聚类处理精度， 减少处理时间。 随着科学技术的发展对聚类的准确度以及运行速度要求越来越高， 未来还要进一步研究优化多源异构数据并行聚类处理精度和时间的方法。