基于加權(quán)的多數(shù)據(jù)集時(shí)態(tài)關(guān)聯(lián)規(guī)則算法

耿麗娟

摘? 要：文章將子數(shù)據(jù)集中的時(shí)態(tài)關(guān)聯(lián)規(guī)則的時(shí)態(tài)因素進(jìn)行了區(qū)間歸一和延伸，再參考有效投票率進(jìn)行規(guī)則剪輯，對剪輯后的子數(shù)據(jù)庫中的規(guī)則進(jìn)行加權(quán)計(jì)算得到最終的時(shí)態(tài)關(guān)聯(lián)規(guī)則，最后通過算法偽代碼具體實(shí)現(xiàn)了該算法。

關(guān)鍵詞：加權(quán);多數(shù)據(jù)集;時(shí)態(tài)關(guān)聯(lián)規(guī)則

中圖分類號：TP311.131? ? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號：2095-2945（2020）26-0026-02

Abstract： In this paper， the temporal factors of the temporal association rules in the sub-data set are normalized and extended， and then the rules are edited with reference to the effective voter turnout rate， and the final temporal association rules are obtained by weighted calculation of the rules in the edited sub-database. Finally， the algorithm is implemented by pseudo code.

Keywords： weighting; multiple data sets; temporal association rules

1 概述

關(guān)聯(lián)規(guī)則描述了兩個(gè)或多個(gè)變量之間的某種潛在規(guī)則。其挖掘過程可概括為兩個(gè)步驟：第一，找出所有的頻繁項(xiàng)集;第二，根據(jù)頻繁項(xiàng)集確定強(qiáng)關(guān)聯(lián)規(guī)則。

2 時(shí)態(tài)關(guān)聯(lián)規(guī)則研究現(xiàn)狀

現(xiàn)行的時(shí)態(tài)關(guān)聯(lián)規(guī)則主要是針對單一數(shù)據(jù)庫進(jìn)行挖掘。但應(yīng)用較多的是多數(shù)據(jù)庫。多數(shù)據(jù)集的挖掘分為三個(gè)步驟：一，對多個(gè)數(shù)據(jù)集進(jìn)行分類;二，對同類數(shù)據(jù)集進(jìn)行局部模式分析;三，將挖掘到的知識進(jìn)行合并[1]。

對時(shí)態(tài)關(guān)聯(lián)規(guī)則國內(nèi)外已經(jīng)有了相關(guān)的研究。歐陽繼紅等提出了一種權(quán)值合成模式[2]，但該方法合成數(shù)據(jù)量很大。歐陽為民等提出了一個(gè)新的時(shí)態(tài)約束下的關(guān)聯(lián)規(guī)則算法[3]。Ale提到了在挖掘關(guān)聯(lián)規(guī)則時(shí)缺失時(shí)態(tài)信息的問題[4]。孟志青研究了一類基于時(shí)態(tài)約束的相鄰時(shí)態(tài)關(guān)聯(lián)問題，但沒有解決多時(shí)間粒度的問題[5]。朱建平等依據(jù)事務(wù)發(fā)生的順序構(gòu)造了加權(quán)關(guān)聯(lián)規(guī)則用來體現(xiàn)數(shù)據(jù)的時(shí)間價(jià)值，力求使規(guī)則的發(fā)現(xiàn)體現(xiàn)一種趨勢[6]。

3 以規(guī)則加權(quán)為基礎(chǔ)的多數(shù)據(jù)集時(shí)態(tài)關(guān)聯(lián)規(guī)則算法

3.1 主要思想和參數(shù)設(shè)置

以往在進(jìn)行多數(shù)據(jù)集關(guān)聯(lián)規(guī)則加權(quán)算法時(shí)很少考慮到時(shí)態(tài)問題，本文將規(guī)則權(quán)值引入到多數(shù)據(jù)庫的時(shí)態(tài)關(guān)聯(lián)規(guī)則挖掘中。

（1）數(shù)據(jù)庫的權(quán)值

設(shè)D1，D2，…Dm為m個(gè)不同的數(shù)據(jù)庫，Num（Di）表示數(shù)據(jù)庫Di中的事務(wù)數(shù)，則數(shù)據(jù)庫Di的權(quán)值為：

（2）關(guān)聯(lián)規(guī)則的權(quán)值

Si為Di中的關(guān)聯(lián)規(guī)則集，S={S1，S2，…Sm}為總關(guān)聯(lián)規(guī)則集，R1，R2，…Rn為總規(guī)則集S中具體的關(guān)聯(lián)規(guī)則。Num（Rk）表示具體規(guī)則Rk的數(shù)據(jù)庫數(shù)目，則我們定義關(guān)聯(lián)規(guī)則Rk的權(quán)值為：

（3）有效投票率

定義了有效投票率minωk，將規(guī)則的權(quán)值與之比較，將權(quán)值小于該閾值的無太大意義的規(guī)則刪除。

（4）合成模式

