張曉東+王斌

摘要：數(shù)據(jù)挖掘自從提出以來(lái)，已經(jīng)得到了廣泛的應(yīng)用和發(fā)展。關(guān)系關(guān)聯(lián)規(guī)則表示一種特定類型的關(guān)聯(lián)規(guī)則，該規(guī)則描述了在數(shù)據(jù)集內(nèi)描述實(shí)例的特征之間發(fā)生的頻繁關(guān)系。該文研究的是重新挖掘一個(gè)數(shù)據(jù)集，這個(gè)數(shù)據(jù)集是之前已經(jīng)被挖掘過(guò)的，但是描述數(shù)據(jù)庫(kù)中的元素的屬性集增加時(shí)，如何更高效的挖掘關(guān)聯(lián)規(guī)則。

關(guān)鍵詞：數(shù)據(jù)挖掘；數(shù)據(jù)屬性集；自適應(yīng)算法；擴(kuò)展

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）28-0023-01

1 數(shù)據(jù)挖掘背景

自從人類進(jìn)入信息社會(huì)以來(lái)，隨著計(jì)算機(jī)和網(wǎng)絡(luò)的普及，科學(xué)技術(shù)迅猛發(fā)展，產(chǎn)生的數(shù)據(jù)量越來(lái)越大，在各個(gè)領(lǐng)域都積累了大量的數(shù)據(jù)，如考試報(bào)名系統(tǒng)人員的報(bào)名信息、搜索引擎每天的海量搜索記錄、購(gòu)物平臺(tái)產(chǎn)生的海量交易記錄和銀行系統(tǒng)每天繁雜的轉(zhuǎn)賬記錄等等。顯然在這些數(shù)據(jù)中蘊(yùn)藏著豐富的可以加以利用的信息，但是傳統(tǒng)的文件系統(tǒng)面對(duì)如此海量的數(shù)據(jù)顯得無(wú)能為力。因此我們迫切需要一種工具和手段，從這些數(shù)據(jù)中挖掘出我們感興趣的信息和知識(shí)。數(shù)據(jù)庫(kù)技術(shù)的發(fā)展有力地加快了人類向信息化時(shí)代發(fā)展的腳步，但是數(shù)據(jù)庫(kù)的統(tǒng)計(jì)和查詢功能，根本無(wú)法滿足人們對(duì)有趣知識(shí)和信息的挖掘需求。于是，人們將數(shù)據(jù)庫(kù)技術(shù)、信息檢索、算法、機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)等技術(shù)相結(jié)合，數(shù)據(jù)挖掘應(yīng)運(yùn)而生。

數(shù)據(jù)挖掘是一門交叉學(xué)科，它融匯了不同學(xué)科的技術(shù)，具有分類、聚類、關(guān)聯(lián)規(guī)則和序列模式的發(fā)現(xiàn)、預(yù)測(cè)、偏差的檢測(cè)等多種功能，各項(xiàng)功能互相聯(lián)系，共同發(fā)揮作用。

2 自適應(yīng)算法在數(shù)據(jù)挖掘中的應(yīng)用

自適應(yīng)算法是一種嶄新的關(guān)聯(lián)規(guī)則挖掘算法。關(guān)聯(lián)規(guī)則挖掘的傳統(tǒng)方法是從一組已知的對(duì)象開始，在數(shù)據(jù)集內(nèi)發(fā)現(xiàn)有趣的關(guān)系關(guān)聯(lián)規(guī)則。在這組已知的對(duì)象中，每個(gè)對(duì)象是由一組屬性來(lái)描述。例如，假設(shè)用D來(lái)表示一個(gè)數(shù)據(jù)集，則|D|表示這個(gè)數(shù)據(jù)集中對(duì)象的個(gè)數(shù)。D中每個(gè)對(duì)象都用n個(gè)屬性{A1μ1A2，...μm-1Am}來(lái)描述，每個(gè)屬性Ai（1≤i≤m）都有唯一的取值，μi表示一種大小關(guān)系，比如≤。但是在現(xiàn)實(shí)生活中，對(duì)象的屬性集可能是要變化的，顯然，為了獲得在這些條件下的對(duì)象集的有趣的關(guān)聯(lián)規(guī)則，也就是當(dāng)描述對(duì)象的屬性集增加的時(shí)候，傳統(tǒng)的挖掘算法可以一次又一次從頭開始應(yīng)用。但這可能是低效的。于是我們提出一種自適應(yīng)算法的思想。

