王立亞，張春英+，劉保相

1.華北理工大學(xué) 理學(xué)院，河北 唐山 063009

2.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063009

帶參數(shù)區(qū)間關(guān)聯(lián)規(guī)則挖掘算法與應(yīng)用*

王立亞1,2，張春英1,2+，劉保相1,2

1.華北理工大學(xué) 理學(xué)院，河北 唐山 063009

2.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063009

WANG Liya,ZHANG Chunying,LIU Baoxiang.Mining algorithm of interval association rule with parameters and its application.Journal of Frontiers of Computer Science and Technology,2016,10(11)：1546-1554.

通過(guò)研究基于經(jīng)典概念格的關(guān)聯(lián)規(guī)則提取算法，結(jié)合區(qū)間概念格的概念性質(zhì)和結(jié)構(gòu)特性，提出了一種帶參數(shù)的區(qū)間關(guān)聯(lián)規(guī)則提取模型，以解決不確定規(guī)則的挖掘問(wèn)題。首先給出了區(qū)間規(guī)則挖掘過(guò)程中的一系列定義和相關(guān)定理，并基于區(qū)間概念的不確定性，定義了區(qū)間關(guān)聯(lián)規(guī)則的度量標(biāo)準(zhǔn)——精度和不確定度；之后構(gòu)建了基于區(qū)間概念格的帶參數(shù)規(guī)則挖掘模型，分析表明模型能提取具有較高支持度和置信度的關(guān)聯(lián)規(guī)則，提高了規(guī)則的可靠性；最后用圖書(shū)推薦的實(shí)例驗(yàn)證了模型的可行性，同時(shí)研究了區(qū)間參數(shù)α和β對(duì)區(qū)間關(guān)聯(lián)規(guī)則的影響。

區(qū)間概念格；帶參數(shù)規(guī)則挖掘；支持度；置信度；規(guī)則精度

1 引言

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘理論最重要的分支之一，主要研究大量數(shù)據(jù)中項(xiàng)集之間潛在的關(guān)聯(lián)或者相關(guān)關(guān)系[1]，最典型的例子是購(gòu)物籃分析，即分析出哪些商品顧客傾向于一起購(gòu)買(mǎi)，從而為決策者提供有利于增加收益的商品擺放方式。例如，銷(xiāo)售界的神話“啤酒與尿布”的故事。啤酒與尿布本來(lái)是風(fēng)馬牛不相及的，但是在美國(guó)一般是母親在家中照看嬰兒，年輕的父親去超市購(gòu)買(mǎi)尿布。父親在購(gòu)買(mǎi)尿布時(shí)，往往會(huì)順便為自己購(gòu)買(mǎi)啤酒，這個(gè)發(fā)現(xiàn)為商家?guī)?lái)了巨大的利潤(rùn)。因此，通過(guò)海量數(shù)據(jù)挖掘出有用的規(guī)則是非常有意義的。

在經(jīng)典概念格中，數(shù)據(jù)集中的最大項(xiàng)集可以由概念結(jié)點(diǎn)的內(nèi)涵表示，因此概念格是進(jìn)行關(guān)聯(lián)規(guī)則挖掘的有效數(shù)學(xué)模型[2]。國(guó)內(nèi)外學(xué)者在概念格與關(guān)聯(lián)規(guī)則挖掘方面做了很多工作，研究成果表明：利用概念格設(shè)計(jì)出的關(guān)聯(lián)規(guī)則算法無(wú)論是在分類(lèi)規(guī)則還是在決策規(guī)則的挖掘上都要比傳統(tǒng)的數(shù)據(jù)挖掘工具有優(yōu)勢(shì)。國(guó)內(nèi)外學(xué)者在基于概念格的關(guān)聯(lián)規(guī)則挖掘方面進(jìn)行了深入的研究。梁吉業(yè)等人提出了一種基于閉標(biāo)記的漸進(jìn)式規(guī)則提取算法[3]。李金海等人則針對(duì)決策形式背景提出了概念格的屬性約簡(jiǎn)及規(guī)則挖掘算法[4]。仇國(guó)芳等人基于決策推理對(duì)變精度概念格進(jìn)行了延伸，將生成的少數(shù)決策規(guī)則集拓展為全部方案集上的決策推理規(guī)則，得到了上下近似決策推理規(guī)則[5-6]。Tang等人基于分類(lèi)概念格提出了分類(lèi)規(guī)則挖掘算法[7]。Fan等人針對(duì)區(qū)間值信息系統(tǒng)提出了一種基于粗集方法的分類(lèi)規(guī)則發(fā)現(xiàn)方法[8]。Hong等人基于模糊粗糙集理論提出了一種從不完備系統(tǒng)中同時(shí)提取確定和不確定模糊規(guī)則的方法，并估計(jì)了學(xué)習(xí)過(guò)程中的遺漏值[9]。王國(guó)胤等人針對(duì)面向領(lǐng)域用戶(hù)的決策規(guī)則挖掘問(wèn)題，用屬性序描述領(lǐng)域用戶(hù)的需求和興趣，提出了一種屬性序下的分層遞階決策規(guī)則挖掘算法[10]。黃加增運(yùn)用粗糙概念格給出了決策形式背景下的多屬性約簡(jiǎn)與規(guī)則提取方法[11]。粗糙集已獲得了一些成功的應(yīng)用實(shí)例[12-13]，但始終應(yīng)用有限，究其原因應(yīng)是其在技術(shù)上還存在著一些問(wèn)題，如置信水平低，規(guī)則數(shù)量龐大等。

