基于SOA的改进型Apriori算法

王 梅，张四平

(湖南信息职业技术学院 计算机工程学院，湖南 长沙 410200)



基于SOA的改进型Apriori算法

王 梅，张四平

(湖南信息职业技术学院 计算机工程学院，湖南 长沙 410200)

针对传统的粗糙集挖掘方法易受到频繁项集中干扰项的影响，导致挖掘精度低的问题，提出基于面向服务构架和时频特征提取的频繁项集关联规则挖掘Apriori算法.通过频繁模式树下的面向服务构架SOA模型，建立频繁项挖掘的频繁模式树，并进行信息融合预处理，构建频繁项集关联规则概念格，并提取数据时频特征，实现Apriori算法改进.仿真结果表明，采用改进Apriori算法进行关联规则的频繁项集挖掘时，数据特征提取精度较高，所需时间少，挖掘精度及指标性能均优于传统方法．

面向服务构架；关联规则；频繁项集；Apriori算法

0 引 言

Apriori算法是一种挖掘关联规则的频繁项集算法，采用面向服务构架(Service-Oriented Architecture，SOA)体系作为信息加工的概念格，用计算机模式识别方法生成频繁项集，使用XML Schema实现频繁项集挖掘.随着Apriori 算法的改进，被广泛应用在并行计算机模式识别、机械故障诊断、决策制定和审计跟踪等领域，经典Apriori挖掘算法采用多处理器进行关联规则特征检测，结合面向服务架构SOA技术寻找频繁项集[1-3]，获得用户行为特征信息.面向服务构架SOA技术是采用分布式传感器节点进行数据感知和通信，根据需求通过网络将应用程序的耦合服务构架进行特征配准和分布式部署[4]，实现更迅速、更可靠的数据传输.在面向服务构架网络模型中，通过频繁项集关联规则挖掘，可提高信息提取和数据分析能力，因此，研究基于面向服务构架SOA的Apriori算法具有重要意义[5]．文献[6]提出基于关联规则的频繁项集挖掘算法，采用证据理论进行关联规则的特征融合和线性特征分解，通过后缀项表的构建，保留面向服务构架频繁项集的完整信息，提高数据挖掘精度，但是该算法在进行关联规则特征空间重构中受到噪声干扰导致挖掘精度低，且计算开销较大，实时性不好；文献[7]提出基于关联规则置信度约束控制的Apriori算法，在支持度大于给定最小支持度下，进行阈值模型的构建，通过判决函数实现对频繁项集规则提取与概念格构建，提高关联规则的目标匹配性能，数据挖掘细节特征分解性能较高，置信度区间内目标信息挖掘特征较为明显，但是该算法随着干扰数据的增大，挖掘环境的信噪比降低，导致频繁项集挖掘的可靠性和收敛性不好；文献[8]提出基于FP-Growth的粗糙集挖掘方法，该算法会随着频繁项集中干扰项的增多，关联规则挖掘精度下降，不适合大范围使用．

因此，提出基于面向服务构架和时频特征提取的改进Apriori算法，首先给出频繁模式树下的面向服务构架模型，并进行频繁项集关联规则概念格构建和数据特征分析，采用时频特征提取方法进行数据特征提取及Apriori算法的改进，最后通过仿真实验进行性能测试.

1 频繁模式树下的面向服务构架模型及预处理

1.1 SOA模型

为了实现对关联规则频繁项集的挖掘，本文在面向服务构架SOA模型下进行Apriori算法的改进设计，结合候选挖掘频繁项集的时频特征，进行频繁模式树的先验概率密度信息提取和数据挖掘，假设X和G为属性集合，M为D和I之间的三元组，频繁项集产生格结构代替每个结点的特征参量β，进行频繁模式树构建．

定义1 (频繁模式树)定义概念格上的规则子集在时频空间上1×k维最小支持度minsup向量为D，在关联规则提取格结构下，通过SOA构架，进行数据项x的相空间重构，在重构的相空间中，构建频繁模式树Vx，其中，重构的特征轨迹满足V(1，i)=p，且频繁模式树的分岔树A，B同时满足以下两个条件：

(1)

(2)

根据上述约束条件，构建频繁模式树下面向服务构架SOA模型，抽取高密度区域置信度因素的条件概率P(A|B)，得到置信度为

(3)

由上述定义，可以得到m维属性分类下，频繁结点属性值的集合阶数为p,全部规则为ai(t),则全部规则属性约束下，频繁项挖掘的干扰项n(t)可表示为

(4)

在频繁项挖掘的样本事务数据库D中，通过候选概念格结点得到事件d的先验概率P(d)，扫描分枝概念树的候选特征参量a1(t)和a2(t)由下式确定：

