數(shù)據(jù)挖掘中分類算法的可擴展性探討

摘? 要： 為了更加靈活的應用分類算法，針對數(shù)據(jù)挖掘中分類算法的可擴展性展開分析，首先介紹決策樹分類算法、K最近鄰分類算法這2種常見分類算法，并且分析分類算法的可擴展性，明確分類算法的作用以及擴展分類算法的3點原因，最后從應用快速算法、及時分割數(shù)據(jù)、表達與維護數(shù)據(jù)關系這3個方面著手，闡述可擴展性的實現(xiàn)方法。數(shù)據(jù)挖掘中分類算法的可擴展性能夠充分發(fā)揮分類算法優(yōu)勢，提高分類結(jié)果準確性，及時完成數(shù)據(jù)挖掘。因此本文主要研究了數(shù)據(jù)挖掘中分類算法的可擴展性，希望能夠提供一定的參考價值。

關鍵詞： 數(shù)據(jù)挖掘;分類算法;可擴展性;決策樹分類算法

中圖分類號： TP312? ? 文獻標識碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.10.035

本文著錄格式：曹素娥. 數(shù)據(jù)挖掘中分類算法的可擴展性探討[J]. 軟件，2019，40（10）：155158

Exploration on Expansibility of Classification

Algorithms in Data Mining

CAO Su-e

（school of Computer and Network Engineering， Shanxi Datong University， Shanxi Datong， 037009）

【Abstract】： In order to apply classification algorithm more flexibly， the scalability of classification algorithm in data mining is analyzed. Firstly， two common classification algorithms， decision tree classification algorithm and K nearest neighbor classification algorithm， are introduced， and the scalability of classification algorithm is analyzed. The function of classification algorithm and three reasons of extended classification algorithm are clarified. Finally， from the application of fast algorithms， timely segmentation of data， expression and maintenance of data relations， expatiate on scalability implementation methods. The scalability of classification algorithm in data mining can give full play to the advantages of classification algorithm， improve the accuracy of classification results， and complete data mining in time. Therefore， this paper mainly studies the scalability of classification algorithm in data mining， hoping to provide some reference value.

【Key words】： Data mining; Classification algorithm; Scalability; Decision tree classification algorithms

0? 引言

數(shù)據(jù)挖掘中分類算法[1]是最為常見的一項技術，按照數(shù)據(jù)集特征構建分類器，以此為未知類別樣本賦予類別。通常分類器構建主要有訓練、測試這兩個環(huán)節(jié)，訓練環(huán)節(jié)需要對訓練數(shù)據(jù)集特征進行分析，使所有類別都有對應的數(shù)據(jù)集模型，進入到測試階段之后，通過類別描述、模型準確劃分測試類別，從而保證分類結(jié)果精準性。分類算法應用的過程中需要了解其中隱藏的規(guī)則，這就需要發(fā)揮分類算法可擴展性特點，下面圍繞這一點展開分析。

1? 數(shù)據(jù)挖掘中的幾種分類算法

1.1? 決策樹分類算法

在數(shù)據(jù)挖掘中，決策樹分類算法[2]屬于非常經(jīng)典的分類算法之一（流程圖見圖1），按照從頂至下遞歸的順序構建決策樹模型。所構建的決策樹所有結(jié)點均通過信息增益度量明確測試屬性，以此進行分類規(guī)則的提取。

1.2? K最近鄰分類算法

實際應用中K最近鄰分類算法的思路非常簡單（流程圖與數(shù)據(jù)結(jié)構見圖2表1），先將樣本所處特征空間內(nèi)K個最相似樣本假設為相同類別，且該樣本也屬于這一類別。按照相鄰最近一個或多個樣本類別判斷未分類樣本類別。分析可知該分類算法是以極限定理為基礎，但其實類別決策使只是和少量有限樣本有密切關系。所以，通過K最近鄰分類算法能夠保證樣本選擇平衡性。同時，因為該算法并非按照類域明確樣本類別，主要是通過鄰近少量樣本為依據(jù)進行確定，所以樣本類域重合、相交較多的未分類樣本集最適合應用該算法。

2? 分類算法可擴展性

