劉興明

摘 要：隨著人們對(duì)信息數(shù)據(jù)量的急速增長(zhǎng)從而數(shù)據(jù)挖掘技術(shù)也隨之應(yīng)運(yùn)而生，這使得人們對(duì)知識(shí)與信息的渴求得到了進(jìn)一步滿足。對(duì)于如何才能快速高效的獲取知識(shí)，對(duì)于信息處理技術(shù)來(lái)說(shuō)已經(jīng)成為當(dāng)前熱門的研究課題。審視當(dāng)前對(duì)于關(guān)聯(lián)規(guī)則的研究現(xiàn)狀，針對(duì)關(guān)聯(lián)研究的現(xiàn)狀，分析實(shí)際問(wèn)題對(duì)于關(guān)聯(lián)規(guī)則總結(jié)出一種新的研究方式，結(jié)論為關(guān)聯(lián)規(guī)則算法在今后的出路和進(jìn)一步的研究上指明了方向。研究過(guò)程中通過(guò)對(duì)文獻(xiàn)的查詢分析和比較分析兩種方法，進(jìn)一步闡述對(duì)典型關(guān)聯(lián)產(chǎn)生影響的各種方法，其中最為重要的是把核心Apriori算法作為一個(gè)研究的基點(diǎn)。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；典型關(guān)聯(lián)；Apriori算法

1 數(shù)據(jù)挖掘技術(shù)

1.1 數(shù)據(jù)挖掘概念

從數(shù)據(jù)挖掘的本質(zhì)上說(shuō)它是一種具有更高商業(yè)價(jià)值的新型信息處理技術(shù)，數(shù)據(jù)挖掘技術(shù)的作用是對(duì)數(shù)據(jù)的應(yīng)用來(lái)說(shuō)的，其目的是使人們從低層次的聯(lián)機(jī)查詢過(guò)渡到對(duì)數(shù)據(jù)決策支持分析預(yù)測(cè)上，從而成為更高層次的應(yīng)用。

1.2 數(shù)據(jù)挖掘技術(shù)的分類

關(guān)于數(shù)據(jù)挖掘針對(duì)其挖掘的對(duì)象，大致的可以做出以下分類，具體分為時(shí)態(tài)數(shù)據(jù)庫(kù)、異質(zhì)數(shù)據(jù)庫(kù)、文本數(shù)據(jù)源、關(guān)系數(shù)據(jù)庫(kù)面向?qū)ο髷?shù)據(jù)庫(kù)（Object-Oriented Database）、空間數(shù)據(jù)庫(kù)、遺產(chǎn)數(shù)據(jù)庫(kù)、多媒體數(shù)據(jù)庫(kù)以及web等比較具有針對(duì)性的挖掘?qū)ο?。針?duì)數(shù)據(jù)挖掘的方法大致的可以歸納為：計(jì)算機(jī)學(xué)習(xí)法、數(shù)理統(tǒng)計(jì)法、信息聚類分析法、遺傳算法Genetic Algorithm、神經(jīng)網(wǎng)絡(luò)Neural Network探索性分析法、不確定性推理和近似推理法、數(shù)據(jù)分析法、證據(jù)理論和元模式法、數(shù)據(jù)集成方法、當(dāng)代數(shù)學(xué)分析法等。

根據(jù)數(shù)據(jù)挖掘技術(shù)的知識(shí)類型可以分為：廣義范圍的知識(shí)挖掘、差異范圍的知識(shí)挖掘、關(guān)聯(lián)范圍的知識(shí)挖掘、預(yù)測(cè)范圍的知識(shí)挖掘等。

1.3 數(shù)據(jù)挖掘的應(yīng)用分析

根據(jù)麻省理工學(xué)院內(nèi)部數(shù)據(jù)整理其科技評(píng)論雜志對(duì)數(shù)據(jù)挖掘技術(shù)的應(yīng)用分析提出了10大新興的科學(xué)技術(shù)數(shù)據(jù)挖掘能夠在未來(lái)5年對(duì)人類的產(chǎn)生生活帶來(lái)重大影響。根據(jù)種種數(shù)據(jù)分析所表明的問(wèn)題我們不難發(fā)現(xiàn)數(shù)據(jù)挖掘技術(shù)面向?qū)嶋H應(yīng)用方面不是一時(shí)的，隨著時(shí)代的發(fā)展社會(huì)信息化進(jìn)程不斷加劇各行業(yè)的業(yè)務(wù)操作也隨之逐漸向現(xiàn)代化流程轉(zhuǎn)變，這一轉(zhuǎn)變促使企業(yè)在處理業(yè)務(wù)時(shí)產(chǎn)生大量的業(yè)務(wù)信息數(shù)據(jù)。對(duì)于一般地企業(yè)內(nèi)部的業(yè)務(wù)信息數(shù)據(jù)來(lái)說(shuō)，其主要是由企業(yè)進(jìn)行商業(yè)運(yùn)作而產(chǎn)生的數(shù)據(jù)，這些數(shù)據(jù)的量一般比較少。這是都是企業(yè)為了獲得市場(chǎng)分析而進(jìn)行收集的，關(guān)于此類的數(shù)據(jù)挖掘的應(yīng)用終將成為企業(yè)進(jìn)行高層次數(shù)據(jù)分析，為行政決策提供技術(shù)支持的骨干技術(shù)。

