數據挖掘算法分析及其并行模式研究

單銀龍

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

【關鍵詞】數據挖掘算法 并行模式

1 數據挖掘的挖掘任務和挖掘方法

跟數據挖掘相關的學科門類較多，其涉及的分類方法多種多樣。根據挖掘角度的差異性，可對數據挖掘方法歸類。由挖掘任務的不同，可將數據挖掘分為這幾種類型：關聯規則發現、數據總結、聚類、異常和趨勢發現等；由挖掘對象的不同，可將數據挖掘分為：面向對象數據庫、文本數據源、異質數據庫等；下文根據挖掘任務以及挖掘方法角度，重點對數據抽取、分類發現、聚類和關聯規則發現四種非常重要的發現任務進行闡述。一個典型的數據挖掘系統結構一般包括數據庫、數據倉庫等幾個部分。如圖1所示。

1.1 數據抽取

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

1.2 分類發現

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

1.3 聚類

聚類是把個體依據某種規律歸類成為若干類別的過程。其最終目標是使相同類別的個體之間距離最小，而不同類別個體間距離最大化。對于聚類而言，其研究方法一般有四種：統計方法、機器學習方法、神經網絡方法和面向數據庫。通過對聚類分析方法的應用實踐發現，其僅僅適合于數據庫較小的情形，這是因為其不具備線性計算復雜度。

1.4 關聯規則發現

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

2 關聯規則挖掘的并行算法分析

2.1 并行算法的基本概念

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

2.2 并行計算模型

要想對一個應用問題進行求解，那么設計良好的并行算法極為重要。如果想讓并行算法作為一個由程序實現結構依賴的算法，那么抽象的并行計算機結構是非常有必要的。這樣才能保障并行算法具有更廣泛的適應性。并行計算模型作為一種并行計算機的抽象結構，主要考慮到的是為了并行算法的設計。所以，并行計算模型從實質意義上來講，它是某一類并行計算機的抽象。

2.3 并行挖掘關聯規則的算法

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

3 小結

數據挖掘算法的并行性可對系統運行速度進行提升，從而提高工作效率，這是因為數據挖掘算法可實現對多個任務的執行。數據挖掘算法并行方式存在差異性，所以，必須根據實際情況使用恰當的挖掘方法，從而讓決策的作用得到最大程度的發揮。隨著數據量處理規模的逐漸增大，所以，對數據挖掘算法并行性研究的意義是不言而喻的。

參考文獻

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

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

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

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

作者單位

金陵科技學院 江蘇省南京市 211169