針對分類算法的可擴展性[3]，分析可以確定以下幾點原因：第一，提升分類精準性。拓展分類算法最為核心的原因，是能夠切實提高分類精準性以及結(jié)果有效性;第二，滿足算法對于空間提出的嚴格要求。很多決策樹算法對于訓練樣本駐留內(nèi)存有一定的限制，因為訓練樣本在主存、高速緩存兩者之間重復進出，降低算法效率低下。所以，拓展分類算法可以有效提高算法效率，滿足空間方面的要求;第三，掌握小事件情況。因為數(shù)據(jù)挖掘中存在一些噪音數(shù)據(jù)，以免小事件錯認成假事件、過適應問題，所以數(shù)據(jù)集內(nèi)部樣本要足量，才能夠更加準確的發(fā)現(xiàn)小事件。為了更高效的拓展分類算法，需要結(jié)合具體要求選擇有效的方法，保證分類算法 可擴展性的實現(xiàn)。

3? 數(shù)據(jù)挖掘中分類算法可擴展性的實現(xiàn)

3.1? 應用快速算法

3.1.1? 構建限制模型空間

通過線性回歸分類、簡單神經(jīng)元、單層決策樹這三種方法可以構建限制模型空間，因為模型空間比較小，使用難度不高的學習算法可以快速學習。

3.1.2? 應用啟發(fā)式搜索

如果只是對非連續(xù)性數(shù)據(jù)進行考慮，那么決策樹算法時間復雜度受樣本數(shù)線性影響發(fā)生變化。然而連續(xù)性數(shù)據(jù)需要結(jié)合情況重復排序，所以最后所表現(xiàn)的復雜度明顯提升。使用啟發(fā)式算法建構決策樹[4]，期間可能缺乏可理解性，一般會使用理解起來比較容易的規(guī)則代表相應的知識，同時為了能夠保證規(guī)則精準性，經(jīng)常選擇減少錯誤剪枝法。但是該方法可擴展性能較差，無法保證計算復雜度。鑒于此，在研究過程中分別了解了RIPPER算法和? 不分而治算法，前者可以有效提升準確性，但是卻 不能保證計算復雜度;后者則極大的提升了分類準確性。

針對分而治之方法的應用[5]，要先以最大信息熵屬性變量為原則劃分數(shù)據(jù)集區(qū)域，隨后將屬性分枝循環(huán)處理。因為經(jīng)過分區(qū)的子節(jié)點只是將初始數(shù)據(jù)集中其中一個子集覆蓋，所以原始訓練集內(nèi)有價值的信息資源可能會遺失，影響最終分類結(jié)果。例如表2所示訓練集[6]，運行C4.5就可以獲得圖3所示的決策樹。但是C4.5忽略了規(guī)則r1：“IFTHENNo”，所以后期針對新樣本（cool，high）分類時，C4.5使用最右邊葉子節(jié)點，將其分類成“Yes”，訓練集內(nèi)“IFTHENNo”樣本比較多，所以分類時將其劃分為“No”。

3.1.3? 分類算法優(yōu)化與拓展

利用數(shù)據(jù)結(jié)構可以有效優(yōu)化、拓展分類算法擴展[7]。那么在決策樹分類的過程中，針對其所具有的連續(xù)屬性，需要在所有內(nèi)部結(jié)點中提煉出最佳分裂標準，期間均要以屬性取值為依據(jù)排列訓練集順序，該環(huán)節(jié)會浪費大量時間。所以，建議應用SLIQ算法，通過預排序技術，消除決策樹所有結(jié)點在數(shù)據(jù)集排序環(huán)節(jié)的相關需求。SLIQ算法在應用中應用廣度優(yōu)先方法建構決策樹，為決策樹內(nèi)葉子結(jié)點明確最優(yōu)分裂標準，同時也可以完成駐留磁盤數(shù)據(jù)集的分類操作。在SLIQ給予數(shù)據(jù)結(jié)構以新的定義，為樹的構造提供方便。因為SLIQ主要是應用駐留磁盤屬性表、單個駐留主存類表，類表大小受訓練集中元組數(shù)目成比例影響產(chǎn)生變化，所以類表無法在主存存放，便會降低SLIQ算法性能。

