淺析分類方法的發展

摘要：分類是數據挖掘的重要任務之一，分類在實際應用中有廣泛的應用，如醫療事業、信用等級等。近年來，分類方法得到了發展，本文對這些方法進行了歸納分析，總結了今后分類方法發展的方向。

關鍵詞：分類；數據挖掘

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)15-20ppp-0c

The Analysis of Classification Methods' Development

WANG Jun-yan

(Institute of Computer Science and Technology， Taiyuan University of science and technology， Taiyuan 030024， China)

Abstract: classification is one important tasks of data mining， it has been used in many application including medical diagnosis， credit grade. In recent years， classification has been developed. The paper concludes the new development of the algorithms.

Key words: classification; data mining

1 引言

分類[1]（Classification）是學會一個分類函數或分類模型（也常常稱作分類器），該模型能把數據庫中的數據項映射到給定類別中的某一個。分類可用于提取描述重要數據類的模型或預測未來的數據趨勢。分類可描述如下：輸入數據，或稱訓練集是一條條記錄組成的。每一條記錄包含若干條屬性，組成一個特征向量。訓練集的每條記錄還有一個特定的類標簽與之對應。該類標簽是系統的輸入，通常是以往的一些經驗數據。一個具體樣本的形式可為樣本向量：(v1，v2，…，vn:c)。在這里vi表示字段值，c表示類別。

分類作為數據挖掘的一個重要分支[2]，在商業、醫學、軍事、體育等領域都有廣泛的應用，在過去的十多年中引起很多來自不同領域學者的關注和研究。除了基本的統計分析方法外，數據挖掘技術主要有：神經網絡（Neural Network）、決策樹（Decision Tree）、粗糙集（Rough Set）、模糊集（Fuzzy Set）、貝葉斯網絡（Bayes Network）、遺傳算法（Genetic Algorithm）、k近鄰分類算法（k Nearest Neighbour）與支持向量機（Support Vector Machine）等。

不同的分類器有不同的特點，目前有三種分類器評價或比較尺度[1]：1) 預測準確度。預測準確度是用得最多的一種比較尺度，特別是對于預測型分類任務，目前公認的方法是10折分層交叉驗證法；2) 計算復雜度。計算復雜度依賴于具體的實現細節和硬件環境，空間和時間的復雜度問題將是非常重要的一個環節；3) 模型描述的簡潔度。模型描述越簡潔越受歡迎，如采用規則表示的分類器結果就較容易理解，而神經網絡方法產生的結果就難以理解。不同的算法有不同的特點，充分認識各算法的優點和存在的缺陷，掌握其適應的環境，方便研究者明確算法的改進和研究，本文主要對算法的研究現狀進行分析和比較。

2 分類方法的發展

2.1 決策樹的分類方法

ID3算法是較早的決策樹歸納算法。當前最有影響的決策樹算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。ID3選擇信息增益值最大的屬性劃分訓練樣本，其目的是進行分裂時系統的熵最小，從而提高算法的運算速度和精確度。這種方法的優點是描述簡單、分類速度快和產生的分類規則易于理解；但缺點是抗噪性差、訓練正例和反例較難控制以及是非遞增學習算法。C4.5是ID3的改進算法，不僅可以處理離散值屬性，還能處理連續值屬性，但是也不能進行增量學習。

SLIQ是一個能夠處理連續及離散屬性的決策樹分類器。該算法針對C4.5分類算法產生的樣本反復掃描和排序低效問題，采用了預排序和寬度優先兩項技術。預排序技術消除了結點數據集排序，寬度優先為決策樹中每個葉結點找到了最優分裂標準。這些技術結合使SLIQ能夠處理大規模的數據集，并能對具有大量的類、屬性與樣本的數據集分類；并且該算法代價不高且生成緊湊精確的樹。缺點是內存駐留數據會隨著輸入紀錄數線性正比增大，限制了分類訓練的數據量。

SPRINT方法完全不受內存的限制，并且處理速度很快，且可擴展。為了減少駐留于內存的數據量，該算法進一步改進了決策樹算法的數據結構，去掉了SLIQ中需要駐留于內存的類別列表，將類別合并到每個屬性列表中。但是對非分裂屬性的屬性列表進行分裂卻比較困難，因此該算法的可擴展性較差。

2.2 貝葉斯分類方法

