數(shù)據(jù)挖掘分類算法研究與探討

摘要：數(shù)據(jù)挖掘技術(shù)是一個(gè)年輕且充滿希望的研究領(lǐng)域，商業(yè)利益的強(qiáng)大驅(qū)動(dòng)力將會(huì)不停地促進(jìn)它的發(fā)展。隨著數(shù)據(jù)庫(kù)應(yīng)用的不斷深化，數(shù)據(jù)庫(kù)的規(guī)模急劇膨脹，數(shù)據(jù)挖掘已成為當(dāng)今研究的熱點(diǎn)，每年都有新的數(shù)據(jù)挖掘方法和模型問世，特別是其中的分類問題，引起了越來越多的關(guān)注。

關(guān)鍵詞：數(shù)據(jù)挖掘；分類；算法

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)35-2339-02

Research and Discuss the Classification Algorithm of Data Mining

SUN Juan

(Department of Information science and Technology， Jiujiang University， Jiujiang 332005， China)

Abstract: That the data mining a technology is that one is young and is full of the go into field hoping， commerce benefit driving force big and powerful will may keep on promoting development of it. Applicative ceaselessness deepens with the data base， the data base scale expands rapidly， the data mining the hot spot already becoming a nowadays studying ， the new data mining of it both method and the model every year coming out， Classification problem especially among them， has aroused more and more attention.

Key words: data mining; classification; algorithm

隨著計(jì)算機(jī)技術(shù)特別是數(shù)據(jù)庫(kù)技術(shù)的迅猛發(fā)展，以及人類活動(dòng)范圍的擴(kuò)展、生活節(jié)奏的加快，人們能以更快速更容易更廉價(jià)的方式獲取和存儲(chǔ)數(shù)據(jù)，這就使得數(shù)據(jù)及其信息量以指數(shù)方式增長(zhǎng)。面對(duì)這些極度膨脹的數(shù)據(jù)，人們受到“信息爆炸”和“數(shù)據(jù)過剩”(Data Glut)的巨大壓力。這些海量數(shù)據(jù)如果不能有效利用起來，將只會(huì)成為“數(shù)據(jù)垃圾”。對(duì)人類社會(huì)進(jìn)步起到巨大作用的是知識(shí)。 數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在規(guī)律、提取有用知識(shí)的方法和技術(shù)[1]。數(shù)據(jù)挖掘包含的內(nèi)容很多，其中很重要的一個(gè)方面是分類規(guī)則挖掘。

分類技術(shù)在很多領(lǐng)域都有應(yīng)用，例如可以通過客戶分類構(gòu)造一個(gè)分類模型來對(duì)銀行貸款進(jìn)行風(fēng)險(xiǎn)評(píng)估；當(dāng)前的市場(chǎng)營(yíng)銷中很重要的一個(gè)特點(diǎn)是強(qiáng)調(diào)客戶細(xì)分。客戶類別分析的功能也在于此，采用數(shù)據(jù)挖掘中的分類技術(shù)，可以將客戶分成不同的類別，比如呼叫中心設(shè)計(jì)時(shí)可以分為：呼叫頻繁的客戶、偶然大量呼叫的客戶、穩(wěn)定呼叫的客戶、其他，幫助呼叫中心尋找出這些不同種類客戶之間的特征，這樣的分類模型可以讓用戶了解不同行為類別客戶的分布特征；其他分類應(yīng)用如文獻(xiàn)檢索和搜索引擎中的自動(dòng)文本分類技術(shù)；安全領(lǐng)域有基于分類技術(shù)的入侵檢測(cè)等等。機(jī)器學(xué)習(xí)、專家系統(tǒng)、統(tǒng)計(jì)學(xué)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的研究人員已經(jīng)提出了許多具體的分類預(yù)測(cè)方法。下面對(duì)幾種主要的分類方法作簡(jiǎn)要的研究與探討：

1 基于判定樹的歸納分類

判定樹是一個(gè)類似流程圖的樹結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，而每個(gè)樹葉節(jié)點(diǎn)代表類或類分布。樹的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。由判定樹可以很容易得到“IF-THEN”形式的分類規(guī)則。方法是沿著由根節(jié)點(diǎn)到樹葉節(jié)點(diǎn)的路徑，路徑上的每個(gè)屬性-值對(duì)形成“IF”部分的一個(gè)合取項(xiàng)，樹葉節(jié)點(diǎn)包含類預(yù)測(cè)，形成“THEN”部分。一條路徑創(chuàng)建一個(gè)規(guī)則。判定樹歸納的基本算法是貪心算法。

算法描述如下：判定樹歸納分類[2]是一種從訓(xùn)練樣本集中推理出判定樹表示形式的分類規(guī)則的方法。它采用自頂向下的遞歸方式，判定樹的最頂節(jié)點(diǎn)是根結(jié)點(diǎn)，樹的內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，從該結(jié)點(diǎn)向下的每個(gè)分支代表一個(gè)測(cè)試輸出，在樹的葉結(jié)點(diǎn)得到分類預(yù)測(cè)。從根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)則，整棵判定樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則。判定樹的優(yōu)點(diǎn)在于它的直觀性和易理解性，判定樹方法不僅能做出分類和預(yù)測(cè)，而且它的生成過程、分類、預(yù)測(cè)以及從判定樹所提取的分類規(guī)則都具有很強(qiáng)的可理解性。

