褚治廣，顏 飛，張 興，李 暢

?

基于C4.5算法和Hadoop云計算平臺的購物意愿分析方法

褚治廣，顏 飛，張 興，李 暢

（遼寧工業(yè)大學 計算中心，遼寧 錦州 121001）

為適應大數(shù)據(jù)背景下的計算需求，首先根據(jù)C4.5算法計算原理的特點，對C4.5進行數(shù)據(jù)處理并行化改進。然后根據(jù)Hadoop云平臺的特點，對數(shù)據(jù)處理流程進行簡要說明。最后，通過搭建Hadoop云平臺環(huán)境，使用隨機生成的測試數(shù)據(jù)集對算法進行驗證。分析消費者可能購買的商品，實現(xiàn)數(shù)據(jù)的利用率最大化、提高交易成交率和挖掘潛在交易。通過實驗分析得出，基于C4.5算法和Hadoop云計算平臺的購物意愿分析方法可以應用到大型電商平臺對消費者的購物意愿進行分析中。

C4.5；Hadoop；計算集群；購物意愿；數(shù)據(jù)挖掘

互聯(lián)網(wǎng)是人類歷史上最成功的科技成果之一，互聯(lián)網(wǎng)在人們生活中的應用，極大地改變了人們的生活方式[1]。近年來，基于Internet的電商平臺快速發(fā)展，網(wǎng)上購物為生活提供了諸多便利。每天電商平臺都將會產(chǎn)生來自各行各業(yè)的海量交易數(shù)據(jù)和瀏覽記錄。如何有效地對海量交易數(shù)據(jù)進行分析和挖掘其潛在價值，對電商企業(yè)來說是具有重要意義。數(shù)據(jù)的潛在價值是企業(yè)發(fā)展的重要經(jīng)濟資產(chǎn)。

在海量的交易數(shù)據(jù)和瀏覽記錄中，隱藏了消費者的購物習慣、未來消費意愿等潛在信息。對消費者的歷史消費記錄進行分析可以有效地推測出消費者購物意愿，以及分析出對購物成功與否產(chǎn)生重要影響的因素。而且可用于企業(yè)較深入地挖掘、獲取數(shù)據(jù)潛在價值，提高交易成交率、庫存規(guī)劃、優(yōu)化市場結構等。毋庸置疑，大數(shù)據(jù)的研究提供了挖掘巨大潛在價值的手段[2]。因此，使用大數(shù)據(jù)分析方法可成為探測數(shù)據(jù)價值的重要手段，具有極其重要的作用[3]。

為此，本文搭建了一個基于Hadoop的云平臺，利用C4.5算法對購物者的一些信息進行分析，比如性別、年齡、所屬地區(qū)、物品類屬等。可用于數(shù)據(jù)分析的眾多方法中，比較適合于消費者行為分析的、而且較為有效的方法是使用決策樹方法來進行信息分類。本文應用到了C4.5算法[4-5]對消費者行為進行分析并構建出決策樹，從而進一步分析出消費者購物意愿。

1 研究現(xiàn)狀

決策樹是應用在數(shù)據(jù)挖掘中最簡單、最直接、最有效的分類算法[6-7]。其中應用比較廣泛的一種是C4.5算法，它對ID3算法進行大量的改進，C4.5算法是以信息增益率作為選擇分裂屬性的標準。解決了測試數(shù)據(jù)屬性值缺失的問題；在決策樹生成前進行修剪[8-9]；能夠?qū)﹄x散的屬性和連續(xù)的屬性值進行處理等。然而，隨著云計算的發(fā)展以及海量數(shù)據(jù)的產(chǎn)生。在海量數(shù)據(jù)集處理過程中，C4.5算法需要花費大量的計算時間，時間效率低下。其次，在傳統(tǒng)的決策樹構造過程中，需要將數(shù)據(jù)集全部裝入內(nèi)存，導致在內(nèi)存上算法具有比較差的伸縮性。為滿足大數(shù)據(jù)背景下的海量數(shù)據(jù)處理，C4.5算法在處理海量數(shù)據(jù)過程中需要并行化處理。

