興趣模型的構(gòu)建與Apriori數(shù)據(jù)挖掘算法優(yōu)化研究*

方文和　李國和　吳衛(wèi)江　洪云峰　周曉明

(1.中國石油大學(xué)(北京)地球物理與信息工程學(xué)院　北京　102249)(2.中國石油大學(xué)(北京)油氣數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室　北京　102249)(3.石大兆信數(shù)字身份管理與物聯(lián)網(wǎng)技術(shù)研究院　北京　100029)

?

興趣模型的構(gòu)建與Apriori數(shù)據(jù)挖掘算法優(yōu)化研究*

方文和1,2,3李國和1,2,3吳衛(wèi)江1,2,3洪云峰3周曉明3

(1.中國石油大學(xué)(北京)地球物理與信息工程學(xué)院北京102249)(2.中國石油大學(xué)(北京)油氣數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室北京102249)(3.石大兆信數(shù)字身份管理與物聯(lián)網(wǎng)技術(shù)研究院北京100029)

摘要分析關(guān)聯(lián)規(guī)則算法實(shí)際過程中參數(shù)規(guī)律,改進(jìn)重構(gòu)Gray和Orlowska興趣度模型,引入興趣項(xiàng)、頻數(shù)閾值、構(gòu)建興趣模型,從而能夠減少不必要的挖掘掃描操作,提高挖掘的效率,使得挖掘更加有針對(duì)性。通過中國石油大學(xué)(北京)油氣數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室提供的標(biāo)準(zhǔn)仿真數(shù)據(jù)集合對(duì)比實(shí)驗(yàn),證明改進(jìn)后的算法效率更高,適合用于特定興趣點(diǎn)的二次高效率挖掘。

關(guān)鍵詞Apriori; 興趣項(xiàng); 關(guān)聯(lián)規(guī)則; 興趣模型; Gray和Orlowska

Class NumberTP3-05

1引言

事物數(shù)據(jù)庫中關(guān)聯(lián)規(guī)則的挖掘?yàn)閿?shù)據(jù)挖掘領(lǐng)域研究重點(diǎn)?？筛爬ǔ蓛蓚€(gè)子問題[1],為尋求符合支撐條件高頻項(xiàng)目集合以及由置信度篩選出關(guān)聯(lián)規(guī)則。前者開銷大,故研究多致力提升頻繁項(xiàng)目集合尋求的效率。此外數(shù)值型、多層關(guān)聯(lián)規(guī)則[2]的研究拓展了關(guān)聯(lián)規(guī)則。

在很多領(lǐng)域,如油田數(shù)據(jù)挖掘中,研究人員往往希望能夠高效地從歷年來積累的大量的油田參數(shù)信息中挖掘出自己感興趣并且有前經(jīng)驗(yàn)?zāi)Ｐ蛥⒖嫉南嚓P(guān)的參數(shù)之間的具體關(guān)聯(lián)規(guī)則關(guān)系,如通過關(guān)鍵的參數(shù)與產(chǎn)量關(guān)聯(lián),可以得到產(chǎn)量與相關(guān)參數(shù)的實(shí)地油田關(guān)系數(shù)據(jù)。從而能夠有針對(duì)性有效率地改進(jìn)驗(yàn)證針對(duì)于具體油田的理論模型。并且可以發(fā)現(xiàn)新關(guān)系。推導(dǎo)出合理的公式,并指導(dǎo)實(shí)際油田工業(yè)生產(chǎn)。而油田數(shù)據(jù)參數(shù)紛雜,故有針對(duì)性地提高挖掘效率顯得十分必要。

本文在分析Apriori算法基礎(chǔ)上,通過對(duì)關(guān)聯(lián)規(guī)則算法實(shí)際過程出現(xiàn)的規(guī)律,改進(jìn)重構(gòu)興趣度模型,引入興趣項(xiàng)和頻數(shù)閾值,構(gòu)建興趣度,以減少對(duì)數(shù)據(jù)庫的檢索,提出改進(jìn)方法,提高Apriori的效率。在中國石油大學(xué)(北京)油氣數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室提供的標(biāo)準(zhǔn)數(shù)據(jù)集合基礎(chǔ)上進(jìn)行效率對(duì)比實(shí)驗(yàn)。

