大規(guī)模數(shù)據(jù)的隨機(jī)森林算法

李 揚(yáng)，祁 樂，聶佩蕓

(1.中國(guó)人民大學(xué) a.應(yīng)用統(tǒng)計(jì)科學(xué)研究中心，b.統(tǒng)計(jì)學(xué)院，c.統(tǒng)計(jì)咨詢研究中心，北京 100872；2.騰訊公司 國(guó)際業(yè)務(wù)部，廣東 深圳 518057)

一、引言

隨著信息技術(shù)的高速發(fā)展，人們生產(chǎn)、收集數(shù)據(jù)的能力大大提升，越來越多的數(shù)據(jù)呈現(xiàn)出樣本海量化、高維化的趨勢(shì)。譬如，阿里巴巴集團(tuán)旗下的淘寶平臺(tái)僅日交易數(shù)據(jù)就多達(dá)數(shù)10TB，F(xiàn)acebook公司每月產(chǎn)生的日志數(shù)據(jù)業(yè)已超過10PB[1]，又如Kaggle平臺(tái)舉辦的數(shù)據(jù)挖掘競(jìng)賽中向參賽者提供的許多規(guī)模龐大的數(shù)據(jù)集等。大規(guī)模數(shù)據(jù)的廣泛應(yīng)用使傳統(tǒng)的統(tǒng)計(jì)分析面臨計(jì)算效率的挑戰(zhàn)[2]。以2017年Kaggle舉辦的建模競(jìng)賽中音樂流媒體服務(wù)商KKBOX向參賽者提供的日志數(shù)據(jù)為例，該競(jìng)賽要求參賽者通過對(duì)日志數(shù)據(jù)合理建模，以準(zhǔn)確預(yù)測(cè)用戶在訂閱到期后是否會(huì)流失。一方面，每個(gè)用戶在音樂軟件中通過實(shí)時(shí)點(diǎn)擊會(huì)產(chǎn)生多種多樣的信息，如點(diǎn)擊的音樂入口、讀取的音樂內(nèi)容、在軟件中停留的時(shí)間等，一個(gè)小時(shí)之內(nèi)產(chǎn)生的日志記錄可達(dá)成百上千條。特別地，音樂軟件的受眾較廣，用戶往往數(shù)以億計(jì)，因此日志數(shù)據(jù)中包含的樣本數(shù)量非常龐大，海量化的數(shù)據(jù)不僅對(duì)計(jì)算機(jī)存儲(chǔ)空間等硬件設(shè)備提出了新挑戰(zhàn)，也將帶來較高的計(jì)算成本，進(jìn)一步制約大數(shù)據(jù)處理技術(shù)的時(shí)效性；另一方面，從用戶、產(chǎn)品以及兩者的交互角度出發(fā)，日志數(shù)據(jù)中會(huì)存在大量與用戶偏好相關(guān)的特征變量。同時(shí)，為更加準(zhǔn)確地了解用戶偏好，對(duì)于隱藏在用戶背后無法被探知的信息，如天氣，心情、環(huán)境等因素，需要人為探索、構(gòu)造一些特征來刻畫，最終數(shù)據(jù)的特征維數(shù)會(huì)大大增加。然而在高維情況下，一些經(jīng)典的分類方法如Fisher判別分析等常常會(huì)失效，且計(jì)算效率同樣面臨嚴(yán)峻的挑戰(zhàn)[3]。因此，針對(duì)這種樣本量大、特征維數(shù)高的大規(guī)模數(shù)據(jù)，如何實(shí)現(xiàn)高效分析是研究者亟待解決的問題。