比如海量嘈雜數(shù)據(jù)進行決策樹算法中[10]，在Hadoop平臺下，通過將C4.5算法以文件分裂的方式進行MapReduce并行化程序設計，增強了處理海量數(shù)據(jù)的能力。而且由實驗結果可得，在訓練集數(shù)據(jù)是嘈雜的情況下，C4.5算法的準確率相對更高。并且基于Hadoop的并行化的C4.5算法具有處理海量數(shù)據(jù)的能力。在對C4.5算法并行化方法中，可將C4.5的并行化應用到海量醫(yī)療數(shù)據(jù)挖掘中[11]，對算法中可并行的部分進行并行化設計。融合Bagging改進C4.5算法和基于MapReduce的并行化C4.5算法進行驗證，對比算法性能。文獻[12]利用MATLAB實現(xiàn)串行的C4.5決策樹，并對構成該決策樹的子函數(shù)進行運行時間分析，確定信息增益率計算的復雜性，縱向劃分數(shù)據(jù)，構建了并行的C4.5決策樹。

由于在決策樹的構建過程中，連續(xù)屬性的端點計算和數(shù)據(jù)掃描會花費決策樹算法時間，因此研究人員通過對連續(xù)屬性離散化實現(xiàn)屬性分割。將需要統(tǒng)計的數(shù)據(jù)分到不同的機器上面進行統(tǒng)計，然后匯總。除此之外，可以對決策樹的構建過程做一些處理[13]：首先，在數(shù)據(jù)的預處理中，主要是對與挖掘任務不相關的數(shù)據(jù)內(nèi)容進行清洗處理，以減少數(shù)據(jù)樣本量，有效地縮短決策樹構建時間開銷。其次，在決策樹算法中對數(shù)據(jù)進行了重新構造，建立屬性表，構造新的數(shù)據(jù)類型能夠更方便快速地構造決策樹，實現(xiàn)C4.5算法在大數(shù)據(jù)處理中的應用。

2 Hadoop平臺的C4.5算法的并行化

本方法在對大量的購物者行為數(shù)據(jù)進行分析的基礎上構建決策樹，從而對消費者潛在的購物意愿進行預測。出于對大數(shù)據(jù)背景的考慮，消費者信息往往是基于Hadoop平臺來存儲的。因此，數(shù)據(jù)往往分布式存儲在不同場地。在決策樹的構建過程中，需要從分布式的場地中提取出來數(shù)據(jù)，那么就需要借助于Hadoop平臺來對數(shù)據(jù)的存儲策略、存儲場地、數(shù)據(jù)處理等進行操作。而傳統(tǒng)決策樹算法無法很好地滿足大數(shù)據(jù)背景下分布式數(shù)據(jù)處理的需求。

2.1 C4.5算法的并行化

本文對C4.5算法并行化改進以適應Hadoop云平臺來構建決策樹。主要是對每個屬性所擁有的信息增益以及信息增益率的計算過程進行并行化改進[14]，改進后實現(xiàn)C4.5算法并行化。從而使得計算過程所花費的時間較大程度地縮短，提高數(shù)據(jù)處理效率，使其達到大數(shù)據(jù)背景下C4.5算法的應用需求[15]。

另外，無論是在實際應用中還是在模擬實驗過程中，難免會出現(xiàn)臟數(shù)據(jù)。數(shù)據(jù)質(zhì)量問題會對大數(shù)據(jù)的分析產(chǎn)生影響。為了保證實驗的準確性，需要對測試數(shù)據(jù)集進行數(shù)據(jù)清洗。數(shù)據(jù)清洗是對數(shù)據(jù)集無效數(shù)據(jù)、空數(shù)據(jù)或冗余數(shù)據(jù)進行清洗，提高數(shù)據(jù)處理效率[16]。在Hadoop云平臺上運行C4.5算法需要在C4.5算法中嵌入map函數(shù)和reduce函數(shù)，然后對其并行化處理，整個數(shù)據(jù)處理過程的主要步驟如圖1所示。

