小螞蟻說：
The Web Conference 2018，即前WWW大會（International Conference of World Wide Web）於4月23-28日期間在法國里昂舉行。螞蟻金服的小夥伴也正位於法國前線參加本次活動。在此次大會上，螞蟻金服也有相關論文入選。本文即螞蟻金服人工智能團隊被錄用於WWW BIG Web track(錄取率17%)的論文——Anomaly Detection with Partially Observed Anomalies的相關分享。想第一時間閱讀論文全文的同學，請複製打開網址【http://lamda.nju.edu.cn/zhangyl/zhangyl_files/www18anomaly.pdf】即可訪問哦！
引言
異常檢測是一類應用極為廣泛的技術，在大量的應用實踐中有著切實的需求。例如，僅就電商交易的場景而言，就存在諸如異常交易挖掘、異常用戶發現等諸多問題中需要用到異常檢測的相關技術。在傳統的研究中，主要存在兩種典型的問題情景：其一是基於完全無監督數據的異常檢測；其二則是基於有監督數據的異常檢測。除此之外，也存在其他的一些問題情景，例如在僅有正常樣本數據情況下的異常檢測問題。區別於以上種種，本文關注的是這樣一種異常檢測問題：在只有極少量的已知異常樣本和大量的無標記數據的情況下，來進行的異常檢測問題。這一場景在諸如URL異常檢測，異常交易挖掘等問題中均可遇到，因而對於這一問題的研究處理有著切實的應用需求。
問題說明
在我們的問題場景中，我們能夠獲得極少數的已知異常樣本以及大量的無標記樣本。形式化地，給定包含m個樣本的數據集
其中前I個樣本構成的集合
是已知的異常樣本集合（本文用y=1來表示異常樣本，y=-1表示正常樣本），而剩餘的m-I個樣本構成的集合
為無標記樣本集合。通常情況下，I遠小於m，即觀察到的已知異常的數目是極少的。我們期望基於現有的數據學習得到模型，在未來的數據上具有著比較好的異常檢測的效果。
問題分析
我們面對的問題場景與傳統的基於無監督學習和監督學習的場景有著明顯的差別，若簡單的形式化為無監督學習而丟棄已有的部分標記信息則會帶來信息的極大損失，且效果不理想；若將無標記的數據完全當作正常樣本來採用監督學習的模型來處理，則會因為引入的大量噪音導致效果欠佳；若將已知異常看作是正樣本，則我們面對的是基於少量正樣本和大量無標記樣本構建的學習模型，表面上看，這與PU（Positive and Unlabeled）Learning有一定的相似性，然而PU Learning中的正樣本大多有著較高的相似性，而異常檢測中的異常樣本往往千差萬別，這使得PU Learning的應用大大受限。
本文針對於這一問題提出一種“兩階段”的方法。在只有極少數目的異常樣本情況下構建模型是困難的，因而本文首先試圖從大量的無標記樣本中挖掘潛在異常樣本（potential anomalies）以及可靠正常樣本（reliable normal samples）；另一方面，由於異常樣本之間往往具有較大的多樣性，因而本文試圖通過聚類將異常樣本劃分為不同的簇而非簡單的當做一個大類來看待。下文將對方法細節進行簡述。
方法介紹
如圖所示，該方法主要包括兩個階段。在第一階段，對已知異常樣本進行聚類，並從未標記樣本中挖掘潛在異常樣本以及可靠正常樣本；第二階段，基於以上的樣本，構建帶權重的多分類模型。
階段一：
對於已知的異常樣本（Observed Anomalies），因其之間可能具有較大的多樣性，我們對其聚類，使得聚類後的每一簇之間具有較高的相似性，這裡可以採用不同的聚類算法，本文基於廣泛使用的k-means聚類算法來實現。
對於無標記的樣本（Unlabeled Instances），我們試圖從中過濾出潛在異常樣本（Potential Anomalies）以及可靠正常樣本（Reliable Normals）。對於異常樣本而言，一方面，它有著容易被隔離（Isolation）的特點，另一方面，它往往與某些已知的異常樣本有著較高的相似性。因而我們分別計算無標記樣本的隔離得分（Isolation Score）和其與異常樣本簇的相似得分（Similarity Score），綜合二者，來得到一個樣本的異常程度總體得分。具體地，我們基於著名的異常檢測算法Isolation Forest的方法計算樣本的隔離得分IS(x):
其中，
，H(n)為harmonic number，h(x)為樣本x在構建的完全隨機樹中經歷的路徑的長度，E(h(x))為平均長度。IS(x)，意味著x的隔離程度越高，是異常樣本的可能性越大。
為計算樣本與已知異常的相似性得分SS(x)，我們首先計算得到已知異常樣本聚類後的各個簇中心
，則
綜合隔離得分IS(x)和相似性得分SS(x)，得到每個樣本的總體得分
其中參數
用於調節二者的影響程度。我們分別選擇
和
的樣本作為潛在異常樣本（Potential Anomalies）以及可靠正常樣本（Reliable Normals），其中
作為參數控制過濾的嚴格程度，篩選出的潛在異常樣本歸於其最近的異常樣本中心所屬的類別。
如此，我們除了擁有已知的異常樣本（Observed Anomalies），還過濾得到了潛在異常樣本（Potential Anomalies）以及可靠正常樣本（Reliable Normals）。
階段二：
在本階段，我們基於以上的樣本構建加權多分類模型來區分不同的異常樣本和正常樣本。具體地，我們依據標記的置信程度進行權重的設置：令所有已知的異常樣本權重為1，對於潛在異常樣本，其TS(x)越高，則其作為異常樣本的置信度越高，權重越大，即
對於可靠正常樣本，其TS(x)越低，則其作為正常樣本的置信度越高，權重越大，即
如此，我們訓練一個加權的多分類模型來優化一下目標：
對於未來的待預測樣本，通過該多分類模型預測其所屬類別，若樣本被分類到任何異常類，則將其視為異常樣本，否則，視為正常樣本。
實驗結果
我們在大量數據集上進行了實驗驗證，並綜合對比了基於無監督學習的算法、基於監督學習的算法以及基於PU Learning的算法來驗證以上算法在我們的場景中的性能。
數據信息如下表所示，值得注意的是，我們的實驗數據具有著較大的多樣性，而數據中已知的異常樣本數據是極少的。
實驗結果如下表所示，我們可以看到，無論是無監督還是監督學習的算法，效果都是不理想的。基於PU Learning的算法在某些數據上表現尚可，而在某些數據上的表現則較差。我們的方法在各個數據上均有著比較好的性能表現。
業務應用
我們將這一算法應用到URL攻擊檢測的真實應用中。對於URL攻擊而言，常常存在諸如XXE (XML External Entity Injection), XSS (Cross SiteScript) 以及SQL injection等各種不同的攻擊類型，作為異常訪問，其相互之間具有一定的差異，若統一對待，則可能帶來不理想的效果。除此之外，我們面對的數據是大量的未標記URL以及少量已經檢測出來的URL攻擊，這與本文所描述的問題場景完全吻合。
為驗證不同算法的效果，我們選取了幾天的URL訪問數據來進行檢測，並對打分最高的1000樣本進行人為的判定，結果如下表所示，我們可以發現，在真實的業務場景中，這一算法同樣體現出了性能上的優勢，從而驗證了這一算法的可靠性。
總結
本文介紹了我們針對於一種特定異常檢測場景的算法，在該場景下，我們只有極少量的已打標異常樣本和大量的無標記樣本。我們提出的方法充分考慮了異常樣本具有多樣性的特點，綜合兼顧樣本本身的隔離性以及其與已知異常樣本的相似性來進行樣本的篩選，並進一步構建了加權多分類模型來對未知樣本進行預測，實驗結果表明我們的方法相比其他方法具有顯著的性能優勢。這一問題設定在很多的業務場景中均有可能遇到，因而具有切實的應用價值。
閱讀更多 螞蟻金服科技 的文章