(5)

依次类推，当m(t)与θ(t)互质，相关结点的最小计数值满足N≤Mm(t)θ(t)，且M>4τ，频繁项挖掘的相位信息为θ1，θ2，...，θq，此时频繁模式树下的面向服务构架SOA模型属性集为S={n1}，所有候选结点组合满足，表明对任意1≤i≤L时间复杂度ni(1≤i≤L)存在唯一解[9-15]．

定义2 候选概念格设置.给定频繁模式树下，面向服务构架SOA模型的冗余规则S=(U，A，V，f)，其中，U为冗余规则论域，A为相关冗余结点的属性集，设Θ为频繁概念格规则提取函数m:2Θ→[0，1]，保留项集对应的父结点满足下列条件：

(6)

(7)

(8)

(9)

在C4.5决策树模型下，进行频繁项目列表的减枝处理，剔除相关冗余结点，此时满足时间复杂度，U在等价关系C下可划分为E=U/RC={Ei|i=1，2，…，n}，频繁概念格规则提取的事务TID为S=(U，C∪D，V，f)，其中，C和D分别为条件属性和决策属性.

1.2 数据预处理

根据F1构造频繁项挖掘的频繁模式树(FP-tree)，设置FP-tree上的结点计数为count，任意分枝Ti(i=1，2…，m，m为分枝个数)的子集为Ni(Ni≥1)，相关结点最小计数分枝长度的序贯采样为O(Ni)，频繁项目列表簇间数据传输的最短路径通过调节因子λ(k)进行自适应修正，在重建的特征子空间中得到频繁项目列表调节因子为

(10)

其中，c(k)=tr[N(k)]/tr[C(k)]，表示频繁项集关联规则解析特征模型，满足

(11)

其中

(12)

(13)

(14)

其中，Bi(k)为量化初始状态x(0)的均值Dij(k)为量化测量值方差，当w(k)和ui(k)，i=1，2，…，N相对独立时，频繁项集关联规则到达融合中心的矢量特征为xiri(x).则得到频繁项集关联规则挖掘的信息融合动态方程为

(15)

式中，rj(x)为融合误差，xi为幅值.采用后缀项表构造map，进行数据融合模型的构建，提取一组频繁项集，确定在某一时刻的频率分量，得到数据传送量为

(16)

其中，后缀项表函数g(Ij)定义为

(17)

综上所述可知，进行后缀项表构造及信息融合预处理，为实现基于SOA的关联规则频繁项集挖掘提供准确的数据基础．

2 频繁项集挖掘算法

2.1 频繁项集时频特征提取

在上述进行数据结构分析和信息融合预处理的基础上，进行算法改进设计，通过研究基于面向服务构架SOA的Apriori算法，实现频繁项集关联规则挖掘，提高信息提取和数据分析能力.传统方法采用基于FP-Growth的粗糙集挖掘方法，当频繁项集中干扰项的增加时，挖掘精度会降低[16-20].因此，提出基于面向服务构架和时频特征提取的频繁项集关联规则挖掘Apriori算法.根据时频分辨率正则训练迁移法则，建立频繁项集关联规则数据集局域化矢量模型。假设当数据集局域化先验数据xm+1的决策属性取值为dm+1=d1，引入相关系数法进行虚假分量识别，由此计算出粗糙集虚假分量为

(18)

(19)

若时频特征提取过程是一个对规则项进行局部正交分解的过程，则通过特征空间重构，得到基于SOA的关联规则频繁项集挖掘时的时频特征，即

(20)

(21)

其中，虚假分量L与原规则项频繁集T的相关系数为

(22)

在此基础上，采用固有模态函数分解变换，对关联规则频繁项集挖掘目标函数进行求导，得到优化频繁项集挖掘的目标函数满足

(23)

根据上述时频特征提取结果可知，虚假分量L与原频繁项集T的相关性很小，采用数据结构子空间进行重建，结合时频特征提取结果，能较好地实现Apriori算法改进．

2.2 频繁项集关联规则挖掘Apriori算法

假设，频繁项集关联规则的训练集为{xi，yi}，分解得到IMF分量线性函数为

(24)

其中：w为各分量的权值向量；b为频繁项集关联规则挖掘的偏置量.将ei与设定门限e进行比较，得到闭频繁项挖掘属性X的增益函数，且满足约束优化问题

(25)

式中，C为基核函数；wi为粗糙集支持度.将上述约束优化问题转化为计算最小支持度问题，得到基于时频特征提取的闭频繁项挖掘一致性集成模型：

(26)

上式为一个Lagrange函数；αi为反馈均衡串扰抑制算子.基于线性均衡模型进行数据挖掘传输随机序列迭代，迭代函数为

