基于聚類的多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)算法

鄒 磊，朱 晶，聶曉輝，蘇 亞，裴 丹，孫 宇

1(清華大學(xué) 計算機(jī)系，北京 100084) 2(北京小桔科技(滴滴出行)有限公司，北京 100193)

1 引 言

隨著大數(shù)據(jù)概念的普及，人們逐漸認(rèn)識到了海量數(shù)據(jù)中存在的巨大價值.各種針對大數(shù)據(jù)的數(shù)據(jù)挖掘研究和成果也如雨后春筍般涌現(xiàn)，熱點(diǎn)發(fā)現(xiàn)就是被廣泛研究的數(shù)據(jù)挖掘問題之一[1-3，18，19].熱點(diǎn)發(fā)現(xiàn)有助于快速地初步了解整體數(shù)據(jù)的特點(diǎn)，并為后續(xù)的分析工作提供方向與決策基礎(chǔ).通過熱點(diǎn)發(fā)現(xiàn)能夠從網(wǎng)民產(chǎn)生的海量文本內(nèi)容中挖掘出當(dāng)前網(wǎng)民討論的熱點(diǎn)話題，例如反腐，某明星結(jié)婚等，以及這些話題的熱度[3].通過熱點(diǎn)發(fā)現(xiàn)還能夠快速發(fā)現(xiàn)用戶數(shù)據(jù)的明顯特征，例如用戶通常在白天使用某項服務(wù)，以及大部分用戶都使用蘋果手機(jī)等.本文針對多維數(shù)據(jù)的熱點(diǎn)發(fā)現(xiàn)進(jìn)行研究.

多維數(shù)據(jù)通常包含多個與目標(biāo)事件相關(guān)的特征，這些特征可以是用戶的手機(jī)品牌、使用的服務(wù)類型、事件發(fā)生的時間、用戶的地理位置、用戶的網(wǎng)絡(luò)延遲、軟件版本、服務(wù)器負(fù)載、用戶年齡等，每次目標(biāo)事件發(fā)生都對應(yīng)一條多維數(shù)據(jù).例如圖 1所示，該多維數(shù)據(jù)包含5個特征，并且展示了7條數(shù)據(jù)作為示例.特征可以根據(jù)其取值特點(diǎn)分成數(shù)值型特征和類別型特征.數(shù)值型特征的取值是存在一維歐式距離關(guān)系的數(shù)值，例如圖 1中的網(wǎng)絡(luò)延遲和時間.類別型特征的取值被分成多個類別，例如圖 1中的手機(jī)品牌，網(wǎng)絡(luò)類型，所在城市.

圖1 多維數(shù)據(jù)示例
Fig.1 Example of multi-dimensional and multi-class data

如果把多維數(shù)據(jù)的每一個特征都看作一個維度，那么多維數(shù)據(jù)就是分布于由各個特征的取值范圍構(gòu)成的特征空間中的數(shù)據(jù).例如圖 2所示，在由時間、網(wǎng)絡(luò)延遲和所在城市三個特征構(gòu)成的特征空間中，每個黑色方格都是一條數(shù)據(jù)，白色方格表示該處沒有數(shù)據(jù).多維數(shù)據(jù)的熱點(diǎn)發(fā)現(xiàn)希望能夠找出圖中數(shù)據(jù)集中的兩個熱點(diǎn)區(qū)域(圖中的虛線處)，并以特征取值組合[17]{時間∈[18，24]，所在城市∈[北京，深圳，上海]，網(wǎng)絡(luò)延遲<30ms}和{時間∈[6，9]}將這兩個熱點(diǎn)區(qū)域的信息呈現(xiàn)給數(shù)據(jù)分析人員，特征取值組合通過限定一個或者多個特征的取值范圍來表示數(shù)據(jù)的取值范圍.實(shí)際的特征空間通常會超過三維，但是受限于圖片的表達(dá)能力，在這里僅以三維特征空間作為例子.這些熱點(diǎn)信息有助于進(jìn)行定向推薦、優(yōu)惠卷精準(zhǔn)發(fā)放、針對性優(yōu)化產(chǎn)品性能、以及廣告定向投放等.

圖2 多維數(shù)據(jù)聚集區(qū)域示例Fig.2 Example of data area with high density

近年來，有非常多的熱點(diǎn)分析研究成果發(fā)表.[1]利用MapReduce加速K-means的計算，設(shè)計了ASQHTD算法，用于從航空領(lǐng)域的大量文檔中發(fā)掘航空公司服務(wù)品質(zhì)熱點(diǎn).該文首先對文本進(jìn)行特征提取，提取出僅含有數(shù)值型特征的高維文本向量，然后用ASQHTD作用于這些文本向量找到航空品質(zhì)熱點(diǎn).[2]基于MFIHC聚類和TOPSIS針對短小的微博數(shù)據(jù)設(shè)計了實(shí)時熱點(diǎn)發(fā)現(xiàn)算法，該文在對文本特征進(jìn)行聚類時引入了知網(wǎng)的主義庫進(jìn)行語義的相似度計算.[3]基于LDA設(shè)計了OLDA模型，用于對網(wǎng)民的評論進(jìn)行熱點(diǎn)發(fā)現(xiàn).但是這些算法或者是基于相關(guān)的領(lǐng)域?qū)I(yè)知識對原始數(shù)據(jù)進(jìn)行特征提取之后得到只含有一種類型特征的多維數(shù)據(jù)(即只有數(shù)值型特征或者只有類別型特征)[1]，或者根據(jù)相關(guān)的領(lǐng)域?qū)I(yè)知識為數(shù)據(jù)設(shè)計距離或者相似度計算方法[2]，這些算法都無法直接用于解決多維數(shù)據(jù)的熱點(diǎn)發(fā)現(xiàn)問題.