3.2? 及時分割數(shù)據(jù)

數(shù)據(jù)分割[8]主要可以避免算法在數(shù)據(jù)集中運行，從而將大數(shù)據(jù)集中數(shù)據(jù)挖掘問題加以解決。選擇樣本程序時需要挑選一或多個子集，將其與學習算法一一對應，以此便可以形成分類法。獲得的分類法可以利用組合程序的方式形成一個分類法。若將數(shù)據(jù)集視為一個表格，可以采用實例抽樣、特征抽樣的方式達到分類抽樣的目的。為了有效處理多個子集，建議使用串行處理。并行處理這兩種方式。

其中實例抽樣比較常用隨機抽樣、策略抽樣這兩種方法，策略抽樣在類分布均勻性較差的訓練集內(nèi)比較常用。特征抽樣的應用，一方面是因為屬性集增長之后，過適應會有更大的幾率出現(xiàn)，這時需要選擇屬性較高的子集保證算法準確性。另一方面，屬性數(shù)量在算法執(zhí)行時間復雜度中屬于核心要素，所體現(xiàn)的復雜度并非受屬性數(shù)線性增長影響。那么在算法分割中應用特征選擇這一方法，需要在已經(jīng)掌握知識的基礎上去除不需要屬性，隨后選擇域，為該域賦予相關性，在眾多屬性中選擇一個子集，計算某個屬性與目標規(guī)則二者之間具備的相關性，構建屬性子集。鑒于此，可以確定盡管數(shù)據(jù)分割能夠在大數(shù)據(jù)集分類中應用，但分類精準性不高。

3.3? 表達與維護數(shù)據(jù)關系

3.3.1? 融合分類算法與數(shù)據(jù)庫技術

數(shù)據(jù)挖掘算法在計算環(huán)節(jié)一般會消耗大量時間，計算任務的完成還需要有充足的磁盤I/O操作作為支持。通過數(shù)據(jù)庫技術[8～9]可以將復雜計算、I/O操作中存在的問題解決，使用該種方法也可以節(jié)省時間，通過編程語言完成基本搜索。與此同時，為了更好的表達數(shù)據(jù)之間的關系，需要將分類算法、數(shù)據(jù)庫技術充分結(jié)合，這也是目前研究的要點。通過分析與實踐總結(jié)三種可行的結(jié)合方法，即幾乎不使用數(shù)據(jù)庫、稀疏結(jié)合、緊密結(jié)合。目前數(shù)據(jù)挖掘系統(tǒng)中以幾乎不使用數(shù)據(jù)庫架構最為常見，通過自己研發(fā)的存儲管理模式，可以按照特殊挖掘任務對存儲管理進行優(yōu)化，但是其缺點在于無法實現(xiàn)數(shù)據(jù)庫成熟技術的充分應用。

數(shù)據(jù)庫管理系統(tǒng)有非常強的存儲管理性能，同時對于數(shù)據(jù)挖掘操作也給予幫助。例如一些數(shù)據(jù)挖掘系統(tǒng)所應用的恢復機制、日志機制、并發(fā)控制能力，支持用戶按照數(shù)據(jù)備份來實現(xiàn)數(shù)據(jù)挖掘查詢。其他數(shù)據(jù)挖掘系統(tǒng)中也運用了數(shù)據(jù)庫技術，但其作用只是體現(xiàn)在數(shù)據(jù)的存儲、恢復上，主編程語言內(nèi)部嵌入SQL查詢，可以在系統(tǒng)中輸入SQL選擇語句，調(diào)取相應的記錄集，如此一來結(jié)果記錄集的拷貝與應用浪費大量時間，直接降低了運行效率。

