分類算法的研究進展

孫嘉睿

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

一、分類算法概述

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

二、常見分類算法

2.1決策樹

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

2.2貝葉斯分類

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

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

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

2.4遺傳算法

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

2.5 KNN算法

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

參 考 文 獻

[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] 毛國君，段立娟，王實等.數(shù)據(jù)挖掘原理與算法[M].北京：清華大學(xué)出版社，2005：123—127.

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