通常熱點(diǎn)發(fā)現(xiàn)問題都通過聚類方法解決[1-3]，本文也使用聚類方法來解決多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)問題.根據(jù)多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)的需求，本文選擇了聚類算法CLTree[4]作為基線算法.CLTree通過往目標(biāo)數(shù)據(jù)中均勻地填充一類虛擬數(shù)據(jù)來構(gòu)造雙類別數(shù)據(jù)，再用決策樹對數(shù)據(jù)進(jìn)行分類，分類完成后將虛擬數(shù)據(jù)移除，分類結(jié)果就成了聚類結(jié)果.

本文對CLTree[4]進(jìn)行如下重要改進(jìn)，設(shè)計了CLTree+來解決數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)問題：

1)增加了對類別型特征聚類支持.CLTree在對類別型特征進(jìn)行聚類時，必須先根據(jù)一定的規(guī)則將類別型數(shù)據(jù)轉(zhuǎn)換成數(shù)值型數(shù)據(jù)，而CLTree+可以直接處理類別型特征，提升了聚類效果和算法的適用性.

2)提升了對存在周期性特性的數(shù)值型特征進(jìn)行聚類的效果.存在周期性特性的數(shù)值型特征包括幾點(diǎn)，周幾等.CLTree+根據(jù)特征的周期性提出了新的聚類方法，相比于CLTree直接將存在周期性的特征當(dāng)成數(shù)值型特征處理，CLTree+可以得到更好的聚類效果.下文中用周期型特征指代含有周期性特性的數(shù)值型特征，數(shù)值型特征均指代不含有周期性特性的數(shù)值型特征.

3)CLTree+對計算速度進(jìn)行了優(yōu)化.CLTree會先將數(shù)據(jù)分裂成盡可能小的子集，再對這些子集進(jìn)行聚類，當(dāng)數(shù)據(jù)量非常大時，這種方法的計算時間開銷非常大.CLTree+引入了剪枝策略，使數(shù)據(jù)分裂到符合要求即停止，使計算效率提升了O(n)倍.

CLTree+被應(yīng)用于某大型互聯(lián)網(wǎng)公司的業(yè)務(wù)數(shù)據(jù)，得到了很好的效果，成功地找出了若干符合專家經(jīng)驗(yàn)的數(shù)據(jù)熱點(diǎn).

2 研究目標(biāo)

熱點(diǎn)定義：熱點(diǎn)是指特征空間中的數(shù)據(jù)區(qū)域Area，其數(shù)據(jù)密度D>=Dthr，并且數(shù)據(jù)量Q>=Qthr.Dthr和Qthr為常數(shù)閾值，其取值根據(jù)具體應(yīng)用由專家根據(jù)相關(guān)領(lǐng)域的專業(yè)知識選取.

熱點(diǎn)的表示：熱點(diǎn)用特征取值組合表示.周期型特征的取值范圍采用[16]中的表示方式，表示為[a，b)、[a，b]、(a，b)或者(a，b]，其中以[a，b)為例說明其含義，用P表示該特征的周期，0≤a，b

(1)

數(shù)據(jù)密度定義：用于描述特征取值組合的數(shù)據(jù)集中程度的數(shù)據(jù)密度D的計算方式為

(2)

其中#data為該特征取值組合覆蓋的數(shù)據(jù)數(shù)量；Li為該特征取值組合所確定的區(qū)域中特征i的長度.

連續(xù)數(shù)值型特征取值范圍可表示為(a,b]、[a,b]、(a,b)、[a,b)離散數(shù)值型特征取值范圍表示為，其長度為

L=b-a

(3)

連續(xù)周期型特征取值范圍可表示為(a,b]、[a,b]、(a,b)、[a,b)，離散周期型特征取值范圍表示為[a,b)，P為該特征的周期，其長度為

(4)

取值范圍為集合{v1，v2，…,vn}的類別型特征的長度為

L=mod({v1,v2,…,vn})

(5)

如果某個特征沒有出現(xiàn)在特征取值組合中，這意味著對這個特征沒有限制，那么該特征的取值范圍為整體數(shù)據(jù)中該特征的取值范圍，在計算該特征取值組合的數(shù)據(jù)密度時也需要除以該特征的長度.例如，對于圖 1中的數(shù)據(jù)，特征取值組合{時間∈[20點(diǎn)，4點(diǎn))，網(wǎng)絡(luò)類型=4G，所在城市≠北京}的各個特征的長度分別如表 1所示，周期型特征時間的取值范圍為20點(diǎn)至4點(diǎn)，4點(diǎn)先加上一個周期24小時再減去20點(diǎn)得到長度為8；手機(jī)品牌的取值范圍沒有限制，該特征所有可能的不同取值有3種；網(wǎng)絡(luò)類型限定為4G，該特征長度為1；網(wǎng)絡(luò)延遲的取值范圍也沒有限制，該特征長度為其最大取值103ms減去8ms.不同的特征其長度的物理意義不同.