通過(guò)以上的分析可知，運(yùn)用粗糙集進(jìn)行屬性約簡(jiǎn)，提取規(guī)則，或者直接運(yùn)用粗糙概念格挖掘規(guī)則，雖然能夠同時(shí)提取確定性-不確定性規(guī)則，也部分地緩解了規(guī)則庫(kù)過(guò)于龐大的問(wèn)題，并提高了規(guī)則挖掘的實(shí)效性，但其置信度和支持度仍然過(guò)于低下。于是，尋找一種更高效的規(guī)則表示模型和挖掘算法是當(dāng)前迫切需要解決的問(wèn)題。區(qū)間概念格[14-15]是在粗糙概念格基礎(chǔ)上，考慮概念外延為區(qū)間[α,β](0≤α≤β≤1)范圍內(nèi)滿(mǎn)足內(nèi)涵屬性的對(duì)象集而得到的一種新的概念層次結(jié)構(gòu)，其能夠描述決策中對(duì)符合一定條件范圍的規(guī)則進(jìn)行提取的實(shí)際問(wèn)題。研究區(qū)間概念格的帶參數(shù)關(guān)聯(lián)規(guī)則挖掘算法對(duì)于挖掘不確定規(guī)則和制定不確定決策有很大的現(xiàn)實(shí)意義。

本文結(jié)合區(qū)間概念格的結(jié)構(gòu)特性和結(jié)點(diǎn)性質(zhì)，給出了針對(duì)不確定規(guī)則的度量標(biāo)準(zhǔn)——精度和不確定度，構(gòu)建了基于區(qū)間概念格的帶參數(shù)規(guī)則挖掘模型，研究了區(qū)間參數(shù)α和β對(duì)區(qū)間關(guān)聯(lián)規(guī)則的影響。

2 關(guān)聯(lián)規(guī)則基本理論

設(shè)I={i1,i2,…,in}是項(xiàng)的集合，與任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫(kù)中的事務(wù)集合。其中每個(gè)事務(wù)T是項(xiàng)的集合，滿(mǎn)足T?I；設(shè)A為項(xiàng)的集合，當(dāng)且僅當(dāng)滿(mǎn)足A?T，稱(chēng)事務(wù)T包含A[1-2]。

關(guān)聯(lián)規(guī)則[1-2]是形如 A?B的蘊(yùn)含式，其中有A?I，B?I，并且滿(mǎn)足A?B=?。

在事務(wù)集合D中，關(guān)聯(lián)規(guī)則A?B具有支持度θ和置信度c。其中支持度θ是概率P(A?B)，表示事務(wù)包含A?B的百分比；置信度c是條件概率P(B|A)，表示D中的事務(wù)在包含A的同時(shí)也包含B的百分比。分別定義為：

關(guān)聯(lián)規(guī)則的支持度描述一個(gè)關(guān)聯(lián)規(guī)則的有用性，置信度描述了其確定性[1-2]。如將商場(chǎng)中所有商品設(shè)成一個(gè)集合，顧客購(gòu)買(mǎi)面包的同時(shí)也購(gòu)買(mǎi)牛奶的關(guān)聯(lián)規(guī)則支持度為1.5%，就表示所有數(shù)據(jù)中有1.5%的交易記錄同時(shí)包含面包和牛奶；其置信度為55%就表示在所有交易記錄中有55%的顧客在購(gòu)買(mǎi)面包的情況下還會(huì)購(gòu)買(mǎi)牛奶。

滿(mǎn)足最小支持度閾值min_Sup和最小置信度閾值min_Conf的規(guī)則稱(chēng)作強(qiáng)規(guī)則，可以用百分?jǐn)?shù)表示支持度和置信度，一般由用戶(hù)或者專(zhuān)家來(lái)設(shè)置閾值min_Sup和min_Conf。

