太阳城集团

  • / 12
  • 下载费用:30 金币  

一种低消耗的APRIORI方法.pdf

关 键 词:
一种 低消耗 APRIORI 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201510721082.3

申请日:

2015.10.30

公开号:

CN105224687A

公开日:

2016.01.06

当前法律状态:

授权

有效性:

有权

法律详情: 授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20151030|||公开
IPC分类号: G06F17/30 主分类号: G06F17/30
申请人: 宁波大学
发明人: 郑紫微; 金涛
地址: 315211 浙江省宁波市江北区风华路818号
优先权:
专利代理机构: 宁波诚源专利事务所有限公司 33102 代理人: 邓青玲
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

太阳城集团CN201510721082.3

授权太阳城集团号:

||||||

法律状态太阳城集团日:

2018.10.19|||2016.02.03|||2016.01.06

法律状态类型:

授权|||实质审查的生效|||公开

摘要

太阳城集团本发明涉及一种低消耗的Apriori方法,用于对智能移动终端的移动轨迹的关联移动规则进行挖掘,包括将移动节点移动轨迹的太阳城集团属性与空间属性一同作为挖掘对象数据,充分考虑移动轨迹的太阳城集团和空间双重属性,并且在由候选频繁项集生成频繁项集的过程中,缩小移动轨迹数据集扫描范围,减少获取候选项集的太阳城集团,从而达到低消耗的目的。相较于传统Apriori方法,本发明提供的Apriori方法适用于挖掘智能移动终端的移动轨迹关联规则。

权利要求书

权利要求书
1.  一种低消耗的Apriori方法,用于对智能移动终端的移动轨迹的关联移动规则进行挖掘,其特征在于:包括如下步骤:
步骤一、使用迭代方法挖掘智能移动终端的移动轨迹数据集中所有频繁项集,并记录每个频繁项集的日期,计算每个频繁项集的支持度;
步骤二、利用步骤一得出的频繁项集,生成移动节点所有可能的关联移动规则,并计算每条移动规则的置信度,记录移动节点每条关联移动规则的日期以及计算每条关联移动规则日期的远近变动因子;同时,根据记录的日期和计算的日期远近变动因子,计算每条关联移动规则的日期加权值TWeight(R),从而得到强关联性移动规则;其中,每条关联移动规则日期对应的远变动因子m和近变动因子n计算公式如下:
m=|MaxDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek,n=|MinDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek;]]>
每条关联移动规则的日期加权值TWeight(R)计算公式如下:
TWeight(R)=RuleDate-MinDatenMaxDatem·MinDaten·MaxDatemMaxDatem+MinDaten×100;]]>
其中,RuleDate、MaxDate以及MinData分别表示移动规则的日期、移动轨迹数据集中最近的记录日期与最远的记录日期;m为移动轨迹数据集中的最近记录日期MaxDate的变动因子,即近变动因子;n为移动轨迹数据集中的最远记录日期MinData的变动因子,即远变动因子;K为该移动规则日期RuleDate所在月的总天数,RuleDatek表示该月中第k天的日期值;
步骤三、根据移动节点当前轨迹及步骤二生成的关联移动规则,预测移动节点下一个移动轨迹:
假定当前移动节点的移动轨迹为T:(cn,tn)→(cm,tm),遍历所有关联移动规则,如果关联移动规则R包含移动轨迹T则说明关联移动规则R是匹配的移动规则,然后根据下式计算关联移动规则R的匹配度,匹配度越高则越有可能是移动节点下一个移动轨迹:
Score(R)=Confidence(R)+TWeight(R)
其中,Score(R)为关联移动规则R的匹配度,Confidence(R)为关联移动规则R的置 信度,TWeight(R)为关联移动规则R的日期加权值;
在步骤一中,将智能移动终端的移动轨迹的太阳城集团属性与空间属性一同作为挖掘对象数据,用事务数据库D表示智能移动终端的移动轨迹数据集,每条事务条目用移动轨迹记录表示,每条移动轨迹记录则用多个轨迹数据组成,轨迹数据用p1,p2,…pn-2,pn-1,pn表示,其中pn={(cn,tn)|cn∈C,tn∈T},代表移动节点在太阳城集团点tn接入了路由器cn,集合C代表移动节点日常经过的所有接入路由器,T代表每天划分的X个太阳城集团段集合,X=12或24或48或72;并引入记录ID号来标识每一条智能移动终端的移动轨迹;所述步骤一具体由如下方式实现:
(1)、首先遍历整个事务数据库D获得1-候选项集C1,然后计算1-候选项集C1中每个候选项的支持度,同时标识出包含该候选项的所有记录ID号,最后删除1-候选项集C1中支持度小于最小支持度阈值的候选项,就得到了1-频繁项集L1;
(2)、利用1-频繁项集L1进行内连接运算计算出2-候选项集C2,计算2-候选项集C2中每个候选项的支持度是通过将2-候选项集C2中每个2-候选项拆分成若干个单独的1-频繁项;
(3)、找出所有(2)拆分出的1-频繁项中支持度最小的1-频繁项,同时找出所有包含该1-频繁项的记录ID号;
(4)、遍历(3)中得到的记录ID号的移动轨迹记录来计算每条候选频繁项的支持度,最后删除2-候选项集C2中支持度小于最小支持度阈值的候选项就得到了2-频繁项集L2;
(5)、3-频繁项集L3的获取同样是需要将3-频繁项拆分成若干个单独的1-频繁项,其余计算过程和2-频繁项集L2相同,依次类推,算出k-频繁项集Lk,直到无法再生成频繁项为止。