目前，許多學(xué)者針對(duì)算法耗時(shí)長(zhǎng)、計(jì)算效率低的問題提出了相應(yīng)解決方案。針對(duì)樣本量較大的情況，Bickel、Kleiner等在自助法(Bootstrap方法)基礎(chǔ)上分別又提出了m-n自助法、Bootstrap of Little Bag方法(BLB)[4-5]。這兩種方法通過不同方式對(duì)數(shù)據(jù)進(jìn)行抽樣，降低了數(shù)據(jù)量級(jí)，從而在樣本量過高時(shí)實(shí)現(xiàn)了計(jì)算效率的提升。但是上述方法會(huì)在一定程度上降低數(shù)據(jù)的變異性，且BLB方法在應(yīng)用過程中需要同時(shí)優(yōu)化兩個(gè)參數(shù)，即樣本子集的數(shù)量以及每個(gè)樣本子集上重復(fù)抽樣的次數(shù)，利用枚舉法確定參數(shù)也會(huì)大大限制該方法在計(jì)算時(shí)間上的優(yōu)勢(shì)。因此，Sengupta等人在此基礎(chǔ)上將在每個(gè)樣本子集上重復(fù)抽樣的次數(shù)固定為1，提出了Subsample Double Bootstrap(SDB)方法，即在BLB方法的基礎(chǔ)上以犧牲數(shù)據(jù)一些變異性為代價(jià)，進(jìn)一步提高計(jì)算速度[6]。然而，不論是BLB方法還是SDB方法，它們的出發(fā)點(diǎn)均只考慮了數(shù)據(jù)量大的情境，對(duì)特征維度較高時(shí)如何實(shí)現(xiàn)高效分析并沒有進(jìn)行討論，因此并不能完全解決大規(guī)模數(shù)據(jù)的計(jì)算挑戰(zhàn)。同時(shí)，還有一類正則化方法比如通過添加懲罰項(xiàng)LASSO、SCAD等，或者在超高維的情況下事先利用邊際回歸篩選重要變量，在篩選變量的基礎(chǔ)上添加懲罰項(xiàng)實(shí)現(xiàn)降維，以降低計(jì)算復(fù)雜度、提高計(jì)算的可行性。然而，這類方法也僅僅解決了特征維度方面的計(jì)算問題；特別地，當(dāng)變量間具有較強(qiáng)的相關(guān)性時(shí)，不宜利用邊際回歸篩選變量，所以，在這種情況下利用該方法提升計(jì)算效率也不具合理性。除此之外，還有一種解決問題的常見思路是將復(fù)雜任務(wù)分解為多個(gè)子任務(wù)，通過并行計(jì)算節(jié)約運(yùn)行時(shí)間[7]。比如鐘龍申、Luo等分別將并行化計(jì)算方式應(yīng)用在隨機(jī)森林算法以及帶有正則化約束的支持向量機(jī)算法中以提高運(yùn)算效率[8-9]；又如Fang和Ma針對(duì)大規(guī)模數(shù)據(jù)提出了一種自助加罰法(Bootstrap Penalization)，該方法同時(shí)從特征維度、樣本維度出發(fā)，通過將計(jì)算復(fù)雜的加罰任務(wù)拆分成多個(gè)低計(jì)算量的子任務(wù)，使其在多臺(tái)計(jì)算機(jī)上并行計(jì)算，最終通過加權(quán)的方式將不同的子任務(wù)的結(jié)果合并進(jìn)行決策，顯著的減少了運(yùn)算時(shí)間，提高了計(jì)算的可行性[10]。但是，這種方法主要針對(duì)加罰估計(jì)的問題進(jìn)行討論，且實(shí)現(xiàn)過程中涉及多個(gè)調(diào)節(jié)參數(shù)的選取，不同的調(diào)節(jié)參數(shù)可能會(huì)對(duì)估計(jì)結(jié)果產(chǎn)生不同程度的影響。隨機(jī)森林是由Breiman在Bagging 集成學(xué)習(xí)理論基礎(chǔ)上提出的一種通過多棵分類回歸樹進(jìn)行組合預(yù)測(cè)的統(tǒng)計(jì)算法。目前針對(duì)隨機(jī)森林算法的優(yōu)化研究大多還只集中在提升算法精度上，比如如何進(jìn)行特征選擇、參數(shù)優(yōu)化以及處理樣本不平衡等問題。吳瓊等、曹正鳳、汪桂金分別利用NCL(Neighborhood Cleaning Rule)技術(shù)、聚類算法、SMOTE算法等思想對(duì)隨機(jī)森林算法進(jìn)行改進(jìn)以解決樣本不平衡帶來的算法性能下降的挑戰(zhàn)[11-13]。Paul等在隨機(jī)森林算法中借鑒了強(qiáng)化學(xué)習(xí)的思想，提出了增強(qiáng)隨機(jī)森林(Reinforced Random Forest)[14]，馬景義等結(jié)合Adaboost 算法和隨機(jī)森林算法的優(yōu)點(diǎn)提出了擬自適應(yīng)隨機(jī)森林，這兩種新算法在提高分類的準(zhǔn)確性上均取得了不錯(cuò)的效果[15]。Gall 等對(duì)隨機(jī)森林的投票過程進(jìn)行了優(yōu)化改進(jìn)[16]。特別地，針對(duì)面向高維數(shù)據(jù)的隨機(jī)森林算法存在的不足，汪桂金還提出了基于智能算法的隨機(jī)森林特征選擇和參數(shù)優(yōu)化，并通過搭建分布式計(jì)算平臺(tái) Hadoop 對(duì)并行化隨機(jī)森林算法展開研究[13]。然而，這類并行運(yùn)算的方法主要利用了外在計(jì)算平臺(tái)的優(yōu)勢(shì)降低計(jì)算成本。

因此結(jié)合前人研究，為了在盡量保證算法有效性的前提下同時(shí)解決大規(guī)模數(shù)據(jù)樣本量大、特征維度高帶來的計(jì)算問題，本文利用“分治”思想提出了一種分析框架，并以隨機(jī)森林算法為例內(nèi)嵌其中提出大規(guī)模隨機(jī)森林算法(BLOCK-SDB-RF)，以探索機(jī)器學(xué)習(xí)算法在大規(guī)模高維實(shí)際數(shù)據(jù)分析中的作用。

二、方法

(一)基礎(chǔ)算法