圖1 數(shù)據(jù)流圖

其映射和簡化過程的說明[17]：開始執(zhí)行Map動作前調(diào)用setup，在setup中預讀取所有需要的Mapper數(shù)據(jù)。數(shù)據(jù)流經(jīng)Map后，會將處理結果轉至Reducer進行處理。而Reducer過程可將具有相同key值的數(shù)據(jù)集歸約到一塊。而后，所得到的處理數(shù)據(jù)將直接寫入HDFS之中。

2.2 決策樹的構建

在Hadoop云平臺下生成決策樹所需的判定依據(jù)來自C4.5算法對數(shù)據(jù)集屬性的計算和判定，因此，結合圖1對提出的C4.5算法[18]進行了改進，算法描述如下所示。

輸入：數(shù)據(jù)集S，由離散值屬性表示，節(jié)點T。

輸出：一棵決策樹。

(1)創(chuàng)建根節(jié)點T，如果數(shù)據(jù)集S中實例的屬性相同或者實例僅有1例，則設置節(jié)點T作為葉節(jié)點；

(2)IF數(shù)據(jù)集S中實例的屬性相同

(3)Then返回T為葉節(jié)點，標記其屬性；

(4)IF數(shù)據(jù)集S中實例為空

(5)Then返回T為葉節(jié)點，將其標記為數(shù)據(jù)集S中最普通的類；

(6)否則，選擇數(shù)據(jù)集S屬性列表中信息增益率最高的屬性作為屬性；

(7)標記結點T為屬性；

(8)將數(shù)據(jù)集S根據(jù)輸出屬性的不同劃分成1，2，…，S子集，生成’節(jié)點的孩子節(jié)點1，2，…，T；

(9)對于每一組(S，T)，遞歸生成子樹T。

在C4.5算法構建決策樹的過程中，引入了信息熵(Entropy)的概念，實現(xiàn)每個分類的構建都與其選擇的目標分類相關[19-21]。利用信息增益來構造決策樹是一種采用平均信息量處理屬性不確定的信息的最佳方法，信息熵公式為：

信息增益為信息熵的有效減少量，根據(jù)它就能夠確定在不同的層次上選擇相應的變量來分類。假設存在2個類P和N，并且記錄集S中包括個屬于類P的記錄和個屬于類N的記錄。那么，用于確定記錄集S中某個記錄屬于哪個類的所有信息量為：

假設以變量為樹的根，將數(shù)據(jù)集S分成若干子類，其中每個中有條記錄屬于類P，和條記錄屬于類N。則信息量計算如下：

(3)

假設以變量為分類節(jié)點，則變量的信息增量為：

信息增益函數(shù)的定義為：

(5)

C4.5算法是以信息增益率來選擇分類屬性的。而信息增益率等于信息增益與分割信息量的比值，其中分割信息量計算公式為：

由上述公式可得，信息增益率是任意樣本子集占總樣本集的比例，即信息增益率為：

(7)

本方法在對大量的購物者行為數(shù)據(jù)進行分析的基礎上構建一棵決策樹，從而對消費者潛在的購物意愿進行預測。

3 實驗與數(shù)據(jù)分析

3.1 實驗環(huán)境

為了模擬電商平臺，本文搭建了由20臺普通計算機組成的一個小型的云平臺。具體說明為：本文所搭建環(huán)境中，Hadoop集群由20臺計算機組成，其中1臺作為Master節(jié)點，其余為Slaver計算節(jié)點。每臺PC硬件均為Intel Dual-core 2.6 GHz處理器，2 G內(nèi)存，500 G硬盤，Ubuntu-12.10-server-i386系統(tǒng)，開發(fā)環(huán)境中的JDK版本為1.6.0_27，數(shù)據(jù)庫采用Mysql 5.5版本，Hadoop-1.20.2。

