Aprior算法概述及其在无线传感器网络中的应用

1、aprior算法概述及其在无线传感器网络中的应用摘要关联规则的挖掘作为数据挖掘的一个分支，描述了数据库中数据项z间存在的潜在关系 的规则。而aprior算法则是关联规则里的一项基本算法，它通过对频繁项集的层层迭代， 找出了事物之间的关联关系。文章首先对aprior算法的原理进行概述与简单的分析，然后 进一步探讨aprior算法在实际的应用中所遇到问题与瓶颈，并介绍儿种针对aprior算法的 改进办法。aprior算法的日的是在一个数据集中找出项与项之间的关系，它主要应用丁商 业领域，帮助获取数据z间的关系、规律、趋势等模式，辅助决策者进行决策。然而，随着 物联网与无线传感器技术的发展，我们认识

2、到aprior算法也可以被应用到该领域当屮。通 过该算法可以发现大量节点之间的有用关联或相关联系，以此消除节点之间信息的冗余，并 帮助用户对数据进行冇效的融合、分类、查询、分析、理解和决策。此外，该方法能够冇效 减少信息处理屮通信和计算所消耗的能最，缩短数据查询响应的时间，从而延长整个网络的 寿命。关键词apriori算法apriori算法改进关联规则无线传感器网络abstractas a branch of data mining, the mining of association rules describes potential relationships of data items.

3、 apriori algorithm is one of the basic algorithms in association rule method. through the iteration of frequent item sets, it finds the associations among the items. at first, this article introduces the outline of the algorithm in a simple way. then, it turns to the difficulties and bottleneck of a

4、priori algorithm in practical use, and introduce some improvement of apriori. the aim of apriori is to find the relationships among the items, it was first used in business field, helping managers to acquire the patterns of relationship, rule and trend however，with the development of iot and wsn, it

5、 has been recognized that apriori algorithm can be applied in this field too. apriori can help us to exploit the inherent correlations between sensor readings. this approach can help users to manage data efficiently during aggregation, classification, prediction, query, understanding and decision-ma

6、king. the simulation results show that the proposed method can reduce computation and communication energy in information processing effectively, shorten data queiy response time and then prolong the network lifetime.key words apriori algorithm; improvement of apriori algorithm; association rule; wi

7、reless sensor networkaprior算法原理概述aprior 算法最早是曲 rakesh agrawal 和 ramakrishnan srikant 两位i専士在 1994 年提；l的 。关联规则反映了一个事物与其它事物之间的相互依存性和关联性。如呆两个或者多个事物z间存在一定的关联关系，那么其中一个事物就能够通过其他事物预测得到。典型的关联 规则应用是超市购物篮数据进行分析。通过发现顾客放入货篮屮的不同商品之间的关系来分 析顾客的购买习惯，商家就可以通过挖掘出的关联关系结果进行销售策略的调整，获得更高 的利润。在介绍aprior算法z前，文章先对有关的一些概念定义做出概述

8、。基本概念1. 项：对一个数据表而言，表的每个字段都具有一个或多个不同的值。字段的每种取值都是一 个项。2. 项集：项的集合被称为项集。包含k个项的项集被称为k项集，k表示项集小项的数目。3. 事务：事务是项的集合。本质上一个事务就是事实表中的一条记录。事务的集合称为事务集。 一般用符号d表示事务集。4. 支持度：支持度反映的是关联规则的强度叫称support(x=>y)为关联规则x=>y的支持度。支 持度的数值即为d中事务同时包含x和y的百分比。即：5. 置信度：置信度反映的是关联规则的频度。称confidcncc(x=>y)为关联规则x=>y的置信度。 置信度的数值

9、即为d中包含a的事务同吋也包含b的百分比。w：confidence(x => y)= p(y | x)=包含x和y的元组数包含a的元组数6. 频繁项集：项集的出现频率是包含项集的事务数，简称项集的频率。如果项集出现的频率人于或等 于最小支持度阈值与d中事务总数的乘积，则称项集满足最小支持度阈值，满足阈值的项 集即为频繁项集。通常把频繁k项集记作lko算法描述在上述基本定义的基础之上，挖掘关联规则问题实际上可以被分为2个子问题：(1) 找出存在于事务集d屮的所有频繁项集。其中，频繁项集的支持度不小于用户或领 域专家给定的最小支持度阈值。(2) 利川频繁项集牛成强关联规则。这些规则必须满足最