隨機(jī)森林是一種以決策樹為基學(xué)習(xí)器的集成算法，通過樣本維度的Bootstrap重抽樣與特征維度的隨機(jī)抽樣制造出更多的隨機(jī)性，以實(shí)現(xiàn)減少預(yù)測(cè)方差的目的。在決策樹的建立過程中，通過測(cè)度輸出變量的異質(zhì)性指標(biāo)找到?jīng)Q策樹節(jié)點(diǎn)的最佳分組變量與最佳分割點(diǎn)。令X表示自變量，Y表示因變量，對(duì)于分類問題，一般采用Gini指數(shù)或信息熵測(cè)度輸出變量的異質(zhì)性，見式(1)、式(2)，其中pk表示樣本屬于第k類的概率，k=1，2，…，|Y|，|Y|表示數(shù)據(jù)集D中包含的類別數(shù)。

(1)

(2)

對(duì)于回歸問題，方差常常被用來測(cè)量輸出變量的異質(zhì)性，見式(3)。

(3)

異質(zhì)性指標(biāo)越高，意味著數(shù)據(jù)的雜亂程度越深。因此，為了使決策樹更好的實(shí)現(xiàn)分類(回歸)，往往通過最大化輸出變量的異質(zhì)性指標(biāo)減少量構(gòu)建決策樹。以分類問題中的Gini指數(shù)為例，需要優(yōu)化的具體模型如式(4)。

(4)

其中，t表示決策樹節(jié)點(diǎn)，Gini(t)和N表示分組前輸出變量的Gini指數(shù)和樣本量，Nr、Gini(tr)、Nl、Gini(tl)分別代表分組后右子樹、左子樹的Gini指數(shù)及樣本量。最佳分組變量與最佳分割點(diǎn)應(yīng)是使ΔGini(t)最大的變量與分割點(diǎn)。

(二)大規(guī)模隨機(jī)森林算法

BLOCK-SDB-RF利用“分治”思想處理大規(guī)模數(shù)據(jù)，算法設(shè)計(jì)主要解決由樣本量大、特征維數(shù)高導(dǎo)致的計(jì)算效率低的問題。通過對(duì)樣本維度與特征維度同時(shí)進(jìn)行處理，BLOCK-SDB-RF方法可以有效減少計(jì)算時(shí)間，提高計(jì)算效率。

顯然地，BLOCK-SDB-RF方法對(duì)特征維度的分組降維解決了隨機(jī)森林算法在特征維數(shù)較高時(shí)帶來的過擬合及信息損失的問題。同時(shí)，以特征的重要性為權(quán)重在每組特征中隨機(jī)抽取一部分(所有組總計(jì)抽取z維特征)作為最終建模的變量，這樣既保證了所有特征變量均有進(jìn)入到模型的可能，又增大了重要特征被抽中的可能性，從而減少算法的信息損失。另一方面，通過對(duì)樣本維度的隨機(jī)分塊，減少了構(gòu)建每棵決策樹所需樣本中不重復(fù)樣本的數(shù)量，有利于降低每棵決策樹的運(yùn)行時(shí)間。即便最終子集的樣本量恢復(fù)到與原數(shù)據(jù)集相同，但考慮到子集中不重復(fù)的樣本數(shù)至多只有s個(gè)，計(jì)算時(shí)只需通過對(duì)樣本加權(quán)即可用較短的時(shí)間得出結(jié)果，并不會(huì)因此增加運(yùn)算成本。算法的整體思路與流程見圖1。

(三)時(shí)間復(fù)雜度及數(shù)據(jù)覆蓋率分析

1.時(shí)間復(fù)雜度分析

算法的時(shí)間復(fù)雜度需要從樣本維度和特征維度兩方面考慮。從樣本維度看，隨機(jī)森林算法需對(duì)原數(shù)據(jù)集進(jìn)行R次Bootstrap抽樣，所得的每一個(gè)子樣本集至多包含n個(gè)不同的樣本，其樣本維度的時(shí)間復(fù)雜度可以表示為(R+1)×t(n)；BLOCK-SDB-RF在b個(gè)大小為s的子樣本集上分別進(jìn)行一次有放回抽樣，所得樣本集最多只包含s個(gè)不同的樣本，相應(yīng)樣本維度的時(shí)間復(fù)雜度可記為2b×t(s)。從特征維度看，由于隨機(jī)森林算法對(duì)每一個(gè)Bootstrap子樣本集都從p維特征中抽取比例為1/2的變量建立一棵決策樹，因此特征維度的時(shí)間復(fù)雜度為(R+1)×t(p)；同理，考慮到BLOCK-SDB-RF方法通過分組降維將變量維數(shù)降低至z，相應(yīng)特征維度的時(shí)間復(fù)雜度為2b×t(z)。因此，BLOCK-SDB-RF的總時(shí)間復(fù)雜度可記為2b×t(sz)，隨機(jī)森林算法的總時(shí)間復(fù)雜度記為(R+1)×t(np)。在單機(jī)運(yùn)算的前提下，運(yùn)算成本的對(duì)比情況會(huì)受到Bootstrap抽樣次數(shù)R和子樣本集數(shù)量b的大小的影響。然而Sengupta等提到，在BLB方法中推薦R取值為100，b根據(jù)情況推薦取值在2到10之間，因此一般來講，BLOCK-SDB-RF方法的時(shí)間成本更加低廉。在并行計(jì)算的前提下，由于s、z相較n、p更小，顯然有t(sz)

