一種改進的CLTree算法

李卓航

（浙江大學信息與電子工程學院，浙江 杭州310058）

一種改進的CLTree算法

李卓航

（浙江大學信息與電子工程學院，浙江 杭州310058）

針對聚類算法CLTree精度低、算法效率低的問題，提出了CLTree-R算法，之后將其應用于UCI數據集進行聚類分析?；赟park平臺的特性對數據進行并行處理，加快了算法運行效率。實驗結果也表明，使用該算法對官方數據集進行聚類分析時，可以得到較為合理的顧客劃分。

聚類；Spark；數據挖掘；并行化

1 引言

聚類算法是數據挖掘十大算法之一［1］，聚類定義為將物理或抽象對象的集合分成由類似對象組成的多個類的過程。聚類需要達成的目標是類間的差別盡量大，而類內的差別盡量小，通常被用于探索性分析。數據挖掘的精髓在于從海量價值密度低的數據中發現高價值的結論，聚類可以應用于數據分析、圖像分割及文件恢復等領域。

本文提出了一種改進的決策樹歸納聚類CLTree算法［2］，原算法的基本思想是把聚類問題轉化為分類問題，在進行決策樹生長時采取信息增益的標準生成樹的分支，即Quinlan J R［3］提出的著名ID3算法中的度量標準，而之后的C4.5算法論證了采用信息增益比率這一度量標準比信息增益的效果好［4］，本文使用改進的算法構造完CLTree之后，再利用預剪枝策略實現聚類分析。最后基于Spark平臺實現并行化處理，提高了算法效率，可以解決GB級以上數據的處理問題。

2 理論基礎

2.1 CLTree算法

首先，CLTree算法是一種基于網格劃分的典型聚類算法，網格劃分有由底向上和自頂向下兩種，CLTree算法采用了自頂向下的劃分方法，其優點在于無需指定劃分參數、適用于高維數據、對噪音不敏感，其劃分過程如下所示。

步驟1 將數據空間分成m個區域。

步驟2 對每個區域進行劃分。

步驟3 如滿足劃分停止規則轉步驟2，否則轉步驟4。

步驟4 停止劃分。

CLTree算法劃分的標準是信息增益，根據這個劃分標準，依照參考文獻［4］的步驟建立決策樹，其核心思想是提供構建決策樹對數值型數據實現聚類分析，而決策樹算法沒有已知的類標簽，不能直接進行聚類分析。可以通過將數據空間中的類別看成被低密度區域分割開的高密度區域，這樣所有數據都具有A類標簽，此時假設數據空間中存在另一種B類標簽，把空間中的數據區域與空白區域加以分類，可以解決聚類問題。

2.2 C4.5算法

C4.5算法實質上是對ID3算法的一種擴展，另外C4.5算法還可以處理連續型數據，而ID3算法只能處理離散型數據，其計算式如下：

其中，S為樣本集，A為離散屬性。Info（S）是信息熵，是決策樹進行正確判斷時需要的信息量。設S中有m個類，則：

其中，pj為S中含有類j的概率。

C4.5的選擇準則為信息增益比率，其計算式如下：

其中，TP為同一類的群體被劃分到同一簇中，TN為不同類的群體被劃分到不同簇中，FP為不同類的群體被劃分到同一簇中，TN為同一類的群體被劃分到不同簇中。

劃分信息計算式為：

其中，c為劃分的總數。SplitInfo（S，A）是以屬性 A 作為劃分依據時，S的廣度與劃分的均勻性。

C4.5算法比ID3算法的信息增益大，可以解決多值屬性的信息量傾斜問題。另外，C4.5采用預剪枝策略控制決策樹無止境增長，避免得到層數很小的無意義分類［5］。

2.3 Spark平臺