(27)

其中

(28)

当数据码元速率一定的情况下，用扩展后的序列去调制载波，在迭代步长足够的情况下，采用判决反馈均衡实现时间窗口重排，得到频繁项集关联规则挖掘的传递函数为

(29)

(30)

沿着中心路由遍历每条事务模式路由T，得到Apriori算法的特征空间协方差矩阵为

(31)

在m维属性分类中构造闭频繁模式的邻居簇头，得到特征挖掘的相关性函数满足为

(32)

3 实验分析与性能测试

为了测试改进Apriori算法的性能，进行仿真实验对比分析，实验建立在面向服务构架SOA的Hadoop平台上，硬件环境为：CPU Inter Pentium 4，内存为2G.实验数据集采用breast cancer关联规则闭频繁项数据集，频繁项集关联规则的采样样本时间间隔为0.25 s，时长T=0.1 s，采样点数为100.采用时频特征提取方法合成数据集testdata(DC15000TB8000RT100)，得到测试数据集合.根据上述仿真环境和参数设定，进行仿真实验分析.首先进行数据信息采样，构造频繁项挖掘的FP-tree，得到原始的关联规则频繁项集特征分布，如图1所示．

图 1 关联规则频繁项集特征分布 图 2 两种算法下闭频繁项数据集 的Apriori分枝结果Fig.1 Characteristics of frequent itemsets distributed association rules Fig.2 Closed frequent items under two kinds of algorithm Apriori branch of data sets

以上述采集关联规则频繁项集为测试对象，进行Apriori分离处理，分别采用本文方法和传统基于关联规则置信度约束控制的Apriori方法，得到对闭频繁项数据集的Apriori分离结果，如图2所示．

图 3 不同算法的挖掘时间对比Fig.3 Different algorithms of mining time

从图2可见，采用本文方法进行关联规则频繁项集挖掘，相比传统方法，对数据的分簇挖掘性能较好，受到的干扰较小，性能较高.为了定量对比算法性能，分别采用本文方法(PFP-P)和传统方法(文献[4]给出的PFP算法，文献[8]对文献[4]改进的PFP-C算法)进行对比，以挖掘时间为测试指标，得到仿真结果，如图3所示．

从图3可见，采用本文改进的Apriori算法进行关联规则的频繁项集挖掘，消耗时间最少，挖掘加速比较高，相反，PFP算法及PFP-C算法的挖掘加速比和挖掘时间均较差，性能低于改进方法，由此说明，改进方法性能较好，具有一定的优势．

4 结束语

针对传统Apriori算法挖掘效率低，误差大的问题,提出基于面向服务构架和时频特征提取的频繁项集关联规则挖掘Apriori算法，通过频繁模式树下的面向服务构架SOA模型，建立频繁项挖掘的FP-tree，并进行信息融合预处理，构建频繁项集关联规则概念格和数据时频特征提取，实现Apriori算法改进.研究结果表明，采用改进方法时其挖掘性能较好，耗时等测试指标均优于传统方法，展示了较好的应用价值．

[1] 尚朝轩，王品，韩壮志，等. 基于类决策树分类的特征层融合识别算法[J]. 控制与决策，2016，31(6):1009-1014．

SHANG Chaoxuan，WANG Pin，HAN Zhuangzhi，et al. Feature-level fusion recognition algorithm based on analogy decision tree classification[J]. Control and Decision，2016，31(6):1009-1014．

[2] IHSNA A Kareem，MEHDI G Duaimi. Improved accuracy for decision tree algorithm based on unsupervised discretization[J]. International Journal of Computer Science and Mobile Computing，2014，3(6):176-183．

[3] PEI Jian，HAN Jiawei，MAO Runying. CLOSET：An efficient algorithm for mining frequent closed itemsets[J]. Acm Sigmod Workshop on Research Issues in Data Mining and Knowledge Discovery，2000，4(2):21-30．

[4] CHONG F T，HECK M J R，RANGANATHAN P，et al. Data center energy efficiency：improving energy efficiency in data centers beyond technology scaling[J]. IEEE Design & Test，2014，31(1):93-104．

[5] 郎振红. 基于云计算自主学习平台的设计[J]. 电子设计工程，2016，24(1):35-39．

LANG Zhenhong. A design of self-study’s platform system based on cloud computing[J]. Electronic Design Engineering,2016，24(1):35-39．

[6] MORENO Salinas D，PASCOAL A M，ARANDA J. Optimal sensor placement for multiple target positioning with range-only measurements in two-dimensional scenarios[J]. Sensors，2013，13(8):10674-10710．

[7] LEE W，BANG H，LEEGHIM H. Cooperative localization between small UAVs using a combination of heterogeneous sensors[J]. Aerospace Science and Technology，2013，27(1):105-111．