對于同一份數(shù)據(jù)集的不同特征取值組合，可以用它們的數(shù)據(jù)密度來對比不同特征取值組合下的相對數(shù)據(jù)疏密程度.但是數(shù)據(jù)密度無法用于對比不同數(shù)據(jù)集下的特征取值組合的數(shù)據(jù)疏密程度，因?yàn)椴煌臄?shù)據(jù)集的特征集不同，其特征長度的物理意義不同.

表1 特征長度計算方法示例Table 1 Example of calculating feature′s length

本文針對多維數(shù)據(jù)進(jìn)行熱點(diǎn)發(fā)現(xiàn)的具體目標(biāo)是要找出一些滿足以下條件的特征取值組合：

1)特征取值組合的數(shù)量越少越好.根據(jù)奧卡姆剃刀原則[14]，特征取值組合的數(shù)量越少，數(shù)據(jù)分析人員越易于理解.

2)每個特征取值組合下的數(shù)據(jù)都比較密集.特征取值組合的數(shù)據(jù)密集程度通過數(shù)據(jù)密度與整體數(shù)據(jù)的數(shù)據(jù)密度的比值來評價.

3)每個特征取值組合包含的數(shù)據(jù)量都較大.特征取值組合表現(xiàn)出的數(shù)據(jù)特點(diǎn)的顯著程度與數(shù)據(jù)量呈正相關(guān)，如果數(shù)據(jù)量太少，那么這個特征取值組合表現(xiàn)出的特點(diǎn)不顯著，因此并不是熱點(diǎn).

4)各個特征取值組合之間必須沒有數(shù)據(jù)重疊，例如{服務(wù)類型=快車&&用戶設(shè)備=蘋果}與{用戶設(shè)備=蘋果}這兩個特征取值組合中間就存在數(shù)據(jù)的重疊，它們都包含了滿足條件{服務(wù)類型=快車&&用戶設(shè)備=蘋果}的數(shù)據(jù).找出的這些特征取值組合是呈現(xiàn)給數(shù)據(jù)分析人員進(jìn)行后續(xù)的人工分析的，各個特征取值組合之間沒有重疊可以使這些特征取值組合的意義更加直觀.

然而前三個訴求其實(shí)是矛盾的，為了覆蓋盡可能多的數(shù)據(jù)通常會導(dǎo)致特征取值組合的平均數(shù)據(jù)密度的下降，最極端的例子就是整體數(shù)據(jù)構(gòu)成一個特征取值組合時，雖然數(shù)據(jù)覆蓋量為100%，但是只要數(shù)據(jù)不是均勻分布地，就肯定能找到數(shù)據(jù)密度更高的特征取值組合.特征取值組合數(shù)量越少與它們的的平均數(shù)據(jù)密度越大這兩個訴求也是相悖的，因?yàn)橹灰粋€熱點(diǎn)內(nèi)的數(shù)據(jù)不是平均分布的，就總是能夠在其中找到數(shù)據(jù)密度更大的特征取值組合.不同數(shù)據(jù)對這三個訴求的側(cè)重點(diǎn)也不同，因此很難對熱點(diǎn)發(fā)現(xiàn)的結(jié)果設(shè)定一個最優(yōu)的評價標(biāo)準(zhǔn).數(shù)據(jù)分析人員需要根據(jù)自己的實(shí)際需要，通過調(diào)整算法的輸入?yún)?shù)葉結(jié)點(diǎn)最小數(shù)據(jù)量和最小信息熵增益來權(quán)衡這三個訴求.

3 多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)算法介紹

3.1 基本思想

本文使用聚類方法來解決多維數(shù)據(jù)的熱點(diǎn)發(fā)現(xiàn)問題.例如圖 3中的二維數(shù)據(jù)所示，其中的黑色點(diǎn)就是業(yè)務(wù)數(shù)據(jù)，數(shù)據(jù)集中分布在兩片區(qū)域A和B中，區(qū)域C的數(shù)據(jù)則非常的稀疏.根據(jù)前面提到的需求，理想的情況是能夠找出表示A和B兩個區(qū)域的特征取值組合.為了實(shí)現(xiàn)這個目標(biāo)，首先對數(shù)據(jù)進(jìn)行聚類，在數(shù)據(jù)被聚成A，B和C三個類之后，再用剛好能夠覆蓋類中所有數(shù)據(jù)的特征取值的組合來界定每個類的邊界.描述類A和類B邊界的特征取值組合就是多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)希望找到的結(jié)果.

3.2 聚類算法選擇