2關(guān)聯(lián)規(guī)則概述

令D的一個(gè)子集A滿足A?D,則稱事務(wù)包含項(xiàng)集A。關(guān)聯(lián)規(guī)則A?B即A?D、B?D、A∩B=Φ[3]。

支持度與置信度是關(guān)聯(lián)規(guī)則中最重要兩個(gè)關(guān)鍵指標(biāo),它們分別為整個(gè)數(shù)據(jù)集合統(tǒng)計(jì)中的支持關(guān)鍵、關(guān)聯(lián)的可信關(guān)鍵。

支持度=P(A∪B),置信度=P(A/B)。P(A∪B),P(A/B)大于一定關(guān)聯(lián)方有關(guān)聯(lián)規(guī)則一定的實(shí)際應(yīng)用上價(jià)值,其值稱為最低支持閾值minSup和最低置信閾值minConf,于規(guī)則關(guān)聯(lián)符合minSup者即頻繁項(xiàng)集;符合minSup及minConf兩者規(guī)則即強(qiáng)規(guī)則[4]。高效的頻繁項(xiàng)集、強(qiáng)規(guī)則即是目的。

3Apriori算法

Apriori算法過程:

1) 挖掘得頻繁k-項(xiàng)集;

2) 其后由minSup篩選出頻繁k-項(xiàng)集;

3) 合并所有的頻繁k-項(xiàng)集,用minConf指標(biāo)來篩選得到頻繁關(guān)聯(lián)規(guī)則。

該算法關(guān)鍵步驟為連接與剪枝。描述如下:

1) 連接步:可連接的Lk-1自連接,得候選k項(xiàng)集Ck;

2) 剪枝步:Lk的超集即是Ck。掃描數(shù)據(jù)庫,將Ck每一個(gè)候選計(jì)數(shù),標(biāo)記的該計(jì)數(shù)值大于等于最小支持度的候選為頻繁的,即屬于Lk。

Ck若很大,則需大量計(jì)算量。為減少計(jì)算量,故壓縮Ck,根據(jù)Apriori特性:一切不頻繁(K-1)項(xiàng)集合皆非頻繁K項(xiàng)集合子集。故一待選K項(xiàng)集合(K-1)項(xiàng)集不處于Lk,待選項(xiàng)亦非頻繁的,可從Ck內(nèi)刪去[5]。改子集檢測(cè)能采用在頻繁項(xiàng)集建立的散列樹方法迅速完成。

此外,傳統(tǒng)Apriori算法過程中頻繁掃描數(shù)據(jù)庫;minSup和minConf挖掘過程中固定不可變,否則需重新挖掘。挖掘過程中沒有排除并不感興趣,浪費(fèi)大量的時(shí)間。

4改進(jìn)的Apriori算法

性質(zhì)1:若A?B,則|AB|≥minCount。若|T|

性質(zhì)2:若關(guān)聯(lián)規(guī)則中有A?B,則A與B為頻繁項(xiàng)集,而AB可能不為頻繁項(xiàng)集。[7]

定義3:令挖掘的目標(biāo)項(xiàng)集合為I,即興趣項(xiàng)集合。記錄I子集組成的項(xiàng)集在事務(wù)數(shù)據(jù)庫中的頻數(shù)為興趣項(xiàng)頻數(shù)。支持頻數(shù)閾值minSupCount為minSupCount=|D|*minSup[8]。

令關(guān)聯(lián)規(guī)則A?B中|A∪B|的最小值為minCount即頻數(shù)閾值。其中:

minCount=minSupCount*minConf

由于關(guān)聯(lián)規(guī)則A?B成立,A、B為頻繁項(xiàng)集,即|A|>minSupCount,|B|>minSupCount。A?B成立,故Conf(A?B)≥minConf。所以|A∪B|≥|A|*minConf≥|D|*minSup*minConf,即I子集里所有項(xiàng)集數(shù)不能小于minCount。

