基于聚類的多維數據熱點發現算法

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

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

1 引 言

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

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

圖1 多維數據示例
Fig.1 Example of multi-dimensional and multi-class data

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

圖2 多維數據聚集區域示例Fig.2 Example of data area with high density

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

通常熱點發現問題都通過聚類方法解決[1-3]，本文也使用聚類方法來解決多維數據熱點發現問題.根據多維數據熱點發現的需求，本文選擇了聚類算法CLTree[4]作為基線算法.CLTree通過往目標數據中均勻地填充一類虛擬數據來構造雙類別數據，再用決策樹對數據進行分類，分類完成后將虛擬數據移除，分類結果就成了聚類結果.

本文對CLTree[4]進行如下重要改進，設計了CLTree+來解決數據熱點發現問題：

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

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

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

CLTree+被應用于某大型互聯網公司的業務數據，得到了很好的效果，成功地找出了若干符合專家經驗的數據熱點.

2 研究目標

熱點定義：熱點是指特征空間中的數據區域Area，其數據密度D>=Dthr，并且數據量Q>=Qthr.Dthr和Qthr為常數閾值，其取值根據具體應用由專家根據相關領域的專業知識選取.

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

(1)

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

(2)

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

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

L=b-a

(3)

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

(4)

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

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

(5)

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

對于同一份數據集的不同特征取值組合，可以用它們的數據密度來對比不同特征取值組合下的相對數據疏密程度.但是數據密度無法用于對比不同數據集下的特征取值組合的數據疏密程度，因為不同的數據集的特征集不同，其特征長度的物理意義不同.

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

本文針對多維數據進行熱點發現的具體目標是要找出一些滿足以下條件的特征取值組合：

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

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

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

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

然而前三個訴求其實是矛盾的，為了覆蓋盡可能多的數據通常會導致特征取值組合的平均數據密度的下降，最極端的例子就是整體數據構成一個特征取值組合時，雖然數據覆蓋量為100%，但是只要數據不是均勻分布地，就肯定能找到數據密度更高的特征取值組合.特征取值組合數量越少與它們的的平均數據密度越大這兩個訴求也是相悖的，因為只要一個熱點內的數據不是平均分布的，就總是能夠在其中找到數據密度更大的特征取值組合.不同數據對這三個訴求的側重點也不同，因此很難對熱點發現的結果設定一個最優的評價標準.數據分析人員需要根據自己的實際需要，通過調整算法的輸入參數葉結點最小數據量和最小信息熵增益來權衡這三個訴求.

3 多維數據熱點發現算法介紹

3.1 基本思想

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

3.2 聚類算法選擇

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

圖3 熱點發現算法基本思路示意圖Fig.3 Basic idea of hotspot detection alogrithm

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

圖4 多維數據熱點發現算法流程圖Fig.4 Flowchart of multi-dimen-sional data hotspot detection algorithm

3.3 算法流程

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

3.4 數據邊界確定

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

3.5 CLTree+

CLTree+相對于CLTree進行了如下三點改進.

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

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

3.5.2 類別型特征上的最佳分裂點選擇

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

算法1.類別型特征最佳分裂點選取

輸入：待聚類的數據集data，待選取最佳分裂點的特征F，葉結點最小數據量minlen，最小信息增益minentro

輸出：特征F上的最佳分裂點split

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

2)split = None

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

4) spliti= 將data分裂成datal和datar的分裂點

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 周期型特征上的最佳分裂點選擇

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

(6)

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

算法2.周期型特征最佳分裂點選取

輸入：待聚類的數據集data，待選取最佳分裂點的特征F，特征F的周期P，葉結點最小數據量minlen，最小信息增益minentro

輸出：特征F上的最佳分裂點

1)將特征F的數值映射到一個周期的范圍內，并根據特征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

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

3.6 數據熱點獲取

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

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

4 算法時間復雜度分析

4.1 CLTree的時間復雜度分析

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

4.2 CLTree+的時間復雜度分析

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

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

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

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

O(mcatn+mnumn3+mpern4)

(7)

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

5 實驗與結果分析

5.1 實驗數據介紹

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

所有實驗數據都進行了脫敏，時間特征的取值加入了一定小時數的時間偏移，其它類別型特征的取值都用編號代替.

5.2 實驗結果介紹

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

表2 特征信息Table 2 Feature information

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

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

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

表3 訂單數據聚類結果類信息Table 3 Clusters information of CLTree+ clustering result

圖5還能夠給出數據在單維度上分布的信息.因為決策樹會優先選擇區分度最大的特征對數據進行分裂，因此越接近根結點的分裂特征，對數據的區分度越大，即在這些特征上數據分布得越不均勻.從圖 5中可以發現數據首先根據服務進行分裂，而通過數據集在服務特征上的單維度分布可以發現82.7%的訂單都是使用的服務4，還有11.9%的訂單都是使用的服務5，使用這兩種服務的訂單占了所的訂單的94.6%.

5.3 效果評估

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

圖7 x被當成數值型特征時CLTree的聚類結果Fig.7 Clustering result of CLTree when x is treated as numerical feature

5.4 CLTree與CLTree+處理周期型數據效果對比

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

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

5.5 性能評估

用于測試實驗程序運行速度的硬件環境為一臺搭載英特爾至強E5-2620，2.4GHz，64GB內存的服務器，操作系統為Debian 8.7，所使用的編程語言為Python2.7.實驗程序為一個單機版單線程程序，并沒有使用任何集群技術或者多線程技術.

5.5.1 CLTree與CLTree+的性能對比

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

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

5.5.2 CLTree+性能

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

圖10 數據量對程序運行速度的影響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 特征對程序運行速度的影響Table 4 Influence of feature′s character on programme′s running speed

6 結束語

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