聚類問題是一個已經(jīng)被研究了非常久的基礎(chǔ)機(jī)器學(xué)習(xí)問題，有非常多的聚類算法已經(jīng)被設(shè)計出來并成功地運(yùn)用到不同的場景[5-12].但是多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)問題對聚類算法的要求非常多，首先數(shù)據(jù)分析人員可能并不知道數(shù)據(jù)應(yīng)該被聚成多少類，其次聚類結(jié)果的邊界越整齊越好，從而能夠輕易地表示為特征取值的組合，除此之外，多維數(shù)據(jù)中既有類別型特征，又有數(shù)值型特征，聚類算法需要能夠處理這兩類特征.而各個聚類算法都有自己的應(yīng)用限制，很少有聚類算法能夠完美地滿足上述所有要求.例如常用的K-means算法需要輸入聚類數(shù)作為參數(shù)，同時K-means聚類得到的不同類之間的邊界通常是不規(guī)則的，并且為了用特征取值組合描述類，同時各個特征取值組合之間沒有重疊，需要對聚類的結(jié)果進(jìn)行復(fù)雜的調(diào)整.因此在選擇聚類算法時還需要對所有聚類算法進(jìn)行仔細(xì)挑選.根據(jù)多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)的需求和各種聚類算法的優(yōu)缺點(diǎn)，CLTree最終被選擇作為解決多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)的基線算法.

圖3 熱點(diǎn)發(fā)現(xiàn)算法基本思路示意圖Fig.3 Basic idea of hotspot detection alogrithm

CLTree的聚類結(jié)果的邊界整齊，可以直接用特征的取值組合進(jìn)行表示，并且不需要預(yù)先輸入需要將數(shù)據(jù)分成多少類，CLTree會根據(jù)數(shù)據(jù)的特點(diǎn)決定聚類結(jié)果中類的數(shù)目，因此本文選擇CLTree作為基線算法.但是CLTree僅支持處理數(shù)值型特征、處理具有周期性的數(shù)值型特征效果不好，并且計算效率低.本文創(chuàng)新設(shè)計的CLTree+算法有效解決了CLTree的上述缺點(diǎn).

圖4 多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)算法流程圖Fig.4 Flowchart of multi-dimen-sional data hotspot detection algorithm

3.3 算法流程

算法的基本流程如圖 4所示.

3.4 數(shù)據(jù)邊界確定

在使用CLTree+為數(shù)據(jù)進(jìn)行聚類以及計算數(shù)據(jù)密度時都需要確定整體數(shù)據(jù)的取值范圍.數(shù)值型特征的取值范圍為其取值的最小值與最大值之間的范圍，即[vmin，vmax].周期型特征的取值范圍為一個周期P的范圍，即[0,P).類別型特征的取值范圍為整體數(shù)據(jù)的取值集合{v1，v2，…，vn}.

3.5 CLTree+

CLTree+相對于CLTree進(jìn)行了如下三點(diǎn)改進(jìn).

3.5.1 通過剪枝提升算法的計算效率

CLTree首先將數(shù)據(jù)分裂成盡可能小的子集，直到每個子集中只包含最多兩條數(shù)據(jù)或者該子集中的所有數(shù)據(jù)都相同為止，然后再根據(jù)算法的兩個輸入?yún)?shù)類最小數(shù)據(jù)量和相鄰類最小相對密度差將相鄰的子集進(jìn)行合并.這種將數(shù)據(jù)先分裂成更小子集再合并子集的方法實(shí)際上是多此一舉，并且在實(shí)際使用過程中這種作法的時間開銷太大，當(dāng)數(shù)據(jù)量非常大的時候，這種開銷用戶是無法承受的.同時這種方法會導(dǎo)致原本還可以進(jìn)一步分裂的子集最終被劃分成一個類，因?yàn)镃LTree分裂數(shù)據(jù)的邏輯是在滿足最大信息增益的前提下看該次分裂成的子集是否滿足類最小數(shù)據(jù)量.假如子集A根據(jù)CLTree算法的最佳分裂規(guī)則會被分裂成B和C兩個子集，但是子集B中的數(shù)據(jù)量小于類最小數(shù)據(jù)量，那么在CLTree最終的合并過程中B和C又會被合并成A，A將作為最終聚類結(jié)果的一個類.但是實(shí)際上A還可能被分裂成D和E子集，D和E的數(shù)據(jù)量都大于類最小數(shù)據(jù)量，只是A分裂成D和E的信息增益要小于A分裂成B和C.CLTree+在數(shù)據(jù)分裂時會首先根據(jù)類最小數(shù)據(jù)量篩選候選分裂點(diǎn)，再根據(jù)最大信息增益在這些候選分裂點(diǎn)中選擇最佳的分裂點(diǎn)，如果最佳的分裂點(diǎn)得到的信息增益小于最小信息增益，則該子數(shù)據(jù)集停止分裂.本文根據(jù)該規(guī)則修改CLTree為數(shù)值型特征尋找最佳分裂點(diǎn)的evaluateCut(D)算法[4]為evaluateCutPlus(D)算法，并用evalueateCutPlus(D)算法來為數(shù)值型特征選擇該特征上的最佳分裂點(diǎn).

3.5.2 類別型特征上的最佳分裂點(diǎn)選擇