4.1建立興趣度模型

興趣度包括主觀興趣度與客觀興趣度兩方面。目前對(duì)興趣度的研究主要集中在客觀興趣度方面。[8]

根據(jù)Gray和Orlowska興趣度模型[9]得:

Interests(A?

*(p(A)p(B))m

由于關(guān)聯(lián)規(guī)則算法實(shí)際過程出現(xiàn)如規(guī)律[10],要求改進(jìn)重構(gòu)Gray和Orlowska的興趣度模型。

1) 規(guī)則A?B,A在事務(wù)數(shù)據(jù)庫中出現(xiàn)的概率越大則推導(dǎo)出由其引出關(guān)聯(lián)規(guī)則興趣越高,即A出現(xiàn)的概率越大規(guī)則A?B的興趣度應(yīng)該越大[11]。

2)A和項(xiàng)B的耦合程度越高則其關(guān)聯(lián)規(guī)則越希望被挖掘出來[12],Interests(A?B)應(yīng)該越大[12]。

3)B在事務(wù)數(shù)據(jù)庫中出現(xiàn)的概率越大表明引起項(xiàng)B的條件越多[13],則A?B概率就越小,故B與Interests(A?B)成一定反比關(guān)系[15]。

4)A?B出現(xiàn)的概率越大Interests(A?B)應(yīng)該越大[16]。

綜合上述改進(jìn)興趣度模型為

根據(jù)設(shè)定的興趣度模型結(jié)合支持度與置信度評(píng)價(jià)標(biāo)準(zhǔn)得出新的強(qiáng)關(guān)聯(lián)規(guī)則定義[14],即當(dāng)Sup(A?B)≥minSup、Conf(A?B)≥minConf且Interests(A?B)≥minInterests時(shí),稱關(guān)聯(lián)規(guī)則A?B為強(qiáng)關(guān)聯(lián)規(guī)則[16]。

4.2算法實(shí)現(xiàn)步驟

Apriori算法的改進(jìn)如下:

第一步:對(duì)興趣項(xiàng)的各個(gè)子集合的項(xiàng)頻數(shù)進(jìn)行計(jì)算

1) 準(zhǔn)備待挖掘的目標(biāo)項(xiàng)集合為I(興趣項(xiàng))和待挖掘的數(shù)據(jù)庫;

2) 掃描事務(wù)數(shù)據(jù)庫;

第二步:找出關(guān)聯(lián)關(guān)系

1) 輸入minSup,minConf,Interests(A?B),把minSup轉(zhuǎn)化為minSupCount。

2) 對(duì)保存的興趣項(xiàng)子集進(jìn)行掃描,挖掘頻繁項(xiàng)集合,如果子集頻數(shù)小于minCount進(jìn)行刪除。

3) 從計(jì)算獲得的頻繁項(xiàng)集合中,尋找置信度不小于minConf,興趣度不小于Interests(A?B)的關(guān)聯(lián)關(guān)系,并輸出。

5算法性能分析

為驗(yàn)證改進(jìn)后算法的效率,采用C#2008編譯環(huán)境下,sql server2008數(shù)據(jù)庫,在Intel(R)Pentium(R)雙核3.00GHz,2.5GB內(nèi)存250GB硬盤、Windows XP sp2操作系統(tǒng)環(huán)境。樣本數(shù)據(jù)文件是中國石油大學(xué)(北京)油氣數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室提供的關(guān)聯(lián)規(guī)則的標(biāo)準(zhǔn)仿真數(shù)據(jù)集,測(cè)試數(shù)據(jù)包含事務(wù)數(shù)為13457,每個(gè)事務(wù)包含156個(gè)屬性。在相同的硬件配置條件下,對(duì)Apriori算法和改進(jìn)后的Apriori算法的支持度從0.1,0.2,0.3,0.4,0.5的情況下,進(jìn)行100次測(cè)試取平均值,統(tǒng)計(jì)結(jié)果如表1所示。