说明书

说明书一种低消耗的Apriori方法
技术领域
本发明涉及一种低消耗的Apriori方法。
背景技术
如何在海量的数据中,挖掘其中隐藏的、人们感兴趣的知识,已经成为了一个研究的热点。Agrawal等在1994年提出使用Apriori方法对顾客交易的数据库项之间的关联规则进行挖掘,这种方法分成以下两部分来完成:首先,找出数据库中所有出现频率比最小支持度大或者相等的频繁项集;然后,根据所得到的频繁项集来制定强关联规则,同时这些强关联规则必须要满足最小可信度以及最小支持度这两个基本的条件。
从上面方法实现的两个部分可以看出,Apriori方法的实现分成以下两个步骤:1、首先使用迭代方法对数据集中的所有项集进行扫描,并且设定一个支持度阈值,筛选出数据集中的所有频繁项集,即将支持度低于阈值的项集全部淘汰掉,而将支持度高于这个阈值的项集认为是频繁项集;2、得到所有的频繁项集之后,就可以利用它挖掘出强关联规则,对于每个频繁项集l产生强关联规则的基本步骤可以总结为以下两步:a、生成l所有的非空真子集;b、对于l的每个非空真子集lz,如果l的支持度除以lz的支持度大于或等于min_conf,则输出强关联规则lz→(l-lz)。
传统Apriori方法其挖掘对象的事务数据库中,内部的事务条目只具有空间属性,不适用于挖掘移动节点移动轨迹关联规则。
另外,如果将传统的Apriori方法直接移植到硬件资源有限的移动终端中应用,效率会变得非常低,首先在于执行过程中需要消耗较高的存储空间来保存大量的候选项集,其次需要消耗较长太阳城集团的CPU资源对整个移动轨迹数据集进行多次重复的扫描来获得全部候选项集。因此,如何使Apriori算法变得更加低耗就显得尤为的重要。
发明内容
本发明所要解决的技术问题是针对上述现有技术提供一种低消耗的Apriori方法。
本发明解决上述技术问题所采用的技术方案为:低消耗的Apriori方法,用于对智能移动终端的移动轨迹的关联移动规则进行挖掘,其特征在于:包括如下步骤:
步骤一、使用迭代方法挖掘智能移动终端的移动轨迹数据集中所有频繁项集,并记 录每个频繁项集的日期,计算每个频繁项集的支持度;
步骤二、利用步骤一得出的频繁项集,生成移动节点所有可能的关联移动规则,并计算每条移动规则的置信度,记录移动节点每条关联移动规则的日期以及计算每条关联移动规则日期的远近变动因子;同时,根据记录的日期和计算的日期远近变动因子,计算每条关联移动规则的日期加权值TWeight(R),从而得到强关联性移动规则;其中,每条关联移动规则日期对应的远变动因子m和近变动因子n计算公式如下:
m=|MaxDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek,n=|MinDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek;]]>
每条关联移动规则的日期加权值TWeight(R)计算公式如下:
TWeight(R)=RuleDate-MinDatenMaxDatem-MinDaten·MinDaten·MaxDatemMaxDatem+MinDaten×100;]]>
其中,RuleDate、MaxDate以及MinData分别表示移动规则的日期、移动轨迹数据集中最近的记录日期与最远的记录日期;m为移动轨迹数据集中的最近记录日期MaxDate的变动因子,即近变动因子;n为移动轨迹数据集中的最远记录日期MinData的变动因子,即远变动因子;K为该移动规则日期RuleDate所在月的总天数,RuleDatek表示该月中第k天的日期值;
步骤三、根据移动节点当前轨迹及步骤二生成的关联移动规则,预测移动节点下一个移动轨迹:
假定当前移动节点的移动轨迹为T:(cn,tn)→(cm,tm),遍历所有关联移动规则,如果关联移动规则R包含移动轨迹T则说明关联移动规则R是匹配的移动规则,然后根据下式计算关联移动规则R的匹配度,匹配度越高则越有可能是移动节点下一个移动轨迹:
Score(R)=Confidence(R)+TWeight(R)
其中,Score(R)为关联移动规则R的匹配度,Confidence(R)为关联移动规则R的置信度,TWeight(R)为关联移动规则R的日期加权值;其中,
在步骤一中,将智能移动终端的移动轨迹的太阳城集团属性与空间属性一同作为挖掘对象数据,用事务数据库D表示智能移动终端的移动轨迹数据集,每条事务条目用移动轨迹记录表示,每条移动轨迹记录则用多个轨迹数据组成,轨迹数据用p1,p2,…pn-2,pn-1,pn 表示,其中pn={(cn,tn)|cnEC,tnET},代表移动节点在太阳城集团点tn接入了路由器cn,集合C代表移动节点日常经过的所有接入路由器,T代表每天划分的X个太阳城集团段集合,X=12或24或48或72;并引入记录ID号来标识每一条智能移动终端的移动轨迹;所述步骤一具体由如下方式实现:
(1)、首先遍历整个事务数据库D获得1-候选项集C1,然后计算1-候选项集C1中每个候选项的支持度,同时标识出包含该候选项的所有记录ID号,最后删除1-候选项集C1中支持度小于最小支持度阈值的候选项,就得到了1-频繁项集L1;
(2)、利用1-频繁项集L1进行内连接运算计算出2-候选项集C2,计算2-候选项集C2中每个候选项的支持度是通过将2-候选项集C2中每个2-候选项拆分成若干个单独的1-频繁项;
(3)、找出所有(2)拆分出的1-频繁项中支持度最小的1-频繁项,同时找出所有包含该1-频繁项的记录ID号;
(4)、遍历(3)中得到的记录ID号的移动轨迹记录来计算每条候选频繁项的支持度;
(5)、3-频繁项集L3的获取同样是需要将3-频繁项拆分成若干个单独的1-频繁项,其余计算过程和2-频繁项集L2相同,依次类推,算出k-频繁项集Lk,直到无法再生成频繁项为止。
与现有技术相比,本发明的优点在于:将移动节点移动轨迹的太阳城集团属性与空间属性一同作为挖掘对象数据,充分考虑了移动轨迹的太阳城集团和空间双重属性,并且在由候选频繁项集生成频繁项集的过程中,缩小了移动轨迹数据集扫描范围,减少了获取候选项集的太阳城集团,从而达到低消耗的目的,相较于传统Apriori方法,本发明提供的Apriori方法适用用于挖掘智能移动终端的移动轨迹关联规则。
附图说明
图1为本发明实施例中低消耗的Apriori方法流程图。
具体实施方式
以下结合附图实施例对本发明作进一步详细描述。
如图1所示的低消耗的Apriori方法,用于对智能移动终端的移动轨迹的关联移动规则进行挖掘,其特征在于,包含如下步骤:
步骤一、使用迭代方法挖掘对象数据集中所有频繁项集,并记录每个频繁项集的日期,计算每个频繁项集的支持度;该步骤中,将智能移动终端的移动轨迹的太阳城集团属性与空间属性一同作为挖掘对象数据,用事务数据库D表示智能移动终端的移动轨迹数据集,每条事务条目用移动轨迹记录表示,每条移动轨迹记录则用多个轨迹数据组成,轨迹数据用p1,p2,…pn-2,pn表示,其中pn={(cn,tn)|cnEC,tnET},代表移动节点在太阳城集团点tn接入了路由器cn,集合C代表移动节点日常经过的所有接入路由器,T代表每天划分的X个太阳城集团段集合,X=12或24或48或72;并引入记录ID号来标识每一条智能移动终端的移动轨迹;所述步骤一具体由如下方式实现:
(1)、首先遍历整个事务数据库D获得1-候选项集C1,然后计算1-候选项集C1中每个候选项的支持度,同时标识出包含该候选项的所有记录ID号,最后删除1-候选项集C1中支持度小于最小支持度阈值的候选项,就得到了1-频繁项集L1;
(2)、利用1-频繁项集L1进行内连接运算计算出2-候选项集C2,计算2-候选项集C2中每个候选项的支持度是通过将2-候选项集C2中每个2-候选项拆分成若干个单独的1-频繁项;这里内连接运算为现有常规技术;
(3)、找出所有(2)拆分出的1-频繁项中支持度最小的1-频繁项,同时找出所有包含该1-频繁项的记录ID号;
(4)、遍历(3)中得到的记录ID号的移动轨迹记录来计算每条候选频繁项的支持度,最后删除2-候选项集C2中支持度小于最小支持度阈值的候选项就得到了2-频繁项集L2;
(5)、3-频繁项集L3的获取同样是需要将3-频繁项拆分成若干个单独的1-频繁项,其余计算过程和2-频繁项集L2相同,依次类推,算出k-频繁项集Lk,直到无法再生成频繁项为止;
步骤二、利用步骤一得出的频繁项集,生成移动节点所有可能的关联移动规则,并计算每条移动规则的置信度;该步骤中生成移动节点所有可能的关联移动规则过程与传统Apriori方法相同,计算每条移动规则的置信度的方法也与传统Apriori方法相同,即为现有常规技术,此处不再详细描述现有常规技术;
但不同的是,在该步骤中,需要同时记录移动节点每条关联移动规则的日期以及计算每条关联移动规则日期的远近变动因子;同时,根据记录的日期和计算的日期远近变 动因子,计算每条关联移动规则的日期加权值TWeight(R),从而得到强关联性移动规则,其中,每条关联移动规则日期对应的远变动因子m和近变动因子n计算公式如下:
m=|MaxDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek,n=|MinDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek;]]>
每条关联移动规则的日期加权值TWeight(R)计算公式如下:
TWeight(R)=RuleDate-MinDatenMaxDatem-MinDaten·MinDaten·MaxDatemMaxDatem+MinDaten×100;]]>
其中,RuleDate、MaxDate以及MinData分别表示移动规则的日期、移动轨迹数据集中最近的记录日期与最远的记录日期;m为移动轨迹数据集中的最近记录日期MaxDate的变动因子,即近变动因子;n为移动轨迹数据集中的最远记录日期MinData的变动因子,即远变动因子;K为该移动规则日期RuleDate所在月的总天数,RuleDatek表示该月中第k天的日期值;例如,该移动规则日期RuleDate为2月27日,则K=28;RuleDate25=25;又如,该移动规则日期RuleDate为3月1日,则K=31,RuleDate26=26;通过引入每条关联移动规则日期对应的远变动因子m和近变动因子n,可以对每条关联移动规则所在日期做出准确定位,以消除日期变动对后续计算日期加权值带来的波动影响,提高日期加权值的计算精确度;
步骤三、根据移动节点当前轨迹及步骤二生成的关联移动规则,预测移动节点下一个移动轨迹:
假定当前移动节点的移动轨迹为T:(cx,tx)→(cy,ty),遍历所有关联移动规则,如果关联移动规则R包含移动轨迹T则说明关联移动规则R是匹配的移动规则,然后根据下式计算关联移动规则R的匹配度,匹配度越高则越有可能是移动节点下一个移动轨迹:
Score(R)=Confidence(R)+TWeight(R)
其中,Score(R)为关联移动规则R的匹配度,Confidence(R)为关联移动规则R的置信度,TWeight(R)为关联移动规则R的日期加权值。
下面以一个例子来具体描述本发明实施例中步骤一使用迭代方法挖掘对象数据集中所有频繁项集的执行过程,算法输入为下表所示的移动轨迹数据集,内部数据是同时具有太阳城集团和空间属性的移动轨迹记录,最小支持度阈值则设置为3,X=48:
移动轨迹数据集D
记录ID移动轨迹记录T1(1,t1),(2,t2)(5,t5)T2(2,t2),(4,t4)T9(2,t2),(4,t4)T9(1,t1),(2,t2),(4,t4)T9(1,t1),(3,t3)T9(2,t2),(3,t3)T9(1,t1),(3,t3)T9(1,t1),(2,t2)(3,t3),(5,t5)T9(1,t1),(2,t2),(4,t4)
首先遍历整个移动轨迹数据集D获得1-候选项集C1,然后计算1-候选项集C1中每个候选项的支持度,同时标识出包含该候选项的所有记录ID号,最后删除1-候选项集C1中支持度小于最小支持度阈值的候选项就得到了1-频繁项集L1,如下表所示:
1-频繁项集L1
频繁项支持度记录IDs(1,t1)6T1,T4,T5,T7,T8,T9(5,t5)7T1,T2,T3,T4,T6,T8,T9(1,t1)5T5,T6,T7,T8,T9(5,t5)3T2,T3,T4(5,t5)2T1,T8删除
接下来的步骤是利用1-频繁项集内连接运算的方式计算出2-候选项集C2,计算C2中每个候选项的支持度是通过将2-候选项集C2中每个2-候选项拆分成两个单独的1-频繁项,接着扫描包含两个1-频繁项中支持度较小的频繁项的所有移动轨迹记录而不再是通过遍历整个移动轨迹数据集D来得到。例如下表中的2-候选项(1,t1),(2,t2)可以拆分成两个频繁项(1,t1)和(2,t2),通过查询1-频繁项集L1可以知道(1,t1)的支持度小于(2,t2),因此计算(1,t1),(2,t2)的支持度就只需扫描记录ID号为T1、T4、T5、T7、T8、T9的移动轨迹记录,最后删除2-候选项集C2中支持度小于最小支持度阈值的候选项就得到了2-频繁项集L2,如下表所示:
2-频繁项集L2
2-候选项支持度1-频繁项记录IDs(1,t1),(2,t2)4(1,t1)T1,T4,T5,T7,T8,T9(1,t1),(3,t3)4(1,t1)T5,T6,T7,T8,T9(2,t2),(3,t3)1(5,t5)T2,T3,T4删除(2,t2),(3,t3)3(1,t1)T5,T6,T7,T8,T9(2,t2),(4,t4)3(5,t5)T2,T3,T4(3,t3),(4,t4)0(4,t4)T2,T3,T4删除
3-频繁项集L3的获取则是需要将3-频繁项拆分成三个单独的1-频繁项,其余计算过程和2-频繁项集L2相同,依次类推出k-频繁项集Lk,直到无法再生成频繁项为止,下表为3-频繁项集L3:
3-频繁项集L3
3-候选项支持度1-频繁项记录IDs(1,t1),(2,t2),(3,t3)2(3,t3)T5,T6,T7,T8,T9删除(1,t1),(2,t2),(3,t3)1(4,t4)T2,T3,T4删除(1,t1),(2,t2),(3,t3)0(4,t4)T2,T3,T4删除(2,t2),(3,t3),(4,t4)0(4,t4)T2,T3,T4删除
现有Apriori方法中,在由候选频繁项集生成频繁项集的过程中需要遍历整个移动轨迹数据集D来计算每条候选频繁项的支持度;而本实施例提供的方式,缩小了移动轨迹数据集扫描范围,减少了获取候选项集的太阳城集团,从而可以达到低消耗的目的。
下面再以另外一个具体的例子来具体描述本发明实施例中Apriori方法的执行过程,下表是一个具体的事务数据库D,X=48:
日期事务条目2.28(0,t3),(2,t4),(8,t18),(4,t24)3.1(2,t4),(8,t18),(4,t24),(5,t27)3.2(2,t4),(8,t18),(3,t21),(4,t24)3.3(2,t4),(8,t21),(4,t24),(5,t27)daten…pn-2,pn-1,pn
使用本实施例中的步骤一描述的方法挖掘事务数据库D中的所有频繁项集,结果如下表所示:
频繁项集支持度日期(2,t4),(8,t18)x2.28(2,t4),(4,t24)y3.1(2,t4),(8,t18),(4,t24)z3.2(8,t18),(4,t24)w3.3…………………Pn-2,Pn-1,Pn>min_suppdate
利用频繁项集生成移动节点所有可能的关联移动规则,并计算每条移动规则的置信度,结果如下表所示:
日期关联移动规则置信度2.28(2,t4)→(8,t18)95%3.1(2,t4)→(4,t24)91%3.2(2,t4),(8,t18)→(4,t24)87%3.3(2,t18)→(4,t24)90%………………datern-1→rn>min_conf
记录移动节点每条关联移动规则的日期以及计算每条关联移动规则日期的远近变动因子;同时,根据记录的日期和计算的日期远近变动因子,计算每条关联移动规则的日期加权值TWeight(R),从而得到强关联性移动规则,其中,每条关联移动规则日期对应的远变动因子m和近变动因子n计算公式如下:
M=|MaxDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek,n=|MinDate-1KΣk=1KRuleDatek|Σk=1KRuleDatek;]]>
每条关联移动规则的日期加权值TWeight(R)计算公式如下:
TWeight(R)=RuleDate-MinDatenMaxDatem-MinDaten·MinDaten·MaxDatemMaxDatem+MinDaten×100;]]>
其中,RuleDate、MaxDate以及MinData分别表示移动规则的日期、移动轨迹数据集中最近的记录日期与最远的记录日期;m为移动轨迹数据集中的最近记录日期 MaxDate的变动因子,即近变动因子;n为移动轨迹数据集中的最远记录日期MinData的变动因子,即远变动因子;K为该移动规则日期RuleDate所在月的总天数,RuleDatek表示该月中第k天的日期值;结果如下表所示:
日期关联移动规则置信度日期权值2.28(2,t4)→(8,t18)95%w13.1(2,t4)→(4,t24)91%w23.2(2,t4),(8,t18)→(4,t24)87%w33.3(8,t18)→(4,t24)90%w4……………………datern-1→rn>min_confwn
根据移动节点当前轨迹及关联移动规则,预测移动节点下一个移动轨迹:
假定当前移动节点的移动轨迹为T:(2,t4)→(8,t18),遍历所有关联移动规则,如果关联移动规则R包含移动轨迹T则说明关联移动规则R是匹配的移动规则,然后根据下式计算关联移动规则R的匹配度,匹配度越高则越有可能是移动节点下一个移动轨迹:
Score(R)=Confidence(R)+TWeight(R)
其中,Score(R)为关联移动规则R的匹配度,Confidence(R)为关联移动规则R的置信度,TWeight(R)为关联移动规则R的日期加权值;
结果如下表所示:
预测输出匹配度(2,t4),(8,t18)→(4,t24)………………
最后预测输出(4,t24),即移动节点最有可能在太阳城集团点t24接入了4号路由器。

太阳城集团本文
本文标题:一种低消耗的APRIORI方法.pdf
链接地址:http://zh228.com/p-6397413.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');