10、小支持度和最小置信度。事实上，关联规则挖掘的核心问题是第一个子问题。apriori算法所处理的即为上述第 一个子问题。找到频繁项集最直观的办法即为先产牛事务集d小所有可能的项集，并计算他们的支 持度。如果事务集中含有x个项，那么可能的项集将有2勺个，那么该算法的时间复杂度 将是随数据项的规模的增大呈指数型增长的。当项的数量很人时，该算法的效率将会非常差。apriori算法通过利用频繁项集的性质对每次迭代过程的输入进行了剪枝，提前去掉了 部分不可能成为频繁项集的组合，减少了计算项集频率的次数，提高了算法的效率。频繁项集具冇如下性质(apriori性质)：频繁项集的所冇非空子集一定也是频繁的，任

11、何非频繁项集的超集一定也是非频繁的。根据这个性质，apriori算法的基木思想就是从1 维频繁项集的集合l出发，根据k-1维的频繁项集的集合lk_i，计算k维频繁项集的集合 直到计算出的高维频繁项集的集合为空为止。那么，apriori算法是如何从lku得到lk的呢？ apriori的实现方法分为以下三步1) 连接步骤：连接li中的(kl)频繁项集生成k项候选集，得到候选集的集合ck。可以 连接的条件是2个k-1维项的前k-2项相等并且第1个(kl)项集的第k-1项比第2个 (k-1)-项集的笫kl项小。记k为l3中的笫i个项集元素，叩为h中的笫j个项，贝ij条 件即为 hl=12lah2=12

12、2/ahk2=12k2ahklvl2kl其中,hklvl2kl可 以确保不产生重复的k项集。2) 删除步骤：利用apriori性质对ck进行的枝。剪枝的规则是：若一个k项候选集的任 一子集(kl)项集不属于(kl)项频繁集lk，那么该候选k项集就不可能成为一个频繁 k项集，可以将其从ck中删除。3) 计数步骤：扫描事务集d,累加k项候选集在事务集中出现的次数。对于一条事务和 一个候选项集，若事务包含该候选项集，则该候选项集出现的次数就加1。最示根据给 定的最小支持度阈值生成k项频繁集。算法在实际应用中的改进从上一部分的算法描述中可以看出，实际应用屮apriori算法需要人量进行的3个操作 依次

13、为：1) 判断2个k项集是否前k-1项相同且最后一项不同；2) 判断一个项集是否为另一个项集的子集；3) 扔描数据库计算候选集出现的频率。第1个操作存在于合并步骤中，第2个操作存在于删除步骤和记数步骤中，第3个操作 用在判断候选项集是不是频繁项集中。这3个操作占用了程序运行的大部分时间，尤其是 多次扫描数据库。如果能减少这3个操作执行的次数，就町以提高apriori算法的运行效率 连接策略优化如果一个k项集1满足每一项呈字典序递增，即11<12< -<lk,则称这个项集为有 序集；若对2个k项有序集lx和ly之间对位比较,即1和lyi比较,若有lxl=lyla- alxi-1

14、 =lyi-1 alxi<lyi, 1 <i<k, w'j称 lx 比 ly 小，记为 mly。若 m 个 k项有序项集 lbl2,-,lm, 有li<12<-<lnp则称这rn个k项集z间有序。如果lk中的所有项集都满足上述2个性质， 那么対于2个(kl)项频繁集lx和ly,若lx不能和ly连接，则lx与ly之后的所有(kl)项集都 不能满足连接条件。所以，只耍lx与ly不能连接，就不需要再判断l与ly之后的所有(kl) 项集是否能连接。例如，对于一个频繁 2 项集的集合 l2=i1,12,ii,13,ii,15,12,13,12,14,12,15

15、, 那么在连接过程中，当对11,12进行连接时，在扫描到12,13发现不能连接后，贝'j12,13以 后的项集都不能再和11,12进行连接。事实上，只要做到按照字典序排列以及自我连接的顺序进行，之后得到c, lk也必 然是冇序的，因此，在每一步的连接过程当中，对于lk中的每一个项集，如果一旦发现无 法进行连接，即可中断对木项集的连接，转到对下一个项集的连接扫描当中。这样一定程度 上提升了 apriori算法的效率。修剪频繁项集普通的apriori算法会在候选集的集合ck屮进行剪枝，去掉那些无法成为频繁项集的元 素。然而实际上，修剪还可以发牛在lk屮，进一步减少ck的数量以及lkh我连接

