數(shù)據(jù)挖掘算法分析及其并行模式研究

單銀龍

摘 要 所謂數(shù)據(jù)挖掘，就是指采用一些算法，通過利用算法，發(fā)現(xiàn)隱藏在數(shù)據(jù)中事先未知的、用戶感興趣的知識的一個過程。在本文中，首先對數(shù)據(jù)挖掘任務(wù)和挖掘方法進行了闡述，并對其數(shù)據(jù)挖掘算法并行模式進行了相關(guān)研究。

【關(guān)鍵詞】數(shù)據(jù)挖掘算法 并行模式

1 數(shù)據(jù)挖掘的挖掘任務(wù)和挖掘方法

跟數(shù)據(jù)挖掘相關(guān)的學(xué)科門類較多，其涉及的分類方法多種多樣。根據(jù)挖掘角度的差異性，可對數(shù)據(jù)挖掘方法歸類。由挖掘任務(wù)的不同，可將數(shù)據(jù)挖掘分為這幾種類型：關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、數(shù)據(jù)總結(jié)、聚類、異常和趨勢發(fā)現(xiàn)等；由挖掘?qū)ο蟮牟煌?，可將?shù)據(jù)挖掘分為：面向?qū)ο髷?shù)據(jù)庫、文本數(shù)據(jù)源、異質(zhì)數(shù)據(jù)庫等；下文根據(jù)挖掘任務(wù)以及挖掘方法角度，重點對數(shù)據(jù)抽取、分類發(fā)現(xiàn)、聚類和關(guān)聯(lián)規(guī)則發(fā)現(xiàn)四種非常重要的發(fā)現(xiàn)任務(wù)進行闡述。一個典型的數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)一般包括數(shù)據(jù)庫、數(shù)據(jù)倉庫等幾個部分。如圖1所示。

1.1 數(shù)據(jù)抽取

數(shù)據(jù)抽取是對給定數(shù)據(jù)的緊湊描述，其運用的手段就是對數(shù)據(jù)進行濃縮處理。其中，最簡單的一種數(shù)據(jù)抽取方法就是對數(shù)據(jù)庫中的各字段上的統(tǒng)計值進行計算，這些統(tǒng)計值一般包括和值、均值、方差值等，另外，使用折線圖等圖形對數(shù)據(jù)庫字段進行表示也是一種比較傳統(tǒng)而簡單的數(shù)據(jù)抽取方法。數(shù)據(jù)挖掘關(guān)注的焦點是以數(shù)據(jù)泛化的視角來討論數(shù)據(jù)總結(jié)。所謂數(shù)據(jù)泛化，把低層次的數(shù)據(jù)抽象到高層次的一個過程。之所以把低層次的數(shù)據(jù)抽象到高層次，這是因為大家有對視圖從較高層次處理或者瀏覽有關(guān)數(shù)據(jù)的需要，所以，通過對數(shù)據(jù)進行多層次的泛化是有其合理的解釋的。

1.2 分類發(fā)現(xiàn)

在數(shù)據(jù)挖掘的所有任務(wù)中，分類是其中極為重要的任務(wù)之一。在所有商業(yè)應(yīng)用的數(shù)據(jù)挖掘任務(wù)中，分類得到了最大范圍的應(yīng)用。我們知道，分類的目標(biāo)是構(gòu)造分類函數(shù)或分類模型。在數(shù)據(jù)庫中，數(shù)據(jù)項在分類模型的作用下映射到某一個給定類別。在分類的用途中，預(yù)測是其中一個較為重要的用途。通過預(yù)測，從歷史數(shù)據(jù)記錄中推論得到給定數(shù)據(jù)的推廣描述，最后實現(xiàn)對未來數(shù)據(jù)的預(yù)測目標(biāo)。在對分類器進行構(gòu)造的過程中，必須使用訓(xùn)練樣本數(shù)據(jù)集作為輸入。訓(xùn)練集一般由數(shù)據(jù)庫記錄或元組構(gòu)成，其中，元組是由特征向量組成的。樣本的一般形式為（u1，u2，...，un；c）；其中 ui為字段值，c為類別。

1.3 聚類