算法策略如下：①判定樹以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)開始；②如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為樹葉，并用該類標(biāo)記；③否則，基于啟發(fā)式或統(tǒng)計(jì)式策略選擇能夠最好地將樣本分類的屬性，將樣本分類；④對(duì)測(cè)試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分枝，并以此為根據(jù)劃分樣本；⑤使用同樣的過程，遞歸地形成每個(gè)劃分上的樣本判定樹。

停止劃分的條件：給定節(jié)點(diǎn)的所有樣本屬于同一類：沒有剩余屬性可以用來進(jìn)一步劃分樣本，此時(shí)使用多數(shù)表決(用訓(xùn)練集中的多數(shù)所在的類標(biāo)記它)；沒有樣本剩余。

2 KNN法(K-Nearest Neighbor)

KNN(K Nearest Neighbors)算法[3]又叫K最臨近方法，總體來說KNN算法是相對(duì)比較容易理解的算法之一，假設(shè)每一個(gè)類包含多個(gè)樣本數(shù)據(jù)，而且每個(gè)數(shù)據(jù)都有一個(gè)唯一的類標(biāo)記表示這些樣本是屬于哪一個(gè)分類，KNN就是計(jì)算每個(gè)樣本數(shù)據(jù)到待分類數(shù)據(jù)的距離，取和待分類數(shù)據(jù)最近的K各樣本數(shù)據(jù)，那么這個(gè)K個(gè)樣本數(shù)據(jù)中哪個(gè)類別的樣本數(shù)據(jù)占多數(shù)，則待分類數(shù)據(jù)就屬于該類別。

KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

該方法的不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。另外還有一種Reverse KNN法，能降低KNN算法的計(jì)算復(fù)雜度，提高分類的效率。

該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

3 VSM法

VSM法即向量空間模型(Vector Space Model)法，由Salton等人于60年代末提出。這是最早也是最出名的信息檢索方面的數(shù)學(xué)模型。其基本思想是將文檔表示為加權(quán)的特征向量：D=D(T1，W1;T2，W2;…;Tn，Wn)，然后通過計(jì)算文本相似度的方法來確定待分樣本的類別。當(dāng)文本被表示為空間向量模型的時(shí)候，文本的相似度就可以借助特征向量之間的內(nèi)積來表示。

在實(shí)際應(yīng)用中，VSM法一般事先依據(jù)語(yǔ)料庫(kù)中的訓(xùn)練樣本和分類體系建立類別向量空間。當(dāng)需要對(duì)一篇待分樣本進(jìn)行分類的時(shí)候，只需要計(jì)算待分樣本和每一個(gè)類別向量的相似度即內(nèi)積，然后選取相似度最大的類別作為該待分樣本所對(duì)應(yīng)的類別。

由于VSM法中需要事先計(jì)算類別的空間向量，而該空間向量的建立又很大程度的依賴于該類別向量中所包含的特征項(xiàng)。根據(jù)研究發(fā)現(xiàn)，類別中所包含的非零特征項(xiàng)越多，其包含的每個(gè)特征項(xiàng)對(duì)于類別的表達(dá)能力越弱。因此，VSM法相對(duì)其他分類方法而言，更適合于專業(yè)文獻(xiàn)的分類。

4 Bayes法

Bayes法是一種在已知先驗(yàn)概率與類條件概率的情況下的模式分類方法，待分樣本的分類結(jié)果取決于各類域中樣本的全體。

設(shè)訓(xùn)練樣本集分為M類，記為C={c1，…，ci，…cM}，每類的先驗(yàn)概率為P(ci)，i=1，2，…，M。當(dāng)樣本集非常大時(shí)，可以認(rèn)為P(ci)=ci類樣本數(shù)/總樣本數(shù)。對(duì)于一個(gè)待分樣本X，其歸于cj類的類條件概率是P(X/ci)，則根據(jù)Bayes定理，可得到cj類的后驗(yàn)概率P(ci/X)：

P(ci/x)=P(x/ci)·P(ci)/P(x) （1）

若P(ci/X)=MaxjP(cj/X)，i=1，2，…，M，j=1，2，…，M，則有x∈ci（2）

（2）式是最大后驗(yàn)概率判決準(zhǔn)則，將（1）式代入（2）式，則有：

若P(x/ci)P(ci)=Maxj[P(x/cj)P(cj)]，i=1，2，…，M，j=1，2，…，M，則x∈ci，這就是常用到的Bayes分類判決準(zhǔn)則。經(jīng)過長(zhǎng)期的研究，Bayes分類方法在理論上論證得比較充分，在應(yīng)用上也是非常廣泛的。