項(xiàng)集表示的是數(shù)據(jù)項(xiàng)的集合；k-項(xiàng)集表示包含k個(gè)數(shù)據(jù)項(xiàng)的項(xiàng)集。一個(gè)項(xiàng)集的出現(xiàn)頻度，也稱(chēng)為該項(xiàng)集的支持頻度，就是D中包含該項(xiàng)集的記錄數(shù)。如果某個(gè)項(xiàng)集滿(mǎn)足最小支持度閾值，則說(shuō)明該項(xiàng)集的出現(xiàn)頻度大于數(shù)據(jù)集D中的記錄數(shù)乘以最小支持度閾值；最小支持頻度就是記錄中滿(mǎn)足最小支持度閾值的記錄數(shù)。滿(mǎn)足最小支持度閾值的項(xiàng)集稱(chēng)為頻繁項(xiàng)集[1]。

挖掘關(guān)聯(lián)規(guī)則的主要步驟如下：

步驟1發(fā)現(xiàn)所有的頻繁項(xiàng)集，這些項(xiàng)集的頻度大于或等于最小支持頻度。

步驟2根據(jù)上一步得到的頻繁項(xiàng)集，產(chǎn)生滿(mǎn)足置信度閾值的關(guān)聯(lián)規(guī)則。

3 帶參數(shù)區(qū)間關(guān)聯(lián)規(guī)則挖掘

區(qū)間概念格與其他概念格在格結(jié)構(gòu)及結(jié)點(diǎn)上有較大差異，首先重新給出區(qū)間規(guī)則挖掘過(guò)程中的一系列定義和相關(guān)定理；其次，定義了區(qū)間關(guān)聯(lián)規(guī)則的精度與不確定度；最后，構(gòu)建了基于區(qū)間概念格的關(guān)聯(lián)規(guī)則挖掘模型，通過(guò)分析表明了模型的正確性。

3.1 區(qū)間關(guān)聯(lián)規(guī)則及度量

事務(wù)數(shù)據(jù)庫(kù)可以轉(zhuǎn)換成一個(gè)形式背景(U,A,R)，其中U是事務(wù)的集合，A是數(shù)據(jù)庫(kù)中特征（屬性）的集合，當(dāng)x∈U，a∈A時(shí)，xRa表示a屬于x的項(xiàng)集。

定義1設(shè)最小支持度閾值為θ，對(duì)于區(qū)間概念格中任一概念結(jié)點(diǎn)C，若其上界外延(Mα)中的對(duì)象個(gè)數(shù)不小于（大于或者等于）|U|×θ，則C稱(chēng)為α-上界頻繁結(jié)點(diǎn)，與C對(duì)應(yīng)的內(nèi)涵Y稱(chēng)為α-上界頻繁項(xiàng)集；若其下界外延(Mβ)中的對(duì)象個(gè)數(shù)不小于|U|×θ，則稱(chēng)C為β-下界頻繁結(jié)點(diǎn)，對(duì)應(yīng)的Y稱(chēng)為β-下界頻繁項(xiàng)集。

與經(jīng)典概念格不同，區(qū)間概念格中的父子概念在頻繁性上不具有特定的關(guān)系。

定義2設(shè)最小支持度閾值和最小置信度閾值分別為θ和c，區(qū)間概念格中兩個(gè)頻繁概念結(jié)點(diǎn)C1=構(gòu)成的結(jié)點(diǎn)二元組(C1,C2)滿(mǎn)足且，則(C1,C2)被稱(chēng)為α-上界候選二元組；同樣，當(dāng)(C1,C2)滿(mǎn)足且，則(C1,C2)被稱(chēng)為 β-下界候選二元組。將由候選二元組(C1,C2)得到的規(guī)則集合記為Rules(C1,C2)。

區(qū)間概念中有上下界兩個(gè)概念外延，可分別提取α-上界關(guān)聯(lián)規(guī)則和β-下界關(guān)聯(lián)規(guī)則。它們的支持度和置信度計(jì)算方法如下。

式中：|???|表示對(duì)象的個(gè)數(shù)。

定義3設(shè)規(guī)則A?B是由候選二元組(C1,C2)生成的α-上界關(guān)聯(lián)規(guī)則，C1的上界外延，C1的內(nèi)涵Y1，C2的上界外延為，C2的內(nèi)涵為Y2，則A?B的規(guī)則精度為：

則規(guī)則A?B的不確定度為：

定義4對(duì)區(qū)間關(guān)聯(lián)規(guī)則A?B，若滿(mǎn)足如下兩個(gè)條件，則被稱(chēng)為強(qiáng)關(guān)聯(lián)規(guī)則：