輸入：

輸出：分類結(jié)果或回歸結(jié)果。

過程：

1.將χp=(X1，X2，…，Xp)隨機(jī)劃分為c組：

2.從χn中隨機(jī)抽取比例q的樣本構(gòu)成樣本集合χn，q

3.fori1 toc

end

6.forj1 to b

end

7.結(jié)合b棵決策樹的分類結(jié)果或回歸結(jié)果進(jìn)行綜合決策

圖1 BLOCK-SDB-RF算法結(jié)構(gòu)圖

2.數(shù)據(jù)覆蓋率分析

為了在數(shù)據(jù)覆蓋率方面對(duì)BLOCK-SDB-RF方法、RF方法實(shí)現(xiàn)更加公平比較，研究者在給定相同的時(shí)間成本下，分別計(jì)算兩種方法對(duì)數(shù)據(jù)的覆蓋情況。同時(shí)，為了便于比較，提出了兩個(gè)假設(shè)條件：

條件1：不失一般性，假定RF方法Bootstrap抽樣次數(shù)R=1；

條件2：假定時(shí)間復(fù)雜度t(np)、t(sz)滿足條件t(np)≥bt(sz)。

提出條件1的目的是為了限制時(shí)間成本，在給定RF方法Bootstrap抽樣次數(shù)R=1的前提下，相應(yīng)的時(shí)間成本為(R+1)×t(np)。條件2的提出給定了時(shí)間復(fù)雜度t(np)、t(sz)的大小關(guān)系，該條件的成立意味著在一個(gè)樣本量為n、特征維數(shù)為p的數(shù)據(jù)集上建立一棵決策樹的耗時(shí)大于或等于在一個(gè)樣本量為s、特征維數(shù)為z的數(shù)據(jù)集上建立決策樹耗時(shí)的b倍。這也是為了實(shí)現(xiàn)數(shù)據(jù)覆蓋率的對(duì)比而提出的條件，事實(shí)上，兩個(gè)時(shí)間復(fù)雜度的大小未必總是符合線性關(guān)系的條件。從數(shù)據(jù)覆蓋率看，當(dāng)滿足以上兩個(gè)條件時(shí)，在相同的時(shí)間成本下BLOCK-SDB-RF方法能覆蓋到更多的數(shù)據(jù)。事實(shí)上，在隨機(jī)森林算法的實(shí)現(xiàn)過程中，每一次利用Bootstrap抽取子樣本集時(shí)，由于單個(gè)樣本的入樣概率為1/n，重復(fù)抽取n次后，大約有(1-1/n)n的樣本在整個(gè)算法中不會(huì)參與訓(xùn)練模型。當(dāng)n趨于無窮大時(shí)，約有1/e的樣本從未被抽中，即在隨機(jī)森林算法的一次Bootstrap抽樣中，樣本覆蓋率約為1-1/e。同樣地，在BLOCK-SDB-RF中每一個(gè)子集的Bootstrap抽樣大約有s/n×(1-1/s)n的樣本在整個(gè)算法中不會(huì)參與訓(xùn)練模型。當(dāng)數(shù)據(jù)集的樣本量特別高時(shí)，可以認(rèn)為BLOCK-SDB-RF方法的一個(gè)子集樣本Bootstrap抽樣覆蓋率是s/n×[1-(1/e)b]。當(dāng)Bootstrap抽樣次數(shù)R=1時(shí)，RF方法的數(shù)據(jù)覆蓋率約為1-1/e，在相同的時(shí)間成本下利用BLOCK-SDB-RF方法進(jìn)行計(jì)算時(shí)，由于t(np)≥bt(sz)，可以覆蓋到b×{s/n×[1-(1/e)b]}的數(shù)據(jù)，即此時(shí)BLOCK-SDB-RF方法的數(shù)據(jù)覆蓋率為1-(1/e)b，顯然高于隨機(jī)森林算法。

三、數(shù)值模擬

為證明BLOCK-SDB-RF方法在不同類型實(shí)際數(shù)據(jù)中具有良好的應(yīng)用效果，本文以隨機(jī)森林方法(以下記為RF)為參照，分別設(shè)置了不同樣本量、不同特征維數(shù)場(chǎng)景下的模擬分析，同時(shí)考慮到變量間往往并不完全相互獨(dú)立，增加第三種模擬場(chǎng)景以探究在變量間相關(guān)性不同的情況下兩種方法的效果對(duì)比。