16、的次数。通过对apriori性质的进一步挖掘，我们还可以得到关于频繁项集的另一个性质卩若 在k维数据项目集x=i】,i2,i中，存在一个jex,使得|lk.(j)|<kl,则x不是频繁项冃 集。其中，|lk“(j)|表示(kl)维频繁项目集的集合lk.冲包含j的个数。对于这个性质的总观 理解就是：如果x是频繁项集，那么它的任意一个k子集必然会出现在li当小。那么x 中的每项在lk_i中就必然出现kl次。因此，若x之屮的某一项在l"屮的出现次数小于 kl那么，x必然不是频繁项集。根据这个性质，如果某一项c在lh中出现的次数小于k-1次，那么包含这个项c的项 集不盂要参与连接。因为

17、由这些项集连接而成的候选集必然包括一个项c,使得|lkj(c)|<kl, 从而使这个候选集不可能成为频繁项集。因此，有如下修剪频繁集的优化策略：先计算iujoi，其+jeu=ua|aglk.i,即计算冲所有项目的频度,再找出那些 频度小于kl的项目，记为l=i|lk(i)|<kl,然后在lei中去掉所冇包含u中任一元素的 频繁项目集，从而得到一个新的更小的kl维频繁项目集的集合l.p再由lli与口身相 连接生成候选k维数据项h集的集合co这样牛成的候选k维数据项目集合cs 般比原 来的由l"生成的集合ck要小一些。数据库优化策略在apriori算法中，多次扫描数据库需要消