（1）A?B是頻繁項(xiàng)集，Sup(A?B)≥θ；

（2）Conf(A?B)≥c，即|P(A?B)|/|P(A)|≥c。式中，θ為最小支持度閾值；c為最小置信度閾值。

定理1區(qū)間概念格中，如果(C1,C2)和(C1,C3)是候選二元組且C3>C2，則Rules(C1,C3)中的規(guī)則都可以由Rules(C1,C2)中的某條規(guī)則導(dǎo)出。

區(qū)間概念格的上下界外延是具有內(nèi)涵中一部分屬性的對(duì)象的集合，因此由區(qū)間概念格提取的規(guī)則是不確定的，需要對(duì)其進(jìn)行度量。

定義5設(shè)α-規(guī)則集為Ω={Rules1,Rules2,…,Rulesk}，規(guī)則集中的規(guī)則Rulesi對(duì)應(yīng)的不確定度為UDα-Ri，則α-規(guī)則集的不確定度為：

設(shè) β-規(guī)則集為Ω′={Rules1′,Rules2′,…,Rulesm′}，規(guī)則集中的規(guī)則Rulesj′對(duì)應(yīng)的不確定度為UDβ-Rj，則β-規(guī)則集的不確定度為：

區(qū)間關(guān)聯(lián)規(guī)則的不確定度為：

3.2 帶參數(shù)規(guī)則挖掘算法

算法1帶參數(shù)區(qū)間規(guī)則挖掘算法

輸出：區(qū)間關(guān)聯(lián)規(guī)則。

步驟1廣度優(yōu)先遍歷區(qū)間概念格，得到α-上界頻繁結(jié)點(diǎn)集合α-Fcset及 β-下界頻繁結(jié)點(diǎn)集合β-Fcset。

步驟2生成所有α-上界候選二元組和β-下界候選二元組。

步驟3消除冗余的候選二元組。

步驟4由上一步中得到的α-上界候選二元組和 β-下界候選二元組可以計(jì)算α-上界頻繁項(xiàng)集α-Fcset和β-下界頻繁項(xiàng)集β-Fcset。

步驟5生成α-上界關(guān)聯(lián)規(guī)則集α-Rulesset和β-下界關(guān)聯(lián)規(guī)則集β-Rulesset。

3.3 算法分析

本文提出的帶參數(shù)區(qū)間關(guān)聯(lián)規(guī)則提取算法的時(shí)間復(fù)雜度由頻繁項(xiàng)集計(jì)算與關(guān)聯(lián)規(guī)則生成兩部分組成。頻繁項(xiàng)集的計(jì)算分為頻繁結(jié)點(diǎn)搜索，候選二元組生成，去除冗余3個(gè)過(guò)程。設(shè)區(qū)間概念格中概念結(jié)點(diǎn)數(shù)為n，則有小于等于n個(gè)頻繁結(jié)點(diǎn)，頻繁結(jié)點(diǎn)搜索的時(shí)間復(fù)雜度為O(n)。候選二元組生成的時(shí)間復(fù)雜度為O(n2)，其與每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)數(shù)量有關(guān)系，空間復(fù)雜度為2n2。去除冗余過(guò)程的時(shí)間復(fù)雜度為O(n4)，空間復(fù)雜度為4n4。區(qū)間關(guān)聯(lián)規(guī)則生成過(guò)程的時(shí)間復(fù)雜度為O(n4)，空間復(fù)雜度為8n4。

算法生成的頻繁結(jié)點(diǎn)是基于外延基數(shù)不小于形式背景中對(duì)象個(gè)數(shù)與最小支持度閾值θ的乘積，即滿(mǎn)足強(qiáng)關(guān)聯(lián)規(guī)則的第1個(gè)判別條件；生成的候選二元組中兩個(gè)概念的外延基數(shù)的比值不小于最小置信度閾值c，即滿(mǎn)足強(qiáng)關(guān)聯(lián)規(guī)則的第2個(gè)判別條件。綜合以上兩點(diǎn)，算法保障了提取的規(guī)則都是強(qiáng)關(guān)聯(lián)規(guī)則。此外，算法去除了冗余候選二元組，實(shí)現(xiàn)了對(duì)區(qū)間關(guān)聯(lián)規(guī)則的縮減?；诖怂惴芴崛〕鲚^精煉的不確定強(qiáng)規(guī)則，提高了規(guī)則的可靠性。

4 實(shí)例驗(yàn)證

