大數(shù)據(jù)下一種規(guī)則的快速挖掘技術(shù)研究

摘 要：近年來，數(shù)據(jù)挖掘技術(shù)已經(jīng)應(yīng)用到各個領(lǐng)域。數(shù)據(jù)挖掘通常會產(chǎn)生大量規(guī)則，產(chǎn)生的關(guān)聯(lián)規(guī)則大多數(shù)是冗余的，導(dǎo)致用戶難以分析并利用這些數(shù)據(jù)。本文致力于在大數(shù)據(jù)下對大量的冗余規(guī)則進(jìn)行修剪，提出一種修剪算法的改進(jìn)算法，并通過試驗(yàn)證明了該方法的有效性。

關(guān)鍵詞：大數(shù)據(jù);數(shù)據(jù)挖掘;冗余

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1003-5168（2018）25-0037-02

1 研究背景

隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)逐漸滲透到當(dāng)今每一個行業(yè)和業(yè)務(wù)職能領(lǐng)域，成為重要的生產(chǎn)因素。面對當(dāng)前海量數(shù)據(jù)，如何準(zhǔn)確有效地挖掘數(shù)據(jù)已經(jīng)成為行業(yè)未來發(fā)展的趨勢。關(guān)聯(lián)規(guī)則的挖掘研究一直是數(shù)據(jù)挖掘領(lǐng)域的一個熱門研究課題，現(xiàn)在已經(jīng)被廣泛地應(yīng)用到各個領(lǐng)域。近年來，國內(nèi)外研究主要集中在關(guān)聯(lián)規(guī)則冗余修剪以減少關(guān)聯(lián)規(guī)則的數(shù)量，減少不必要的挖掘。由此，本文致力于修剪冗余的關(guān)聯(lián)規(guī)則，提高挖掘質(zhì)量，并提出一種關(guān)聯(lián)規(guī)則的修剪方法。首先，根據(jù)規(guī)則與數(shù)據(jù)的匹配度進(jìn)行修剪，并計(jì)算數(shù)據(jù)與規(guī)則的平均匹配度，如果小于閾值，則修改規(guī)則，再根據(jù)機(jī)器學(xué)習(xí)中的相似性度量方法，在剩余的規(guī)則中選擇興趣度最優(yōu)的數(shù)量關(guān)聯(lián)規(guī)則，最后獲得除去冗余規(guī)則后的關(guān)聯(lián)規(guī)則。

本文所采用的方法最大限度地縮短了修剪所需要的處理時間，生成了一個準(zhǔn)確的最小關(guān)聯(lián)規(guī)則集，并能與傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘方法保持相同的準(zhǔn)確度，這使得冗余規(guī)則的修剪易于理解，可讀性強(qiáng)。

2 關(guān)聯(lián)規(guī)則的基本概念

關(guān)聯(lián)規(guī)則的定義[1]是這樣描述的：設(shè)[I=i1，i2，…，im]是由m個不同屬性（項(xiàng)目）組成的集合，[ikk=1，2，…，m]稱為項(xiàng)。事務(wù)數(shù)據(jù)庫D是事務(wù)T的集合，其事務(wù)數(shù)記作[D]，其中T是項(xiàng)的集合，并且[T?I]。對應(yīng)每一個事務(wù)有唯一的標(biāo)識，記作TID。關(guān)聯(lián)規(guī)則是形如[X?Y]的蘊(yùn)涵式，其中X包含于I，Y包含于I，并且[X∩Y=?]。傳統(tǒng)的Apriori算法中規(guī)則生成方法非常簡單，但計(jì)算復(fù)雜，規(guī)則之間存在大量的冗余。尤其是當(dāng)項(xiàng)集包含的項(xiàng)目比較多時，所生成的冗余規(guī)則成指數(shù)增長，并且不能保證規(guī)則的有效性。關(guān)聯(lián)規(guī)則有兩個度量標(biāo)準(zhǔn)：支持度（support）和置信度（confidence）。設(shè)有關(guān)聯(lián)規(guī)則[X?Y]，則關(guān)聯(lián)規(guī)則的支持度的定義為：[supportX?Y=supportX?Y]。關(guān)聯(lián)規(guī)則的置信度定義為：[confidenceX?Y=support][X?Y/supportX=PY|X]。支持度[supportX?Y]是指在交易數(shù)據(jù)庫中同時包含X和Y的交易數(shù)占所有交易數(shù)的百分比。置信度[confidenceX?Y]是指同時包含X和Y的交易數(shù)與包含X的交易數(shù)之比。關(guān)聯(lián)規(guī)則的支持度反映了該規(guī)則所發(fā)生的頻度，關(guān)聯(lián)規(guī)則的置信度則表明了整體規(guī)則的準(zhǔn)確程度。通常來說，只有支持度和置信度同時達(dá)到較高的關(guān)聯(lián)規(guī)則才可能是用戶感興趣、有用的關(guān)聯(lián)規(guī)則。