[8] KARLSSON J，ROWE W，XU L，et al. Fast missing-data IAA with application to notched spectrum SAR[J]. IEEE Transactions on Aerospace Electronic Systems，2014，50(2):959-971．

[9] PARK H R，LI Jie. Sparse covariance-based high resolution time delay estimation for spread spectrum signals[J]. Electronics Letters，2015，51(2):155-157．

[10] WANG Lin，ZHANG Fa，ARJONA Aroca J，et al. Green DCN：A general framework for achieving energy efficiency in data center networks[J]. IEEE Journal on Selected Areas in Communications，2014，32(1):4-15．

[11] 虞飞，陶建武，陈诚，等.基于稀疏协方差矩阵迭代的单快拍气流速度估计算法[J].电子与信息学报，2015，37(3):574-579．

YU Fei,TAO Jianwu，CHEN Cheng,et al.Single snapshot airspeed estimation based on sparse covariance matrix iteration[J].Journal of Electronics & Information Technology,2015，37(3):574-579．

[12] 周镭，单锋，刘鹏，等. 基于供应链的企业信息化评价模型的建立[J]. 西安工程大学学报，2015，29(6):772-779．

ZHOU Lei，SHAN Feng，LIU Peng，et al. The establishment of the enterprise informatization evaluation model based on supply chain[J]. Journal of Xi’an Polytechnic University，2015，29(6):772-779．

[13] KALEVA J，TOLLI A，JUNTTI M. Weighted sum rate maximization for interfering broadcast channel via successive convex approximation[C]//IEEE Global Communications Conference， Anaheim，2012：3838-3843．

[14] LIU Heng，DING Zhiguo ，FAN Pingzhi，et al. Precoding design for interference suppression in multi-cell multi-user networks[J]. IET Communications，2014，8(9):1534-1540．

[15] RATHEESH M，DAVID M J. System-level performance of interference alignment[J]. IEEE Transactions on Wireless Communications，2015，14(2):1060-1070．

[16] GENG Zhe，DENG Hai，HIMED B. Adaptive radar beamforming for interference mitigation in radar-wireless spectrum sharing[J]. IEEE Signal Processing Letters，2015，22(4):484-488．

[17] YANG Yunchuan，SUN Cong，ZHAO Hui，et al. Algorithms for secrecy guarantee with null space beamforming in two-way relay networks[J]. IEEE Transactions on Signal Processing，2014，62(8):2111-2126．

[18] 吴鸿华，穆勇，屈忠锋，等. 基于面板数据的接近性和相似性关联度模型[J]. 控制与决策，2016，31(3):555-558．

WU Honghua，MU Yong，QU Zhongfeng，et al. Similarity and nearness relational degree based on panel data[J]. Control and Decision，2016，31(3):555-558．

[19] 阎芳，李元章，张全新，等. 基于对象的OpenXML复合文件去重方法研究[J]. 计算机研究与发展，2015，52(7):1546-1557

YAN Fang，LI Yuanzhang，ZHANG Quanxin，et al. Object based data de-duplication method for open XML compound files[J]. Journal of Computer Research and Development，2015，52(7):1546-1557．

编辑、校对：师 琅

Improved Apriori algorithm based on SOA

WANG Mei， ZHANG Siping

(School of Computer Engineering， Hunan College of Information， Changsha 410200， China)

In the view of the traditional method of rough set mining method easily affected by frequent items focused distractions， leading to the problem of low digging precision, based on service oriented architecture and time-frequency feature extraction,Apriori algorithm for mining association rules is proposed.Through frequent pattern tree of service-oriented architecture SOA model， the FP-tree of frequent items mining is set up， information fusion is preprocessed， concept lattice and association rule are built and data frequent item sets time-frequency feature is extracted， achieving improved Apriori algorithm. The simulation results show that with the improved algorithm the data feature extraction has high precision， less time required; mining precision and performance indicators are better than those of traditional methods．

service oriented architecture; association rule; frequent item set; apriori algorithm

1674-649X(2016)04-0487-07

10.13338/j.issn.1674-649x.2016.04.014

2016-03-16

湖南省教育厅高校研究基金资助项目(15C0980)

王梅(1978—)，女，湖南省长沙市人，湖南信息技术学院讲师，研究方向为大数据、数据处理.

E-mail:siping_zhang@sina.com

王梅，张四平.基于SOA的改进型Apriori算法[J].西安工程大学学报，2016，30(4)：487-493.

WANGMei，ZHANGSiping.ImprovedApriorialgorithmbasedonSOA[J].JournalofXi′anPolytechnicUniversity,2016，30(4)：487-493.

TP

A