表1　算法實(shí)驗(yàn)測(cè)試結(jié)果

兩種算法的軟硬件測(cè)試環(huán)境相同,如圖1比較Apriori算法和改進(jìn)后的Apriori算法的計(jì)算時(shí)間,其中小圓點(diǎn)趨勢(shì)線是標(biāo)準(zhǔn)Apriori算法的擬合線,方塊點(diǎn)連線為改進(jìn)后的Apriori算法的擬合線,可知改進(jìn)后的Apriori算法的計(jì)算時(shí)間小于Apriori算法。

圖1　算法效率對(duì)比

6結(jié)語

本文通過對(duì)關(guān)聯(lián)規(guī)則算法實(shí)際過程參數(shù)相關(guān)關(guān)系進(jìn)行分析研究,改進(jìn)重構(gòu)Gray和Orlowska興趣度模型,使之更符合實(shí)際挖掘規(guī)律。具體挖掘引入興趣項(xiàng)和頻數(shù)閾值,構(gòu)建興趣度,以減少對(duì)數(shù)據(jù)庫的檢索,提出改進(jìn)的算法,提高Apriori的效率。該算法能夠有效減少不感興趣的部分的數(shù)據(jù)庫掃描操作,降低數(shù)據(jù)庫的掃描頻數(shù)。在中國石油大學(xué)(北京)油氣數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室提供的標(biāo)準(zhǔn)數(shù)據(jù)集合基礎(chǔ)上經(jīng)對(duì)比實(shí)驗(yàn):改進(jìn)后的關(guān)聯(lián)規(guī)則挖掘時(shí)間效率較高,使得關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘更加有針對(duì)性。

參 考 文 獻(xiàn)

[1] Al-Betar M A, Doush I A, Khader A T, et al. Novel selectionshemes for harmony search[J] . Applied Mathematicsand Computation,2012,218(10):6095-6117.

[2] Khmelev D, Tweedy F J. Using Markov chains for identification of Writers[J]. Literary and Linguistic Computing,2001,16(4):299-307.

[3] 徐章艷,張師超,盧景麗.挖掘關(guān)聯(lián)規(guī)則中的一種優(yōu)化的Apriori算法[J].計(jì)算機(jī)工程,2003(19):83-87.

XU Zhangyan, ZHANG Shichao, LU Jingli. An optimized Apriori algorithm for mining association rules[J]. Computer Engineering,2003(19):83-87.

[4] 朱玉全,孫志揮.大型事務(wù)數(shù)據(jù)庫中的一種快速的規(guī)則挖掘算法[J].計(jì)算機(jī)科學(xué),2002(10):59-69.

ZHU Yuquan, SUN Zhihui. A fast rule mining algorithm forlarge database[J]. Computer Science,2002(10):59-69.

[5] Mao YX, Shi Bl. AFOPT-Tax: An efficient method for mining generalized requent itemsets[C]//Proc. of the 2nd Asian Conf. on Intelligent Information and Database Systems(Aciids),2010:82-92.

[6] Agrawal R, Srikant R. Fast algorithms for mining association rules[C]//Proc. of the Int’t Conf. on Very Large Data Bases(VLDB). Santiago,1994:487-499.

[7] Mahdavi M, Fesanghary M, Damangir E. An Improved Harmo-ny Search Algorithm for Solving Optimization Problems[J]. Applied Mathematics and Computation,2007,188(2):1567-1579.

[8] 覃雄派,王會(huì)舉.數(shù)據(jù)管理技術(shù)的新格局[J].軟件學(xué)報(bào),2013(2):175-197.

QIN Xiong, WANG Huiju. New pattern of data management technology[J]. Software Journal,2013(2):175-197.

[9] Yule G U. On sentence length as a statistical characteristic of stylein prose with application to two cases of disputed authorship[J]. Biometrika,1938,30:363-390.