隨著圖書(shū)館館藏資源的增加和互聯(lián)網(wǎng)技術(shù)的發(fā)展，高校圖書(shū)館中的圖書(shū)信息得到了爆炸式增長(zhǎng)，如何根據(jù)歷史借閱數(shù)據(jù)庫(kù)得到關(guān)聯(lián)規(guī)則，并將這類(lèi)規(guī)則直接作為知識(shí)推薦給用戶(hù)，實(shí)現(xiàn)系統(tǒng)的書(shū)籍推薦功能和館藏圖書(shū)的高效利用成為當(dāng)下圖書(shū)館管理系統(tǒng)研究的重點(diǎn)。表1所示為6位讀者對(duì)6本書(shū)的借閱情況形成的形式背景表。設(shè)α=0.7，β=0.8。運(yùn)用區(qū)間概念格構(gòu)造[14]及其壓縮[15]方法，得到如表2所示的區(qū)間概念和如圖1所示的區(qū)間概念格結(jié)構(gòu)。

Table 1 Formal context表1 形式背景

Table 2 Interval concepts from Table 1表2 由表1中形式背景得到的區(qū)間概念

4.1 基于區(qū)間概念格的規(guī)則提取

設(shè)定最小支持度閾值θ=50%和最小置信度閾值θ=80%。通過(guò)遍歷區(qū)間概念格中所有概念結(jié)點(diǎn)得到0.7-上界頻繁結(jié)點(diǎn)集合0.7-Fcset={C3,C5,C9,C19, C20,C23,C26,C28,C30,C34}及 0.8-下界頻繁結(jié)點(diǎn)集合0.8-Fcset={C3,C5,C9,C34}。

其次，由0.7-Fcset和0.8-Fcset生成0.7-上界候選二元組和0.8-下界候選二元組并去除冗余，結(jié)果如表3所示。

由0.7-上界候選二元組生成0.7-上界關(guān)聯(lián)規(guī)則0.7-Rluesset={c?abe,be?ac,bce?a,c?bde,be?cd, bce?d,c?bef,be?cf,bce?f,abcf?e,abef?c,acef?b}。由0.8-下界候選二元組生成0.8-下界關(guān)聯(lián)規(guī)則0.8-Rluesset={c?be,be?c}。

由以上可以看出，提取出的下界關(guān)聯(lián)規(guī)則只有兩條，在進(jìn)行推薦時(shí)可供參考的規(guī)則較少。此時(shí)，可將上界關(guān)聯(lián)規(guī)則作為下界關(guān)聯(lián)規(guī)則的一個(gè)補(bǔ)充，豐富推薦內(nèi)容。由下界關(guān)聯(lián)規(guī)則be?c做出的圖書(shū)推薦為：當(dāng)讀者閱讀了b、e時(shí)，為其推薦c。此時(shí)，讀者可選擇的圖書(shū)只有一種，可將上界關(guān)聯(lián)規(guī)則be?ac作為一個(gè)有力的補(bǔ)充，即最終的圖書(shū)推薦為：當(dāng)讀者閱讀了b、e時(shí)，為其推薦a、c。

計(jì)算0.7-Rluesset和0.8-Rluesset中所有關(guān)聯(lián)規(guī)則的支持度、置信度、精度和不確定度，得到表4所示的結(jié)果。

由表4可以看出，提取出的規(guī)則的支持度均不小于θ=50%且置信度均不小于c=80%，即全部為強(qiáng)關(guān)聯(lián)規(guī)則。由表4可以計(jì)算出0.7-Rluesset和0.8-Rluesset的不確定度分別為：UD0.7-Rluesset=0.25，UD0.8-Rluesset=0。因此，區(qū)間關(guān)聯(lián)規(guī)則的不確定度UD=max{0.25,0}= 0.25。

Fig.1 Interval concept lattice from Table 1圖1 由表1中的形式背景得到的區(qū)間概念格結(jié)構(gòu)

Table 3 Candidate binary groups表3 候選二元組

Table 4 Result of 4 measurements of association rules表4 區(qū)間關(guān)聯(lián)規(guī)則4種度量結(jié)果

4.2 對(duì)比與分析

在表1所示的形式背景下，基于概念格理論的不同關(guān)聯(lián)規(guī)則挖掘模型的頻繁結(jié)點(diǎn)數(shù)、關(guān)聯(lián)規(guī)則數(shù)、精度與不確定度如表5所示。