與數(shù)據(jù)庫相結(jié)合的架構主要是應用數(shù)據(jù)庫技術，數(shù)據(jù)挖掘中的一些計算由數(shù)據(jù)庫系統(tǒng)負責，以免應用程序數(shù)據(jù)傳輸環(huán)節(jié)浪費時間，使算法執(zhí)行效率得到提升。一些數(shù)據(jù)挖掘系統(tǒng)開始應用該種方法，同時也可以使用UDF（用戶自定義函數(shù)）進行決策樹分類，但是因為UDF并非數(shù)據(jù)庫系統(tǒng)內(nèi)部函數(shù)，其所具備的功能需要通過用戶編程的方式體現(xiàn)，數(shù)據(jù)庫查詢、處理這兩項功能沒有得到體現(xiàn)，這便對其性能的提升帶來限制。鑒于此，以標準數(shù)據(jù)庫技術為基礎研發(fā)了KDS算法，利用復雜查詢執(zhí)行、UDF調(diào)用達到預期目的。同時也可以也使用數(shù)據(jù)庫技術獲得帶有可擴展功能的分類算法，即GAC-RDB，發(fā)揮關系數(shù)據(jù)庫管理系統(tǒng)優(yōu)勢，利用聚集計算這一項功能完成分類分布統(tǒng)計等一系列操作，最大程度的提升算法運行效率。

3.3.2? 采用分布式模式進行數(shù)據(jù)挖掘

分布式數(shù)據(jù)挖掘在實踐過程中主要有三個流程，第一，將未挖掘數(shù)據(jù)劃分為多個子集，子集數(shù)量以可用處理器數(shù)量為準，將所有數(shù)據(jù)子集傳輸至處理器中;第二，所有處理器在運行期間形成的數(shù)據(jù)需要應用挖掘算法傳遞到局部數(shù)據(jù)子集，這時處理器運行相應數(shù)據(jù)挖掘算法;第三，所有數(shù)據(jù)挖掘算法將局部知識、全局知識、一致知識進行整合。這種分布式數(shù)據(jù)挖掘與抽樣方法類似，分布式處理主要是通過預測精度的方式保證速度，在實踐中有極高的使用價值。

4? 結(jié)束語

綜上所述，分類算法作為非常重要的數(shù)據(jù)挖掘技術，需要按照算法效率、計算準確性等做出綜合考慮，充分發(fā)揮算法可擴展性，獲得準確的分類結(jié)果，同時優(yōu)化算法性能。目前關于數(shù)據(jù)挖掘中分類算法的研究處于發(fā)展階段，其中還存在一些問題亟待解決，尤其是分類算法可擴展性，相關人員需要從這一方面入手，展開深入探究，明確可擴展性對于分類算法與數(shù)據(jù)挖掘的重要作用，使用有效的方法完成分類算法的擴展，獲得準確的數(shù)據(jù)分類結(jié)果。

參考文獻

[1]Stanfill Bryan， Reehl Sarah， Bramer Lisa， Nakayasu Ernesto S， Rich Stephen S， Metz Thomas O， Rewers Marian， Webb- Robertson Bobbie-Jo. Extending Classification Algorithms to Case-Control Studies.[J]. Biomedical engineering and com pu ta tional biology， 2019， 10.

[2]張玉梅. 基于Web數(shù)據(jù)挖掘的個性化推薦系統(tǒng)設計[J]. 信息技術與信息化， 2019（6）： 12-15.

[3]陳志忠. 數(shù)據(jù)挖掘算法在云平臺應用中的優(yōu)化與實施[J]. 電子元器件與信息技術， 2019（3）： 8-11.

[4]趙小強， 劉夢依. 基于不平衡數(shù)據(jù)集的主動學習分類算法[J]. 控制工程， 2019， 26（2）： 314-319.

[5]Chao Chuan Jia， Chuan Jiang Wang， Ting Yang， Bing Hui Fan， Fu Gui He. A 3D Point Cloud Filtering Algorithm based on Surface Variation Factor Classification[J]. Procedia Com puter Science， 2019， 154.

[6]鐘彩. 邊緣檢測算法在圖像預處理中的應用[J]. 軟件， 2013， 34（1）： 158-159.

[7]王雨萌， 武小軍， 羅雅晨. 基于數(shù)據(jù)挖掘和RandomForest算法的助學金分類研究[J]. 中國市場， 2019（03）： 50-52.

[8]馮杰， 屈志毅， 李志輝. 基于分類稀疏表示的人臉表情識別[J]. 軟件， 2013， 34（11）： 59-61.