在模擬數(shù)據(jù)中，Xn×p從均值為零向量的p元正態(tài)分布中生成，該多元正態(tài)分布的協(xié)方差矩陣為分塊對(duì)角矩陣，如式(5)所示。協(xié)方差矩陣由虛線劃分為4部分，其中設(shè)定第一部分大小為10×10的子矩陣中元素非零，即除前10個(gè)變量間具有系數(shù)為cor的相關(guān)關(guān)系以外，其他變量間均不具有相關(guān)性。Yn×1由線性回歸模型Y=Xβ+ε生成，然后通過Sigmoid變換將其轉(zhuǎn)化為0-1變量。其中，隨機(jī)干擾項(xiàng)ε服從標(biāo)準(zhǔn)正態(tài)分布N(0，1)，自變量系數(shù)β設(shè)為{a，…，a，-a，…，-a，0，…，0}，a與-a的數(shù)量均為10，且a從正態(tài)分布N(3，0.5)中產(chǎn)生。

1…cor0…0??cor?…0cor…10…00…01…00…00…00…00…1

(5)

研究采用以下指標(biāo)以度量BLOCK-SDB-RF方法的應(yīng)用效果。其中TPR為召回率，表示所有正類中，有多少被預(yù)測(cè)成正類(正類預(yù)測(cè)正確)。TNR表示所有反類中，有多少被預(yù)測(cè)成反類(反類預(yù)測(cè)正確)。預(yù)測(cè)正確率Accuracy表示所有樣本中分類正確的比例，指標(biāo)G-mean的含義比TPR、TNR更加綜合，具體定義為：

與預(yù)測(cè)正確率Accuracy的區(qū)別在于當(dāng)正負(fù)樣本存在不平衡時(shí)G-mean的參考價(jià)值較大。四類指標(biāo)均為越高越好。

(一)不同樣本量

在第一個(gè)模擬場(chǎng)景中，設(shè)定特征維數(shù)p=1 000，變量間相關(guān)系數(shù)cor=0.5。分別考慮數(shù)據(jù)樣本量為40 000、60 000、80 000、100 000的情況下，BLOCK-SDB-RF方法和RF方法的應(yīng)用效果，結(jié)果見圖2。圖2中 (a)、(b)、(c)、(d)的橫軸名稱為t，表示計(jì)算耗費(fèi)的時(shí)間，縱軸為指標(biāo)G-mean，用以衡量預(yù)測(cè)結(jié)果的準(zhǔn)確率，該指標(biāo)越大意味著預(yù)測(cè)結(jié)果越準(zhǔn)確；圖2中實(shí)線表示BLOCK-SDB-RF方法，虛線表示RF方法。為便于對(duì)兩種方法進(jìn)行對(duì)比，借鑒Sengupta等的思路考慮在相同的計(jì)算時(shí)間內(nèi)哪種方法能以更快的速度達(dá)到合理準(zhǔn)確的結(jié)果，此處結(jié)合模擬場(chǎng)景將時(shí)間限定為800秒[6]。

由圖2(a)可見，BLOCK-SDB-RF方法的G-mean指標(biāo)在30秒附近急劇增加并很快達(dá)到穩(wěn)定狀態(tài)，較短時(shí)間內(nèi)完成了計(jì)算；而RF方法的G-mean指標(biāo)在近200秒附近才有相似的變化，800秒內(nèi)并沒有完成計(jì)算?？梢娕cRF方法相比，BLOCK-SDB-RF方法的計(jì)算以更快的速度達(dá)到收斂，圖2(b)、(c)、(d)的情況類似。同時(shí)，與圖2(b)、(c)、(d)對(duì)比發(fā)現(xiàn)，隨著數(shù)據(jù)的樣本量不斷增加，BLOCK-SDB-RF與RF兩種方法的G-mean指標(biāo)達(dá)到一定程度的耗時(shí)差距越來越大，表明BLOCK-SDB-RF方法在數(shù)據(jù)的樣本量越大時(shí)計(jì)算速度的優(yōu)勢(shì)越突出。

圖2 不同數(shù)據(jù)量下的方法對(duì)比圖

另一方面，為了進(jìn)一步比較兩種算法的準(zhǔn)確性，給出四種指標(biāo)G-mean、TPR、TNR，預(yù)測(cè)正確率的對(duì)比情況，見表1。其中，TPR、TNR分別表示正、負(fù)樣本中預(yù)測(cè)正確的比例，G-mean、預(yù)測(cè)正確率度量了總體的預(yù)測(cè)準(zhǔn)確率，四類指標(biāo)均為越高越好。由表1見，在不同的樣本數(shù)量下，BLOCK-SDB-RF方法的表現(xiàn)基本上優(yōu)于RF方法。

表1 算法準(zhǔn)確性對(duì)比

(二)不同特征維數(shù)

第二種場(chǎng)景下，設(shè)定數(shù)據(jù)的樣本量n=40 000，變量間相關(guān)系數(shù)cor=0.5。比較RF和BLOCK-SDB-RF兩種方法在特征維數(shù)分別為1 000，2 000，3 000，5 000時(shí)的表現(xiàn)，結(jié)果見圖3?？紤]到變量維數(shù)增加，為了更清晰的展示結(jié)果，將時(shí)間限定為1 600秒。

圖3 不同特征維數(shù)下的方法對(duì)比圖