18、耗较多的时间。如何在这步操作中提高效率 显得尤为重要。木文介绍了一种使用了布尔矩阵来记录数据库屮事务信息的方法，该方法只 须扫描一次数据库，大大减少了程序对外存储器的访问次数。设1=山甩,邙是项的集合，任务相关的数据d是数据库事务的集合，其小每个事务t 是项的集合，使得tol每个事务有一个标识符，称作tido定义项集i的布尔矩阵为：( 、d = (1丿2,d = ，212n "1 以pn j其中，p是事务数量；n是项的数目。0 /严其中，tij=l i et/表示第：项是否岀现在笫j个事务中。因此，项b的支持度 为:psupport_count(i7)=2 tjj1=1同理，一个k项

19、集的支持度计数为：psupport_counti.人，九=工(5 a%人人以)=1根据以上两个公式，我们仅需刈数据库进行次读収并牛:成布尔矩阵。之后再利用访内 操作读取矩阵屮的元索，就町以计算出项集的支持度，极人的减少了数据庄的访问次数。apriori算法在无线传感器网络当中的应用背景意义无线传感器网络是计算机科学技术一个新的研究领域，具有十分广阔的应用前景，已引 起学术界和工业界的高度重视。它综合了传感器技术、嵌入式计算技术、分布式信息处理技 术和无线通信技术，能够协作地实时监测、感知和采集各种环境或监测对象的信息，并对其 进行处理，传送到这些信息的川户。对于观察者來说，传感器网络的核心是感

20、知数据，而 不是网络硬件。观察者感兴趣的是传感器产生的数据，而不是传感器本身。以数据为中心的 传感器网络的基木思想是，把传感器视为感知数据流或感知数据源，把传感器网络视为感知 数据空间或感知数据库，把数据管理和处理作为网络的应用目标，使用户如同使用通常的数 据库管理系统和数据处理系统样白如地在传感器网络上进行感知数据的管理和处理。无线 传感器网络中传感器节点密集，分布范围广，长期监测使得信息量巨大，如果把所冇采集的 数据按事先指定的方式传输到屮心节点进行分析和处理十分困难其至不可实现，所以日前传 感器网络人多采用分布式信息处理技术。如何从大量分布式感知数据中捉収或挖掘有用的知 识，就成为无线传

21、感网络中信息处理的核心问题。能否把传统的数据挖掘知识应用到传感器 网络信息处理中来也是人们所关心的问题。传感器节点间关联规则的挖掘対无线传感器网络中的信息处理有重大的意义，它可以帮 助用户对数据进行有效的融合、分类、压缩、存储/查询、分析、理解以及基于感知数据决 策,减少信息处理中通信和计算所消耗的能量，延长整个网络的寿命。在无线传感器网络中， 有时人们十分想知道，当某一个传感器节点采集的温度为高时，网络屮还有哪些节点采集的 温度很可能也为高。为i叫答这个问题，就需要进行节点关联分析。在杳询时，我们可以很容 易地利用节点z间的关联找出区域温度的最大值、最小值，在查询平均温度时甚至可以用一 个节

22、点的温度来替代整个强关联节点的温度值。另外，在节点分簇时，把数据具有强关联的 节点分在同一个簇，能方便节点之间的预测，有效促进数据融合和压缩。在满足用八粘:度要 求的情况下，其至可以采用轮流工作的方式，即使强关联节点小的一个节点工作，而其他节 点处休眠状态，来完成信息的釆集，从而大大降低信息通信和计算的能耗，延长网络寿命。基本概念在无线传感器网络中，分析各个传感器节点中相应测量数据值就町获得节点z间的关联 性。如果两个节点所采集的数据总是或大部分时候都相同，那么我们称它们z间具冇强关联 性。传感器网络屮节点关联规则的挖掘的基本单位是节点，而传统的数据库关联规则挖掘小 的基木单位是数据项，它们之

23、间即有联系又有区别。首先，这里的项的概念与传统的关联规则挖掘有所不同,在无线传感器网络中，节点a、 b的测量值一般町以根据用户耍求的精度划分为区间范围。这些离散化的记录值，我们称z 为数据项刃。数据项相同则表示在某一吋刻a、b所采集的数据值相同。注意这里的值相同 只有和时间一起考虑才有意义，而传统数据库的关联挖掘一般与吋间顺序无关。其次，我们把a、b节点在同一时刻采样数据项相同的次数与节点采样总次数之比称为a=>b的支持度。同理，置信度被定义为节点a采集到数据的同时，节点b也采集到相同 数据的概率，即为条件概率p(b|a)o最后，与传统的关联规则中的频繁项集対应，所采集的数据项满足最小支

24、持度的节点就 称为频繁节点集。所采集数据项同时满足最小支持度和最小置信度的节点称为强关联节点, 并认为这种关联规则是有意义的。最小支持度阈值和最小信任度阈值通常由用户或领域专家 來设定。 =j与传统的关联规则一样，无线传感器网络节点关联规则挖掘也需要分成两步：首先发现 所冇的频繁节点集，这些节点集的频度至少应等于预先设置的最小支持频度；其次根据所获 得的频繁节点集，产住相应的强关联规则。根据定义，这些规则必须满足最小置信度阈值。 相对于第一步，第二步的处理相对简单，因此挖掘关联规则的整个性能就是由第一步中的操 作的复杂度所决定。理论上，前文提到的传统apriori »法可以解决上述第

25、一步的过程，但 在无线传感器网络中，要对每个节点的关联性都进行判断，显然不太对能。因为有些节点相 互之间距离很远，要在他们之间进行通信会消耗大量的能量0。节点z间的关联性为传统数据库关联性相比有其独有的特性。地域性：距离比较近 的节点貝有强关联的可能性比距离远的节点具有强关联的可能性大很多；稳定性：如果两个 节点历史上一直是强关联，那么，在接下來一段时间强关联的可能性很大；整体性：如果一 个节点周围所有的节点都和某一节点f强关联，那么这个节点和节点f强关联的町能性很 大,反之亦然。基于上述特性，木文将介绍一种区域频繁扩展树12(arca frequency expand tree afet)的

26、方法对apriori算法进行改进，使z大大减少候选节点集，减少通信和计算所 需的能耗和时间。图1.区域频繁扩展树(afet)如图1所示，它采用分区域考虑节点z间的频繁性。设定-关联范围(半径为d),并设 定中心节点与这一范围之外的节点强关联的可能性较少。这样，算法先从某-根节点出发(比 如a),在区域范围内找到所冇节点构成候选节点集c2 (如图1中的(a, b), (a, c), (a, d), 筛选岀人于最小支持度阈值频繁节点集构成集合l2 (如图1中的(a, b),(a, d)o再分别由 集合中其它的未扩展节点(如b)进行深度或广度优先搜索，再通过同样的办法在关联范围 半径内得到候选集的集合ck，进而得到lk0此外，除了前文曾经提到过的传统apriori算法的剪枝策略，如果一个候选节点周围所 冇的节点都属于(kl)项频繁节点集lk.|o,则认为该候选节点属于k项频繁节点集l|< (如节 点0)。反之，如果该节点周围所有的节点都不属于l“，则把该节点从g删除。通过以上描述，该算法的步骤可以粗略的分成如下儿步2