自適應(yīng)算法適用于在第一次挖掘結(jié)束，屬性擴(kuò)展之后需要進(jìn)行第二次挖掘的時(shí)候。如果表示這些數(shù)據(jù)元素的屬性集擴(kuò)展s項(xiàng)，分別是m+1，m+2，...，m+s項(xiàng)。很顯然，擴(kuò)展之后，描述數(shù)據(jù)元素的向量變成m+s維。這個(gè)時(shí)候，我們應(yīng)該充分利用第一次的挖掘結(jié)果。在一項(xiàng)集結(jié)合的時(shí)候，舊屬性之間不能再進(jìn)行結(jié)合，相結(jié)合的兩個(gè)屬性至少要有一個(gè)是新屬性，這樣結(jié)合，得出的結(jié)果一定是第一次挖掘的時(shí)候所沒(méi)有的，是嶄新的規(guī)則。

自適應(yīng)算法識(shí)別有趣的關(guān)聯(lián)規(guī)則是一個(gè)迭代的過(guò)程，首先是基于關(guān)聯(lián)規(guī)則長(zhǎng)度的迭代，然后驗(yàn)證的候選人的最小支持度和最小置信度。在開始階段，它先計(jì)算長(zhǎng)度為2的關(guān)聯(lián)規(guī)則的支持度和置信度，選出有趣的關(guān)聯(lián)規(guī)則，即驗(yàn)證關(guān)聯(lián)規(guī)則的最小支持度和最小置信度。長(zhǎng)度為k的關(guān)聯(lián)規(guī)則挖掘過(guò)程分為兩個(gè)階段。第一個(gè)階段是要產(chǎn)生候選項(xiàng)，長(zhǎng)度為k的候選項(xiàng)的產(chǎn)生來(lái)源于兩部分。一部分是屬性集擴(kuò)展之前的數(shù)據(jù)集中，另一部分是在屬性集擴(kuò)展之前的數(shù)據(jù)集中的兩個(gè)長(zhǎng)度為k-1的關(guān)聯(lián)規(guī)則結(jié)合而成。第二個(gè)階段是要掃描數(shù)據(jù)集，驗(yàn)證最小支持度和最小置信度，找出有趣的關(guān)聯(lián)規(guī)則。

由上述可知，自適應(yīng)算法對(duì)第一次挖掘的結(jié)果采取了“回避”的策略，并沒(méi)有在已有的結(jié)果上花費(fèi)時(shí)間，而是采用了一種新穎的屬性結(jié)合方式，讓那s個(gè)新屬性和所有的m+s個(gè)屬性相結(jié)合，這樣就保證了結(jié)合出來(lái)的關(guān)聯(lián)規(guī)則是新的關(guān)聯(lián)規(guī)則，直觀上可以看出效率更高。

3 結(jié)束語(yǔ)

在本文中，我們提出了挖掘關(guān)聯(lián)規(guī)則的一種嶄新的挖掘思想——自適應(yīng)挖掘思想。這種思想是在第一次挖掘之后，如何利用已有的結(jié)果，盡快挖掘出所有有趣的關(guān)聯(lián)規(guī)則。但這種算法仍然是順序挖掘算法，并沒(méi)有考慮到在多處理機(jī)系統(tǒng)的環(huán)境下，如何利用并行思想，更加高效的挖掘信息。在未來(lái)的工作中，我們準(zhǔn)備把并行思想融入到自適應(yīng)算法之中。

參考文獻(xiàn)：

[1]韓家煒，裴健.數(shù)據(jù)挖掘概念與技術(shù)[M].3版.范明，孟小峰，譯. 機(jī)械工業(yè) 出版時(shí)間，2012.

[2]紀(jì)希禹.數(shù)據(jù)挖掘技術(shù)應(yīng)用實(shí)例[M].北京：機(jī)械工業(yè)出版社，2008.

[3]R. Agrawal， T. Imielinski， A. Swarmi， Mining association rules between sets of items in large databases[C]. Proceedings of the ACM SIGMOD Conference on Management of Data 1993：207–216.

[4]譚建豪.數(shù)據(jù)挖掘技術(shù)[M]. 水利水電出版社， 2009.

[5]R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In VLDB， pages 487–499， 1994.