與第一種模擬場(chǎng)景相同，圖中橫軸為t，表示計(jì)算耗費(fèi)的時(shí)間，縱軸為指標(biāo)G-mean，實(shí)線表示BLOCK-SDB-RF方法，虛線表示RF方法。結(jié)果顯示，在特征維數(shù)為1 000時(shí)，BLOCK-SDB-RF方法的G-mean指標(biāo)50秒左右達(dá)到了穩(wěn)定狀態(tài)，僅在500秒內(nèi)就完成了計(jì)算；而RF方法在200秒附近G-mean 指標(biāo)才有顯著的增長(zhǎng)，具體參見圖3(a)。同時(shí)由圖3(b)、(c)、(d)可見，不論特征維數(shù)高低，BLOCK-SDB-RF方法總是可以在更短時(shí)間完成計(jì)算，并以比RF方法更快的計(jì)算速度使結(jié)果的G-mean指標(biāo)達(dá)到穩(wěn)定。同時(shí)，隨著特征維數(shù)的不斷增加，兩種方法所需的計(jì)算時(shí)間也越長(zhǎng)。特別地，BLOCK-SDB-RF達(dá)到一定預(yù)測(cè)精度的耗時(shí)短于RF方法的程度越來越大，表明BLOCK-SDB-RF在特征維數(shù)不斷增長(zhǎng)時(shí)計(jì)算速度的優(yōu)勢(shì)越來越明顯。

表2 算法準(zhǔn)確性對(duì)比

同樣的，從分類準(zhǔn)確性的角度來看，不論特征維度高低，BLOCK-SDB-RF方法的表現(xiàn)也基本上優(yōu)于RF方法。特別的，隨著特征維度的增加，RF方法的G-mean和預(yù)測(cè)正確率指標(biāo)有逐步下降的趨勢(shì)，而BLOCK-SDB-RF方法的準(zhǔn)確率相對(duì)更加穩(wěn)定。

(三)不同變量相關(guān)性

在實(shí)際中，變量間往往并不是完全相互獨(dú)立的，為探究變量間的不同相關(guān)性對(duì)兩種方法計(jì)算效果的影響，本節(jié)設(shè)定數(shù)據(jù)的樣本量n=40 000，p=1 000，比較在變量間相關(guān)性分別為0.1，0.3，0.6，0.9四種情況下，BLOCK-SDB-RF和RF方法在計(jì)算速度方面的差異。同樣地，為便于對(duì)兩種方法進(jìn)行對(duì)比，此處結(jié)合模擬場(chǎng)景將時(shí)間限定為1 000秒，結(jié)果見圖4。

圖4 不同變量間相關(guān)性的方法對(duì)比圖

表3 算法準(zhǔn)確性對(duì)比

圖4(a)顯示，在變量間相關(guān)系數(shù)為0.1時(shí)，BLOCK-SDB-RF方法的G-mean指標(biāo)在40秒左右快速增長(zhǎng)，200秒左右就完成了運(yùn)算；而RF方法在限定的1 000秒內(nèi)未完成計(jì)算，且在200秒附近G-mean 才開始急劇增加，再一次表明與RF相比，BLOCK-SDB-RF方法具有更高的計(jì)算效率。同時(shí)，由圖4的(b)、(c)、(d)發(fā)現(xiàn)，變量間的不同相關(guān)性并不影響B(tài)LOCK-SDB-RF在計(jì)算速度方面的優(yōu)勢(shì)，BLOCK-SDB-RF始終以明顯較快的速度達(dá)到收斂。然而由表3可見，隨著變量間相關(guān)性的增加，在對(duì)全部特征進(jìn)行分組降維時(shí)受到的干擾也越來越大，因此BLOCK-SDB-RF方法的預(yù)測(cè)準(zhǔn)確率會(huì)有明顯下降，RF方法的分類準(zhǔn)確率也會(huì)受到一定程度的影響。但從總體上講，相比RF方法，BLOCK-SDB-RF的分類準(zhǔn)確率更高。

四、實(shí)證分析

本文的實(shí)證數(shù)據(jù)是由音樂流媒體服務(wù)商KKBOX提供的日志數(shù)據(jù)，來源于2017年Kaggle平臺(tái)舉辦的一場(chǎng)數(shù)據(jù)挖掘競(jìng)賽。該競(jìng)賽向大眾提供了訓(xùn)練集合表、測(cè)試集合表等按時(shí)間順序劃分的日志數(shù)據(jù)與歌曲信息表、用戶信息表、歌曲補(bǔ)充信息表共5個(gè)表格。為便于分析，本文對(duì)該競(jìng)賽提供的5個(gè)表格數(shù)據(jù)進(jìn)行了清洗與整合，并結(jié)合特征工程從用戶、歌曲及兩者交互三個(gè)維度提取不同的特征變量，最終得到樣本量為100 000、特征維數(shù)為1 089的大規(guī)模數(shù)據(jù)集(除去歌曲id、用戶id及因變量“是否重復(fù)聽歌”三個(gè)變量)。數(shù)據(jù)集的整體結(jié)構(gòu)如圖5所示，部分變量及含義見表4。

