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

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

中圖分類號(hào)： TP312? ? 文獻(xiàn)標(biāo)識(shí)碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.10.035

本文著錄格式：曹素娥. 數(shù)據(jù)挖掘中分類算法的可擴(kuò)展性探討[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]是最為常見的一項(xiàng)技術(shù)，按照數(shù)據(jù)集特征構(gòu)建分類器，以此為未知類別樣本賦予類別。通常分類器構(gòu)建主要有訓(xùn)練、測試這兩個(gè)環(huán)節(jié)，訓(xùn)練環(huán)節(jié)需要對(duì)訓(xùn)練數(shù)據(jù)集特征進(jìn)行分析，使所有類別都有對(duì)應(yīng)的數(shù)據(jù)集模型，進(jìn)入到測試階段之后，通過類別描述、模型準(zhǔn)確劃分測試類別，從而保證分類結(jié)果精準(zhǔn)性。分類算法應(yīng)用的過程中需要了解其中隱藏的規(guī)則，這就需要發(fā)揮分類算法可擴(kuò)展性特點(diǎn)，下面圍繞這一點(diǎn)展開分析。

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

1.1? 決策樹分類算法

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

1.2? K最近鄰分類算法

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

2? 分類算法可擴(kuò)展性

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

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

3.1? 應(yīng)用快速算法

3.1.1? 構(gòu)建限制模型空間

通過線性回歸分類、簡單神經(jīng)元、單層決策樹這三種方法可以構(gòu)建限制模型空間，因?yàn)槟Ｐ涂臻g比較小，使用難度不高的學(xué)習(xí)算法可以快速學(xué)習(xí)。

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

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

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

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

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

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

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

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

3.3? 表達(dá)與維護(hù)數(shù)據(jù)關(guān)系

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

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

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

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

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

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

4? 結(jié)束語

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

參考文獻(xiàn)

[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ù)挖掘的個(gè)性化推薦系統(tǒng)設(shè)計(jì)[J]. 信息技術(shù)與信息化， 2019（6）： 12-15.

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

[4]趙小強(qiáng)， 劉夢(mèng)依. 基于不平衡數(shù)據(jù)集的主動(dòng)學(xué)習(xí)分類算法[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]鐘彩. 邊緣檢測算法在圖像預(yù)處理中的應(yīng)用[J]. 軟件， 2013， 34（1）： 158-159.

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

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