由表5可見(jiàn)，基于概念格的關(guān)聯(lián)規(guī)則挖掘算法、基于概念格的無(wú)冗余規(guī)則挖掘算法（non-redundant association rule mining algorithm based on concept lattice，NARMC）[16]、FP-tree上頻繁概念格的無(wú)冗余關(guān)聯(lián)規(guī)則提取算法DFCLA（discover frequent concept lattice algorithm）[17]、基于FP-tree和約束概念格的關(guān)聯(lián)規(guī)則挖掘算法DFTFH（depth-first traversal FP-tree toHasse）[18]和基于頻繁閉項(xiàng)集格（frequent closed itemsent lattice，F(xiàn)CIL）的關(guān)聯(lián)規(guī)則挖掘模型[19]均提取出3條關(guān)聯(lián)規(guī)則，且精度為1，不確定度為0，也就是說(shuō)由這3個(gè)模型挖掘的規(guī)則不包含不確定信息，且規(guī)則數(shù)目少，不足以滿(mǎn)足用戶(hù)的需求。粗糙概念格提取出的規(guī)則數(shù)目多達(dá)31條，其精度僅為0.17，說(shuō)明挖掘的規(guī)則應(yīng)用效率低且可靠性差，在實(shí)際應(yīng)用時(shí)不能準(zhǔn)確反映不確定信息。由區(qū)間概念格提取的關(guān)聯(lián)規(guī)則數(shù)目為14，精度為0.75，不確定度為0.25，說(shuō)明區(qū)間概念格可提取出不確定規(guī)則，彌補(bǔ)了概念格、NARMC算法、DFCLA算法、DFTFH算法和基于FCIL的關(guān)聯(lián)規(guī)則挖掘模型不能提取不確定規(guī)則的不足；與粗糙概念格相比，提高了規(guī)則的應(yīng)用效率與可靠性。

此外，由區(qū)間概念格提取的關(guān)聯(lián)規(guī)則的數(shù)量、精度與不確定度均可根據(jù)用戶(hù)需求，通過(guò)調(diào)整區(qū)間參數(shù)實(shí)現(xiàn)動(dòng)態(tài)調(diào)控。

Table 5 Analysis summary table of different models based on concept lattice theory表5 基于概念格理論的不同模型對(duì)比分析匯總表

4.3 區(qū)間參數(shù)對(duì)規(guī)則的影響

區(qū)間概念的外延是由區(qū)間參數(shù)α和β決定的，區(qū)間參數(shù)的變化會(huì)影響區(qū)間概念和區(qū)間概念格結(jié)構(gòu)，進(jìn)而對(duì)區(qū)間關(guān)聯(lián)規(guī)則的數(shù)量、不確定度等產(chǎn)生影響。

當(dāng)α=0.5，β變化時(shí)，生成的關(guān)聯(lián)規(guī)則數(shù)量和區(qū)間關(guān)聯(lián)規(guī)則不確定度的變化情況如圖2所示。圖2表明，α=0.5時(shí)，β-下界關(guān)聯(lián)規(guī)則數(shù)量和β-下界關(guān)聯(lián)規(guī)則不確定度都隨著β增大而減??；區(qū)間關(guān)聯(lián)規(guī)則的不確定度依賴(lài)0.5-上界關(guān)聯(lián)規(guī)則不確定度的變化。

當(dāng)β=0.9，α變化時(shí)，關(guān)聯(lián)規(guī)則數(shù)量和區(qū)間關(guān)聯(lián)規(guī)則不確定度的變化情況如圖3所示。由圖3可知，β=0.9時(shí)，α-上界關(guān)聯(lián)規(guī)則數(shù)量和α-上界關(guān)聯(lián)規(guī)則不確定度都隨著α增大而減小。α-上界關(guān)聯(lián)規(guī)則不確定度與區(qū)間關(guān)聯(lián)規(guī)則不確定度在圖3中重合，此時(shí)區(qū)間關(guān)聯(lián)規(guī)則的不確定度依賴(lài)α的變化。

Fig.2 Influence ofβto association rules inα=0.5圖2 α=0.5時(shí)β變化對(duì)關(guān)聯(lián)規(guī)則的影響

Fig.3 Influence ofαto association rules inβ=0.9圖3 β=0.9時(shí)α變化對(duì)關(guān)聯(lián)規(guī)則的影響

5 結(jié)論與展望

本文提出了基于區(qū)間概念格的帶參數(shù)關(guān)聯(lián)規(guī)則挖掘模型，定義了度量區(qū)間關(guān)聯(lián)規(guī)則的不確定度，分析了區(qū)間參數(shù)α和β的變化對(duì)關(guān)聯(lián)規(guī)則的影響。通過(guò)實(shí)例證明了挖掘算法的正確性與可行性，區(qū)間參數(shù)研究的實(shí)例表明，區(qū)間關(guān)聯(lián)規(guī)則的不確定度更依賴(lài)于參數(shù)α的變化，為進(jìn)一步研究調(diào)整參數(shù)以提高規(guī)則的可控性奠定了基礎(chǔ)。

[1]Tan P N,Steinbach M,Kumar V.Introduction to data mining[M].Beijing:Posts and Telecom Press,2011.