貝葉斯分類是統計學分類方法，是利用Bayes定理來預測一個未知類別的樣本可能屬性，選擇其可能性最大的類別作為樣本的類別。樸素貝葉斯網絡作為一種快速而高效的算法而受到人們的關注，但是其屬性獨立性并不符合現實世界，這樣的假設降低了樸素貝葉斯網絡的性能；但是如果考慮所有屬性之間的依賴關系，使其表示依賴關系的能力增強，允許屬性之間可以形成任意的有向圖，由于其結構的任意性，這樣使得貝葉斯網絡的結構難以學習，然而，貝葉斯網絡的學習是一個NP-Complete 問題。

目前對于貝葉斯網絡的改進主要包括了[3]：1) 基于屬性選擇的方法，保證選擇的屬性之間具有最大的屬性獨立性，其中代表算法是由Langley[4]提出SBC（Selective Navie bayes）；2) 擴展樸素貝葉斯網絡的結構，考慮屬性之間的依賴關系，降低屬性獨立性假設，其中代表算法是由Friedman[5]提出樹擴展的貝葉斯網絡TAN（Tree Augmented Na?ve bayes）；3) 基于實例的學習算法[6]。

其中1)、2)的算法是根據訓練集合構造一個分類器，是一種積極的學習算法，3)的方法是一種消極的學習算法。

2.3 粗糙集分類方法

粗糙集[7]理論是一種刻劃不完整和不確定性數據的數學工具，不需要先驗知識，能有效處理各種不完備信息，從中發現隱含的知識，并和各種分類技術相結合建立起能夠對不完備數據進行分類的算法。粗糙集理論包含求取數據中最小不變集和最小規則集的理論，即約簡算法，這也是粗糙集理論在分類中的主要應用。

2.4 神經網絡

神經網絡是分類技術中重要方法之一，是大量的簡單神經元按一定規則連接構成的網絡系統。它能夠模擬人類大腦的結構和功能，采用某種學習算法從訓練樣本中學習，并將獲取的知識存儲在網絡各單元之間的連接權中。神經網絡主要有前向神經網絡、后向神經網絡和自組織網絡。目前神經網絡分類算法研究較多集中在以BP為代表的神經網絡上。文獻[8]提出了粒子群優化算法用于神經網絡訓練，在訓練權值同時刪除冗余連接，與BP結果比較表明算法的有效性。文獻[9]提出旋轉曲面變換粒子群優化算法的神經網絡，使待優化函數跳出局部極值點，提高訓練權值的效率。

2.5 K近鄰分類算法

K近鄰分類算法是最簡單有效的分類方法之一，是在多維空間中找到與未知樣本最近鄰的K個點，并根據這K個點的類別判斷未知樣本的類別。但是有兩個最大缺點：1)由于要存儲所有的訓練數據，所以對大規模數據集進行分類是低效的；2) 分類的效果在很大程度上依賴于K值選擇的好壞。文獻[10]提出一種有效的K近鄰分類算法，利用向量方差和小波逼近系數得出兩個不等式，根據這兩個不等式，分類效率得到了提高。文獻[11]提出用粒子群優化算法對訓練樣本進行有指導的全局隨機搜索，掠過大量不可能的K向量，該算法比KNN方法計算時間降低了70%。

2.6 基于關聯規則挖掘的分類方法

關聯分類方法一般由兩部組成：第一步用關聯規則挖掘算法從訓練數據集中挖掘出所有滿足指定支持度和置信度的類關聯規則，支持度用于衡量關聯規則在整個數據集中的統計重要性，而置信度用于衡量關聯規則的可信程度；第二步使用啟發式方法從挖掘出的類關聯規則中挑選出一組高質量的規則用于分類。

Agrawal等人于1993年提出了算法AIS和SETM，1994年又提出了Apriori和AprioriTid，后兩個算法和前兩個算法的不同之處在于：在對數據庫的一次遍歷中，那些候選數據項目被計數以及產生候選數據項目集的方法。但前兩者方法的缺點是會導致許多不必要的數據項目集的生成和計數。由于目前日常生活中如附加郵遞、目錄設計、追加銷售、倉儲規劃都用到了關聯規則，因此首先要考慮關聯規則的高效更新問題，D.w.cheung提出了增量式更新算法FUP，它的基本框架和Apriori是一致的；接著馮玉才等提出了兩種高效的增量式更新算法IUA和PIUA，主要考慮當最小支持度和最小可信度發生變化時，當前交易數據庫中關聯規則的更新問題。

2.7 支持向量機方法的發展

支持向量機方法是建立在統計學習理論的VC維理論和結構風險最小原理基礎之上的。根據有限樣本信息、在模型的復雜性和學習能力之間尋求折衷，以期獲得最好推廣能力。它非常適合于處理非線性問題。分類問題是支持向量機最為成熟和應用最廣的算法。但是由于SVM的訓練時間會隨著數據集的增大而增加，所以在處理大規模數據集時，SVM往往需要較長的訓練時間。

