基于Apriori算法的數(shù)據(jù)挖掘系統(tǒng)設(shè)計

摘 要：近年來，網(wǎng)絡(luò)的快速發(fā)展和普及，使人們真正進入到了信息時代。同樣的，隨之而來的就是人們面對這么一大堆信息如何檢索的問題。人們面對這么一大堆數(shù)據(jù)資源，迫切的需要新的數(shù)據(jù)分析的方法，以便更快更智能的檢索出自己需要的信息，將需要的信息轉(zhuǎn)化成有用的知識，為我們的決策提供科學(xué)的支持。

關(guān)鍵詞：Apriori算法；數(shù)據(jù)挖掘；系統(tǒng)設(shè)計

中圖分類號：TP311

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

目前人工智能和數(shù)據(jù)庫領(lǐng)域研究的熱點問題之一便是數(shù)據(jù)挖掘，英文稱之為Datemining，國內(nèi)學(xué)者也將其譯為數(shù)據(jù)庫的知識發(fā)現(xiàn)。數(shù)據(jù)挖掘簡單來講，就是從復(fù)雜的數(shù)據(jù)庫中找到隱含的，也是先前不被眾人所知的具有很大的隱含價值的信息的過程。數(shù)據(jù)挖掘主要基于機器學(xué)習(xí)、人工智能、模式識別、可視化、數(shù)據(jù)庫、統(tǒng)計學(xué)等原理，是一種決策支持過程。他能夠根據(jù)企業(yè)龐大的數(shù)據(jù)庫，通過歸納分析，作出最理性的判斷。并且能夠從數(shù)據(jù)庫中挖掘出潛在的客戶信息，幫助企業(yè)家根據(jù)市場走向調(diào)整策略，規(guī)避風(fēng)險。

2 數(shù)據(jù)挖掘項目計

MATLAB數(shù)學(xué)平臺與數(shù)據(jù)挖掘系統(tǒng)有以下功能：

2.1 最優(yōu)化

包括一些常用的最優(yōu)化方法的程序?qū)崿F(xiàn)，使一些實際問題分析求解的過程功能化，求解簡一化，求解結(jié)果精確化。

2.2 數(shù)值計算

包括一些重要的典型算法的功能程序化、界面化，使一些大型的數(shù)據(jù)分析及功能運算模式化，機器化。

2.3 數(shù)據(jù)挖掘

包括一些重要的分類方法的程序?qū)崿F(xiàn)，便于使用者對巨大的數(shù)據(jù)具有初步的處理和挖掘，為其科學(xué)決策提供支持。

3 數(shù)據(jù)挖掘系統(tǒng)設(shè)計思路

本系統(tǒng)的設(shè)計思路與其他系統(tǒng)開發(fā)的思路相同，采用模塊化的思路來實現(xiàn)系統(tǒng)各個不同的功能，最后通過模塊之間的耦合，來完成系統(tǒng)的整體開發(fā)。

本系統(tǒng)分為三個模塊，在不同的模塊下耦合了一些子模塊：

3.1 最優(yōu)化模塊

加步長搜索法、對分法、Newton切線法、黃金分割法、拋物線插值法。

3.2 數(shù)值計算模塊

（1）線性方程組直接解法：高斯消去法、LU分解法、QR分解法、反射矩陣法、旋轉(zhuǎn)矩陣法。

（2）多項式函數(shù)插值法：多項式插值法、拉格朗日插值法、牛頓插值法、埃爾米特插值法、三次樣條插值法。

（3）函數(shù)逼近：三角正交函數(shù)系逼近、勒讓德正交多項式逼近、切比雪夫正交多項式逼近、埃爾米正交特多項式逼近。

（4）數(shù)值微分：變步長與外推加速技術(shù)法、變步長梯形法、牛頓——科茨法、高斯公式法、蒙特卡洛模擬求積法。

（5）數(shù)值積分：基于接格朗日多項式法、基于樣條函數(shù)的求導(dǎo)法。

3.3 數(shù)據(jù)挖掘模塊

（1）數(shù)據(jù)與處理：缺省值處理、噪聲處理、數(shù)據(jù)集成、集度規(guī)約、數(shù)據(jù)變換。

（2）決策樹：計算信息熵、C4.5方法、CART方法、SLIQ方法、SPRINT方法。

（3）分類挖掘：貝葉斯檢測法、K—近鄰方法。

（4）關(guān)聯(lián)挖掘：Apriori算法。

（5）聚類挖掘：K-MEANS法。

4 系統(tǒng)設(shè)計流程

4.1 概要設(shè)計

首先，對系統(tǒng)設(shè)計要有一個總體上的規(guī)劃，也就是系統(tǒng)的設(shè)計概要。系統(tǒng)的概要設(shè)計需要充分考慮軟件的設(shè)計，包括如下方面：系統(tǒng)處理流程、數(shù)據(jù)的結(jié)構(gòu)設(shè)計、系統(tǒng)的組織結(jié)構(gòu)、接口設(shè)計、更能分配、模塊兒劃分、出錯處理設(shè)計等，在以上充分考慮的基礎(chǔ)上，作為軟件設(shè)計的基礎(chǔ)工作。

4.2 詳細設(shè)計

軟件系統(tǒng)的詳細設(shè)計需要建立在系統(tǒng)概要設(shè)計的基礎(chǔ)之上。軟件的詳細設(shè)計也就是在概要設(shè)計上豐富化，主要涉及到的內(nèi)容有軟件的主要算法、聚類的層次結(jié)構(gòu)和調(diào)用關(guān)系以及數(shù)據(jù)結(jié)構(gòu)等內(nèi)容。設(shè)計者在軟件詳細設(shè)計時，為了進行編碼和測試，應(yīng)當充分考慮每一個子程序的設(shè)計。還要保證各個模塊之間相互的協(xié)調(diào)，以保證對軟件整體的支持。