[2]Hu Xuegang,Wang Yuanyuan.A fast RECL-based algorithm for mining association rules[J].Computer Engineering andApplications,2005,41(22):180-183.

[3]Liang Jiye,Wang Junhong.A new lattice structure and method for extracting association rules based on concept lattice[J].International Journal of Computer Science and Network Security,2006,6(11):107-114.

[4]Li Jinhai,Lv Yuejin.Attribute reduction and extraction in decision formal context based on concept lattice[J].Mathematics in Practice and Theory,2009(7):137-144.

[5]Qiu Guofang.Approaches to reasoning in decision making based on variable threshold concept lattices[J].Systems Engineering—Theory&Practice,2010,30(6):1092-1098.

[6]Qiu Guofang,Ma Jianmin,Yang Hongzhi,et al.Mathematical model of concept granular computing system[J].Science China:F Series Information Science,2009,39(12): 1239-1247.

[7]Tang Jingsheng,He Wei,Zhang Wei,et al.An algorithm of extracting classification rule based on classified concept lattice[C]//Proceedings of the 2nd International Workshop on Database Technology and Applications,Wuhan,China,Nov 27-28,2010.Piscataway,USA:IEEE,2010:428-431.

[8]Fan Y N,Tseng T L,Chern C C.Rule inducation based on an incremental rough set[J].Expert Systems with Applications,2009,36(9):11439-11450.

[9]Hong T P,Tseng L H,Chien B C.Mining from incomplete quantitative data by fuzzy rough sets[J].Expert Systems withApplications,2010,37(3):2644-2653.

[10]Guan Lihe,Wang Guoyin,Hu Feng.A decision rules mining algorithm based on attribute order[J].Control and Decision, 2012,27(2):313-316.

[11]Huang Jiazeng.Based on rough concept lattice attribute and rule acquisition[J].Software,2011,32(10):16-23.

[12]Leung Y,Manfred M F,Wu Weizhi.A rough set approach for the discovery of classification rules in interval-valued information systems[J].International Journal of Approximate Reasoning,2008,47(2):233-246.

[13]Dong Wei,Wang Jianhui,Gu Shusheng.Rule induction approach based on variable precision rough set theory[J].Control Engineering of China,2007,14(1):73-75.

[14]Zhang Chunying,Wang Liya.Incremental construction algorithm based on attribute power set for interval concept lattice[J].Application Research of Computers,2014,31 (3):731-734.

[15]Zhang Chunying,Wang Liya,Liu Baoxiang.Dynamic reduction theory for interval concept lattice based on covering [J].Journal of Shandong University:Natural Science,2014, 49(8):15-21.

[16]Wang Wei.Association rule mining and change mining based on the concept lattice[D].Jinan:Shangdong University,2012.

[17]Wang Hui,Wang Jing.Non-redundant association rules extraction of frequent concept lattice based on FP-tree[J].Computer Engineering andApplications,2012,48(15):12-15.

[18]Fu Dongmei,Wang Zhiqiang.Mining algorithm of association rule based on FP-tree and constrained concept lattice and application research[J].Application Research of Computers,2014,31(4):1013-1015.

[19]Zhai Yue,Qin Fang.Concept lattice-based extaction algorithm for non-redundancy association rules[J].Computer Applications and Software,2015,32(4):46-49.

附中文參考文獻(xiàn)：

[1]Tan P N,Steinbach M,Kumar V.數(shù)據(jù)挖掘?qū)д揫M].北京:人民郵電出版社,2011.

[2]胡學(xué)鋼,王媛媛.一種基于約簡(jiǎn)概念格的關(guān)聯(lián)規(guī)則快速求解算法[J].計(jì)算機(jī)工程與應(yīng)用,2005,41(22):180-183.

[4]李金海,呂躍進(jìn).基于概念格的決策形式背景屬性約簡(jiǎn)及規(guī)則提取[J].數(shù)學(xué)實(shí)踐與認(rèn)識(shí),2009(7):137-144.

[5]仇國(guó)芳.基于變精度概念格的決策推理方法[J].系統(tǒng)工程理論與實(shí)踐,2010,30(6):1092-1098.

[6]仇國(guó)芳,馬建敏,楊宏志,等.概念粒計(jì)算系統(tǒng)的數(shù)學(xué)模型[J].中國(guó)科學(xué):F輯信息科學(xué),2009,39(12):1239-1247.

[10]官禮和,王國(guó)胤,胡峰.一種基于屬性序的決策規(guī)則挖掘算法[J].控制與決策,2012,27(2):313-316.