2 關(guān)聯(lián)規(guī)則挖掘理論的研究

2.1 發(fā)現(xiàn)頻繁項(xiàng)目集

該技術(shù)可以通過(guò)用戶給定的minsupport尋找所有與用戶給定的頻繁項(xiàng)目集Frequent Itemset即滿足support不小于minsupport的項(xiàng)目集。但是從實(shí)際出發(fā)不難看出，諸如此類的頻繁項(xiàng)目集從某種意義上來(lái)講具有互相包含的關(guān)系，因而我們一般只關(guān)心那些不被數(shù)據(jù)挖掘所包含的所謂頻繁大項(xiàng)集Frequent Large Itemset的集合，對(duì)于這些頻繁大項(xiàng)集來(lái)說(shuō)它們只是促使關(guān)聯(lián)規(guī)則形成的基礎(chǔ)。

2.2 生成關(guān)聯(lián)規(guī)則

通過(guò)用戶給定的（minconfidence）在每個(gè)最大頻繁項(xiàng)目，項(xiàng)目集中尋找confidence不小于minconfidence的關(guān)聯(lián)規(guī)則。近年來(lái)關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)，比較流行的方法是基于Agrawal等人建立的項(xiàng)目集格空間理論。這個(gè)理論的核心是這樣的原理，頻繁項(xiàng)目集的子集是頻繁項(xiàng)目集，非頻繁項(xiàng)目集的超集是非頻繁項(xiàng)目集。對(duì)于子問(wèn)題2而言，也許在每個(gè)頻繁大項(xiàng)集中逐一匹配規(guī)則并進(jìn)行。Confidence I1→I2≥ minconfidence的測(cè)試是必需的，因此這部分工作相對(duì)比較成熟。為了完善了一個(gè)稱為Apriori的關(guān)聯(lián)規(guī)則挖掘法這個(gè)算法一直作為經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法被引用，隨著數(shù)據(jù)庫(kù)容量的增大重復(fù)訪問(wèn)數(shù)據(jù)庫(kù)，外存將導(dǎo)致性能低下，因此探索新的理論和算法來(lái)減少數(shù)據(jù)庫(kù)的掃描次數(shù)和侯選集空間占用已經(jīng)成為近年來(lái)關(guān)聯(lián)規(guī)則挖掘研究的熱點(diǎn)之一。

3 時(shí)態(tài)約束關(guān)聯(lián)規(guī)則挖掘問(wèn)題及算法

3.1 聚焦挖掘任務(wù)，提高挖掘效率

數(shù)據(jù)挖掘理論最初的研究側(cè)重點(diǎn)是模型的建立以及算法的設(shè)計(jì)。隨著應(yīng)用于不同的場(chǎng)合，得出的結(jié)果證明單純而又孤立的挖掘工具效果并不理想。傳統(tǒng)的數(shù)據(jù)挖掘項(xiàng)目中，會(huì)進(jìn)行詳盡而反復(fù)的調(diào)研分析，并根據(jù)用戶的需求制定細(xì)致的任務(wù)計(jì)劃，最終的結(jié)果卻并不理想，不能得到想要的結(jié)果。在算法中，如果想要得到用戶的挖掘目標(biāo)，除了算法之外，還需要有特定的實(shí)現(xiàn)機(jī)制，使得我們的挖掘計(jì)劃能夠轉(zhuǎn)變成對(duì)一個(gè)系統(tǒng)工作的控制，這樣才能使得挖掘項(xiàng)目能有期望的結(jié)果。這樣的約束，不需要局限于某一個(gè)挖掘數(shù)據(jù)的階段，在任何階段都可以實(shí)現(xiàn)。而這樣的算法機(jī)制，也是交互式數(shù)據(jù)挖掘算法的基本形式，通過(guò)這樣的過(guò)程，來(lái)達(dá)到更好以及快速地完成挖掘任務(wù)。

3.2 保證挖掘的精確性

從數(shù)據(jù)挖掘的算法也可以看出，結(jié)果具有不可預(yù)測(cè)性，而正因此，對(duì)于算法運(yùn)行的過(guò)程中，遇到的問(wèn)題也是難以把握的，所以算法還需要加上反饋機(jī)制，通過(guò)這樣的反饋，來(lái)進(jìn)行驗(yàn)證結(jié)果并修正算法中的數(shù)據(jù)，如果這個(gè)過(guò)程中，挖掘到的數(shù)據(jù)是正確的，但也未必是用戶所側(cè)重的，所以數(shù)據(jù)挖掘的結(jié)果不僅要具有邏輯上的正確性，還要能夠滿足用戶的主管偏好；也就是既要準(zhǔn)確，還要可信且符合用戶需求。而約束就是這樣實(shí)現(xiàn)的，通過(guò)約束發(fā)現(xiàn)算法中的問(wèn)題并及時(shí)校正算法，以最終能夠滿足各項(xiàng)需求。

