數(shù)據(jù)挖掘中的分類問(wèn)題

分類（classification）問(wèn)題是數(shù)據(jù)挖掘領(lǐng)域研究的歷史最為悠長(zhǎng)，也是研究的較為透徹的問(wèn)題。在數(shù)據(jù)挖掘領(lǐng)域，分類可以看成是從一個(gè)數(shù)據(jù)集到一組預(yù)先定義的、非交疊的類別的映射過(guò)程。其中映射關(guān)系的生成以及映射關(guān)系的應(yīng)用就是數(shù)據(jù)挖掘分類方法主要的研究?jī)?nèi)容。這里的映射關(guān)系就是我們常說(shuō)的分類函數(shù)或分類模型（分類器），映射關(guān)系的應(yīng)用就對(duì)應(yīng)于我們使用分類器將數(shù)據(jù)集中的數(shù)據(jù)項(xiàng)劃分到給定類別中的某一個(gè)類別的過(guò)程。

舉一個(gè)簡(jiǎn)單的例子，我們?nèi)耸窃趺磪^(qū)分另一個(gè)人是男性和女性的問(wèn)題就是一個(gè)分類的問(wèn)題。在我們的大腦中早就建立了男人和女人的模型，每當(dāng)我們遇到一個(gè)陌生人的時(shí)候，我們的大腦就獲取到了這個(gè)人的特征信息，通過(guò)大腦中的模型去將這個(gè)人歸類到男性或者女性的類別中（當(dāng)然人的大腦神經(jīng)系統(tǒng)處理這個(gè)問(wèn)題時(shí)的流程往往比我們這里敘述的復(fù)雜的多）。但是我們大腦中的模型是怎么建立的呢？是生來(lái)就有的嗎？很明顯不是。我們大腦建立模型的過(guò)程都是從過(guò)去的經(jīng)驗(yàn)中總結(jié)積累出來(lái)的，并在實(shí)踐過(guò)程中不斷地修正或擴(kuò)充。

很明顯我們就可以從上面的例子中得出分類的實(shí)踐意義是什么——分類從歷史的特征數(shù)據(jù)中推導(dǎo)出特定對(duì)象的描述模型，用來(lái)對(duì)未來(lái)數(shù)據(jù)的預(yù)測(cè)和分析。分類方法具有廣泛的應(yīng)用領(lǐng)域，比如醫(yī)療診斷、信用卡系統(tǒng)的信用分級(jí)、圖像模式識(shí)別、網(wǎng)絡(luò)數(shù)據(jù)分類等。

1分類的基本概念和過(guò)程描述：

分類的定義：給定一個(gè)數(shù)據(jù)集D={t1,t2,…,tn}和一組類C={C1,C2,…,Cn}，分類問(wèn)題就是去確定一個(gè)映射f：D->C，每個(gè)元組ti被分配到一個(gè)類中。類Cj包含映射到該類中的所有數(shù)據(jù)元組，即Cj={ti | f(ti)=Cj，1<=i<=n，且ti∈D}。

一般地，數(shù)據(jù)分類分類兩個(gè)步驟：建模和模型應(yīng)用。

1.建立模型，描述預(yù)訂的數(shù)據(jù)類集和概念集。

通過(guò)分析由屬性描述的數(shù)據(jù)集元組來(lái)構(gòu)造模型。數(shù)據(jù)元組即樣本、實(shí)例或?qū)ο?。用于建模而被分析的?shù)據(jù)元組的集合形成了訓(xùn)練集，訓(xùn)練集中的樣本即是訓(xùn)練元組。為了保證建造的模型與與原始數(shù)據(jù)的分布匹配且可用，我們需要從樣本群中隨機(jī)的選取訓(xùn)練樣本。每個(gè)訓(xùn)練元組都有一個(gè)特定的類標(biāo)簽與之對(duì)應(yīng)，即對(duì)于樣本數(shù)據(jù)X，其中x是他的訓(xùn)練元組，y是對(duì)應(yīng)的類標(biāo)簽，X就可以理解為類似的二維坐標(biāo)關(guān)系X（x，y），當(dāng)然這里只是便于理解的簡(jiǎn)單例子。實(shí)際上，x往往包含多個(gè)特征值，是多維向量。

分類器模型的一般表示形式為分類規(guī)則、決策樹或等式、不等式、規(guī)則式等形式，這個(gè)分類器模型對(duì)歷史數(shù)據(jù)分布模型進(jìn)行了歸納，可以用來(lái)為以后的數(shù)據(jù)樣本分類，也能幫助人們更好的理解數(shù)據(jù)集的內(nèi)容或含義。

2.分類模型的應(yīng)用。

分類器在使用之前，首先要準(zhǔn)確的評(píng)估模型的預(yù)測(cè)準(zhǔn)確率，只有在模型的準(zhǔn)確率可以接受時(shí)，才可以用它來(lái)對(duì)類標(biāo)號(hào)未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。模型在給定測(cè)試數(shù)據(jù)上的準(zhǔn)確率是指測(cè)試樣本被模型正確分類的百分比，對(duì)于每個(gè)測(cè)試樣本，將已知的類標(biāo)號(hào)和該樣本被分類模型預(yù)測(cè)的類作比較，這樣就確定了測(cè)試樣本是否被準(zhǔn)確分類。需要注意的是，若將訓(xùn)練數(shù)據(jù)用作測(cè)試數(shù)據(jù)，則模型的預(yù)測(cè)準(zhǔn)確率將過(guò)分樂(lè)觀，因?yàn)閷W(xué)習(xí)模型傾向于過(guò)分的擬合訓(xùn)練數(shù)據(jù)。因此，比較合理的模型評(píng)估方法是使用交叉驗(yàn)證法，從原始數(shù)據(jù)集中隨機(jī)選取獨(dú)立于訓(xùn)練樣本的測(cè)試數(shù)據(jù)。