圖5 特征維度示意圖

表4 數(shù)據(jù)特征示例(部分)

文章以“用戶重復(fù)聽歌”事件作為準(zhǔn)則判斷用戶對(duì)歌曲是否喜愛，即如果用戶在第一次點(diǎn)擊某首歌曲之后的一個(gè)月里觸發(fā)“重復(fù)聽歌”事件，則認(rèn)為用戶喜愛該歌曲，將因變量記為1，否則記為0。考慮到數(shù)據(jù)集樣本量大，特征維數(shù)高，本文利用BLOCK-SDB-RF方法在訓(xùn)練集上建模，并在測(cè)試集上對(duì)用戶是否會(huì)重復(fù)聽歌進(jìn)行預(yù)測(cè)，以期更好地了解用戶的聽歌偏好。

(一)初步探索

在建模之前，對(duì)用戶、歌曲及兩者交互三個(gè)維度下變量間的相關(guān)關(guān)系進(jìn)行初步探索?？紤]到變量間的關(guān)系并不能由簡(jiǎn)單的線性相關(guān)進(jìn)行刻畫，文中采用了秩相關(guān)系數(shù)，部分變量間的相關(guān)關(guān)系如圖6所示。圖6中帶斜線陰影部分表示負(fù)相關(guān)，未帶斜線陰影部分代表正相關(guān)，顏色的深淺表示變量間相關(guān)關(guān)系的強(qiáng)弱，顏色越深，意味著相關(guān)關(guān)系越強(qiáng)。

結(jié)果顯示，用戶點(diǎn)擊的來源信息(X26，X25)即用戶通過點(diǎn)擊電臺(tái)、專輯或者其他方式進(jìn)入該歌播放的比例、用戶最后聽歌時(shí)間(X91)、歌曲流行程度(X23)對(duì)因變量Y是否重復(fù)聽歌的影響比較顯著。歌曲-用戶交互維度中，特定用戶對(duì)歌手(X29)、作曲家(X30)、作詞人(X31)的喜好也對(duì)Y有影響，但是相關(guān)性較之用戶維度、歌曲維度的變量更弱。另一方面，不同特征間也具有一定程度的相關(guān)關(guān)系，比如X20用戶對(duì)發(fā)行年份的偏好、X21某歌曲計(jì)數(shù)、X22某用戶計(jì)數(shù)三個(gè)特征間具有較強(qiáng)的正相關(guān)關(guān)系等。但是考慮到在數(shù)值模擬部分發(fā)現(xiàn)，特征變量間的相關(guān)性并不會(huì)影響B(tài)LOCK-SDB-RF方法在計(jì)算時(shí)間方面的優(yōu)勢(shì)，因此仍然可以使用該方法對(duì)數(shù)據(jù)進(jìn)行建模、預(yù)測(cè)。

圖6 部分變量間的秩相關(guān)圖

(二)實(shí)證結(jié)果

將清洗后的數(shù)據(jù)集按照3∶1劃分為訓(xùn)練集與測(cè)試集。在訓(xùn)練集上分別利用RF、BLOCK-SDB-RF兩種方法建立模型，然后在相應(yīng)測(cè)試集上進(jìn)行預(yù)測(cè)，得到實(shí)證結(jié)果如下。

1.相同時(shí)間內(nèi)計(jì)算結(jié)果對(duì)比

為節(jié)約時(shí)間成本并方便結(jié)果對(duì)比，同樣借鑒Sengupta等的思路，考慮在1 000秒時(shí)間內(nèi)哪種方法能以更快的速度達(dá)到合理準(zhǔn)確的結(jié)果，最終結(jié)果如圖7所示[6]。圖7中橫軸為time，表示計(jì)算消耗的時(shí)間；縱軸為指標(biāo)G-mean，實(shí)線表示BLOCK-SDB-RF方法，虛線表示RF方法。結(jié)果顯示，RF方法在測(cè)試集預(yù)測(cè)結(jié)果的G-mean指標(biāo)于700秒附近開始急劇增加并達(dá)到一定高度，而BLOCK-SDB-RF方法在400秒附近就發(fā)生了類似變化，表明BLOCK-SDB-RF方法在計(jì)算時(shí)間方面具有一定優(yōu)勢(shì)。

圖7 實(shí)證數(shù)據(jù)結(jié)果對(duì)比圖

2.不限制計(jì)算時(shí)間的結(jié)果對(duì)比

當(dāng)不限制計(jì)算時(shí)間時(shí)，分別使用RF、BLOCK-SDB-RF方法對(duì)測(cè)試集做出預(yù)測(cè)，其中RF方法共建立200棵決策樹，得到預(yù)測(cè)結(jié)果見表5。結(jié)果顯示，BLOCK-SDB-RF方法預(yù)測(cè)的總體準(zhǔn)確率為75.9%，G-mean為59.5%，與RF方法得到的計(jì)算結(jié)果基本一致。但是從計(jì)算時(shí)間角度看，BLOCK-SDB-RF方法共消耗計(jì)算時(shí)間13.53分鐘，與RF方法建立200棵決策樹需要耗費(fèi)的20.19小時(shí)相比，大大降低了計(jì)算成本。特別是在更加大型的推薦系統(tǒng)中該方法的優(yōu)勢(shì)將更加明顯。