對于類別型特征，選擇one-against-others[15]二分裂形成候選分裂點(diǎn)，而不選擇窮舉二分裂方式[14]形成分裂候選點(diǎn).這么做是出于兩個方面的考慮，第一點(diǎn)是為了加快決策樹的計算速度.對于一個含有n種不同取值的離散型特征，所有可能的二分裂方式有2^n種，而one-against-others二分裂只有n種分裂方式.第二點(diǎn)是為了使分裂結(jié)果更易于為人所直觀的理解.在類別型特征的維度上，取值不同的數(shù)據(jù)之間并沒有固有的距離關(guān)系，因此僅能確定特征取值相同的數(shù)據(jù)應(yīng)該被聚為一類，不存在像數(shù)值型特征那樣的分裂邊界插入數(shù)據(jù)聚集區(qū)域[4]的情況.對于類別型特征直接根據(jù)信息熵增益選擇最佳分裂點(diǎn).該算法如下：

算法1.類別型特征最佳分裂點(diǎn)選取

輸入：待聚類的數(shù)據(jù)集data，待選取最佳分裂點(diǎn)的特征F，葉結(jié)點(diǎn)最小數(shù)據(jù)量minlen，最小信息增益minentro

輸出：特征F上的最佳分裂點(diǎn)split

1)根據(jù)F的取值對數(shù)據(jù)進(jìn)行去重得到F的無重復(fù)取值集合{vi，i=1，2，…，n}

2)split = None

3)for viin {v1，v2，…，vn}：

4) spliti= 將data分裂成datal和datar的分裂點(diǎn)

5) datal={vjif vj==vifor vjin data}

6) datar={vjif vj!=vifor vjin data}

7) if len(data1)

8) continue

9) split=(split與spliti中信息熵增益更大的一個)

10)返回split

3.5.3 周期型特征上的最佳分裂點(diǎn)選擇

對于周期型特征，不能簡單地將其當(dāng)成數(shù)值型特征進(jìn)行處理.雖然數(shù)據(jù)之間也天然存在著歐式距離的關(guān)系，但是由于該特征的周期性，在計算兩個取值不同的數(shù)據(jù)點(diǎn)在該維度上的距離時有兩種不同的計算方式，以一天的24小時舉個例子，在沒有確定日期的情況下，1點(diǎn)和2點(diǎn)之間可以說隔了1個小時，也可以說是隔了23個小時，因?yàn)榻裉斓?點(diǎn)與明天的1點(diǎn)之間隔了23個小時.如果把周期型數(shù)據(jù)的取值范圍看做一個圓，那么在圓上只找一個切分點(diǎn)是無法將圓分成兩段的，需要兩個切分點(diǎn)才行.[16]在使用決策樹處理周期型特征時，選取兩個切分點(diǎn)將周期型數(shù)據(jù)分成兩段，從而構(gòu)成一個分裂候選點(diǎn).然而CLTree+不能直接根據(jù)信息熵增益從這種方法生成的分裂候選點(diǎn)中選擇最佳分裂點(diǎn)，因?yàn)闀嬖诜至腰c(diǎn)插入聚類中間的情況.處理周期型特征時，首先假設(shè)周期型數(shù)據(jù)的取值都在0至周期P的范圍內(nèi)，如果數(shù)據(jù)的取值不在0至P的范圍內(nèi)，那么其取值可以通過加減P的整數(shù)倍映射到該范圍內(nèi)，周期型數(shù)據(jù)加減周期的整數(shù)倍其取值都是等價的.CLTree+每次在該取值范圍內(nèi)選取一個數(shù)值vi作為數(shù)據(jù)的最小邊界，其它的數(shù)據(jù)的取值v按如下規(guī)則進(jìn)行映射之后得到數(shù)據(jù)集Di.

(6)

然后再用evaluateCutPlus(D)為該特征尋找一個最佳分裂點(diǎn).CLTree+會依次遍歷該特征在0-P上的所有取值作為數(shù)據(jù)的最小邊界分別尋找一個最佳分裂點(diǎn)，這些最佳分裂點(diǎn)中信息熵增益最大的分裂點(diǎn)即為該特征上的最佳分裂點(diǎn).

算法2.周期型特征最佳分裂點(diǎn)選取

輸入：待聚類的數(shù)據(jù)集data，待選取最佳分裂點(diǎn)的特征F，特征F的周期P，葉結(jié)點(diǎn)最小數(shù)據(jù)量minlen，最小信息增益minentro

輸出：特征F上的最佳分裂點(diǎn)

1)將特征F的數(shù)值映射到一個周期的范圍內(nèi)，并根據(jù)特征F的數(shù)值對數(shù)據(jù)進(jìn)行排序以及去重得到無重復(fù)的升序序列{vi，i=1，2，…，n}

2)split=None

3)for viin {v1，v2，…，vn}：

4) datai={vjif vj>=vielse vj+P for vjin data}

5) spliti=evaluateCutPlus(datai)

6) split=(split與spliti中信息熵增益更大的一個)

7)返回split

如果數(shù)據(jù)集最終在所有特征中選擇某一個周期型特征的最佳分裂點(diǎn)作為整個數(shù)據(jù)集的最佳分裂點(diǎn)進(jìn)行分裂，且該分裂點(diǎn)是將數(shù)據(jù)映射成Di后得到的，那么在切分得到的子數(shù)據(jù)集中，數(shù)據(jù)會一直保持映射成Di，無需再重新進(jìn)行映射.

3.6 數(shù)據(jù)熱點(diǎn)獲取