[10] 高宏賓,潘谷,黃義明.基于頻繁項(xiàng)集特性的Apriori算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2007(10):2273-2276.

GAO Hongbin, PAN Gu, HUANG Yiming. Improvement of Apriori algorithm based on frequent item sets[J]. Computer Engineering and Design,2007(10):2273-2296.

[11] Liu GM, Lu HJ, Lou WW, et al. Efficient mining of frequent patterns using ascending frequency ordered prefix-tree[J]. Data Mining and Knowledge Discovery(DMKD),2004,9(3):249-274.

[12] 李金厚,周麗平,于曉青.基于用戶操作行為的興趣度的分析與計(jì)算[J].工業(yè)控制計(jì)算機(jī),2011(7):64-67.

LI Jinhou, ZHOU Liping, YU Xiaoqing. Analysis and calculation of interest based on user’s operation behavior[J]. Industrial Control Computer,2011(7):64-67.

[13] Sriphaew K, Theeramunkong T. Fast algorithm for mining generalized frequent patterns of generalized association rules[J]. IEICE Trans. on Information and Systems(TOIS),2004,E87-D(3):761-770.

[14] 尤磊,蘭洋,熊炎.一種基于關(guān)系代數(shù)的Apriori優(yōu)化方法[J].信陽師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2010(1):156-160.

YOU Lei, LAN Yang, XIONG Yan. Apriori optimization method based on relational algebra[J]. Journal of Xinyang Normal University(NATURAL SCIENCE EDITION),2010(1):156-160.

[16] 王偉勤,鄭燊海.Apriori算法的進(jìn)一步改進(jìn)[J].計(jì)算機(jī)與數(shù)字工程,2009(4):20-23.

WANG Weiqin, ZANG Shenhai. Further improvement of Apriori algorithm[J]. Computer and Digital Engineering,2009(4):20-23.

Optimization of Apriori Algorithm for Mining Interest Model

FANG Wenhe1,2,3LI Guohe1,2,3WU Weijiang1,2,3HONG Yunfeng3ZHOU Xiaoming3

(1. College of Geophysics and Information Engineering, China University of Petroleum, Beijing102249)(2. Beijing Key Lab of Data Mining for Petroleum Data, China University of Petroleum, Beijing102249)(3. PanPass Institute of Digital Identification Management and Internet of Things, Beijing100029)

AbstractParameters of association rules algorithm in the actual process are analyzed, the interest model of Gray and Orlowska reconstruction is improved, interest, frequency threshold are introduced, interest model is built, which can reduce unnecessary mining scanning operation, improve the efficiency of mining, the mining more targeted. The standard simulation data set of the Key Laboratory of China University of Petroleum(Beijing) is used to prove the efficiency of the improved algorithm is higher, which is suitable for the two time efficient mining of specific interest points.

Key WordsApriori, interest, association rules, interest model, Gray and Orlowska

* 收稿日期:2015年11月4日,修回日期:2015年12月25日

基金項(xiàng)目:國家高新技術(shù)研究發(fā)展計(jì)劃(編號(hào):2009AA062802);國家自然科學(xué)基金(編號(hào):60473125);中國石油(CNPC)石油科技中青年創(chuàng)新基金(編號(hào):05E7013);國家重大專項(xiàng)子課題(編號(hào):G5800-08-ZS-WX)資助。

作者簡介:方文和,男,碩士研究生,研究方向:知識(shí)發(fā)現(xiàn),數(shù)據(jù)挖掘,信息安全。李國和,男,博士,教授,博士生導(dǎo)師,研究方向:人工智能,知識(shí)發(fā)現(xiàn),信息安全。吳衛(wèi)江,男,博士,副教授,研究方向:人工智能,知識(shí)發(fā)現(xiàn)。洪云峰,男,研究方向:ERP與數(shù)據(jù)管理。周曉明,男,高級(jí)工程師,研究方向:信息管理系統(tǒng)、決策支持。

中圖分類號(hào)TP3-05

DOI:10.3969/j.issn.1672-9722.2016.05.001