分類(lèi)算法的研究進(jìn)展

孫嘉睿

分類(lèi)是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識(shí)別中一個(gè)重要的研究領(lǐng)域，分類(lèi)的目的是根據(jù)數(shù)據(jù)集的特點(diǎn)構(gòu)造一個(gè)分類(lèi)函數(shù)或分類(lèi)模型，該分類(lèi)模型能把未知類(lèi)別的樣本映射到給定類(lèi)別中的某一個(gè)。分類(lèi)和回歸都可以用于預(yù)測(cè)，和回歸方法不同的是，分類(lèi)的輸出是離散的類(lèi)別值，而回歸的輸出是連續(xù)或有序值。

一、分類(lèi)算法概述

為了提高分類(lèi)的準(zhǔn)確性、有效性和可伸縮性，在進(jìn)行分類(lèi)之前，通常要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，包括：（1）數(shù)據(jù)清理，其目的是消除或減少數(shù)據(jù)噪聲處理空缺值。（2）相關(guān)性分析，由于數(shù)據(jù)集中的許多屬性可能與分類(lèi)任務(wù)不相關(guān)，若包含這些屬性將減慢和可能誤導(dǎo)分析過(guò)程，所以相關(guān)性分析的目的就是刪除這些不相關(guān)的或兀余的屬性。（3）數(shù)據(jù)變換，數(shù)據(jù)可以概化到較高層概念，比如連續(xù)值屬性“收入”的數(shù)值可以概化為離散值：低、中、高。又比如，標(biāo)稱(chēng)值屬性“市”可概化到高層概念“省”此外，數(shù)據(jù)也可以規(guī)范化，規(guī)范化將給定的值按比例縮放，落入較小的區(qū)間，比如【0，1】等。

二、常見(jiàn)分類(lèi)算法

2.1決策樹(shù)

決策樹(shù)是用于分類(lèi)和預(yù)測(cè)的主要技術(shù)之一，決策樹(shù)學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，它著眼于從一組無(wú)次序、無(wú)規(guī)則的實(shí)例中推理出以決策樹(shù)表示的分類(lèi)規(guī)則。構(gòu)造決策樹(shù)的目的是找出屬性和類(lèi)別間的關(guān)系，用它來(lái)預(yù)測(cè)將來(lái)未知類(lèi)別的記錄的類(lèi)別。它采用自頂向下的遞歸方式，在決策樹(shù)的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性的比較，并根據(jù)不同屬性值判斷從該節(jié)點(diǎn)向下的分支，在決策樹(shù)的葉節(jié)點(diǎn)得到結(jié)論。

2.2貝葉斯分類(lèi)

貝葉斯分類(lèi)是統(tǒng)計(jì)學(xué)分類(lèi)方法，它足一類(lèi)利用概率統(tǒng)計(jì)知識(shí)進(jìn)行分類(lèi)的算法。在許多場(chǎng)合，樸素貝葉斯（Naive Bayes，NB）分類(lèi)算法可以與決策樹(shù)和神經(jīng)網(wǎng)絡(luò)分類(lèi)算法相媲美，該算法能運(yùn)用到大型數(shù)據(jù)庫(kù)中，且方法簡(jiǎn)單、分類(lèi)準(zhǔn)確率高、速度快。由于貝葉斯定理假設(shè)一個(gè)屬性值對(duì)給定類(lèi)的影響?yīng)毩⒂谄渌鼘傩缘闹担思僭O(shè)在實(shí)際情況中經(jīng)常是不成立的，因此其分類(lèi)準(zhǔn)確率可能會(huì)下降。為此，就出現(xiàn)了許多降低獨(dú)立性假設(shè)的貝葉斯分類(lèi)算法，TAN（tree augmented Bayes network）算法。

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

