李卓航

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

一種改進(jìn)的CLTree算法

李卓航

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

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

聚類；Spark；數(shù)據(jù)挖掘；并行化

1 引言

聚類算法是數(shù)據(jù)挖掘十大算法之一［1］，聚類定義為將物理或抽象對象的集合分成由類似對象組成的多個(gè)類的過程。聚類需要達(dá)成的目標(biāo)是類間的差別盡量大，而類內(nèi)的差別盡量小，通常被用于探索性分析。數(shù)據(jù)挖掘的精髓在于從海量價(jià)值密度低的數(shù)據(jù)中發(fā)現(xiàn)高價(jià)值的結(jié)論，聚類可以應(yīng)用于數(shù)據(jù)分析、圖像分割及文件恢復(fù)等領(lǐng)域。

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

2 理論基礎(chǔ)

2.1 CLTree算法

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

步驟1 將數(shù)據(jù)空間分成m個(gè)區(qū)域。

步驟2 對每個(gè)區(qū)域進(jìn)行劃分。

步驟3 如滿足劃分停止規(guī)則轉(zhuǎn)步驟2，否則轉(zhuǎn)步驟4。

步驟4 停止劃分。

CLTree算法劃分的標(biāo)準(zhǔn)是信息增益，根據(jù)這個(gè)劃分標(biāo)準(zhǔn)，依照參考文獻(xiàn)［4］的步驟建立決策樹，其核心思想是提供構(gòu)建決策樹對數(shù)值型數(shù)據(jù)實(shí)現(xiàn)聚類分析，而決策樹算法沒有已知的類標(biāo)簽，不能直接進(jìn)行聚類分析?？梢酝ㄟ^將數(shù)據(jù)空間中的類別看成被低密度區(qū)域分割開的高密度區(qū)域，這樣所有數(shù)據(jù)都具有A類標(biāo)簽，此時(shí)假設(shè)數(shù)據(jù)空間中存在另一種B類標(biāo)簽，把空間中的數(shù)據(jù)區(qū)域與空白區(qū)域加以分類，可以解決聚類問題。

2.2 C4.5算法

C4.5算法實(shí)質(zhì)上是對ID3算法的一種擴(kuò)展，另外C4.5算法還可以處理連續(xù)型數(shù)據(jù)，而ID3算法只能處理離散型數(shù)據(jù)，其計(jì)算式如下：

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

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

C4.5的選擇準(zhǔn)則為信息增益比率，其計(jì)算式如下：

其中，TP為同一類的群體被劃分到同一簇中，TN為不同類的群體被劃分到不同簇中，F(xiàn)P為不同類的群體被劃分到同一簇中，TN為同一類的群體被劃分到不同簇中。

劃分信息計(jì)算式為：

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

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

2.3 Spark平臺

Spark平臺是一個(gè)新生的分布式云計(jì)算平臺。文件系統(tǒng)、數(shù)據(jù)庫、數(shù)據(jù)處理系統(tǒng)、機(jī)器學(xué)習(xí)是Spark平臺的組成部分。Spark共有4層架構(gòu)，即應(yīng)用層、數(shù)據(jù)處理層、數(shù)據(jù)管理層、資源管理層。頂層負(fù)責(zé)把數(shù)據(jù)分組傳遞給Spark計(jì)算平臺，得到想要的處理結(jié)果。數(shù)據(jù)處理層對數(shù)據(jù)進(jìn)行加工，是一種以內(nèi)存為基礎(chǔ)但不全依賴內(nèi)存的計(jì)算，將計(jì)算結(jié)果回傳給上層，即應(yīng)用層。數(shù)據(jù)管理層的功能是共享平臺內(nèi)的信息。資源管理層的功能與YARN或者M(jìn)esos類似，可以為集群提供信息共享的管道。

Spark生態(tài)系統(tǒng)指的是廣義Spark，該Spark計(jì)算平臺也含有4層架構(gòu)且架構(gòu)形式與Hadoop類似，如圖1所示。

圖1 Spark架構(gòu)

2.4 聚類評價(jià)指標(biāo)