[11]黃加增.基于粗糙概念格的屬性約簡(jiǎn)及規(guī)則獲取[J].軟件,2011,32(10):16-23.

[13]董威,王建輝,顧樹(shù)生.基于可變精度粗糙集理論的規(guī)則獲取算法[J].控制工程,2007,14(1):73-75.

[15]張春英,王立亞,劉保相.基于覆蓋的區(qū)間概念格動(dòng)態(tài)壓縮原理與實(shí)現(xiàn)[J].山東大學(xué)學(xué)報(bào):理學(xué)版,2014,49(8):15-21.

[16]王瑋.基于概念格的關(guān)聯(lián)規(guī)則挖掘及變化模式研究[D].濟(jì)南:山東大學(xué),2012.

[17]王慧,王京.FP-tree上頻繁概念格的無(wú)冗余關(guān)聯(lián)規(guī)則提取[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(15):12-15.

[18]付冬梅,王志強(qiáng).基于FP-tree和約束概念格的關(guān)聯(lián)規(guī)則挖掘算法及應(yīng)用研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(4): 1013-1015.

[19]翟悅,秦放.基于概念格的無(wú)冗余關(guān)聯(lián)規(guī)則提取算法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(4):46-49.

WANG Liya was born in 1987.She received the M.S.degree from North China University of Science and Technology in 2015.Now she engages in teaching and scientific research at North China University of Science and Technology, and is the member of CCF.Her research interests include concept lattice and data mining,etc.

王立亞（1987—），女，河北唐山人，2015年于華北理工大學(xué)獲得碩士學(xué)位，目前在華北理工大學(xué)從事教學(xué)科研工作，CCF會(huì)員，主要研究領(lǐng)域?yàn)楦拍罡?，?shù)據(jù)挖掘等。

ZHANG Chunying was born in 1969.She received the Ph.D.degree from Yanshan University in 2014.Now she is a professor and M.S.supervisor at North China University of Science and Technology,and the member of CCF. Her research interests include data mining,concept lattice and social networks,etc.

張春英（1969—），女，河北唐山人，2014年于燕山大學(xué)獲得博士學(xué)位，現(xiàn)為華北理工大學(xué)教授、碩士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，概念格，社會(huì)網(wǎng)絡(luò)等。出版專(zhuān)著1部，編寫(xiě)教材6部，發(fā)表學(xué)術(shù)論文60余篇，主研國(guó)家自然科學(xué)基金項(xiàng)目1項(xiàng)，完成省部級(jí)項(xiàng)目7項(xiàng)。

LIU Baoxiang was born in 1957.He is a professor and M.S.supervisor at North China University of Science and Technology.His research interests include concept lattice,data mining and fuzzy control,etc.

劉保相（1957—），男，河北衡水人，華北理工大學(xué)教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)楦拍罡?，?shù)據(jù)挖掘，模糊控制等。出版專(zhuān)著2部，編寫(xiě)教材9部，發(fā)表學(xué)術(shù)論文80余篇，主持省部級(jí)以上科研項(xiàng)目20余項(xiàng)。

MiningAlgorithm of IntervalAssociation Rule with Parameters and ItsApplication?

WANG Liya1,2,ZHANG Chunying1,2+,LIU Baoxiang1,2
1.College of Science,North China University of Science and Technology,Tangshan,Hebei 063009,China
2.Key Laboratory for Data Science andApplication of Hebei Province,Tangshan,Hebei 063009,China
+Corresponding author:E-mail:hblg_zcy@126.com

After analyzing the association rule mining algorithm of classical concept lattice,in order to solve the issue of mining uncertain rule,this paper puts forward the model of mining interval association rule with parameters,combining with the properties of concept and structure of interval concept lattice.Firstly,this paper gives a series of definitions and related theorems in the course of mining interval rule,and based on the uncertainty of concept lattice,defines the measurable standard of interval association rule.Then,this paper constructs the model of mining rule with parameters based on interval concept lattice,and the analysis shows that the model can effectively extract association rules with high degree of support and confidence,so it improves the dependability of rules.Finally,through a case of book recommendation,this paper verifies the feasibility of this model,meanwhile studies the influence ofαandβto interval association rule.

interval concept lattice;rule mining with parameters;support degree;confidence degree;rule accuracy

10.3778/j.issn.1673-9418.1506018

A

TP18；TP301.6

*The National Natural Science Foundation of China under Grant Nos.61370168，61472340(國(guó)家自然科學(xué)基金);the Natural Science Foundation of Hebei Province under Grant No.F2016209344(河北省自然科學(xué)基金項(xiàng)目).

Received 2015-06,Accepted 2016-01.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-01-07,http://www.cnki.net/kcms/detail/11.5602.TP.20160107.1540.004.html