4.3 編碼

系統(tǒng)編碼階段，也是整個系統(tǒng)設(shè)計的核心階段。為了實現(xiàn)軟件各方面的功能，需要對目標系統(tǒng)的功能、界面和接口等方面進行調(diào)試。這個階段要求設(shè)計者要有足夠的耐心和細心，需要根據(jù)之前的詳細設(shè)計，對數(shù)據(jù)結(jié)構(gòu)、模塊實現(xiàn)和算法等方面理解透，然后才可以進行具體的編寫程序工作。

4.4 系統(tǒng)耦合

在編碼的基礎(chǔ)上，根據(jù)各個子系統(tǒng)的特性通過幾口設(shè)計將各個模塊藕合在一起，形成最原始的挖掘系統(tǒng)，在設(shè)計接口的過程中要做到高內(nèi)聚低耦合，有利于下一步的系統(tǒng)測試及相關(guān)問題的解決。

4.5 系統(tǒng)調(diào)試

根據(jù)設(shè)計初衷，對系統(tǒng)各個功能進行測試，發(fā)現(xiàn)問題并解決問題，測試過程中要做到黑盒和白盒測試法的交互進行，相關(guān)程序編碼人員輔助進行盡量做到用戶界面友好性。在此過程中如發(fā)現(xiàn)一些與設(shè)計初衷有出入，權(quán)衡系統(tǒng)的健壯性與實用性，或修改設(shè)計方案，或作適當取舍。

5 部分模塊算法分析和設(shè)計

Apriori算法

5.1 Apriari算法步驟

（1）掃描整個事物數(shù)據(jù)庫，產(chǎn)生候選1一項集的集合C1；

（2）根據(jù)最小支持度min_ sup，從C1中產(chǎn)生頻繁1一項集的集合L1；

（3）對k>1，重復(fù)執(zhí)行步驟（4）、（5）、（6）；

（4）對Lk執(zhí)行連接和剪枝操作，產(chǎn)生獲選（k+1）一項集的集合Ck+1；

（5）根據(jù)最小支持度min_ sup，從Ck+1產(chǎn)生頻繁（k+1）—項集的集合Lk+1；

（6）若Lk不等于φ，則k=k+I，跳往步驟（4）；否則，跳往步驟（7）；

（7）根據(jù)最小置信度min_sup，由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則。

5.2 算法偽代碼

Input：Database，D，of transactions；minimum support threshold： min_sup

Output：L一frequenct itemsets in D

（1）L1={largel-itemsets}；

（2）FOR （k=2；Lk-1 不等于φ； k++）DO BEGIN

（3） Ck=apriori_gen （ Lk-1）；//Ck個元素的候選集

（4） FOR all transactions t∈D DO BEGIN

（5） C1= subset（Ct ，t）； //Ct是所有t包含的候選集元素

（6） FOR all candidates c ∈Ct Do

（7） C.COUNT++；

（8） END

（9）LK={C∈CK C.COUNT>min _sup_count}

（10） END

（11）Answer=∪Lk

函數(shù)apriori_gen（）的定義

（1）FOR all itemset p∈LK-1 DO BEGIN

（2）FOR all itemset q∈LK-1 DO BEGIN

（3） IF

p.item1=q.item1∧（p.item2=q.item2） ∧（p.item3=q.item3） ∧…∧（p.itemk-1=itemk-1）

THEN

（4） c=p∞q //把q的k-1個元素連接到p后，即c 有k個元素

（5） IF has_infrequent_subset（c，L）THEN

（6） delete c； //刪除含有非頻繁項目子集的候選元素

（7） ELSE

（8） add c into C；

（9） END

（10） END

（11） RETURN C

附錄

[1]Apriori算法

function [M_matrix，N_matrix]=Apriori（support，min_con，Sheet1）

%% 輸入要進行分析的數(shù)據(jù)

n=length（Sheet1（：，1））；

% min_con=0.6；%最小置信度。

% support=2/9；%支持度

D_matrix=cell（0，0）；

for m=1：k

clear A_matrix B_matrix；

e=0；

%% 挑選支持度大于最小置信度事物集C_matrix

for i=1：b

a=0；

for j=1：n

if

a=a+1；

end

end

if a/n>=support

e=e+1；

C_matrix{e，2}=a/n；

C_matrix{e，1}=B_matrix（i，：）；

end

if e==0

break；

end

end

參考文獻：

[1]郭科.最優(yōu)化方法極其應(yīng)用[M].北京：高等教育出版社，2010.

[2]魏友華.現(xiàn)代數(shù)值計算[M].北京：人民郵電出版社，2009.

[3]朱明.數(shù)據(jù)挖掘[M].合肥：中國科技大學(xué)出版社，2008.

[4]陳東方.C語言程序設(shè)計[M].北京：清華大學(xué)出版社，2010.

[5]王文建.高級語言程序設(shè)計[M].北京：清華大學(xué)出版社，2008.

作者簡介：張琪（1983.11-），男，浙江寧波人，本科，學(xué)士學(xué)位，同濟大學(xué)在職研究生，現(xiàn)為外高橋出入境邊防檢查站技術(shù)隊副主任科員，主要研究外高橋邊檢口岸管控的數(shù)據(jù)挖掘以及相關(guān)系統(tǒng)的研發(fā)。

作者單位：同濟大學(xué)，上海 200092