Spark平臺是一個新生的分布式云計算平臺。文件系統、數據庫、數據處理系統、機器學習是Spark平臺的組成部分。Spark共有4層架構，即應用層、數據處理層、數據管理層、資源管理層。頂層負責把數據分組傳遞給Spark計算平臺，得到想要的處理結果。數據處理層對數據進行加工，是一種以內存為基礎但不全依賴內存的計算，將計算結果回傳給上層，即應用層。數據管理層的功能是共享平臺內的信息。資源管理層的功能與YARN或者Mesos類似，可以為集群提供信息共享的管道。

Spark生態系統指的是廣義Spark，該Spark計算平臺也含有4層架構且架構形式與Hadoop類似，如圖1所示。

圖1 Spark架構

2.4 聚類評價指標

芮氏指標（RI）是評價聚類效果的手段之一，其值越大，說明聚類的效果越好，其計算式為：

3 CLTree-R算法

3.1 CLTree算法缺點及其改進

雖然CLTree能夠很好地處理高維數據，但是還是存在些許不足：首先，CLTree算法采用ID3經典算法里的劃分標準來構建決策樹，所以在把聚類分開時會偏向屬性值較多的變量，因此分簇的精度會降低［6］。其次，在劃分過程中需要對數據集進行多次掃描，算法效率降低。

針對以上不足，提出兩點改進：C4.5算法中的度量標準要比原算法采用的度量標準好，所以把CLTree算法中的度量標準信息增益替換為信息增益比率，在Spark里通過新建Entropy_Ratio單例對象并混入Impurity特質實現替換，提出CLTree-R（CLTree-ratio）算法。利用可以并行處理大數據集的Spark平臺解決算法效率低的問題。

3.2 CLTree-R算法的Spark實現

在Spark平臺中，RDD是高度抽象的數據集合，它有3個固有特點，分別是分區、函數、依賴。分區是為了并行，函數用來計算，而依賴是利用DAG圖處理每個RDD先后關系的前提。

Spark里的分區方式有 3種：HashPartitioner、RangePartitioner、自定義。本文采用 RangePartitioner，因為采用RangePartitioner實現分區，能夠盡量保證每個分區中數據量的均勻，而且分區之間是有序的，即每個分區中的元素都比另一個分區內的元素小或者大，但是分區內的元素不能保證順序，簡單說就是將一定范圍內的數映射到某一個分區內。先進行分區，然后進行局部聚類，最后根據局部聚類好的數據再次進行聚類，最后進行規約操作。

主要實現代碼如下：

Procedure CLTree-RTest（appName，master，jar，file，Ratio，maxDepth）

貴州省科技廳立項支持的“山地特色高效紫蘇新品種示范與產業化”項目實施初見成效，項目依托省科技特派員，采用“公司+科技特派員+農戶”的模式實施成果轉化，應用奇蘇2號、奇蘇3號分別在德江縣、思南縣、黎平縣等地建設示范基地示范帶動1000余畝。

輸入 應用程序名A，主節點M，程序jar包J，源數據F，信息增益比率計算方法R，樹的最大深度D。

輸出 trainErr。

Begin

New SparkConf scf

scf.appName＜- A

scf.master＜- M

New SparkContext sc

sc.jarLocation＜- J

Load File F

FD＜- F.split（“＼054”）.map（_.toDouble）

Label＜- Train（FD，F，D）

Predict＜- Label.predict

trainErr ＜- FindNotEqual（Label，Predict）／FD

sc.stop

End

End CLTree-RTest

4 實驗分析

4.1 實驗數據與實驗環境

實驗數據選自 UCI［7］數據庫，選取 Taxi Service Trajectory數據集，包括9個特征，共計1 710 671條交易記錄。

采用 CentOS操作系統，AMD Athlon 64×2 Dual Core Processor4000+的 CPU （主頻 2.10 GHz，內存 2 GB）。Spark平臺配置：操作系統為 CentOS 6.5（64 bit），一個主節點，兩個從節點。

4.2 實驗結果與分析