芮氏指標(biāo)（RI）是評價(jià)聚類效果的手段之一，其值越大，說明聚類的效果越好，其計(jì)算式為：

3 CLTree-R算法

3.1 CLTree算法缺點(diǎn)及其改進(jìn)

雖然CLTree能夠很好地處理高維數(shù)據(jù)，但是還是存在些許不足：首先，CLTree算法采用ID3經(jīng)典算法里的劃分標(biāo)準(zhǔn)來構(gòu)建決策樹，所以在把聚類分開時(shí)會(huì)偏向?qū)傩灾递^多的變量，因此分簇的精度會(huì)降低［6］。其次，在劃分過程中需要對數(shù)據(jù)集進(jìn)行多次掃描，算法效率降低。

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

3.2 CLTree-R算法的Spark實(shí)現(xiàn)

在Spark平臺中，RDD是高度抽象的數(shù)據(jù)集合，它有3個(gè)固有特點(diǎn)，分別是分區(qū)、函數(shù)、依賴。分區(qū)是為了并行，函數(shù)用來計(jì)算，而依賴是利用DAG圖處理每個(gè)RDD先后關(guān)系的前提。

Spark里的分區(qū)方式有 3種：HashPartitioner、RangePartitioner、自定義。本文采用 RangePartitioner，因?yàn)椴捎肦angePartitioner實(shí)現(xiàn)分區(qū)，能夠盡量保證每個(gè)分區(qū)中數(shù)據(jù)量的均勻，而且分區(qū)之間是有序的，即每個(gè)分區(qū)中的元素都比另一個(gè)分區(qū)內(nèi)的元素小或者大，但是分區(qū)內(nèi)的元素不能保證順序，簡單說就是將一定范圍內(nèi)的數(shù)映射到某一個(gè)分區(qū)內(nèi)。先進(jìn)行分區(qū)，然后進(jìn)行局部聚類，最后根據(jù)局部聚類好的數(shù)據(jù)再次進(jìn)行聚類，最后進(jìn)行規(guī)約操作。

主要實(shí)現(xiàn)代碼如下：

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

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

輸入 應(yīng)用程序名A，主節(jié)點(diǎn)M，程序jar包J，源數(shù)據(jù)F，信息增益比率計(jì)算方法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(xiàn)，D）

Predict＜- Label.predict

trainErr ＜- FindNotEqual（Label，Predict）／FD

sc.stop

End

End CLTree-RTest

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)數(shù)據(jù)選自 UCI［7］數(shù)據(jù)庫，選取 Taxi Service Trajectory數(shù)據(jù)集，包括9個(gè)特征，共計(jì)1 710 671條交易記錄。

采用 CentOS操作系統(tǒng)，AMD Athlon 64×2 Dual Core Processor4000+的 CPU （主頻 2.10 GHz，內(nèi)存 2 GB）。Spark平臺配置：操作系統(tǒng)為 CentOS 6.5（64 bit），一個(gè)主節(jié)點(diǎn)，兩個(gè)從節(jié)點(diǎn)。

4.2 實(shí)驗(yàn)結(jié)果與分析

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

表1 CLTree算法改進(jìn)前后的芮氏指標(biāo)

表2 數(shù)據(jù)集的相關(guān)屬性及其取值情況

表3 聚類實(shí)驗(yàn)結(jié)果

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

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

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

5 結(jié)束語

本文提出了一種改進(jìn)之后的CLTree-R算法，實(shí)驗(yàn)分析和測試表明，該方法可以合理劃分不同種類的乘客，進(jìn)而讓出租車公司更好地服務(wù)于大眾?；赟park平臺，采用了較好的分區(qū)策略可以讓算法更快地運(yùn)行。將以上特性應(yīng)用于Taxi Service Trajectory數(shù)據(jù)集，對高層將有極大的幫助。

［1］韓家煒.數(shù)據(jù)挖掘：概念與技術(shù)［M］.北京：機(jī)械工業(yè)出版社，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數(shù)據(jù)挖掘方法及應(yīng)用［M］.北京：電子工業(yè)出版社，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］.計(jì)算機(jī)科學(xué)，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-），男，浙江大學(xué)信息與電子工程學(xué)院本科在讀。