3.2 實驗數(shù)據(jù)分析

為了實現(xiàn)更客觀的對消費者購物意愿的分析，本文采用了隨機生成的方式，產(chǎn)生約100億條沒有傾向性的消費者購物記錄，包括性別、年齡、所屬區(qū)域、購物類型。將產(chǎn)生的數(shù)據(jù)首先存在Mysql數(shù)據(jù)庫中，然后通過Hadoop平臺將數(shù)據(jù)遷移到數(shù)據(jù)存儲倉庫Hive之中。在數(shù)據(jù)轉存至Hive中時，對消費記錄數(shù)據(jù)的描述進行了離散化處理，并按照將消費者性別分為男、女；地域為中國各個省份以及其他國家和地區(qū)；年齡分為青少年、中年、老年；類別為日用百貨共15大項。

(1)計算分類屬性的信息量

對于類別屬性A(是否是男性)屬于正例y和反例n的個數(shù)分別為321、179個，則()=321/500，()=179/500，分類屬性的信息量為：

(2)計算測試屬性的信息增益率

以屬性“年齡”為例，取值為青少年、中年、老年，其實例數(shù)分別為202、226、72個。當取值為青少年時，正例為128個，反例為74個；當取值為中年時，正例為149個，反例為77個；當取值為老年時，正例為44個，反例為28個。則：

以屬性“Area”為例，同age的原理一樣：

以屬性“Category”為例，同上述原理相同：

由上述計算結果可得：在本實驗中，年齡的信息增益率最大，即年齡所含的信息對分類的幫助最大，因此選擇“年齡”為測試屬性。同理，可得出“地區(qū)”為決策樹下一個節(jié)點的測試屬性，以此類推最后是類目。依據(jù)測試屬性集所生成的決策樹即可分析出消費者可能需要購買的商品，從而挖掘出這些消費數(shù)據(jù)的潛在價值，實現(xiàn)數(shù)據(jù)的利用率最大化。

因此，此基于C4.5算法和Hadoop云計算平臺的購物意愿分析方法可以應用到大型電商平臺對消費者的購物意愿進行分析當中，從而挖掘出隱藏在消費記錄中的潛在價值，提高交易成交率和挖掘潛在交易[22]。以京東618品質(zhì)狂歡節(jié)第一單快遞7 min送達為例，類似的交易可以利用購物意愿分析方法對購物者購物意愿進行預測，做到配送時間更短、簽收速度更快，為消費者提供更高品質(zhì)的購物體驗。

3.2 MapReduce計算效率驗證

本文還對基于C4.5算法的MapReduce在分布式并行環(huán)境下的計算效率進行評估擴展能力。主要從2個方面來進行評估：(1)節(jié)點數(shù)不同情況下的性能表現(xiàn)。(2)測試數(shù)據(jù)集大小不同時，計算性能表現(xiàn)。

本文實驗所采用數(shù)據(jù)集分別為10、20、30 G，記錄數(shù)據(jù)支持度為5%、10%、15% 3種情況下時，計算節(jié)點為5、10、15、20個運算節(jié)點的表現(xiàn)。

第一組實驗為10G數(shù)據(jù)在5、10、15、20個運算節(jié)點上實際運行時的計算時間展示。10 G數(shù)據(jù)大概含有1億條事務，測試結果如圖2所示。

圖2 10 G數(shù)據(jù)測試表現(xiàn)圖

圖3 20 G數(shù)據(jù)測試表現(xiàn)圖

第二組實驗是將20 G數(shù)據(jù)分別在5、10、15、20運算節(jié)點上實際運行。根據(jù)實驗1所述，20 G數(shù)據(jù)大概含有2億條事務。計算時間展示結果如圖3所示。