Bayes方法的薄弱環(huán)節(jié)在于實(shí)際情況下，類別總體的概率分布和各類樣本的概率分布函數(shù)(或密度函數(shù))常常是不知道的。為了獲得它們，就要求樣本足夠大。另外，Bayes法要求表達(dá)文本的主題詞相互獨(dú)立，這樣的條件在實(shí)際文本中一般很難滿足，因此該方法往往在效果上難以達(dá)到理論上的最大值。

5 神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)的研究至今已有60多年的歷史。1943年，心理學(xué)家McCulloch和數(shù)學(xué)家Pitts合作，提出了形式神經(jīng)元的數(shù)學(xué)模型，即MP模型[4]，從此，神經(jīng)網(wǎng)絡(luò)引起了許多科學(xué)家的興趣。但隨著對(duì)感知機(jī)為代表的神經(jīng)網(wǎng)絡(luò)的功能和局限性的深入分析等原因，使神經(jīng)網(wǎng)絡(luò)的研究陷入低潮。但是仍有一些學(xué)者堅(jiān)持研究，并取得了一些成果，出現(xiàn)了Grossberg的ART模型和Kohonen的SOM模型。1982年，通過引入能量函數(shù)的概念，Hopfied研究了網(wǎng)絡(luò)的動(dòng)力學(xué)性質(zhì)，并用電子線路設(shè)計(jì)出相應(yīng)的網(wǎng)絡(luò)，進(jìn)而掀起了神經(jīng)網(wǎng)絡(luò)新的研究高潮。1986年，Rumellhart和McCllel-land等提出了PDP理論，尤其是發(fā)展了多層前向網(wǎng)絡(luò)的BP算法，成為迄今應(yīng)用最普遍的學(xué)習(xí)算法。

神經(jīng)網(wǎng)絡(luò)可解決目前數(shù)據(jù)挖掘存在幾個(gè)方面的問題：

1) 數(shù)據(jù)的量度和維度，面對(duì)大量復(fù)雜、非線性、時(shí)序性與噪音普遍存在的數(shù)據(jù)；

2) 數(shù)據(jù)分析的目標(biāo)具有多樣性，使其在表述和處理上都涉及到領(lǐng)域知識(shí)；

3) 在復(fù)雜目標(biāo)下，對(duì)海量數(shù)據(jù)集的分析，目前還沒有現(xiàn)成的且滿足可計(jì)算條件的一般性理論的方法。然而，神經(jīng)網(wǎng)絡(luò)在對(duì)噪聲數(shù)據(jù)的高承受能力以及對(duì)未經(jīng)訓(xùn)練的數(shù)據(jù)分類模式的能力方面有很大優(yōu)勢(shì)。因此設(shè)計(jì)出基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)挖掘方法，并將其用于真實(shí)世界問題，是可行且也是必要的。

人工神經(jīng)網(wǎng)絡(luò)可用于數(shù)據(jù)挖掘的分類、聚類、特征挖掘、預(yù)測(cè)和模式識(shí)別等方面，因此，人工神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘中占有舉足輕重的作用。

總之，數(shù)據(jù)挖掘技術(shù)是一個(gè)年輕且充滿希望的研究領(lǐng)域，商業(yè)利益的強(qiáng)大驅(qū)動(dòng)力將會(huì)不停地促進(jìn)它的發(fā)展。每年都有新的數(shù)據(jù)挖掘方法和模型問世，人們對(duì)它的研究正日益廣泛和深入。盡管如此，數(shù)據(jù)挖掘技術(shù)仍然面臨著許多問題和挑戰(zhàn)：如數(shù)據(jù)挖掘方法的效率亟待提高，尤其是超大規(guī)模數(shù)據(jù)集中數(shù)據(jù)挖掘的效率；開發(fā)適應(yīng)多數(shù)據(jù)類型、容噪的挖掘方法，以解決異質(zhì)數(shù)據(jù)集的數(shù)據(jù)挖掘問題；動(dòng)態(tài)數(shù)據(jù)和知識(shí)的數(shù)據(jù)挖掘；網(wǎng)絡(luò)與分布式環(huán)境下的數(shù)據(jù)挖掘等；另外，近年來多媒體數(shù)據(jù)庫(kù)發(fā)展很快，面向多媒體數(shù)據(jù)庫(kù)的挖掘技術(shù)和軟件今后將成為研究開發(fā)的熱點(diǎn)。

參考文獻(xiàn)：

[1] 范明，孟小峰.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2001.

[2] 王旅，彭宏，胡勁松.基于判定樹歸納分類的土質(zhì)分類定名方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27(11):1929-1931.

[3] 王燕，李睿，李明.數(shù)據(jù)挖掘技術(shù)應(yīng)用研究[J].甘肅科技，2001，17(1):49-50.

[4] 毛國(guó)君，段立娟，王實(shí)，等.數(shù)據(jù)挖掘原理與算法[M].北京：清華大學(xué)出版社，2007.