CLTree+是沿著數(shù)據(jù)的整齊邊界分裂數(shù)據(jù)的，因此CLTree+的聚類結(jié)果能夠天然地用特征取值的組合來表示.從根結(jié)點(diǎn)到該葉結(jié)點(diǎn)的分裂路徑即一系列特征取值條件的組合就可以表示該類.

本文以整體數(shù)據(jù)的密度Dglob作為基準(zhǔn)線，并為所有類計算其數(shù)據(jù)密度與Dglob的比值.CLTree+的聚類結(jié)果中數(shù)據(jù)密度大于Dglob的類即可視作熱點(diǎn).用戶在實(shí)際使用該算法時可以根據(jù)實(shí)際情況選擇密度最大的若干個類作為數(shù)據(jù)熱點(diǎn).

4 算法時間復(fù)雜度分析

4.1 CLTree的時間復(fù)雜度分析

對于只包含數(shù)值型特征，數(shù)值型特征分裂時采用{取值<=v}和{取值>v}二分裂以及{取值>=v}和{取值

4.2 CLTree+的時間復(fù)雜度分析

因?yàn)镃LTree僅支持處理數(shù)值型特征，因此在對比CLTree+和CLTree的時間復(fù)雜度時，僅考慮CLTree+處理數(shù)值型特征的情況.因?yàn)镃LTree+會根據(jù)葉結(jié)點(diǎn)最小數(shù)據(jù)量提前結(jié)束決策樹分裂，因此CLTree+的結(jié)點(diǎn)數(shù)量不是O(n)，而是O(1/k)，其中k為葉結(jié)點(diǎn)最小數(shù)據(jù)量與總數(shù)據(jù)量n的比值，取值通常為常數(shù).構(gòu)建CLTree+的時間復(fù)雜度為O(mn3).CLTree的時間復(fù)雜度是CLTree+的O(n)倍.

對于類別型特征，CLTree+采用one-against-others二分裂，只需要遍歷O(n)個分裂點(diǎn)，并且不需要對數(shù)據(jù)進(jìn)行排序，處理每個特征時只需要遍歷一次數(shù)據(jù).只包含類別型特征的CLTree+的時間復(fù)雜度為O(mn).

對于周期型特征，CLTree+將其轉(zhuǎn)換成數(shù)值型特征進(jìn)行處理，相當(dāng)于多了n倍特征，只包含周期型特征的CLTree+的時間復(fù)雜度為O(mn4).

對于含有mnum個數(shù)值型特征，mcat個類別型特征，mper個周期型特征的數(shù)據(jù)，CLTree+的時間復(fù)雜度為：

O(mcatn+mnumn3+mpern4)

(7)

CLTree+的時間復(fù)雜度受所處理數(shù)據(jù)的特征類型影響非常大，處理周期型特征需要花費(fèi)的時間最長，處理類別型特征需要花費(fèi)的時間最短.

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

5.1 實(shí)驗(yàn)數(shù)據(jù)介紹

本次實(shí)驗(yàn)使用的業(yè)務(wù)數(shù)據(jù)為國內(nèi)一家移動出行公司的訂單數(shù)據(jù)，該數(shù)據(jù)為2017年中某一周內(nèi)全國的業(yè)務(wù)數(shù)據(jù).每一個用戶使用一次該公司的服務(wù)就會產(chǎn)生一條業(yè)務(wù)數(shù)據(jù)，為了保護(hù)該公司的商業(yè)信息，以及考慮到實(shí)驗(yàn)程序與硬件的計算能力，實(shí)際被使用的數(shù)據(jù)量已經(jīng)經(jīng)過了采樣，采樣之后的數(shù)據(jù)量為10萬條.每條業(yè)務(wù)數(shù)據(jù)都包含了7個特征，各個特征的信息如表 2所示.

所有實(shí)驗(yàn)數(shù)據(jù)都進(jìn)行了脫敏，時間特征的取值加入了一定小時數(shù)的時間偏移，其它類別型特征的取值都用編號代替.

5.2 實(shí)驗(yàn)結(jié)果介紹

將CLTree+應(yīng)用到實(shí)驗(yàn)數(shù)據(jù)后得到如圖 5所示的聚類樹，為了使圖片更加清晰，部分內(nèi)容放到圖 6中顯示.算法輸入?yún)?shù)葉結(jié)點(diǎn)最小數(shù)據(jù)量定為總數(shù)據(jù)量的5%，最小信息熵增益定為0.01.圖 5記錄了數(shù)據(jù)分裂的詳細(xì)過程，圖中每一個結(jié)點(diǎn)都表示數(shù)據(jù)分裂過程中的一個數(shù)據(jù)子集，最上層的根結(jié)點(diǎn)表示整體數(shù)據(jù)集.如果一個結(jié)點(diǎn)有子結(jié)點(diǎn)，則說明該數(shù)據(jù)集繼續(xù)進(jìn)行了分裂.結(jié)點(diǎn)中的特征名表示該數(shù)據(jù)集在該特征上根據(jù)一定的條件進(jìn)行分裂，而連接結(jié)點(diǎn)的邊上的信息表示分裂該數(shù)據(jù)集的條件.例如，根結(jié)點(diǎn)表示的數(shù)據(jù)根據(jù)服務(wù)的取值被分成兩個子數(shù)據(jù)集，一個子數(shù)據(jù)集中數(shù)據(jù)的服務(wù)特征取值均為服務(wù)4，另外一個子數(shù)據(jù)集中數(shù)據(jù)的服務(wù)特征取值均為非服務(wù)4.從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑上的一系列分裂條件就構(gòu)成了表示目標(biāo)結(jié)點(diǎn)的特征取值組合，例如圖 5中的結(jié)點(diǎn)(虛線框)所示，從根結(jié)點(diǎn)到該結(jié)點(diǎn)的4個虛線箭頭表示的分裂條件就構(gòu)成了表示該結(jié)點(diǎn)的特征取值組合{服務(wù)=服務(wù)4，版本=版本8，品牌=品牌57，時間∈[0，15)}.所有的葉子節(jié)點(diǎn)構(gòu)成了最終的聚類結(jié)果.