聚類是把個體依據(jù)某種規(guī)律歸類成為若干類別的過程。其最終目標(biāo)是使相同類別的個體之間距離最小，而不同類別個體間距離最大化。對于聚類而言，其研究方法一般有四種：統(tǒng)計方法、機器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法和面向數(shù)據(jù)庫。通過對聚類分析方法的應(yīng)用實踐發(fā)現(xiàn)，其僅僅適合于數(shù)據(jù)庫較小的情形，這是因為其不具備線性計算復(fù)雜度。

1.4 關(guān)聯(lián)規(guī)則發(fā)現(xiàn)

關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的主要對象是事務(wù)型數(shù)據(jù)庫，針對的應(yīng)用是貨籃數(shù)據(jù)。一般而言，事務(wù)的組成部分不僅包括客戶訂購的物品，還包括客戶的標(biāo)示號。隨著條形碼技術(shù)不斷得到推廣和應(yīng)用，采用前端收款機也可以獲得大量的售貨數(shù)據(jù)。所以，通過分析歷史事務(wù)數(shù)據(jù)，可從顧客那里得到一些有價值的信息。比如，更好的解決擺放貨架商品和規(guī)劃市場的問題。所以，如果能從事務(wù)數(shù)據(jù)中找到關(guān)聯(lián)規(guī)則，這對于零售業(yè)等商業(yè)活動決策的重要性是不言而喻的。

2 關(guān)聯(lián)規(guī)則挖掘的并行算法分析

2.1 并行算法的基本概念

所謂并行算法，即對可同時執(zhí)行的進程集合，通過進程的協(xié)調(diào)作用，達到求解問題的目的。并行算法的設(shè)計是為了使并行機的眾多處理機作用得到最大程度的發(fā)揮，這樣就能更加快速有效解決問題。一般而言，并行算法對并行機存在非常強的依賴性。并行機的不同算法對其有效性會產(chǎn)生影響。

2.2 并行計算模型

要想對一個應(yīng)用問題進行求解，那么設(shè)計良好的并行算法極為重要。如果想讓并行算法作為一個由程序?qū)崿F(xiàn)結(jié)構(gòu)依賴的算法，那么抽象的并行計算機結(jié)構(gòu)是非常有必要的。這樣才能保障并行算法具有更廣泛的適應(yīng)性。并行計算模型作為一種并行計算機的抽象結(jié)構(gòu)，主要考慮到的是為了并行算法的設(shè)計。所以，并行計算模型從實質(zhì)意義上來講，它是某一類并行計算機的抽象。

2.3 并行挖掘關(guān)聯(lián)規(guī)則的算法

在通常情況下，找出頻繁項目集的付出的資金要比從頻繁項目集中找出關(guān)聯(lián)規(guī)則的費用高的多。鑒于此，發(fā)現(xiàn)頻繁項目集的并行算法就具備了重要的意義。產(chǎn)生候選集的算法的計算工作，通常來講，可歸類為兩個步驟。其一為生成候選集，其二為對候選集的計數(shù)。為達到處理器間進行工作分配的目的，就需要使事務(wù)和候選集分配給各處理器的形式多樣化。為達到更優(yōu)的并發(fā)度，候選集可選擇并行計算，或者是并行產(chǎn)生，還可以是兩者并行完成。

3 小結(jié)

數(shù)據(jù)挖掘算法的并行性可對系統(tǒng)運行速度進行提升，從而提高工作效率，這是因為數(shù)據(jù)挖掘算法可實現(xiàn)對多個任務(wù)的執(zhí)行。數(shù)據(jù)挖掘算法并行方式存在差異性，所以，必須根據(jù)實際情況使用恰當(dāng)?shù)耐诰蚍椒?，從而讓決策的作用得到最大程度的發(fā)揮。隨著數(shù)據(jù)量處理規(guī)模的逐漸增大，所以，對數(shù)據(jù)挖掘算法并行性研究的意義是不言而喻的。

參考文獻

[1]趙峰，李慶華.并行序列挖掘的一種改進算法[J].華中科技大學(xué)學(xué)報（自然科學(xué)版）.2003，31（10）：38-40.

[2]陳國良，安虹等.并行算法實踐[M].北京：高等教育出版社，2004.

[3]馬傳香，簡鐘.序列模式挖掘的并行算法研究[J].計算機工程，2005，31（06）.

[4]施建強，劉曉平.基于遺傳算法的數(shù)據(jù)挖掘技術(shù)的研究[J].電腦與信息技術(shù)，2003（01）：9-14

作者單位

金陵科技學(xué)院 江蘇省南京市 211169