AIOps從運維到運營：多維數(shù)據(jù)熱點發(fā)現(xiàn)算法

原創(chuàng)：?鄒磊 張明

簡介

? ? ? ?本文介紹一種多維數(shù)據(jù)熱點發(fā)現(xiàn)的AIOps算法桶雀，既可應(yīng)用于運維, 也可以應(yīng)用于運營，都是Ops (Operations)唬复。該工作發(fā)表于《小型微型計算機系統(tǒng)》矗积。

?該方法通過對多維數(shù)據(jù)進行聚類，找出數(shù)據(jù)聚集的區(qū)域敞咧，并通過特征取值組合（例如｛時間∈[18,24]棘捣，所在城市∈[北京,深圳，上海]休建，網(wǎng)絡(luò)延遲<30ms｝）將其表示出來乍恐。本文將數(shù)據(jù)聚集的區(qū)域稱為數(shù)據(jù)熱點，數(shù)據(jù)熱點可以作為多維數(shù)據(jù)的一種可視化方法测砂。

作者｜鄒磊 張明

編輯｜Vicky

背景

用戶數(shù)據(jù)分析是企業(yè)優(yōu)化服務(wù)質(zhì)量茵烈、提升用戶體驗的重要一環(huán)，常用的用戶數(shù)據(jù)分析方法包括細分分析砌些、對比分析呜投、漏斗分析、同期群分析存璃、聚類分析仑荐、AB測試、埋點分析纵东、來源分析粘招、用戶分析、表單分析等偎球，而熱點發(fā)現(xiàn)是用戶數(shù)據(jù)分析中沒有使用的方法男图。熱點發(fā)現(xiàn)的概念大家在生活中會經(jīng)常接觸示姿，例如微博熱搜、百度的搜索熱點等逊笆，這些熱點發(fā)現(xiàn)的工作本質(zhì)上都是對大量的文本數(shù)據(jù)進行挖掘栈戳，找出這些文本數(shù)據(jù)聚集的區(qū)域，即熱搜难裆、熱點子檀、主流觀點等。用戶數(shù)據(jù)通常組織為多維數(shù)據(jù)的形式乃戈，針對文本數(shù)據(jù)進行的熱點發(fā)現(xiàn)工作無法直接應(yīng)用于多維數(shù)據(jù)褂痰。

多維數(shù)據(jù)通常包含多個與目標(biāo)事件相關(guān)的特征，這些特征可以是用戶的手機品牌症虑、使用的服務(wù)類型缩歪、事件發(fā)生的時間、用戶的地理位置谍憔、用戶的網(wǎng)絡(luò)延遲匪蝙、軟件版本、服務(wù)器負載习贫、用戶年齡等逛球，每次目標(biāo)事件發(fā)生都對應(yīng)一條多維數(shù)據(jù)。例如圖 1所示苫昌，該多維數(shù)據(jù)包含5個特征颤绕，并且展示了7條數(shù)據(jù)作為示例。

圖 1多維數(shù)據(jù)示例

如果把多維數(shù)據(jù)的每一個特征都看作一個維度祟身，那么多維數(shù)據(jù)就是分布于由各個特征的取值范圍構(gòu)成的特征空間中的數(shù)據(jù)奥务。例如圖 2所示，在由時間袜硫、網(wǎng)絡(luò)延遲和所在城市三個特征構(gòu)成的特征空間中汗洒，每個黑色方格都是一條數(shù)據(jù)，白色方格表示該處沒有數(shù)據(jù)父款。多維數(shù)據(jù)的熱點發(fā)現(xiàn)希望能夠找出圖中數(shù)據(jù)集中的兩個熱點區(qū)域（圖中的虛線處），并以特征取值組合｛時間∈[18,24]瞻凤，所在城市∈[北京,深圳憨攒，上海]，網(wǎng)絡(luò)延遲<30ms｝和｛時間∈[6,9]｝將這兩個熱點區(qū)域的信息呈現(xiàn)給數(shù)據(jù)分析人員阀参，特征取值組合通過限定一個或者多個特征的取值范圍來表示數(shù)據(jù)的取值范圍肝集。實際的特征空間通常會超過三維，但是受限于圖片的表達能力蛛壳，在這里僅以三維特征空間作為例子杏瞻。

圖 2多維數(shù)據(jù)聚集區(qū)域示例

術(shù)語定義

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

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

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

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

1. 基本思想

圖 3熱點發(fā)現(xiàn)算法基本思路示意圖

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

2.? ?聚類算法選擇

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

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

? 通過剪枝提升了聚類的計算效率。

? 增加對類別型特征的聚類支持临燃。

? 提升了具有周期性特征的數(shù)值型特征的聚類效果睛驳。

3.? ?數(shù)據(jù)熱點獲取

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

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

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

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

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

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

實驗與結(jié)果分析

1. 實驗數(shù)據(jù)介紹

本次實驗使用的業(yè)務(wù)數(shù)據(jù)為國內(nèi)一家移動出行公司的訂單數(shù)據(jù)薯蝎，被使用的數(shù)據(jù)量已經(jīng)經(jīng)過了采樣遥倦，采樣之后的數(shù)據(jù)量約為10萬條。每條業(yè)務(wù)數(shù)據(jù)都包含了7個特征占锯，各個特征的信息如表 1所示：