表2 特征信息Table 2 Feature information

圖5 移動出行公司訂單數(shù)據(jù)建立的CLTree+(部分1)Fig.5 Result of CLTree+ clustering(Part 1)

表3按數(shù)據(jù)密度與整體數(shù)據(jù)的數(shù)據(jù)密度比值降序的方式展示了聚類結(jié)果中所有的類.最后的聚類結(jié)果中能夠出現(xiàn)較多的像類1這樣的數(shù)據(jù)覆蓋量大且數(shù)據(jù)密度較高的類是比較好的結(jié)果，數(shù)據(jù)量大意味著根據(jù)該類進(jìn)行決策的收益更大，數(shù)據(jù)密度大意味著根據(jù)該類進(jìn)行決策時付出相同的成本能夠獲得更大的收益.但是通常子數(shù)據(jù)集會繼續(xù)分裂出密度更大的子數(shù)據(jù)集，得到如類2和類3這樣的數(shù)據(jù)量接近葉結(jié)點(diǎn)最小數(shù)據(jù)量的類.有時也會得到類4這樣的類，其數(shù)據(jù)覆蓋量遠(yuǎn)大于葉結(jié)點(diǎn)最小數(shù)據(jù)量，但數(shù)據(jù)密度遠(yuǎn)低于數(shù)據(jù)密度最大的幾個類.這種類沒有繼續(xù)分裂得到數(shù)據(jù)密度更大的類是因?yàn)檫@個類的數(shù)據(jù)分布已經(jīng)比較均勻，或者雖然能夠分裂出一些數(shù)據(jù)密度非常大的子類，但是這樣的子類的數(shù)據(jù)覆蓋量小于葉結(jié)點(diǎn)最小數(shù)據(jù)量.因此針對特定的數(shù)據(jù)使用該算法時，需要根據(jù)具體的需求仔細(xì)的挑選葉結(jié)點(diǎn)最小數(shù)據(jù)量和最小信息熵增益這兩個參數(shù).對于一些數(shù)據(jù)密度非常低的類，如類10，并不是算法要找的熱點(diǎn)，是可以忽略的類，數(shù)據(jù)分析人員可以根據(jù)自己的需求選擇排序靠前的幾個類作為熱點(diǎn).

圖6 移動出行公司訂單數(shù)據(jù)建立的CLTree+(部分2)Fig.6 Result of CLTree+clustering(Part 2)

表3 訂單數(shù)據(jù)聚類結(jié)果類信息Table 3 Clusters information of CLTree+ clustering result

圖5還能夠給出數(shù)據(jù)在單維度上分布的信息.因?yàn)闆Q策樹會優(yōu)先選擇區(qū)分度最大的特征對數(shù)據(jù)進(jìn)行分裂，因此越接近根結(jié)點(diǎn)的分裂特征，對數(shù)據(jù)的區(qū)分度越大，即在這些特征上數(shù)據(jù)分布得越不均勻.從圖 5中可以發(fā)現(xiàn)數(shù)據(jù)首先根據(jù)服務(wù)進(jìn)行分裂，而通過數(shù)據(jù)集在服務(wù)特征上的單維度分布可以發(fā)現(xiàn)82.7%的訂單都是使用的服務(wù)4，還有11.9%的訂單都是使用的服務(wù)5，使用這兩種服務(wù)的訂單占了所的訂單的94.6%.

5.3 效果評估

并沒有一個通用的指標(biāo)可以用于評價多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)的結(jié)果，并且由于所有可能的特征取值組合數(shù)量巨大，因此也無法通過遍歷并對比所有可能的特征取值組合來評價熱點(diǎn)發(fā)現(xiàn)結(jié)果.目前主要依賴該移動出行公司的數(shù)據(jù)專家結(jié)合具體的專業(yè)知識對結(jié)果進(jìn)行評估.通過對聚類結(jié)果的認(rèn)真評估，數(shù)據(jù)專家一致認(rèn)為熱點(diǎn)發(fā)現(xiàn)的結(jié)果非常符合他們的歷史經(jīng)驗(yàn)，結(jié)果比較理想.

圖7 x被當(dāng)成數(shù)值型特征時CLTree的聚類結(jié)果Fig.7 Clustering result of CLTree when x is treated as numerical feature

5.4 CLTree與CLTree+處理周期型數(shù)據(jù)效果對比