神經(jīng)網(wǎng)絡(luò)是大量的簡(jiǎn)單神經(jīng)元按一定規(guī)則連接構(gòu)成的網(wǎng)絡(luò)系統(tǒng)。它能夠模擬人類(lèi)大腦的結(jié)構(gòu)和功能，采用某種學(xué)習(xí)算法從訓(xùn)練樣本中學(xué)習(xí)，并將獲取的知識(shí)存儲(chǔ)在網(wǎng)絡(luò)各單元之間的連接權(quán)中。神經(jīng)網(wǎng)絡(luò)主要有前向神經(jīng)網(wǎng)絡(luò)、后向神經(jīng)網(wǎng)絡(luò)和自組織網(wǎng)絡(luò)。在數(shù)據(jù)挖掘領(lǐng)域，主要采用前向神經(jīng)網(wǎng)絡(luò)提取分類(lèi)規(guī)則。包括替換的誤差函數(shù)、網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)調(diào)整、學(xué)習(xí)率和要素參數(shù)的動(dòng)態(tài)調(diào)整。近年來(lái)，從神經(jīng)網(wǎng)絡(luò)中提取規(guī)則受到越來(lái)越多的關(guān)注。這主要有以下二種傾向：（1）網(wǎng)絡(luò)結(jié)構(gòu)分解的規(guī)則提取；（2）由神經(jīng)網(wǎng)絡(luò)的非線性映射關(guān)系提取規(guī)則。未來(lái)神經(jīng)網(wǎng)絡(luò)的發(fā)展可向進(jìn)一步降低算法的復(fù)雜度、提高所提取規(guī)則的可理解性及算法的適用性方向發(fā)展。

2.4遺傳算法

遺傳算法是模擬生物進(jìn)化過(guò)程的全局優(yōu)化方法，將較劣的初始解通過(guò)一組遺傳算子（繁殖—— 即選擇、交叉——即重組、變異—— 即突變），在求解空間按一定的隨機(jī)規(guī)則迭代搜索，直到求得問(wèn)題的最優(yōu)解。遺傳算法在數(shù)據(jù)挖掘領(lǐng)域的主要應(yīng)用有：（1）用它和BP算法結(jié)合訓(xùn)練神經(jīng)網(wǎng)絡(luò)，然后從網(wǎng)絡(luò)提取規(guī)則；（2）分類(lèi)系統(tǒng)的設(shè)計(jì)，如編碼方式、信任分配函數(shù)的設(shè)計(jì)以及遺傳算法的改進(jìn)等。遺傳算法用于數(shù)據(jù)挖掘存在的問(wèn)題是：（1）算法較復(fù)雜，（2）收斂于局部極小的過(guò)早收斂等難題未得到解決。

2.5 KNN算法

最臨近分類(lèi)KNN是基于要求的或懶散的學(xué)習(xí)法，即它存放所有的訓(xùn)練樣本，并且直到新的（未標(biāo)記）的樣本需要分類(lèi)時(shí)才建立分類(lèi)。這與諸如決策樹(shù)和神經(jīng)網(wǎng)絡(luò)這樣的急切學(xué)習(xí)法形成鮮明對(duì)比。懶散學(xué)習(xí)法在訓(xùn)練時(shí)比急切學(xué)習(xí)法快，但在分類(lèi)時(shí)慢，特別是當(dāng)與給定的無(wú)標(biāo)號(hào)樣本比較的可能的臨近者（即存放的訓(xùn)練樣本）數(shù)量很大時(shí)，懶散學(xué)習(xí)可能引起很高的計(jì)算開(kāi)銷(xiāo)。

參 考 文 獻(xiàn)

[1] Quinlan J R.Induction of decision trees.Ma—chine Learning. 1986：1—356.

[2] Quinlan J R.C4.5 Programs for machine learning.Morgan Kauffman.1993：81—106.

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

[4]喬向杰，陳功平.數(shù)據(jù)挖掘中分類(lèi)算法的可擴(kuò)展性研究[J].信陽(yáng)師范學(xué)院學(xué)報(bào)，2006（2）：239-242