在關(guān)聯(lián)規(guī)則的挖掘中可能會產(chǎn)生各種各樣的規(guī)則，很多規(guī)則是毫不相關(guān)的。在現(xiàn)階段的研究中，部分研究方向是運(yùn)用閉合項(xiàng)集。所謂閉合項(xiàng)集，就是指一個項(xiàng)集的直接超集的支持度計(jì)數(shù)，不等于其本身的支持度計(jì)數(shù)[2]。如果閉項(xiàng)集同時也是頻繁的，得出支持度大于等于最小支持度閾值，則稱為閉頻繁項(xiàng)集。關(guān)聯(lián)規(guī)則的聚類也被用作挖掘規(guī)則，但還缺少理論的支持。修改后的Apriori[3]方法使大集合縮減為最優(yōu)規(guī)則集。還有一種方法是運(yùn)用多種挖掘軟件的可視化技術(shù)。這種方法雖然可以提供一種數(shù)據(jù)樣式，但依然很難發(fā)現(xiàn)規(guī)則與規(guī)則之間的細(xì)節(jié)相關(guān)關(guān)系。從現(xiàn)在數(shù)據(jù)分析者的需求來看，這些改進(jìn)的方法都是非常有限的。

3 算法分析與試驗(yàn)

傳統(tǒng)的關(guān)聯(lián)規(guī)則處理方法具有顯而易見的缺點(diǎn)，容易過分忽略或者強(qiáng)調(diào)部分規(guī)則。本文通過對關(guān)聯(lián)規(guī)則的平均匹配程度進(jìn)行修剪，再根據(jù)機(jī)器學(xué)習(xí)中的相似性度量方法進(jìn)行評估。改進(jìn)的方法消除了關(guān)聯(lián)規(guī)則之間大量的相似規(guī)則，同時防止規(guī)則在得到的最終結(jié)果中丟失。在簡化過程中，最后生成復(fù)雜度最高的關(guān)聯(lián)規(guī)則和一些比較重要的關(guān)聯(lián)規(guī)則。雖然可能在最小支持度閾值下生成大量的規(guī)則，但可以使用所提出的修剪方法找到最佳頻繁項(xiàng)集。所提出的方法不僅可以從大量毫無關(guān)聯(lián)的關(guān)聯(lián)規(guī)則中減少關(guān)聯(lián)規(guī)則的數(shù)量，還可以得出和其他傳統(tǒng)方法相同或更好的準(zhǔn)確度。

試驗(yàn)的數(shù)據(jù)使用的是UCI Machine Learning Repository提供的數(shù)據(jù)庫。為了使試驗(yàn)數(shù)值更加可視化，本文對數(shù)據(jù)進(jìn)行了處理，本文中關(guān)聯(lián)規(guī)則的屬性為連續(xù)值屬性。為了明確地評估算法，在試驗(yàn)過程中劃分的范圍比實(shí)際分布的情況更寬一些。圖1是原算法和改進(jìn)后算法的規(guī)則數(shù)對比圖。從圖1可看出，與經(jīng)典的Apriori算法相比，本文的修剪方法大幅度減少了候選項(xiàng)集和頻繁項(xiàng)集的數(shù)量，當(dāng)大規(guī)模使用修剪的關(guān)聯(lián)規(guī)則項(xiàng)集時，剩余的關(guān)聯(lián)規(guī)則的數(shù)量會大量減少。同時，改進(jìn)后的方法使關(guān)聯(lián)規(guī)則的結(jié)構(gòu)變得更加簡單。當(dāng)遇到大規(guī)模的數(shù)據(jù)挖掘時，產(chǎn)生的規(guī)則數(shù)量非常巨大。本文改進(jìn)的算法在實(shí)際的數(shù)據(jù)挖掘過程中實(shí)踐優(yōu)于以往的傳統(tǒng)算法。通過本文的方法可以看出，使用減少以至于規(guī)避冗余規(guī)則的提取，大大提高了數(shù)據(jù)挖掘的計(jì)算效率。圖2是原算法和改進(jìn)后算法的運(yùn)行時間對比圖。從圖2可以看出，算法改進(jìn)之后，挖掘關(guān)聯(lián)規(guī)則所使用時間更少。尤其是在使用部分匹配時，在處理時間方面優(yōu)于之前的傳統(tǒng)的Apriori算法。試驗(yàn)結(jié)果表明，與傳統(tǒng)方法相比，該方法的分類精度更高，所用時間更短。

4 結(jié)語

在本文中，筆者提出了一種冗余規(guī)則的改進(jìn)方法。該方法利用修剪關(guān)聯(lián)規(guī)則的冗余來提高計(jì)算效率，并消除關(guān)聯(lián)規(guī)則的冗余規(guī)則。試驗(yàn)結(jié)果表明，該方法有效減少了計(jì)算時間，減少了關(guān)聯(lián)規(guī)則的冗余規(guī)則。通過該方法與其他加速方法相結(jié)合，可以實(shí)現(xiàn)更高效的挖掘。

參考文獻(xiàn)：

[1] Agrawal R，Srikant R. Fast Algorithms for Mining Association Rules in Large Databases[C]// International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc，1994.

[2] Srikant R， Vu Q， Agrawal R. Mining Association Rules with Item Constraints[C]// International Conference on Knowledge Discovery and Data Mining. AAAI Press，1997.

[3] Aggarwal C C， Yu P S. Online Generation of Association Rules[J]. Knowledge amp; Data Engineering IEEE Transactions on， 2001（4）：527-540.