實(shí)驗(yàn)數(shù)據(jù)為在{0≤x≤3或7≤x≤10,0≤y≤7}范圍內(nèi)隨機(jī)生成的二維數(shù)據(jù).用CLTree對該數(shù)據(jù)進(jìn)行聚類得到如圖7所示的兩個類{0≤x≤3,0≤y≤7}和{7≤x≤10,0≤y≤7}.而用CLTree+對該數(shù)據(jù)進(jìn)行聚類并將x軸的數(shù)據(jù)當(dāng)作周期為10的周期型數(shù)據(jù)時圖7中的兩個類會被處理為一個類{x∈[7,3],0≤8≤7}，如圖8所示.

圖8 x被當(dāng)成周期型特征時CLTree+的聚類結(jié)果Fig.8 Clustering result of CLTree+ when x is treated as periodical feature

5.5 性能評估

用于測試實(shí)驗(yàn)程序運(yùn)行速度的硬件環(huán)境為一臺搭載英特爾至強(qiáng)E5-2620，2.4GHz，64GB內(nèi)存的服務(wù)器，操作系統(tǒng)為Debian 8.7，所使用的編程語言為Python2.7.實(shí)驗(yàn)程序?yàn)橐粋€單機(jī)版單線程程序，并沒有使用任何集群技術(shù)或者多線程技術(shù).

5.5.1 CLTree與CLTree+的性能對比

本文使用CLTree與CLTree+處理相同的僅含有數(shù)值型特征的數(shù)據(jù)，得到的性能差異如圖 9所示.在數(shù)據(jù)量相同的情況下，CLTree的運(yùn)行時間遠(yuǎn)高于CLTree+.

圖9 CLTree和CLTree+的性能對比Fig.9 Performance compa-rison of CLTree and CLTree+

5.5.2 CLTree+性能

下面給出了將CLTree+應(yīng)用于某大型互聯(lián)網(wǎng)公司的業(yè)務(wù)數(shù)據(jù)時得到的數(shù)據(jù)量、每條數(shù)據(jù)包含的特征、CLTree+的分裂深度對程序速度的影響.所有程序運(yùn)行速度的數(shù)據(jù)都是運(yùn)行5次程序取平均值得到的.圖 10展示了數(shù)據(jù)量對程序運(yùn)行速度的影響，從圖中可以看出程序的運(yùn)行時間隨著數(shù)據(jù)量的增加基本上是呈線性增長，這是因?yàn)閷?shí)驗(yàn)數(shù)據(jù)中的特征除了時間以外全部為類別型特征.圖 11展示了決策樹分裂深度對程序速度的影響.從圖中可以看出程序的運(yùn)行時間隨著葉結(jié)點(diǎn)數(shù)量的增加而增加，但是增長得越來越慢，基本呈對數(shù)曲線關(guān)系.出現(xiàn)這種情況是因?yàn)殡S著數(shù)據(jù)的分裂，子數(shù)據(jù)集中的數(shù)據(jù)量會越來越少.表 4展示了分別移除各個特征之后對程序運(yùn)行速度的影響，表中的數(shù)據(jù)按照被移除特征的不同取值數(shù)量按升序排列，可以發(fā)現(xiàn)被移除特征的不同取值數(shù)量越多，程序減少的計算時間越多，對于相同類型的特征，不同取值的數(shù)量越多，所需要的計算量越大.客戶端版本與下單時間的不同取值數(shù)量差不多，但是移除下單時間后程序減少的運(yùn)行時間更長，這是因?yàn)橄聠螘r間是周期型特征，處理周期型特征更耗時.

圖10 數(shù)據(jù)量對程序運(yùn)行速度的影響Fig.10 Influence of data size on programme′s running speed圖11 決策樹分裂深度對程序速度的影響Fig.11 Influence of CLTree′s depth on programme′s running speed

表4 特征對程序運(yùn)行速度的影響Table 4 Influence of feature′s character on programme′s running speed

6 結(jié)束語

本文用聚類方法解決了多維數(shù)據(jù)的熱點(diǎn)發(fā)現(xiàn)問題，并詳細(xì)介紹了如何根據(jù)多維數(shù)據(jù)熱點(diǎn)發(fā)現(xiàn)的目標(biāo)設(shè)計的聚類算法CLTree+來解決該問題，以及詳細(xì)地介紹了為了實(shí)現(xiàn)熱點(diǎn)發(fā)現(xiàn)的目標(biāo)而對基線算法CLTree進(jìn)行的改進(jìn).CLTree+可以直接處理類別型特征，處理周期型特征時效果也比CLTree更好.除此之外，CLTree+的計算效率遠(yuǎn)優(yōu)于CLTree.本文設(shè)計的熱點(diǎn)發(fā)現(xiàn)算法提供兩個參數(shù)用于控制找出的熱點(diǎn)的粗細(xì)粒度，方便算法使用者根據(jù)自己分析的數(shù)據(jù)的具體情況進(jìn)行調(diào)整.從實(shí)驗(yàn)結(jié)果來看，算法成功的找出了數(shù)據(jù)聚集的區(qū)域，實(shí)驗(yàn)結(jié)果滿足了預(yù)期的目標(biāo).下一步的工作將主要集中在使用并行化技術(shù)提高程序的運(yùn)行效率，包括單機(jī)多線程并行和集群多機(jī)器并行.