設(shè)D1，D2，…Dm為m個(gè)不同的數(shù)據(jù)庫，Si為Di中的關(guān)聯(lián)規(guī)則集，S={S1，S2，…Sm}為總關(guān)聯(lián)規(guī)則集supp1，supp2，...suppm

分別為各個(gè)數(shù)據(jù)庫的最小支持度，conf1，conf2，...confm分別為各個(gè)數(shù)據(jù)庫的最小置信度，對于特定的關(guān)聯(lián)規(guī)則“A？圯B”，設(shè)此規(guī)則在數(shù)據(jù)庫D1，D2，…Dm中的有效時(shí)間分別為[T1? T1]，[T2? T2]，…[Tm Tm]，則合成后的支持度，置信度和有效時(shí)間分別為：

其中Extent-time函數(shù)包含延展和歸并兩步，關(guān)于時(shí)間區(qū)間的延展和歸并技術(shù)的具體實(shí)現(xiàn)過程參考文獻(xiàn)[2]。

（5）時(shí)態(tài)閾值？駐T

通過函數(shù)延展和歸并后的關(guān)聯(lián)規(guī)則的間區(qū)間差別很大，從幾個(gè)小時(shí)到幾天甚至幾周不等。因此定義了時(shí)態(tài)閾值？駐T，？駐T=[Tmin，Tmax]將規(guī)則合成后的時(shí)間區(qū)間與時(shí)態(tài)閾值比較，將時(shí)間區(qū)間不在此閾值范圍內(nèi)的的規(guī)則刪除。時(shí)態(tài)閾值的值應(yīng)根據(jù)應(yīng)用領(lǐng)域或者規(guī)則類別憑經(jīng)驗(yàn)選取。

3.2 算法偽代碼

規(guī)則縮減算法（Rule Selection）

輸入：數(shù)據(jù)集庫D={D1，D2，…Dm};關(guān)聯(lián)規(guī)則集 S={S1，S2，…Sm};最小投票率minωR

輸出：縮減后的關(guān)聯(lián)規(guī)則集

（1）input? D， S， minωR

（2）for對于數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)庫Di? do

for對于關(guān)聯(lián)規(guī)則集中的每一個(gè)關(guān)聯(lián)規(guī)則R? do

（3）output? S;

規(guī)則合成算法

輸入：關(guān)聯(lián)規(guī)則集 S={S1，S2，…Sm};minsupp;minconf;

輸出：合成后的關(guān)聯(lián)規(guī)則集

（1）input? S={S1，S2，…Sm}，minsupp，minconf;

（2）call? Rule Selection（S）;

（3）for對規(guī)則集中的每條規(guī)則A？圯B? do

（4）分別按照支持度和置信度的高低排列規(guī)則集S中的關(guān)聯(lián)規(guī)則R

（5）對于第四步中支持度和置信度大于閾值的關(guān)聯(lián)規(guī)則R判斷其時(shí)間區(qū)間是否滿足時(shí)態(tài)閾值的要求范圍

（6）輸出R中時(shí)間區(qū)間在時(shí)態(tài)閾值范圍內(nèi)的關(guān)聯(lián)規(guī)則R

4 結(jié)束語

本文介紹了時(shí)態(tài)關(guān)聯(lián)規(guī)則的研究現(xiàn)狀，在此基礎(chǔ)上提出了一種多數(shù)據(jù)集時(shí)態(tài)加權(quán)關(guān)聯(lián)算法，介紹了算法的思想和具體實(shí)現(xiàn)，最后通過算法偽代碼具體實(shí)現(xiàn)了該算法。

參考文獻(xiàn)：

[1]唐懿芳，牛力，張師超.多數(shù)據(jù)源關(guān)聯(lián)規(guī)則挖掘算法研究[J].廣西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，20（4）：27-31.

[2]歐陽繼紅，王仲佳，等.具有動(dòng)態(tài)加權(quán)特性的關(guān)聯(lián)規(guī)則算法[J].吉林大學(xué)學(xué)報(bào)，2005（5），43（3）：314-319.

[3]歐陽為民，蔡慶生.在數(shù)據(jù)庫中發(fā)現(xiàn)具有時(shí)態(tài)約束的關(guān)聯(lián)規(guī)則[J].軟件學(xué)報(bào)，1999，10（5）：527-532.

[4]Ale J M，Rossi G H. An Approach to Cyclic Association Rules[C].In Proc. of the 2000 ACM Symposium on Applied Computing，2000：294-300.

[5]孟志青.一類相鄰時(shí)態(tài)關(guān)聯(lián)規(guī)則的知識發(fā)現(xiàn)問題[J].模式識別與人工智能，2001，14（4）：458-462.

[6]朱建平，樂燕波.數(shù)據(jù)挖掘中加權(quán)時(shí)態(tài)關(guān)聯(lián)規(guī)則的構(gòu)造[J].計(jì)算機(jī)工程，2008，34（6）：51-53.