4 數(shù)據(jù)分割下的挖掘問(wèn)題及算法

對(duì)于理論基礎(chǔ)比較成熟的算法——Apriori算法，研究的側(cè)重點(diǎn)已經(jīng)變?yōu)樾蕟?wèn)題，人們也提出了各種的改進(jìn)算法，本文選區(qū)幾種比較有代表性的加以介紹。

4.1 減少事務(wù)的個(gè)數(shù)

這樣的原理在于，當(dāng)需要處理的事務(wù)不包含長(zhǎng)度為k的大項(xiàng)集，那么也一定不包含長(zhǎng)度為k+1的大項(xiàng)集。在算法處理的過(guò)程中，就可以將這樣的事務(wù)濾去，在下輪掃描過(guò)程中，就可以不需要那么多的事務(wù)集。

4.2 基于劃分的方法

這類算法的比較典型的是頻繁項(xiàng)目生成算法，該算法原理在于：把數(shù)據(jù)庫(kù)分解成邏輯上互不交叉的部分，而每次只需要單獨(dú)考慮一個(gè)分塊，在這樣的分塊中，研究怎樣能夠發(fā)掘頻繁項(xiàng)目集；而對(duì)于怎樣將數(shù)據(jù)進(jìn)入存儲(chǔ)中，可以把需要處理的分塊放入計(jì)算機(jī)內(nèi)存中，這樣有利于算法的并行處理，數(shù)據(jù)量相對(duì)于不分塊前減少，提高了數(shù)據(jù)挖掘的速度。

4.3 基于hash的方法

在上述的發(fā)現(xiàn)頻繁項(xiàng)目集的算法中，有人提出了改進(jìn)算法，基于雜（hash）技術(shù)產(chǎn)生頻繁項(xiàng)目集。而這也是他們?cè)趯?shí)驗(yàn)基礎(chǔ)上提出的，因?yàn)閷?shí)驗(yàn)中，他們發(fā)現(xiàn)頻繁項(xiàng)目集的產(chǎn)生過(guò)程中，計(jì)算量主要集中在2-頻繁項(xiàng)目集上，他們通過(guò)雜湊技術(shù)來(lái)對(duì)這個(gè)問(wèn)題加以解決，把需要掃描的項(xiàng)目分發(fā)于不同的Hash桶，而對(duì)于每對(duì)項(xiàng)目來(lái)說(shuō)，最多只可能在一個(gè)特定的桶內(nèi)，然后通過(guò)實(shí)驗(yàn)分析，可以有效地降低了候選集的產(chǎn)生。當(dāng)然同樣適用于k-頻繁項(xiàng)目集生成上。

4.4 基于采樣的方法

基于抽樣技術(shù)的產(chǎn)生頻繁項(xiàng)目集的算法的原理在于：通過(guò)對(duì)數(shù)據(jù)庫(kù)進(jìn)行抽樣，產(chǎn)生一些可能成立的規(guī)則，然后通過(guò)數(shù)據(jù)庫(kù)的未被抽樣數(shù)據(jù)，進(jìn)行檢驗(yàn)，這些關(guān)聯(lián)規(guī)則是否是否有效。其實(shí)這個(gè)算法本身相對(duì)比較容易實(shí)現(xiàn)，并且能夠極大地減少數(shù)據(jù)挖掘過(guò)程中所付出的I/O代價(jià)，而不利的地方在于，抽樣數(shù)據(jù)的隨機(jī)性以及由此帶來(lái)的結(jié)果的偏差比較大。抽樣原理是統(tǒng)計(jì)學(xué)常用方法，雖然其得到的結(jié)果精確性可能并不盡人意；如果能被運(yùn)用恰當(dāng)?shù)脑?，可以在精度符合要求的情況下使得挖掘效率大大地提高。

[參考文獻(xiàn)]

[1]毛國(guó)君.數(shù)據(jù)挖掘技術(shù)與關(guān)聯(lián)規(guī)則挖掘算法研究[D].北京工業(yè)大學(xué)，2003.

[2]劉君強(qiáng).海量數(shù)據(jù)挖掘技術(shù)研究[D].浙江大學(xué)，2003.

[3]郭秀娟.基于關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法的研究[D].吉林大學(xué)，2004.

[4]王瓊.基于樹的關(guān)聯(lián)規(guī)則挖掘算法研究[D].河南大學(xué)，2013.

[5]王梟翔.基于相關(guān)興趣度的關(guān)聯(lián)規(guī)則挖掘[D].蘭州交通大學(xué)，2013.

[6]馬盈.基于MapReduce構(gòu)造多維數(shù)據(jù)及關(guān)聯(lián)規(guī)則挖掘算法的研究與應(yīng)用[D].東北師范大學(xué)，2013.