表5 預(yù)測(cè)結(jié)果

3.變量重要性分析

在BLOCK-SDB-RF實(shí)施過程中，將分組考察各個(gè)特征變量對(duì)分類結(jié)果的貢獻(xiàn)，并以此作為該特征變量的重要性度量。表6為重要性排名前10的特征變量及其與因變量Y的秩相關(guān)系數(shù)。

由表6可見，BLOCK-SDB-RF方法下重要性排名前10位的特征變量，比如X23某歌曲計(jì)數(shù)(即歌曲的流行程度)、X25某用戶不同界面來源比例、X26某用戶app上音樂入口比例等，與因變量Y的秩相關(guān)系數(shù)也較高，分別為0.184，0.060，0.134。這與建模之前初步探索得出的結(jié)果大體一致，即與因變量Y越相關(guān)的變量越能解釋Y中包含的信息。相比而言，用戶、歌曲維度下的變量比兩者交互維度的變量更重要。

表6 變量重要性排名與秩相關(guān)系數(shù)

五、討論

本文以隨機(jī)森林算法為基礎(chǔ)，結(jié)合“分治”思想提出了大規(guī)模隨機(jī)森林算法，對(duì)樣本量大、特征維度高的數(shù)據(jù)集進(jìn)行分析。在盡量保證算法有效性的前提下，解決了大規(guī)模數(shù)據(jù)帶來的計(jì)算效率問題。通過數(shù)值模擬與實(shí)證分析表明，隨著數(shù)據(jù)量、特征維度的增加，該方法在計(jì)算時(shí)間上的優(yōu)勢(shì)愈發(fā)明顯，同時(shí)變量間的相關(guān)性對(duì)該方法在計(jì)算效率方面的優(yōu)勢(shì)影響并不顯著。然而，在應(yīng)用方面BLOCK-SDB-RF方法仍然存在一些問題有待進(jìn)一步探討。

第一，本文以隨機(jī)森林為基礎(chǔ)算法，通過同時(shí)對(duì)樣本維度和特征維度進(jìn)行處理，將其內(nèi)嵌到本文提出的分析框架中以應(yīng)對(duì)大規(guī)模數(shù)據(jù)帶來的計(jì)算效率的挑戰(zhàn)。事實(shí)上，本文提出的大規(guī)模數(shù)據(jù)分析框架并不局限于隨機(jī)森林算法，其他常用的機(jī)器學(xué)習(xí)算法比如支持向量機(jī)(SVM)等均可以嵌進(jìn)其中。

第二，KKBOX提供的日志數(shù)據(jù)實(shí)際上是一個(gè)不平衡數(shù)據(jù)，其中包含的正樣本(因變量為“重復(fù)聽歌”的樣本)數(shù)量遠(yuǎn)遠(yuǎn)大于負(fù)樣本(因變量為“未重復(fù)聽歌”的樣本)，并且文中并沒有針對(duì)這種情況做出處理，因此在實(shí)證分析部分得到的預(yù)測(cè)結(jié)果會(huì)出現(xiàn)真陽性率較高，真陰性率較低的情況。事實(shí)上，這種不平衡數(shù)據(jù)集在實(shí)際生活中非常普遍，比如貸款違約預(yù)測(cè)的數(shù)據(jù)、醫(yī)療數(shù)據(jù)等，針對(duì)這種數(shù)據(jù)在因變量上分布不平衡的問題，可以考慮通過數(shù)據(jù)層面或者算法層面的調(diào)整解決[17-18]，比如在數(shù)據(jù)層面上利用過采樣、欠采樣將不平衡數(shù)據(jù)調(diào)整為平衡數(shù)據(jù)，或者類似調(diào)整的支持向量機(jī)算法等直接對(duì)算法進(jìn)行修正以適應(yīng)不平衡數(shù)據(jù)。

第三，變量間的相關(guān)性雖然并不影響B(tài)LOCK-SDB-RF方法在計(jì)算時(shí)間方面的優(yōu)勢(shì)，但隨著相關(guān)性的增加，預(yù)測(cè)結(jié)果的準(zhǔn)確率會(huì)因此有所下降。即該方法在提升計(jì)算效率的同時(shí)，有時(shí)會(huì)以犧牲預(yù)測(cè)精度為代價(jià)。特別地，在實(shí)際數(shù)據(jù)中，變量間具有一定程度的相關(guān)性總是不可避免的。這一方面要求我們?cè)陬A(yù)測(cè)的準(zhǔn)確率和計(jì)算效率上做出權(quán)衡，另一方面也需要考慮當(dāng)變量間具有較強(qiáng)的相關(guān)性時(shí)，如何減輕變量選擇結(jié)果受到的干擾，為未來研究指明方向。