簡(jiǎn)單地說(shuō)來(lái)，分類的兩個(gè)步驟可以歸結(jié)為模型的建立和使用模型進(jìn)行分類。模型的建立的過(guò)程就是使用訓(xùn)練數(shù)據(jù)進(jìn)行學(xué)習(xí)的過(guò)程，模型的應(yīng)用過(guò)程就是對(duì)類標(biāo)號(hào)未知的數(shù)據(jù)進(jìn)行分類的過(guò)程。

2從機(jī)器學(xué)習(xí)的角度看分類問(wèn)題：

機(jī)器學(xué)習(xí)中的方法或范式（paradigm）有很多種分類體系，例如從學(xué)習(xí)的方式分，有從例子中學(xué)習(xí)、類比學(xué)習(xí)、分析學(xué)習(xí)等，但一般來(lái)說(shuō)，現(xiàn)在研究得最多、被認(rèn)為最有用的是從例子中學(xué)習(xí)（learning from examples）。對(duì)從例子中學(xué)習(xí)，又有很多分類方法，例如從學(xué)習(xí)的主動(dòng)性方面，可以分為主動(dòng)學(xué)習(xí)（active learning）和被動(dòng)學(xué)習(xí)（passive learning）；從訓(xùn)練過(guò)程啟動(dòng)的早晚，可以分為迫切學(xué)習(xí)（eager learning）和惰性學(xué)習(xí)（lazy learning）；等等。

對(duì)“從例子中學(xué)習(xí)”的方法，從訓(xùn)練樣本的歧義性（ambiguity）的角度來(lái)進(jìn)行分類，機(jī)器學(xué)習(xí)可以分為監(jiān)督學(xué)習(xí)、非監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)，這是機(jī)器學(xué)習(xí)最常見(jiàn)的分類方法。對(duì)于監(jiān)督學(xué)習(xí)，給定一系列訓(xùn)練樣本，其中每個(gè)樣本都做上了標(biāo)記，比如說(shuō)標(biāo)記出這個(gè)樣本來(lái)自對(duì)一個(gè)蘋果的一次觀測(cè)。學(xué)習(xí)的目的是從這些帶有標(biāo)記的樣本中學(xué)習(xí)到一些概念,比如說(shuō)什么樣的數(shù)據(jù)對(duì)應(yīng)蘋果而不是香蕉,并且在未來(lái)給出新的樣本時(shí),能夠正確預(yù)測(cè)新樣本的標(biāo)記。這里所有訓(xùn)練例的概念標(biāo)記都是已知的，因此訓(xùn)練樣本的歧義性最低。簡(jiǎn)單的說(shuō)，監(jiān)督學(xué)習(xí)就是由訓(xùn)練樣本中學(xué)到或建立一個(gè)模式（函數(shù) / learning model），并依此模式推測(cè)新的instances。訓(xùn)練樣本是由數(shù)據(jù)元組（通常是向量）和預(yù)期輸出（類別值）所組成。函數(shù)的輸出可以是一個(gè)連續(xù)的值（稱為回歸分析），或是預(yù)測(cè)一個(gè)分類標(biāo)簽（稱作分類）。

3分類器常見(jiàn)的構(gòu)造方法：

從分類器構(gòu)造參照的理論原理來(lái)源來(lái)看，分類器常見(jiàn)的構(gòu)造方法可以分為3大類：數(shù)理統(tǒng)計(jì)方法、機(jī)器學(xué)習(xí)方法和神經(jīng)網(wǎng)絡(luò)方法等。

數(shù)理統(tǒng)計(jì)方法：包括貝葉斯法和非參數(shù)法。常見(jiàn)的臨近學(xué)習(xí)或基于事例的學(xué)習(xí)（Instance-Based Learning，IBL）屬于非參數(shù)方法。k-最鄰近算法（k-Nearest Neighborhors，簡(jiǎn)稱kNN）就是屬于非參數(shù)方法。

機(jī)器學(xué)習(xí)方法：決策樹法和規(guī)則歸納法。

神經(jīng)網(wǎng)絡(luò)方法：BP算法.

其他，如粗糙集等。

從使用技術(shù)上來(lái)分，可以分為四種類型：基于距離的分類方法、決策樹分類方法、貝葉斯分類方法和規(guī)則歸納方法?；诰嚯x的分類方法主要有最鄰近方法；決策樹方法有ID3、C4.5、VFDT等；貝葉斯方法包括樸素貝葉斯方法和EM算法；規(guī)則歸納方法包括AQ算法、CN2算法和FOIL算法。

分類方法中我們不僅需要研究分類器的構(gòu)造方法和應(yīng)用，還要考慮到分類數(shù)據(jù)的預(yù)處理以及分類算法的性能評(píng)價(jià)。