本文將CLTree-R算法應用于葡萄牙出租車服務軌跡數據集，對乘客的相關信息和司機的表現進行聚類分析?；赟park大數據處理平臺，表1給出了CLTree算法改進前后的芮氏指標。表2描述了數據集的相關屬性及其取值情況，共得到20個服務軌跡的聚類，表3給出了3個聚類結果的描述。

表1 CLTree算法改進前后的芮氏指標

表2 數據集的相關屬性及其取值情況

表3 聚類實驗結果

從表1可以看出，用信息增益比率替換信息增益后，改進算法CLTree-R較原算法CLTree的聚類效果有所提升。

trip_ID表示對于每個旅途來說都有一個唯一的ID。call_type有3種：A表示旅途服務是從中央大廳派出的；B表示旅途服務是在一個具體街道面向出租車司機的；C表示其他情況，比如隨機地點隨機叫車。origin_call表示使用服務的每個機主號碼；origin_stand表示唯一的出租車招呼站；taxi_ID表示每個旅途的出租車ID；timestamp表示旅途開始的時間戳；daytype表示旅途日期類型：D表示正常日期，如工作日、周末，E表示節假日，F表示節假日之前。missing_data為布爾類型，有兩種取值，false表示GPS跟蹤數據流完成，true表示位置丟失。ployline表示位置信息，用經緯度描述。

從表3可以看出，C3主要是在非節假日隨機叫車的乘客，這類乘客是出租車收入的主要群體，此類顧客理應得到日常服務。C42主要是在節假日叫車且會要求出租車到達指定地點的乘客，說明這類乘客經濟實力不錯或者經濟壓力不是很大，針對此類乘客可以試著發展成為長期熟客以達到雙贏。C21主要是一些在節假日來臨前叫車的乘客，且目的地大都是葡萄牙南部。由此得出，本文提出的改進算法CLTree-R可以合理劃分不同類型的乘客。

5 結束語

本文提出了一種改進之后的CLTree-R算法，實驗分析和測試表明，該方法可以合理劃分不同種類的乘客，進而讓出租車公司更好地服務于大眾。基于Spark平臺，采用了較好的分區策略可以讓算法更快地運行。將以上特性應用于Taxi Service Trajectory數據集，對高層將有極大的幫助。

［1］韓家煒.數據挖掘：概念與技術［M］.北京：機械工業出版社，2012.HAN J W.Data mining：concepts and techniques ［M］.Beijing：China Machine Press，2012.

［2］ DUNHAM M H.Datamining introductory and advanced topics［M］.New York：ACM Press，2002：23-60.

［3］QUINLAN J R.Machine learning ［M］.Berlin：Springer，1986：81-106.

［4］ QUINLAN J R.C4.5：program for machine learning ［M］.New York：ACM Press，1993.

［5］薛薇，陳歡歌.SPSS Modeler數據挖掘方法及應用［M］.北京：電子工業出版社，2014.XUE W，CHEN H G.Data mining method and its application of SPSS Modeler ［M］.Beijing：Publishing House of Electronics Industry，2014.

［6］ 伍育紅.聚類算法綜述［J］.計算機科學，2015，42（6A）：491-499.WU Y H.Generaloverview on clustering algorithms ［J］.Computer Science，2015，42（6A）：491-499.

［7］ BLAKE C.UCI repository of machine learning database ［J］.Neural Information Processing Systems，1998.

An improved CLTree algorithm

LI Zhuohang
College of Information Scienceamp;Electronic Engineering，Zhejiang University，Hangzhou 310058，China

An improved algorithm called CLTree-R was proposed.It could compensate the shortcoming of CLTree algorithm such as low accurate and inefficiency.Then CLTree-R was applied in clustering analysis for UCI data sets.In order to improve the efficiency，data set was parallel processed on Spark platform.Experimental results show that this algorithm can get reasonable customer classification when making cluster analysis on official data set.

clustering，Spark，data mining，parallelization

TP399

A

10.11959／j.issn.1000-0801.2016214

2016-05-16；

2016-08-02

李卓航（1994-），男，浙江大學信息與電子工程學院本科在讀。