第三組實驗是將30 G數(shù)據(jù)分別在5、10、15、20個運算節(jié)點上實際運行。根據(jù)實驗1所述，30 G數(shù)據(jù)大概含有3億條事務。計算時間展示結果如圖4所示。

圖4 30 G數(shù)據(jù)測試表現(xiàn)圖

對比上述3組實驗的運算時間結果可以看出，隨著參與運算的節(jié)點數(shù)目的增加，數(shù)據(jù)處理耗費的時間呈遞減趨勢。這就說明參加運算的節(jié)點越多，C4.5算法運行的效率就越高。另一方面，運行時間還與訓練集的大小有關。

由圖2~圖4的測試數(shù)據(jù)集大小不同的情況下運算性能表現(xiàn)可得：(1)數(shù)據(jù)集越龐大，系統(tǒng)運算時間越長。(2)參與運算的節(jié)點越多系統(tǒng)執(zhí)行時間越少。(3)如果參與運算的的節(jié)點數(shù)足夠多的話，即使測試數(shù)據(jù)集很大，其性能表現(xiàn)也會表現(xiàn)得最優(yōu)。如圖4所示，如果30 G的測試數(shù)據(jù)在20個節(jié)點下運行，其運行時間與20 G的測試數(shù)據(jù)時運行時間相差較小?？傊贖adoop平臺的C4.5算法可以明顯提高對海量數(shù)據(jù)的挖掘效率。

4 結束語

針對現(xiàn)在電商平臺每時每刻都會產(chǎn)生來自各行各業(yè)的海量交易數(shù)據(jù)和瀏覽記錄，提出了基于C4.5算法和Hadoop云計算平臺的購物意愿分析方法。對海量交易數(shù)據(jù)進行分析和挖掘其潛在價值，對電商企業(yè)來說具有重要意義。而傳統(tǒng)的單機系統(tǒng)無法勝任龐大數(shù)據(jù)的處理，因此本文搭建Hadoop集群模擬電商平臺，生成數(shù)量龐大的測試數(shù)據(jù)集，通過C4.5決策樹算法，對信息增益率進行推導計算，判斷分類能力強的屬性作為決策樹節(jié)點。從而實現(xiàn)對消費者行為進行分析并根據(jù)購物行為推測出購物者的購物意愿的目的。因此，基于C4.5算法和Hadoop云計算平臺的購物意愿分析方法可以應用到大型電商平臺對消費者的購物意愿進行分析當中。最后，通過實驗結果表明，利用MapReduce實現(xiàn)C4.5算法具有較好的挖掘效率。

[1] 尹浩, 喬波. 大數(shù)據(jù)驅(qū)動的網(wǎng)絡信息平面[J]. 計算機學報, 2016, 39(1): 126-139.

[2] 趙國棟, 易歡歡, 糜萬軍, 等. 大數(shù)據(jù)時代的歷史機遇: 產(chǎn)業(yè)變革與數(shù)據(jù)科學[M]. 北京: 清華出版社, 2013.

[3] 梁吉業(yè), 馮晨嬌, 宋鵬. 大數(shù)據(jù)相關研究綜述[J]. 計算機學報, 2016, 2016, 39(1): 1-18.

[4] Wei D, Wei J. A MapReduce Implementation of C4.5 Decision Tree Algorithm[J]. International Journal of Database Theory & Application, 2014, 7(1): 46-60.

[5] Quinlan J R. Improved use of continuous attributes in C4.5. AI Access Foundation, 1996, 4(1): 77-90.

[6] Witten I H, Frank E. Data mining: practical machine learning tools and techniques[J]. Biomedical Engineering Online, 2011, 51(1): 95-97.

[7] Berry M J A, Linoff G S. Data Mining Techniques: For Marketing, Sales, and Customer Support[C]. John Wiley & Sons Publishing, 1997, 43(1): 1-8.