所有實驗數(shù)據(jù)都進行了脫敏袒哥，時間特征的取值加入了一定小時數(shù)的時間偏移，其它類別型特征的取值都用編號代替消略。

2. 實驗結(jié)果介紹

將CLTree+應(yīng)用到實驗數(shù)據(jù)后得到如圖 5所示的聚類樹堡称。算法輸入?yún)?shù)葉結(jié)點最小數(shù)據(jù)量定為總數(shù)據(jù)量的5%，最小信息熵增益定為0.01艺演。圖 5記錄了數(shù)據(jù)分裂的詳細過程却紧，圖中每一個結(jié)點都表示數(shù)據(jù)分裂過程中的一個數(shù)據(jù)子集，最上層的根結(jié)點表示整體數(shù)據(jù)集胎撤。如果一個結(jié)點有子結(jié)點晓殊，則說明該數(shù)據(jù)集繼續(xù)進行了分裂。結(jié)點中的特征名表示該數(shù)據(jù)集在該特征上根據(jù)一定的條件進行分裂伤提，而連接結(jié)點的邊上的信息表示分裂該數(shù)據(jù)集的條件巫俺。例如，根結(jié)點表示的數(shù)據(jù)根據(jù)服務(wù)的取值被分成兩個子數(shù)據(jù)集肿男，一個子數(shù)據(jù)集中數(shù)據(jù)的服務(wù)特征取值均為服務(wù)4介汹，另外一個子數(shù)據(jù)集中數(shù)據(jù)的服務(wù)特征取值均為非服務(wù)4。從根結(jié)點到目標(biāo)結(jié)點的路徑上的一系列分裂條件就構(gòu)成了表示目標(biāo)結(jié)點的特征取值組合舶沛，例如圖 5中的紅色結(jié)點（虛線框）所示嘹承，從根結(jié)點到該結(jié)點的4個用紅色箭頭（粗箭頭）表示的分裂條件就構(gòu)成了表示該結(jié)點的特征取值組合｛服務(wù)＝服務(wù)4，版本＝版本8冠王，品牌＝品牌57，時間∈[0,15）｝舌镶。所有的葉子節(jié)點構(gòu)成了最終的聚類結(jié)果柱彻。

圖 5移動出行公司訂單數(shù)據(jù)建立的CLTree+

表 2按數(shù)據(jù)密度與整體數(shù)據(jù)的數(shù)據(jù)密度比值降序的方式展示了聚類結(jié)果中所有的類豪娜。最后的聚類結(jié)果中能夠出現(xiàn)較多的像類1這樣的數(shù)據(jù)覆蓋量大且數(shù)據(jù)密度較高的類是比較好的結(jié)果。

3. 效果評估

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

4. 性能評估

用于測試實驗程序運行速度的硬件環(huán)境為一臺搭載英特爾至強E5-2620挎狸，2.4GHz，64GB內(nèi)存的服務(wù)器断楷，操作系統(tǒng)為Debian 8.7,所使用的編程語言為Python2.7锨匆。實驗程序為一個單機版單線程程序，并沒有使用任何集群技術(shù)或者多線程技術(shù)冬筒。

下面給出了將CLTree+應(yīng)用于某大型互聯(lián)網(wǎng)公司的用戶數(shù)據(jù)時得到的數(shù)據(jù)量恐锣、每條數(shù)據(jù)包含的特征、CLTree+的分裂深度對程序速度的影響舞痰。所有程序運行速度的數(shù)據(jù)都是運行5次程序取平均值得到的土榴。圖 10展示了數(shù)據(jù)量對程序運行速度的影響，從圖中可以看出程序的運行時間隨著數(shù)據(jù)量的增加基本上是呈線性增長,這是因為實驗數(shù)據(jù)中的特征除了時間以外全部為類別型特征响牛。圖 11展示了決策樹分裂深度對程序速度的影響玷禽。從圖中可以看出程序的運行時間隨著葉結(jié)點數(shù)量的增加而增加，但是增長得越來越慢娃善，基本呈對數(shù)曲線關(guān)系论衍。出現(xiàn)這種情況是因為隨著數(shù)據(jù)的分裂，子數(shù)據(jù)集中的數(shù)據(jù)量會越來越少聚磺。

圖 10數(shù)據(jù)量對程序運行速度的影響

圖 11決策樹分裂深度對程序速度的影響

結(jié)語

本文介紹了一種多維數(shù)據(jù)熱點發(fā)現(xiàn)算法坯台，通過CLTree+對數(shù)據(jù)進行聚類找出數(shù)據(jù)聚集的熱點區(qū)域。該算法應(yīng)用于真實用戶數(shù)據(jù)瘫寝，取得了很好的效果蜒蕾。

鄒磊，朱晶焕阿，聶曉輝咪啡，蘇亞，裴丹暮屡，孫宇撤摸，《基于聚類的多維數(shù)據(jù)熱點發(fā)現(xiàn)算法》，《小型微型計算機系統(tǒng)》