數據挖掘中分類算法的可擴展性探討

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

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

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

本文著錄格式：曹素娥. 數據挖掘中分類算法的可擴展性探討[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? 引言

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

1? 數據挖掘中的幾種分類算法

1.1? 決策樹分類算法

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

1.2? K最近鄰分類算法

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

2? 分類算法可擴展性

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

3? 數據挖掘中分類算法可擴展性的實現

3.1? 應用快速算法

3.1.1? 構建限制模型空間

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

3.1.2? 應用啟發式搜索

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

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

3.1.3? 分類算法優化與拓展

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

3.2? 及時分割數據

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

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

3.3? 表達與維護數據關系

3.3.1? 融合分類算法與數據庫技術

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

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

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

3.3.2? 采用分布式模式進行數據挖掘

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

4? 結束語

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

參考文獻

[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數據挖掘的個性化推薦系統設計[J]. 信息技術與信息化， 2019（6）： 12-15.

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

[4]趙小強， 劉夢依. 基于不平衡數據集的主動學習分類算法[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]王雨萌， 武小軍， 羅雅晨. 基于數據挖掘和RandomForest算法的助學金分類研究[J]. 中國市場， 2019（03）： 50-52.

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