基于加權(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ī)則剪輯，對(duì)剪輯后的子數(shù)據(jù)庫(kù)中的規(guī)則進(jìn)行加權(quán)計(jì)算得到最終的時(shí)態(tài)關(guān)聯(lián)規(guī)則，最后通過(guò)算法偽代碼具體實(shí)現(xiàn)了該算法。

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

中圖分類號(hào)：TP311.131? ? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號(hào)：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ī)則。其挖掘過(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ī)則主要是針對(duì)單一數(shù)據(jù)庫(kù)進(jìn)行挖掘。但應(yīng)用較多的是多數(shù)據(jù)庫(kù)。多數(shù)據(jù)集的挖掘分為三個(gè)步驟：一，對(duì)多個(gè)數(shù)據(jù)集進(jìn)行分類;二，對(duì)同類數(shù)據(jù)集進(jìn)行局部模式分析;三，將挖掘到的知識(shí)進(jìn)行合并[1]。

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

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

設(shè)D1，D2，…Dm為m個(gè)不同的數(shù)據(jù)庫(kù)，Num（Di）表示數(shù)據(jù)庫(kù)Di中的事務(wù)數(shù)，則數(shù)據(jù)庫(kù)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ù)庫(kù)數(shù)目，則我們定義關(guān)聯(lián)規(guī)則Rk的權(quán)值為：

（3）有效投票率

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

（4）合成模式

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

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

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

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

通過(guò)函數(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ù)集庫(kù)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對(duì)于數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)庫(kù)Di? do

for對(duì)于關(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對(duì)規(guī)則集中的每條規(guī)則A？圯B? do

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

（5）對(duì)于第四步中支持度和置信度大于閾值的關(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é)束語(yǔ)

本文介紹了時(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)，最后通過(guò)算法偽代碼具體實(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]歐陽(yáng)繼紅，王仲佳，等.具有動(dòng)態(tài)加權(quán)特性的關(guān)聯(lián)規(guī)則算法[J].吉林大學(xué)學(xué)報(bào)，2005（5），43（3）：314-319.

[3]歐陽(yáng)為民，蔡慶生.在數(shù)據(jù)庫(kù)中發(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ī)則的知識(shí)發(fā)現(xiàn)問(wèn)題[J].模式識(shí)別與人工智能，2001，14（4）：458-462.

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