[8] Ventura D, Martinez T R. An empirical comparison of discretization methods[J]. Computer and Information Sciences, 1995, 10(2): 443-450.

[9] 李會, 胡笑梅. 決策樹中ID3算法與C4.5算法分析與比較[J]. 水電能源科學, 2008, 26(2): 129-132.

[10] 劉亞秋, 李海濤, 景維鵬. 基于Hadoop的海量嘈雜數(shù)據(jù)決策樹算法的實現(xiàn)[J]. 計算機應用, 2015, 35(4): 1143-1147.

[11] 王寧. ID3決策樹算法分析與改進[D]. 北京: 北京郵電大學, 2013.

[12] 張瑩, 畢卓. 基于SPMD的C4.5并行決策樹加速分析[J]. 計算機技術與發(fā)展, 2015, 25(1): 29-32.

[13] 龍志勇. 基于并行化的決策樹算法優(yōu)化及應用研究[D]. 杭州: 浙江大學, 2015.

[14] 孫媛, 黃剛. 基于Hadoop平臺的C4.5算法的分析與研究[J]. 計算機技術與發(fā)展, 2014(11): 83-86.

[15] Nari S G, Adbulla N, Gazzali Z A M, et al. Measure customer behaviour using C4.5 decision tree mapreduce implementation in big data analytics and data visualization[J]. International Journal for Innovative Research in Science & Technology, 2015, 1(10): 228-235.

[16] 楊東華, 李寧寧, 王宏志, 等. 基于任務合并的并行大數(shù)據(jù)清洗過程優(yōu)化[J]. 計算機學報, 2016, 39(1): 97-108.

[17] Amogh Pramod Kullkarni, Mahesh Khandewal. Survey on hadoop and introduction to YARN[J]. International Journal of Emerging Technology and Advanced Engineering, 2014, 4(5): 82-87.

[18] Wu G, Li H, Hu X, et al. MReC4.5: C4.5 Ensemble Classification with MapReduce[C]// Chinagrid Conference, 2009. Fourth IEEE, 2009: 249-255.

[19] Dunham M H. Data mining: Introductory and Advanced topics[M]. 北京: 清華大學出版社, 2003.

[20] 黃世反, 沈勇, 王瑞芳, 等. 決策樹C4.5算法屬性取值優(yōu)化研究[J]. 計算機科學與應用, 2015, 5(5): 171-178.

[21] 張睿. ID3決策樹算法分析與改進[D]. 蘭州: 蘭州大學, 2010.

[22] Arasanal R M, Rumani D U. Improving MapReduce Performance through Complexity and Performance Based Data Placement in Heterogeneous Hadoop Clusters[C]// International Conference on Distributed Computing and Internet Technology. Springer Berlin Heidelberg, 2013: 115-125.

責任編校：孫 林

Analytic Method of Customers’ Shopping Intention Based on C4.5 Algorithm and Hadoop Platform

CHU Zhi-guang, YAN Fei, ZHANG Xing, LI Chang

（Computer Center, Liaoning University of Technology, Jinzhou 121001, China）

To meet the demand of big data computing, firstly, according to the characteristics of the C4.5 algorithm calculation principle, data processing was carried out on the C4.5 parallelization improvement. Then, considering the features of Hadoop platform, the data processing is explained briefly in this paper. Finally, the experiment used the randomly generated test data sets to verify the algorithm in the Hadoop cloud platform. The method not only helps us to identify customers’ willingness of shopping and realize maximum use of data, it also provides an approach to improve the trade rates and excavate potential deals. According to experimental analysis, the method can be applied to large electric business platform to analyze consumers’ willingness of shopping.

C4.5; Hadoop; computing cluster; purchasing intention; data mining

10.15916/j.issn1674-3261.2017.04.004

TP391.1

A

1674-3261(2017)04-0225-05

2017-02-26

褚治廣(1980-)，男，遼寧錦州人，講師，碩士。