文獻[12]提出了一種多分類問題的改進支持向量機，將GA和SVM相結合，構造了一種參數優化GA-SVM，該方法在多分類非平衡問題上，提高了分類正確率，也提高了學習時間。文獻[13]提出了一種新的支持向量機增量算法，提出了一種誤分點回溯增量算法，先找出新增樣本中誤分的樣本，然后在原樣本集尋找距誤分點最近的樣本作為訓練集的一部分，重新構建分類器，有效保留樣本的分類信息，結果表明比傳統的SVM有更高的分類精度。

2.8 基于群的分類方法

這種方法可以看作是進化算法的一個新的分支，它模擬了生物界中蟻群、魚群和鳥群在覓食或者逃避敵人時的行為，對基于群的分類方法研究，可以將這種方法分為兩類：一類是蟻群算法（ACO），另一類稱為微粒群算法（PSO）。

文獻[14]提出了一種基于蟻群算法的分類規則挖掘算法，針對蟻群算法計算時間長的缺點，提出了一種變異算子，用公用數據作試驗將其結果與C4.5和Ant-Miner比較，顯示變異算子節省了計算時間。

PSO是進化計算的一個新的分支，它模擬了鳥群或魚群的行為。在優化領域中，PSO可以與遺傳算法相媲美。文獻[15]提出了基于粒子群優化算法的模式分類規則獲取，算法用于Iris數據集進行分類規則的提取，與其他算法比較顯示不僅提高了正確率，而且較少了計算時間。文獻[16]將PSO運用于分類規則提取，對PSO進行了改進，改進的算法與C4.5算法比較，試驗結果表明，在預測精度和運行速度上都占優勢。

由于PSO算法用于分類問題還處于初期，因此要將其運用到大規模的應用中還要大量的研究。

3 總結

分類是數據挖掘的主要研究內容之一，本文對分類算法進行了分析，從而便于對已有算法進行改進。未來的數據分類方法研究更多地集中在智能群分類領域，如蟻群算法、遺傳算法、微粒群算法等分類研究上以及混合算法來進行分類。總之，分類方法將朝著更高級、更多樣化和更加綜合化的方向發展。

參考文獻：

[1]邵峰晶，于忠清．數據挖掘原理與算法[M]．中國水利水電出版社，2003.

[2]陳文偉，黃金才．數據倉庫與數據挖掘[M]．人民郵電出版社，2004.

[3]L.Jiang， H.Zhang， Z.Cai and J. Su， Evolutional Naive Bayes， Proceedings of the 2005 International Symposium on Intelligent Computation and its Application， ISICA 2005， pp.344-350， China University of Geosciences Press.

[4]Langley， P.， Sage， S， Induction of selective Bayesian classifiers， in Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (1994)， pp. 339-406.

[5]Friedman， N.， Greiger， D.， Goldszmidt， M.， Bayesian Network Classifiers， Machine Learning 29 (1997) 103-130.

[6]T.Mitchell. Machine Learning.NewYork: McGraw-Hill Press， 1997.

[7]曾黃麟．粗糙理論以及應用[M]．重慶大學出版社，1996.

[8]高海兵、高亮等．基于粒子群優化的神經網絡訓練算法研究[J]．電子學報，2004，9.

[9]熊勇，陳德釗，胡上序．基于旋轉曲面變換PSO算法的神經網絡用于胺類有機物毒性分類[J]．分析化學研究報告，2006，3.

[10]喬玉龍，潘正祥，孫圣和．一種改進的快速K近鄰分類算法[J]．電子學報，2005，6.

[11]張國英，沙蕓，江惠娜．基于粒子群優化的快速KNN分類算法[J]．山東大學學報，2006，6.

[12]黃景濤，馬龍華，錢積新．一種用于多分類問題的改進支持向量機[J]．浙江大學學報，2004，12.

[13]毛建洋，黃道．一種新的支持向量機增量算法[J]．華東理工大學學報，2006，8.

[14]吳正龍，王儒敬等．基于蟻群算法的分類規則挖掘算法[J]．計算機工程與應用，2004.

[15]高亮，高海兵等．基于粒子群優化算法的模式分類規則獲取[J]．華中科技大學學報．2004，11.

[16]延麗萍，曾建潮．利用多群體PSO生成分類規則[J]．計算機工程與科學，2007，2.

收稿日期：2008-03-26

作者簡介：王俊艷（1979-）：女，山西臨猗人，助教，研究生，研究方向為智能計算、系統仿真與計算機應用研究。