數(shù)據(jù)相似度與異常檢測

第4章數(shù)據(jù)相似度與異常檢測4.1

相似度度量4.2

傳統(tǒng)度量方法4.3

大數(shù)據(jù)度量方法4.4

異常檢測1相似度的研究起源于心理學(xué)，是判斷決策和解決問題的重要工具。相似度度量是衡量變量間相互關(guān)系強(qiáng)弱、聯(lián)系緊密程度的重要手段，因此相似度度量經(jīng)常被數(shù)據(jù)挖掘技術(shù)使用，如聚類、最近鄰分類和異常檢測等。4.1相似度度量2對象與屬性的定義及其之間的關(guān)系是相似度度量的基礎(chǔ)知識。數(shù)據(jù)集由對象組成。一個對象代表一個實(shí)體，可以是物理對象（如教室），也可以是抽象對象（如寫作風(fēng)格）。通常，對象用屬性描述（例如對象患者可以用他們的癥狀來描述）。對象又稱樣本、實(shí)例、數(shù)據(jù)對象或數(shù)據(jù)點(diǎn)。如對象存放在數(shù)據(jù)庫中，數(shù)據(jù)庫的行對應(yīng)于對象，而列對應(yīng)于屬性。4.1.1對象與屬性類型4.1相似度度量3（1）屬性（Attribute）

屬性表示對象的一個特征，是一個數(shù)據(jù)字段。在文獻(xiàn)中，屬性、特征（Feature）、維（Dimension）和變量（Variable）可互換。

“特征”一般用在機(jī)器學(xué)習(xí)中?！熬S”則一般在數(shù)據(jù)倉庫中使用。

而統(tǒng)計(jì)學(xué)家更傾向于使用“變量”。數(shù)據(jù)挖掘的專業(yè)人士一般使用術(shù)語“屬性”。如，商品的屬性包括商品ID號、商品名稱、產(chǎn)地和價格等。

屬性的類型由該屬性可能具有的值的集合決定。定性地，屬性可以是名詞型的、二值的、順序型的或數(shù)值型的。4.1.1對象與屬性類型4.1相似度度量4（2）名詞型（Nominal）屬性也稱為標(biāo)稱屬性、無序型屬性或名義型屬性，是與名稱相關(guān)的屬性。名詞型屬性的值是一些符號或事物的名稱。每個值代表某種類別或狀態(tài)，因此名詞型屬性又被視為是分類的（Categorical）。這些值不需要具備有意義的順序。在計(jì)算機(jī)科學(xué)中，這些值也被視為是枚舉的（Enumeration）。如膚色、職業(yè)屬性。

4.1.1對象與屬性類型4.1相似度度量5

盡管名詞型屬性的值是名詞符號，但可用數(shù)值來表示這些符號或名稱。

如，對skin_color，可指定數(shù)值0表示白色，1表示黃色，2表示棕色，3表示黑色。如，商品ID號，可能值也可以是數(shù)值，但是對其進(jìn)行數(shù)學(xué)運(yùn)算沒有意義，所以不需要定量地使用這些數(shù)值，也就是說名詞型屬性時，數(shù)學(xué)運(yùn)算沒有意義。

盡管一個名詞型屬性可以取整數(shù)值，但不能將其視為數(shù)值屬性，因?yàn)?，并不會定量地去使用這些整數(shù)。名詞型屬性不是定量的，不具備有意義的順序。計(jì)算該屬性的均值或中值是沒有意義的。4.1.1對象與屬性類型4.1相似度度量6（3）二值（Binary）屬性

一種名詞型屬性，但其只有兩種類別或狀態(tài)：0或1，其中0通常表示對象沒有該屬性，而1表示對象具備該屬性。

二值屬性，也稱為二元屬性，當(dāng)其屬性的兩種狀態(tài)為true和false時，又稱為布爾（Bool）屬性。

示例：對患者進(jìn)行醫(yī)學(xué)化驗(yàn)，具有兩種可能結(jié)果，屬性medical_test值為1時表示化驗(yàn)結(jié)果為陽性，0表示結(jié)果為陰性。4.1.1對象與屬性類型4.1相似度度量7當(dāng)二值屬性的兩種狀態(tài)具有同等價值并且?guī)в型鹊臋?quán)重時，稱作對稱屬性。當(dāng)二值屬性的狀態(tài)結(jié)果不是同等重要，稱屬性是非對稱的。通常用1來表示相對更重要些（通常是比較少見的）的結(jié)果（如，乙肝病毒陽性），而用0表示另一種結(jié)果（如，乙肝陰性）。4.1.1對象與屬性類型4.1相似度度量8（4）順序型屬性其可能的取值之間具有有意義的順序或秩評定（ranking），但是相鄰值之間的差是未知的。順序型屬性通常用于等級評定調(diào)查。如滿意度、職稱等。順序型屬性同名詞型屬性一樣，可以通過將數(shù)值量的值域劃分成有限個有序類別來表示。4.1.1對象與屬性類型4.1相似度度量9（5）數(shù)值屬性數(shù)值（Numeric）屬性是定量的，用整數(shù)或?qū)崝?shù)值表示，是可度量的量。數(shù)值屬性可以是區(qū)間型的或比率型的。區(qū)間型屬性。區(qū)間型（Interval）屬性是用相等的單位尺度來度量的。區(qū)間型屬性的值可以為正值、負(fù)值和0，區(qū)間型屬性的值是有順序的。如溫度。4.1.1對象與屬性類型4.1相似度度量10（6）比率型屬性比率型（Ratio）屬性不同于區(qū)間型屬性，它是具有固有零點(diǎn)的數(shù)值屬性。也就是說，可以說一個值是另一個值的倍數(shù)，即比率型屬性的度量是比率標(biāo)度的。此外，這些值是有順序的，可計(jì)算其差值、均值等。比率型屬性包括重量、高度、速度、長度、貨幣量、工作年限等。4.1.1對象與屬性類型4.1相似度度量11

在機(jī)器學(xué)習(xí)領(lǐng)域的分類算法通常把屬性分成連續(xù)的或離散的。離散屬性具有有限個或無限可數(shù)個值，可用或不用整數(shù)來表示。

如，屬性skin_color、medical_test都有有限個值，是離散的。離散屬性可以具有數(shù)值值，如年齡取值0到300，身高取值0cm到300cm等。如果屬性可能的值集合是無限的，但是可與自然數(shù)一一對應(yīng)，則稱這個屬性為無限可數(shù)（阿列夫零）的。如，郵政編碼是無限可數(shù)的。

4.1.1對象與屬性類型4.1相似度度量12如果屬性不是離散的，稱之為連續(xù)的。通常，術(shù)語“數(shù)值屬性”與“連續(xù)屬性”通?？梢曰Q使用。實(shí)際上，實(shí)數(shù)值一般用有限位數(shù)字表示，而連續(xù)屬性一般用浮點(diǎn)數(shù)表示。4.1.1對象與屬性類型4.1相似度度量13

兩個對象間的相似度是這兩個對象相似程度的數(shù)值度量，兩者越相似，相似度就越高。相似度s具有對稱性：4.1.2相似度度量定義

大多數(shù)時候，相似度可以標(biāo)準(zhǔn)化為：4.1相似度度量144.1.2相似度度量定義通常，使用相異度（而不是相似度）作為度量標(biāo)準(zhǔn)。相異度用

d(x,y)來表示。通常稱相異度為距離。當(dāng)x和y相似時，距離d(x,y)很小，如果x和y不相似，d(x,y)就很大。不失一般性，假定：

距離也具有對稱性：4.1相似度度量15

通過一個單調(diào)遞減函數(shù)，將距離轉(zhuǎn)換成相似性度量，相似性度量的取值一般在區(qū)間[0,1]之間，值越大，說明兩個對象越相似。

如，可以采用以下變換：a)采用負(fù)指數(shù)函數(shù)，將距離轉(zhuǎn)換為相似度度量，即4.1.3由距離度量變換而來的相似度度量4.1相似度度量164.1.3由距離度量變換而來的相似度度量b)采用距離的倒數(shù)作為相似度度量，為了避免分母為0的情況，在分母上加1，即c)若距離在0～1之間，可采用與1的差作為相似系數(shù)，即d)若距離的取值在一個有限的范圍內(nèi)，可將距離映射（歸一化）到區(qū)間[0,1]內(nèi)，此時的相似度為4.1相似度度量17通常，具有多個屬性的兩個對象間的相似度以單個屬性的相似度組合來定義。如果屬性值匹配，相似度一般定義為1，否則為0。相異度用相反的方法定義，如果屬性值匹配，相異度為0，否則為1。對于由一個順序型屬性描述的對象，由于順序信息要被代入計(jì)算，情況就更復(fù)雜。如，考慮一個在范圍{poor,fair,OK,good,wonderful}內(nèi)測量產(chǎn)品（如糖塊）質(zhì)量的屬性。

4.1.4屬性之間的相似度度量4.1相似度度量18

對于區(qū)間型屬性，兩對象間的相異型的自然度量是它們值之差的絕對值。例如，體重與一年前相比重了10磅。在這種情況下，相異度通常在區(qū)間0到∞之間，而不是在0到1之間。

比率型（Ratio）屬性是在非線性尺度上取得的測量值，如，指數(shù)比率AeBt或Ae-Bt，其中A和B為正的常數(shù)。

典型的例子包括細(xì)胞繁殖增長的數(shù)目描述、放射性元素的衰變。4.1.4屬性之間的相似度度量4.1相似度度量19不同屬性情況下的相似度度量方法4.1.4屬性之間的相似度度量4.1相似度度量20一個對象通常由多個屬性描述。假定n個屬性，每條記錄是n維空間中的一個點(diǎn)，該空間下的距離度量是函數(shù)d(x,y)

，以空間中的兩個點(diǎn)作為參數(shù)，輸出實(shí)數(shù)值。該函數(shù)必須滿足下列準(zhǔn)則：1)非負(fù)性：d(x,y)≥0，非負(fù)。2)同一性：d(x,y)=0，當(dāng)且僅當(dāng)x=y。3)對稱性：d(x,y)=d(y,x)，對稱。4)三角不等式：d(x,y)≤d(x,z)+d(z,y),從對象x到對象y的直接距離不會大于途徑任何其他對象z的距離。4.1.5對象之間的相似度度量4.1相似度度量21

大多情況下，通過計(jì)算對象間距離的方法評估相似度：距離越小，相似度越大。

三角不等式是上述條件中最復(fù)雜的條件。

它的直觀意義是，從x點(diǎn)到y(tǒng)點(diǎn)，間接經(jīng)過第三點(diǎn)不會比直接有任何好處。

三角不等式準(zhǔn)則使得所有的距離測度表現(xiàn)得如同其描述的是從一個點(diǎn)到另一個點(diǎn)的最短路徑的長度。

滿足以上準(zhǔn)則的距離函數(shù)稱為度量（Metric）。注意非負(fù)性被其他三個性質(zhì)所蘊(yùn)含。4.1.5對象之間的相似度度量4.1相似度度量22

針對不同類型的應(yīng)用和數(shù)據(jù)類型，具有不同的相似度度量方法。傳統(tǒng)的相似性度量方法有兩種：距離度量和相似系數(shù)。

當(dāng)對象只包含二值屬性時，稱其之間的相似度度量為相似系數(shù)。

而使用距離度量時，往往是將數(shù)據(jù)對象看成是多維空間的一個點(diǎn)（向量），并在空間中定義點(diǎn)與點(diǎn)之間的距離。

對象之間的相似度計(jì)算涉及描述對象的屬性類型，需要將不同屬性上的相似度整合成一個總的相似度來表示。4.2傳統(tǒng)度量方法23

二值（Binary）屬性只有兩種狀態(tài)：0表示屬性不存在，1表示屬性存在。假設(shè)x和y是兩個包含n個二值屬性的對象。對此二值屬性有四種組合方式：

f00為在對象x和y中均取0的二值屬性個數(shù)，f01為在對象x中取0而在對象y中取1的二值屬性個數(shù)，f10為在對象x中取1而在對象y中取0的二值屬性個數(shù)，f11為在對象x和y中均取1的二值屬性個數(shù)。

二值屬性存在對稱的和不對稱的兩種。若二值屬性的兩個狀態(tài)值所表示的內(nèi)容同等重要，則它是對稱的，否則為不對稱的。4.2.1二值屬性的相似度度量4.2傳統(tǒng)度量方法24

對于對稱二值屬性，常用的二值屬性相似度計(jì)算方法有簡單匹配相關(guān)系數(shù)（SimpleMatchingCoefficient，SMC）,其定義如下：4.2.1二值屬性的相似度度量

f11+

f00為取值相同的屬性個數(shù)，f01+

f10為取值不同的屬性個數(shù)計(jì)算屬性在兩個對象中都存在和都不存在的情況。如，查找某次考試中學(xué)生答案相似的題，即都答對的題和都答錯的題。4.2傳統(tǒng)度量方法25

給定屬性變量disease，它描述檢測結(jié)果是positive（陽性）或negative（陰性），顯然這兩個檢測結(jié)果的重要性是不一樣的。通常，將少見（重要）的情況用1表示（如乙肝陽性），而將其他（不重要）的情況用0表示（如乙肝陰性）。

取值1比取值0更重要、更有意義的二值屬性具有不對稱性。常用Jaccard系數(shù)來定義其對象間的相似度：4.2.1二值屬性的相似度度量4.2傳統(tǒng)度量方法26示例：計(jì)算下面兩個二值向量之間的SMC系數(shù)和Jaccard系數(shù)。

x=(1,0,0,0,0,0,0,0,0,1)，y=(0,0,0,0,0,0,1,0,0,1)f01=1，在x中取0、在y中取1，f10=1，在x中取1、在y中取0f00=7，在x中取0、在y中取0，f11=1，在x中取1、在y中取14.2.1二值屬性的相似度度量4.2傳統(tǒng)度量方法27

歐氏距離（EuclideanDistance）是最為人熟知的距離度量標(biāo)準(zhǔn)，也就是通常所想象的“距離”。在n維歐氏空間中，每個點(diǎn)是一個n維實(shí)數(shù)向量。該空間中的傳統(tǒng)距離度量，即常說的L2范式，定義如下：4.2.2歐氏距離4.2傳統(tǒng)度量方法284.2.2歐氏距離歐氏距離首先計(jì)算每一維上的距離，然后求它們的平方和，最后求算術(shù)平方根。它滿足上述距離四準(zhǔn)則中的前三條。至于歐氏距離是否滿足三角不等式準(zhǔn)則，則需要較多的代數(shù)學(xué)知識才能證明。但是歐氏空間有一個眾所周知的特性，即一個三角形的兩邊之和大于第三邊。4.2傳統(tǒng)度量方法29

另一種常用的歐氏空間距離度量標(biāo)準(zhǔn)是曼哈頓距離（ManhattanDistance）或叫城區(qū)距離（CityBlock），其定義如下：4.2.2歐氏距離

兩個點(diǎn)的距離是每維距離的絕對值之和。4.2傳統(tǒng)度量方法304.2.2歐氏距離Minkowski距離（Lr范式）把歐氏距離和曼哈頓距離包含為特例：r為變量。注意不要將參數(shù)r與空間維數(shù)（屬性個數(shù)）n混淆。4.2傳統(tǒng)度量方法31

L∞范式，當(dāng)r趨向于無窮大時，Lr范式的極限值。即：4.2.2歐氏距離當(dāng)r增大時，只有那個具有最大距離的維度在真正起作用，因此，L∞范式定義為在所有維度i下|xi-yi|中的最大值，也稱為切比雪夫距離（ChebyshevDistance），定義如下：4.2傳統(tǒng)度量方法32例：計(jì)算二維歐氏空間（即通常所說的平面）上的兩個點(diǎn)(7,2)和(4,6)的L1范式、L2范式和L∞范式。4.2.2歐氏距離

L1范式：

L2范式：L∞范式：

4.2傳統(tǒng)度量方法334.2.2歐氏距離Minkowski距離的缺點(diǎn)是使用時量綱或度量單位對計(jì)算結(jié)果有影響，為避免不同量綱影響，通常要先對數(shù)據(jù)進(jìn)行規(guī)范化處理。另外，Minkowski距離沒有考慮屬性間的多重相關(guān)性?？朔嘀叵嚓P(guān)性的一種方法是慎重選擇描述對象的屬性，根據(jù)領(lǐng)域知識或是采用屬性選擇方法來選擇合適的屬性，另一種方法是采用Mahalanobis距離。4.2傳統(tǒng)度量方法34余弦距離（CosineDistance）在有維度的空間下才有意義，包括歐氏空間和離散歐氏空間，而后者坐標(biāo)只采用整數(shù)值或布爾值（0或1）。在上述空間下，點(diǎn)代表方向。兩個點(diǎn)的余弦距離實(shí)際上是點(diǎn)所代表的向量之間的夾角，在任何維數(shù)空間下該夾角的范圍都是0～180度。余弦距離忽略各向量的絕對長度，而著重從形狀方面考慮它們之間的關(guān)系。兩個向量方向接近時，夾角余弦值較大，反之則較小。兩個向量平行時，夾角余弦值為1，向量之間的匹配最大。兩個向量正交時，夾角余弦值則為0，沒有匹配。4.2.3余弦距離4.2傳統(tǒng)度量方法35

首先計(jì)算夾角的余弦值，然后用反余弦函數(shù)將結(jié)果轉(zhuǎn)化為0～180度之間的角度，從而最終得到余弦距離。給定向量x和y，其夾角余弦等于它們的點(diǎn)乘積x·y除以兩個向量的范式L2（即它們到原點(diǎn)的歐氏距離）乘積：4.2.3余弦距離·代表向量點(diǎn)乘，

代表向量的歐氏距離，

4.2傳統(tǒng)度量方法364.2.3余弦距離余弦距離也是一個距離度量。由于余弦距離定義在0～180度之間，因此，余弦距離非負(fù)，當(dāng)且僅當(dāng)兩個向量表示同一方向時向量的夾角為0。余弦距離的對稱性非常明顯：x和y的夾角顯然與y和x的夾角相等。至于三角不等式則能夠通過物理含義來最好地詮釋，如要將向量x旋轉(zhuǎn)到y(tǒng)，可以先從x旋轉(zhuǎn)到z，然后再從z旋轉(zhuǎn)到y(tǒng)。兩次旋轉(zhuǎn)經(jīng)過的夾角之和不會小于直接旋轉(zhuǎn)所得到的夾角。4.2傳統(tǒng)度量方法37例：計(jì)算向量x=(1,-1,2)和向量y=(2,1,1)的余弦距離。計(jì)算點(diǎn)乘積x·y=1×2+(-1)×1+2×1=3，向量x的L2范式

，向量y的L2范式

，x和y的夾角余弦值為1/2，x和y的余弦距離為60度。4.2.3余弦距離4.2傳統(tǒng)度量方法38余弦距離常用來比較文檔，或針對給定的查詢詞向量對文檔排序。當(dāng)屬性是二值屬性時，余弦距離函數(shù)可以用共享特征或?qū)傩越忉尅４藭r，x?y是x和y共同具有的屬性數(shù)，而

是x具有的屬性數(shù)與y具有的屬性數(shù)的幾何均值。于是，此時

變?yōu)閷灿袑傩缘囊环N度量。對于這種情況，余弦距離的一個簡單變種如下：

4.2.3余弦距離該函數(shù)也稱為Tanimoto系數(shù)或Tanimoto距離，通常用于信息檢索（網(wǎng)頁查重、新聞查重、作弊檢測、抄襲檢查）與生物學(xué)分類中。4.2傳統(tǒng)度量方法39

距離度量中一個重要問題就是當(dāng)對象中屬性的量綱單位不同時，距離度量該如何計(jì)算。

當(dāng)傳統(tǒng)的歐氏距離被用來度量分析具有年齡和收入兩個屬性的人的差距時，除非將兩個屬性規(guī)范化，否則差距的距離度量將幾乎被收入屬性完全控制，即變差大的變量在距離中的貢獻(xiàn)大。

另一個問題是對象的某些屬性具有相關(guān)性時，距離度量如何計(jì)算。

這兩個問題同時存在時如何計(jì)算距離度量呢？這種情況下，采用廣義的歐氏距離，即Mahalanobis距離來解決此類問題。4.2.4Mahalanobis距離4.2傳統(tǒng)度量方法40Mahalanobis距離適用于當(dāng)屬性各量的量綱單位不同且適用于屬性間具有相關(guān)性的情況，其分布是近似高斯分布。通常，對象x和y間的Mahalanobis距離定義如下：4.2.4Mahalanobis距離∑是n×n的協(xié)方差矩陣，∑-1是協(xié)方差矩陣的逆。n是維度（分量數(shù)）。4.2傳統(tǒng)度量方法414.2.4Mahalanobis距離對傳統(tǒng)的歐氏距離的改進(jìn)，對線性變換是不變的，克服了歐氏距離受量綱和屬性間的相關(guān)性影響的兩個缺點(diǎn)，是一個很好的判別手段，在分類算法中較常用。但Mahalanobis距離的協(xié)方差矩陣難以確定，計(jì)算量較大，不適合大規(guī)模的數(shù)據(jù)集。4.2傳統(tǒng)度量方法42Jaccard距離用來度量兩個對象的重疊程度，其廣泛應(yīng)用于信息檢索和生物學(xué)分類中，在二值屬性情況下簡化為Jaccard系數(shù)，對于向量型對象，其相似度定義如下：4.2.5Jaccard距離4.2傳統(tǒng)度量方法434.2.5Jaccard距離Jaccard距離的幾何含義很清晰，反映了對象x和y的重疊程度，取值在[0，1]之間。若x、y不相交，則值為0。Jaccard距離可以定義為d(x,y)=1-s(x,y)，也就是說，Jaccard距離等于1減去x、y的交集與并集的比例。

一般來說，如果兩個對象具有相同的屬性時，則這兩個對象可能是相似的。Jaccard相似度系數(shù)是Jaccard系數(shù)的延伸，可用來測量兩個對象屬性之間的相似性。4.2傳統(tǒng)度量方法44

4.2.5Jaccard距離4.2傳統(tǒng)度量方法

45Jaccard距離d(x,y)為一個隨機(jī)最小哈希函數(shù)將x和y映射為不同值的概率。所以，三角不等式條件d(x,y)≤d(x,z)+d(z,y)可以變換為命題：如果h是一個隨機(jī)的最小哈希函數(shù)，那么h(x)≠h(y)的概率不高于h(x)≠h(z)的概率與h(z)≠h(y)的概率之和。然而，因?yàn)橹灰衕(x)≠h(y)，那么至少h(x)和h(y)中的一個一定與h(z)不同。即不可能都是h(z)，否則兩者顯然相等。因此上述命題為真。4.2.5Jaccard距離4.2傳統(tǒng)度量方法46給定一個向量空間，海明距離（HammingDistance）定義為兩個向量中不同分量的個數(shù)。海明距離是一種距離測度。海明距離非負(fù)，當(dāng)且僅當(dāng)兩個向量相等時，海明距離為0。海明距離也明顯滿足三角不等式：如果x和z有m個分量不同，z和y有n個分量不同，那么x和y中不同的分量個數(shù)不可能超過m+n個。向量的分量可來自任何集合。但比較時取值“等”或“不等”，為布爾值。4.2.6海明距離4.2傳統(tǒng)度量方法47海明距離往往應(yīng)用于布爾向量，即這些向量僅僅包含0和1。其定義如下：4.2.6海明距離向量x和y為二值向量，屬性為二值屬性，取值只能取0或1。示例：計(jì)算二值向量x=(1,0,1,0,1)和y=(0,1,0,0,1)的海明距離。這兩個向量的第1、2、3位元素不同，而其他元素均相同，所以其海明距離為3。4.2傳統(tǒng)度量方法48人類社會進(jìn)入了“大數(shù)據(jù)”時代。作為信息獲取的關(guān)鍵技術(shù)，數(shù)據(jù)挖掘、信息檢索和文本分類等信息處理技術(shù)應(yīng)運(yùn)而生。而作為這些技術(shù)的基礎(chǔ)，文檔相似性度量方法有著深刻的研究意義和廣泛的應(yīng)用前景。目前應(yīng)用最廣泛的文檔相似度度量方法是shingling。局部敏感哈希算法把搜索范圍控制在那些可能相似的項(xiàng)對方面，以減少相似度比較的項(xiàng)對。4.3大數(shù)據(jù)度量方法494.3.1文檔的shingling文檔的相似度度量，是判斷一個文件的內(nèi)容與另外一個文件的相似程度，在檢測抄襲文檔、鏡像頁面、同源新聞稿等方面有著廣泛的應(yīng)用。注意，這里的相似程度主要側(cè)重于字面上的相似，而非意義上的相似。Shingling算法將文檔視作是文字組成的字符串，一篇文檔就是一個字符串。文檔的shingle是文檔中一系列相鄰連接的檢索詞集合，提取文檔中shingle的過程就叫做shingling。給出一個文檔D，定義它的wshinglingS(D,w)為D中所有大小為w的不同shingle。4.3大數(shù)據(jù)度量方法504.3.1文檔的shingling如：假設(shè)文檔D為字符串(thepastisinthepast)，那么文檔D的2-shingle組成的集合為{(thepast)，(pastis)，(isin)，(inthe)}。

注意，子串(thepast)在文檔中出現(xiàn)兩次，但是在集合中只出現(xiàn)一次。對于空白串（空格、tab及回車等）的處理存在多種策略。用單個空格來代替任意長度的空白串很合理，采用這種做法，將覆蓋2個或更多詞的shingle和其他shingle區(qū)分開來。4.3大數(shù)據(jù)度量方法514.3.1文檔的shingling（1）Shingling算法的基本思路首先以窗口大小為w的滑動窗對全文本進(jìn)行shingle劃分，劃分好的shingle代表著全文的文本信息，然后對shingle文本進(jìn)行相似度計(jì)算。注意，在大規(guī)模文本中，文本劃分的shingle數(shù)目很龐大，需要很大的系統(tǒng)開支時間。要采取一定的抽取策略減少比較的shingle數(shù)量。4.3大數(shù)據(jù)度量方法524.3.1文檔的shingling（1）Shingling算法的基本思路抽取策略是：首先計(jì)算出兩兩比較文本中shingle的權(quán)重，然后設(shè)置一個權(quán)重門限值Pmin來選擇權(quán)重高的shingle，把經(jīng)過某種策略選擇的shingle，稱為特征shingle。為防止抽取的shingle數(shù)量太少而不足以比較相似性，設(shè)置抽取率r參數(shù)，把特征shingle數(shù)量限定在最小值以上。4.3大數(shù)據(jù)度量方法534.3.1文檔的shinglingShingling算法具體處理流程4.3大數(shù)據(jù)度量方法544.3.1文檔的shingling（2）中文分詞技術(shù)Shingle的概念開始是針對英文文檔提出的，劃分的最小單元是英文單詞，且有空格隔開。但中文文檔如果以字作為shingle劃分的最小單元，那必然導(dǎo)致許多毫無語義信息的冗余shingle，即待比較的shingle數(shù)目增多，算法相應(yīng)的計(jì)算時間復(fù)雜度增加，嚴(yán)重地降低文檔相似性度量的性能，因此中文分詞的準(zhǔn)確率直接影響shingle對文檔主題的反映程度。4.3大數(shù)據(jù)度量方法554.3.1文檔的shingling（2）中文分詞技術(shù)中文分詞技術(shù)有較多研究和軟件，較成功的是基于lucene2.0的IKAnalyzer，實(shí)現(xiàn)了以詞典分詞為基礎(chǔ)的正反向全切分算法，其召回率比普通的基于詞典的算法要大得多，且該軟件是開源的，應(yīng)用非?？旖?。此外，還有中科院和哈工大的中文分詞技術(shù)。4.3大數(shù)據(jù)度量方法564.3.1文檔的shingling

示例：待分詞的文本：安保人員在火車站臺獨(dú)自強(qiáng)守著崗位。

一般的分詞：公安|人員|在|火車|站臺|獨(dú)自|強(qiáng)|守|著|崗位IKAnalyzer：公安|公安人員|人員|在|火車|火車站|站臺|獨(dú)自|自強(qiáng)|守著|崗位4.3大數(shù)據(jù)度量方法574.3.1文檔的shingling（3）滑動窗口大小的設(shè)置Shingle生成是最為關(guān)鍵和最難的的一步?；瑒哟翱诖笮是組成特征元素的詞語組合中字的個數(shù)，它的大小直接決定了文檔的特征元素的總數(shù)，影響算法的時間復(fù)雜度。它還影響到字符串的語義包含度，因?yàn)槎鄠€詞語組合比起一個到兩個詞語的組合，其對主題的反映程度要大。4.3大數(shù)據(jù)度量方法584.3.1文檔的shingling（3）滑動窗口大小的設(shè)置

理論上，滑動窗口大小w可以取任意值。

但是，如果w太小，那么可以推測大部分長度為w的字符串會出現(xiàn)在大部分文檔中。

譬如，當(dāng)窗口大小w=1時，大部分Web網(wǎng)頁中都有很多常見字符，而其它字符很少，此時幾乎所有的Web網(wǎng)頁之間都有較高的文檔相似度。4.3大數(shù)據(jù)度量方法594.3.1文檔的shingling

選擇w值依賴于文檔的典型長度以及典型的字符表大小。注意：w應(yīng)足夠大，以保證任意給定的shingle出現(xiàn)在任意文檔中的概率較低。

對實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)表明:文檔篇幅較短時，如標(biāo)題、關(guān)鍵詞等文檔，w一般取1比較適宜。篇幅較長的正文文檔，w取2為最佳。句子級的相似文檔，即只有句子的組織順序改變，而句子中的詞語組織順序不變，w一般取大于2的值；段落級的相似文檔，中文文本w=5左右，可保留句子的位置信息。4.3大數(shù)據(jù)度量方法604.3.1文檔的shingling（4）基于權(quán)重的shingle抽取策略

計(jì)算shingle權(quán)重的公式：權(quán)重的歸一化：4.3大數(shù)據(jù)度量方法614.3.1文檔的shingling

抽取shingle時，只要設(shè)置一個shingle權(quán)重閾值Pmin。

當(dāng)某個shingle的權(quán)重P>Pmin時，就被選中為特征shingle。

為了防止抽取的shingle數(shù)目極少的情況出現(xiàn)，還設(shè)置了抽取率n，以保證最后供比對的shingle數(shù)量足夠。4.3大數(shù)據(jù)度量方法624.3.1文檔的shingling（5）相似度計(jì)算

基于shingle的算法最后供比較的是shingle字符串。利用Jaccard系數(shù)來計(jì)算文檔間的相似度。

文檔A和文檔B中相同的shingle數(shù)目與他們總的shingle數(shù)目的比值，該值越接近于1，說明兩文檔間的相似度就越高。4.3大數(shù)據(jù)度量方法634.3.1文檔的shingling記w-shingleS(D,w)={S1,S2,L

Sn}，其中Sn是文檔D中滑動窗口大小取w時所對應(yīng)的第n個shingle，并記{P1,P2,L

Pn}為{S1,S2,L

Sn}的權(quán)重系數(shù)，初始化為0，shingle在文檔中的出現(xiàn)頻率系數(shù)計(jì)算如下：

Pki：第i個文檔的第k個shingle的權(quán)重系數(shù)；

fki：第k個shingle在第i個文檔中出現(xiàn)的次數(shù)。4.3大數(shù)據(jù)度量方法644.3.1文檔的shingling

考慮到兩個供比較文檔的篇幅差異和包含關(guān)系，并參考包含相似度的計(jì)算方法，改進(jìn)的相似度計(jì)算公式如下：

sim(A,B)：A相對B的包含相似度，即A中有多少信息來自于B；Nab為A和B相同的shingle數(shù)目；

Na為A中的shingle數(shù)目，根據(jù)上式計(jì)算相似度所得的結(jié)果大于或等于l時直接取1，而小于l的保持不變。4.3大數(shù)據(jù)度量方法654.3.1文檔的shingling

假設(shè)A包含在B中，如果簡單地按照J(rèn)accard系數(shù)的計(jì)算方法，相似度就不會是l，即反應(yīng)不出A包含在B中；

而按照改進(jìn)過的相似度的計(jì)算方法，包含相似度的結(jié)果便是1，意義是A中所有的文檔信息來自于B，因此利用該式的計(jì)算方法還可以衡量出兩個文檔的相互包含度。4.3大數(shù)據(jù)度量方法664.3.1文檔的shingling（6）Shingling算法描述基于shingle的文檔相似度度量算法詳細(xì)描述如下：算法：基于shingle的文檔相似度度量算法。輸入：文檔集合D{d1,d2,…,dn}，初始化w、r、Simmin和Pmin。輸出：相似度大于Simmin的所有文檔。4.3大數(shù)據(jù)度量方法674.3.1文檔的shinglingfori=1tondo

對Di分詞：Di{wi1,wi2,…,win}fork=1toMd-w+1doSik=wk+wk+1+wk+2+wk+w-1endfor

根據(jù)歸一化權(quán)重計(jì)算公式計(jì)算Pi{p1,p2,…,pn}ifPi>PminSi選中為S`i

endififS`i的維度≥n*r

統(tǒng)計(jì)S`i的Fiendifendforfori=1tondoforj=i+1tondo

計(jì)算di和dj的包含相似度Simij和SimjiifSimij≥Simmin

判定第i個文檔相對第j個文檔是相似的

并輸出判定結(jié)果endifendforendfor4.3大數(shù)據(jù)度量方法684.3.1文檔的shingling算法只需在抽取shingle時計(jì)算權(quán)重，對以后的準(zhǔn)確度影響較小，且只要存儲每個文檔被抽取出的shingle即可，不需額外存儲空間。因?yàn)閟hingling算法是從N個文檔中兩兩比較文檔的相似度，因此其時間復(fù)雜度是O(N2)。4.3大數(shù)據(jù)度量方法694.3.2局部敏感哈希

有100萬篇文檔，約有

（5000億）個文檔對需比較，計(jì)算機(jī)計(jì)算每兩篇文檔之間的相似度為1微秒，需要6天時間才能計(jì)算所有的相似度。即使采用并行機(jī)制來減少實(shí)際消耗時間，也無法減少計(jì)算量。

但實(shí)際中往往需要得到那些最相似或者相似度超過某個下界的文檔對，這時只需要關(guān)注那些可能相似的文檔對，而不需要比較所有文檔對的相似度。解決這類問題的主要技術(shù)手段為局部敏感哈希算法（Locality-sensitivehashing，LSH）。4.3大數(shù)據(jù)度量方法704.3.2局部敏感哈希局部敏感哈希又稱為位置敏感哈希，其算法的基本思想是針對空間中的點(diǎn)，通過選用適當(dāng)?shù)木植棵舾泄：瘮?shù)對其進(jìn)行散列，使得散列后的數(shù)據(jù)仍保持原來數(shù)據(jù)的位置關(guān)系，即原來距離較近的點(diǎn)以較大的概率散列到相同的哈希桶中，反之，原來距離較遠(yuǎn)點(diǎn)以較小的概率散列到相同的桶中。4.3大數(shù)據(jù)度量方法714.3.2局部敏感哈希LSH算法索引數(shù)據(jù)的過程如圖。4.3大數(shù)據(jù)度量方法724.3.2局部敏感哈希

在給出局部敏感哈希算法的定義前，先給出以下幾個數(shù)學(xué)表示：

表示lp范數(shù)下的d維空間Rd，空間中的任意點(diǎn)x∈Rd，用

表示lp范數(shù)下的向量x，即

。令S=(X,d)是任意的度量空間，x∈X，以x為球心，r為半徑的球表示為

。

局部敏感哈希算法依賴于局部敏感哈希函數(shù)族，定義H是一個由

映射到集合Rd的哈希函數(shù)族，對于任意兩個點(diǎn)x,y∈Rd，對于任意的從哈希函數(shù)族H中隨機(jī)選擇的一個哈希函數(shù)h，分析h(x)=h(y)的可能性。函數(shù)族是(r1,r2,p1,p2)敏感的，如：

，則

；

，則

。其中，p1,p2,r1,r2

滿足不等式p1>p2和r1<r2

。4.3大數(shù)據(jù)度量方法734.3.2局部敏感哈希

由上述，如兩個空間向量距離小于r1，被散列到同一個桶的概率至少是p1，反之，如兩個空間向量距離大于r2，被散列到同一個桶的概率不會超過p2，因此可以通過選取以上定義中哈希函數(shù)族中帶有參數(shù)的一組映射，通過這種映射，盡量增大同時減小來使得距離較近的點(diǎn)更容易落在一個桶中。

對于參數(shù)k，定義一個函數(shù)族，

，其中

函數(shù)族g(·)就是由k個哈希函數(shù)組成的哈希函數(shù)組。對于一個向量x利用函數(shù)組g(·)中的k個哈希值h1(x),h2(x),…,hn(x)生成哈希索引鍵值。從

中隨機(jī)、獨(dú)立的選擇L個函數(shù)g1,g2,…,gL利用這一組函數(shù)創(chuàng)建哈希索引。4.3大數(shù)據(jù)度量方法744.3.2局部敏感哈希

根據(jù)局部敏感哈希函數(shù)的原理，首先用訓(xùn)練數(shù)據(jù)集P對算法進(jìn)行訓(xùn)練，創(chuàng)建局部敏感哈希索引：隨機(jī)地從局部敏感哈希函數(shù)族H中選取k個哈希函數(shù)

，組成新的哈希函數(shù)組

，再隨機(jī)從i=1,2,…L，再隨機(jī)地從所組成的哈希函數(shù)組中選擇L個局部敏感哈希函數(shù)g1,g2,…,gL對訓(xùn)練集合中的每一個向量x∈P進(jìn)行散列，將其哈希鍵值存儲在函數(shù)值gi(x)對應(yīng)的桶中，建立哈希表索引。在此過程中，需要合理地選擇k和L，算法如下。4.3大數(shù)據(jù)度量方法754.3.2局部敏感哈希算法：局部敏感哈希算法的數(shù)據(jù)處理存儲過程。輸入：點(diǎn)集合P{p1,p2,…,pn}，初始化L和k。輸出：哈希表Ti，i=1,2,…,L。方法：fori=1toLdo

產(chǎn)生隨機(jī)哈希函數(shù)gi=(h1i,h2i,…,hki)//其中h1i,h2i,…,hki從LSH函數(shù)族H中隨機(jī)地選擇得到

通過gi初始化哈希表Ti

endforfori=1toLdoforj=1tondo

在哈希表Ti中的桶gi(pj)中存儲點(diǎn)pj

endforendfor

4.3大數(shù)據(jù)度量方法764.3.2局部敏感哈希算法：局部敏感哈希算法的查詢過程。輸入：待查詢點(diǎn)q，哈希表Ti，i=1,2,…,L，初始化Simmin。輸出：與q關(guān)聯(lián)的數(shù)據(jù)。方法：

初始化數(shù)據(jù)集S為空

fori=1toLdo

回收存儲在桶gi(q)中的數(shù)據(jù)(剔除重復(fù)數(shù)據(jù))，放入S中

endfor

fori=1toS中的數(shù)據(jù)個數(shù)do

forj=i+1tondo

計(jì)算si和q的相似度Simi

ifSimi≥Simmin

判定si和q是相似的報出siendifendforendfor4.3大數(shù)據(jù)度量方法774.3.2局部敏感哈希

構(gòu)建哈希函數(shù)族是局部敏感哈希算法中最基本的要素。選擇不同的哈希函數(shù)，對算法的處理有很大的影響。

哈希函數(shù)族構(gòu)建的原則：如果兩個點(diǎn)相距很近，那么，在經(jīng)過映射操作后，它們?nèi)匀幌嗑嗪芙?/p>

根據(jù)應(yīng)用的情況不同，在不同的距離測度下構(gòu)造的哈希函數(shù)族也不同。

典型的局部敏感哈希函數(shù)族分別是：面向海明距離的哈希函數(shù)族、面向歐式距離的哈希函數(shù)族、面向Jaccard距離的哈希函數(shù)族、面向余弦距離的哈希函數(shù)族。4.3大數(shù)據(jù)度量方法784.3.2局部敏感哈希（1）面向海明距離的哈希函數(shù)族定義：i是向量x中一個隨機(jī)坐標(biāo)，對于每一個點(diǎn)，將它轉(zhuǎn)換到海明空間。

通過將x=(x1,x2,…,xd)轉(zhuǎn)化為二進(jìn)制向量v(x)，令M為點(diǎn)集中所有點(diǎn)坐標(biāo)中的最大值，有

Unary(xi)是由一連串連續(xù)的xi個1和之后的M-xi個0組成的。

這樣，向量v(x)就成為了海明空間Hmd中的點(diǎn)。例：若最大指標(biāo)值是7，一個三維點(diǎn)x的坐標(biāo)是(3,5,7)，則向量v(x)4.3大數(shù)據(jù)度量方法794.3.2局部敏感哈希

應(yīng)用上述局部敏感哈希函數(shù)就可以進(jìn)行數(shù)據(jù)處理了。根據(jù)局部敏感哈希算法，形成L個哈希表，每個哈希表選擇k比特位大小的集合。對于每一個點(diǎn)v(x)，哈希函數(shù)族定義為

，函數(shù)族g就是

式中

是從上述哈希函數(shù)族中隨機(jī)選擇的。

顯然，面向海明距離下的哈希函數(shù)族對高維數(shù)據(jù)進(jìn)行散列的過程就是將多維空間點(diǎn)嵌入到海明空間的過程。采用這種局部敏感哈希函數(shù)族，過程簡單容易實(shí)現(xiàn)是其優(yōu)點(diǎn)，但當(dāng)輸入數(shù)據(jù)集和最大坐標(biāo)值比較大時，嵌入后得到的集合的維數(shù)相對較大，這會消耗很大的內(nèi)存和處理成本。4.3大數(shù)據(jù)度量方法804.3.2局部敏感哈希（2）面向Jaccard距離的哈希函數(shù)族

不同于海明距離，Jaccard距離被用來衡量兩個集合的相似性。Jaccard局部敏感哈希函數(shù)也稱為最小哈希函數(shù)，是將集合中的元素進(jìn)行隨機(jī)獨(dú)立置換然后取最小。對于任意集合

和任意x∈A，F(xiàn)屬于Sn是最小獨(dú)立的，在F中隨機(jī)選擇P有

即集合A中的所有元素具有相同的概率轉(zhuǎn)化為集合A在P下的最小的元素。此時有Jaccard局部敏感哈希函數(shù)為4.3大數(shù)據(jù)度量方法814.3.2局部敏感哈希示例：

給定的兩個文檔A和B在經(jīng)過Jaccard函數(shù)散列后，只有在

時，才認(rèn)為向量A和B沖突即z=h(A)=h(B)，在Jaccard距離定義的相似度下，向量A和B沖突的概率為4.3大數(shù)據(jù)度量方法824.3.2局部敏感哈希（3）面向歐氏距離的哈希函數(shù)族

面向海明距離的哈希函數(shù)族只能應(yīng)用在范數(shù)L1的距離下，這需要空間的嵌入。為了將局部敏感哈希方法應(yīng)用到歐氏空間中，穩(wěn)定分布被應(yīng)用于哈希函數(shù)中，這使得局部敏感哈希算法可以在距離度量

范數(shù)下應(yīng)用，大大增強(qiáng)了算法的實(shí)用性。哈希函數(shù)表示如下：

x，r是Rd中的d維向量，參數(shù)b是隨機(jī)均勻地從[0,w]選擇的實(shí)數(shù)。該方法可泛化為任何距離，而

，已證是有效的。對于任意的d，須從d穩(wěn)定分布中隨機(jī)選取變量構(gòu)成向量r，并用上述方式對高維數(shù)據(jù)降維處理。4.3大數(shù)據(jù)度量方法834.3.2局部敏感哈希（4）面向余弦距離的哈希函數(shù)族

隨機(jī)地從Rd空間中選擇一個單位向量u，定義hu(x)=sign(ux)。這個哈希函數(shù)可以視作使用一個隨機(jī)選擇的超平面將空間劃分為兩半，單位向量u是這個超平面的法向量。給定兩個向量x和y，其沖突的可能性為:

θ是余弦的距離。4.3大數(shù)據(jù)度量方法84異常檢測又稱為異常數(shù)據(jù)挖掘或離群點(diǎn)檢測，就是找出這些行為不同于預(yù)期對象的過程。異常檢測在數(shù)據(jù)挖掘的四大任務(wù)中占據(jù)著非常重要的地位，與預(yù)測模型、聚類分析和關(guān)聯(lián)分析相比，它顯得更有價值，更能體現(xiàn)數(shù)據(jù)挖掘的初衷。4.3大數(shù)據(jù)度量方法85

如，一萬個正常的記錄可能只蘊(yùn)含一條規(guī)則，而十個異常記錄很可能就包含了十條不同的規(guī)則。異常檢測在某些領(lǐng)域很有應(yīng)用價值，這些領(lǐng)域包括保險和信用卡欺騙、貸款審批、藥物研究、醫(yī)療分析、消費(fèi)者行為分析、氣象預(yù)報、金融領(lǐng)域客戶分類、網(wǎng)絡(luò)安全、傳感器/視頻網(wǎng)絡(luò)監(jiān)視和入侵檢測以及文本挖掘中的新穎主題發(fā)現(xiàn)等。

異常檢測問題有兩個子問題構(gòu)成：1.定義在一個數(shù)據(jù)集中不一致或異常的數(shù)據(jù)；2.找出異常的有效挖掘方法。

異常檢測問題可概括為度量數(shù)據(jù)偏離的程度和有效發(fā)現(xiàn)異常的問題。4.3大數(shù)據(jù)度量方法86

進(jìn)行異常檢測首先要定義異常（Outlier）。依賴于相關(guān)的假設(shè)。

從異常檢測算法對異常的定義：異常是既不屬于聚類也不屬于背景噪聲的點(diǎn)，其行為與正常的行為有很大不同。

從聚類算法對異常定義：異常是聚類嵌于其中的背景噪聲。

然而也有些通用的定義能符合不同類型的數(shù)據(jù)和檢測方法。為了在對比各種異常算法時提供統(tǒng)一標(biāo)準(zhǔn)，采用Hawkins（1980年）的定義：“在數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制”。4.3大數(shù)據(jù)度量方法87示例：在圖中，大部分對象都粗略地服從于高斯分布。然而，區(qū)域R中的對象顯著不同。它不太可能與數(shù)據(jù)集中的其他對象服從相同的分布。因此，在該數(shù)據(jù)集中，R中的對象是異常。4.4異常檢測88

異常不同于噪聲數(shù)據(jù)。噪聲是被觀測變量的隨機(jī)誤差或方差。

一般而言，根據(jù)異常判斷的標(biāo)準(zhǔn)以及異常和其他數(shù)據(jù)之間的關(guān)系，可以將異常分為三類，分別是：點(diǎn)異常、情境異常（條件異常）和聚集異常。4.4異常檢測89（1）點(diǎn)異常

在給定的數(shù)據(jù)集中，如果一個數(shù)據(jù)對象明顯偏離數(shù)據(jù)集中的其余對象，則稱該數(shù)據(jù)對象為點(diǎn)異常（GlobalOutlier）。點(diǎn)異常有時也稱為全局異常點(diǎn)或全局離群點(diǎn)，是最簡單的一類異常。大部分異常檢測方法都旨在找出點(diǎn)異常。

在許多應(yīng)用中，點(diǎn)異常檢測都是非常重要的。4.4異常檢測90（2）情境異常

“今天的溫度是2℃。這是一個異常嗎？”這依賴于時間和地點(diǎn)。如圖，如是在南京的冬天，這是正常溫度，而如是南京的夏天，這是異常。與點(diǎn)異常不同，溫度是否是異常依賴于情境——時間、地點(diǎn)和可能的其他因素。4.4異常檢測91

同樣的例子有一個人的身高為210cm，在普通人中認(rèn)為這是一個異常，而在籃球運(yùn)動員中這身高是普遍的。

在給定的數(shù)據(jù)集中，一個數(shù)據(jù)從本身的屬性值來看屬于正常范圍，但是在特定的情境中這個屬性值卻不正常，則稱這個數(shù)據(jù)對象為情境異常（ContextualOutlier）。

情境異常又稱為條件異?；蚯榫畴x群點(diǎn)，因?yàn)榍榫钞惓Ｐ枰紤]的不僅僅是數(shù)據(jù)的屬性值本身，而且考慮了數(shù)據(jù)出現(xiàn)的情境。

因此，在情境異常中，情境必須作為問題定義的一部分加以說明。4.4異常檢測92一般地，在情境異常檢測中，數(shù)據(jù)對象的屬性可劃分為兩組：情境屬性：數(shù)據(jù)對象的情境屬性定義對象的情境。在溫度例子中，情境屬性是時間和地點(diǎn)。行為屬性：定義對象的特征，并用來評估對象關(guān)于它所處的情境是否是異常。在溫度例子中，行為屬性可以是溫度、濕度、氣壓。

在條件異常檢測中，對象是否異常不僅依賴行為屬性，還依賴情境屬性。行為屬性的狀態(tài)在某種情境下可能是異常，在另一種情境下不是異常。

點(diǎn)異常檢測是情境異常檢測的一個特例，即情境屬性集為空，點(diǎn)異常檢測使用整個數(shù)據(jù)集作為情境。情境異常分析為用戶提供了靈活性，因?yàn)橛脩艨梢栽诓煌那榫诚驴紤]異常，這在許多應(yīng)用中是非常需要的。

4.4異常檢測93示例：在信用卡欺騙檢測中，除點(diǎn)異常外，分析人員還可考慮不同情境下的異常。如一位顧客使用了信用卡額度的90%，其屬于具有低信用額度的顧客群，則不應(yīng)視作異常。而高收入人群顧客的類似行為可被視為異常，可帶來商機(jī)——提高其信用額度可能帶來新的收益。

除了對象在行為屬性空間對多數(shù)的偏離度量外，應(yīng)用中情境異常檢測的質(zhì)量還依賴于情境屬性的意義。

情境屬性可視做背景知識的一部分，多由領(lǐng)域?qū)＜掖_定。大多數(shù)應(yīng)用中，得到足夠的信息確定情境屬性或收集高質(zhì)量的情境數(shù)據(jù)都非易事。4.4異常檢測94（3）聚集異常當(dāng)一個數(shù)據(jù)的屬性值在正常范圍內(nèi)，且從情境看也屬于正常時，它也有成為異常的可能。因?yàn)楫惓５某霈F(xiàn)不僅要考慮此數(shù)據(jù)的屬性值、數(shù)據(jù)所在的情境，也要考慮與之關(guān)聯(lián)的多個數(shù)據(jù)組成的模式與整體模式是否符合。在給定的數(shù)據(jù)集中，如果某些對象作為整體明顯地偏離整個數(shù)據(jù)集，則稱這些數(shù)據(jù)對象的集合為聚集異常（CollectiveOutlier）。聚集異常又稱為集體異常點(diǎn)或集體離群點(diǎn)。注意，此時，這個集合中的單個數(shù)據(jù)對象可能都不是異常。4.4異常檢測95示例：在圖中，黑色對象作為整體形成一個聚集異常，因?yàn)檫@些對象的密度比數(shù)據(jù)集中的其他對象高得多。然而，每個黑色對象個體對于整個數(shù)據(jù)集來看并非異常。

聚集異常檢測有許多應(yīng)用。

與點(diǎn)異?；蚯榫钞惓z測不同，在聚集異常檢測中，不僅必須考慮個體對象的行為，而且還要考慮對象群組的行為。因此，為了檢測聚集異常，需要關(guān)于對象之間聯(lián)系的背景知識，如對象之間的距離或相似性度量方法。4.4異常檢測96綜合來看，點(diǎn)異常是異常檢測的基礎(chǔ)，情境異常和聚集異常是點(diǎn)異常的延伸，分別從多個屬性的角度和多個數(shù)據(jù)的角度擴(kuò)展了點(diǎn)異常。首先從點(diǎn)異常檢測技術(shù)的研究出發(fā)，然后將提出的技術(shù)應(yīng)用到情境異常和聚集異常的檢測中。異?？赡苡捎跍y量、輸入錯誤或系統(tǒng)運(yùn)行錯誤而造成，也可能是由數(shù)據(jù)內(nèi)在特性引起的，或因客體的異常行為所導(dǎo)致。由于異常產(chǎn)生的機(jī)制是不確定的，因此，異常檢測算法檢測出的“異?！笔欠裾嬲貙?yīng)為實(shí)際的異常行為，不是由異常檢測算法來說明、解釋的，只能由領(lǐng)域?qū)＜襾斫忉尅?.4異常檢測97異常檢測算法只能從數(shù)據(jù)體現(xiàn)的規(guī)律角度為用戶提供可疑的數(shù)據(jù)，以便用戶引起特別的注意并最后確定是否為真正的異常。從上世紀(jì)80年代起，異常檢測問題在統(tǒng)計(jì)學(xué)領(lǐng)域中得到了廣泛的研究。隨著應(yīng)用領(lǐng)域的擴(kuò)展好更多方法的引入，這一分支得到越來越多的關(guān)注。研究人員不斷拓展異常的定義，涵蓋更多類型的異常。已提出了許多刻畫異常的定義和相應(yīng)的檢測方法。這些方法依據(jù)使用的主要技術(shù)路線大體可分為基于統(tǒng)計(jì)的方法、基于距離的方法、基于密度的方法、基于聚類的方法、基于分類的方法、基于深度的方法以及其他方法（基于小波變換的方法、基于圖的方法、基于模式的方法、基于神經(jīng)網(wǎng)絡(luò)的方法等）。4.4異常檢測98依據(jù)類信息（正?；虍惓＃┛衫玫某潭龋惓Ｍ诰蚩梢苑譃橐韵氯N基本方法：1.無監(jiān)督的異常檢測方法，在實(shí)際情況中，沒有提供類編號；2.有監(jiān)督的異常檢測方法，要求存在異常點(diǎn)和正常點(diǎn)的訓(xùn)練集；3.半監(jiān)督的異常檢測方法，訓(xùn)練數(shù)據(jù)包含被標(biāo)記的正常數(shù)據(jù)，但是沒有關(guān)于異常對象的信息。本文將主要從技術(shù)路線介紹幾種典型的異常檢測方法。4.4異常檢測994.4.1基于統(tǒng)計(jì)的檢測方法統(tǒng)計(jì)學(xué)方法是最早應(yīng)用于異常檢測的一種計(jì)算方法，它通常假設(shè)給定的數(shù)據(jù)集服從一個隨機(jī)分布（如正態(tài)分布等），用不一致性測試(DiscordancyTest)識別異常。這類方法大部分是從針對于不同分布的異常檢測方法發(fā)展起來的，它們通常使用分布來擬合數(shù)據(jù)集，假定所給定的數(shù)據(jù)集存在一個分布或概率模型（如正態(tài)分布或泊松分布），數(shù)據(jù)集中的正常數(shù)據(jù)由該分布或模型產(chǎn)生，將與模型不一致（即分布不符合）的數(shù)據(jù)標(biāo)識為異常數(shù)據(jù)。4.4異常檢測1004.4.1基于統(tǒng)計(jì)的檢測方法基于統(tǒng)計(jì)分布的異常檢測方法在應(yīng)用時依賴于數(shù)據(jù)分布，如參數(shù)分布（如均值或方差）、期望異常點(diǎn)的數(shù)目（置信度區(qū)間）。正常數(shù)據(jù)出現(xiàn)在該分布或模型的高概率區(qū)域中，而低概率區(qū)域中的數(shù)據(jù)則認(rèn)為是異常。有許多不同的方法來學(xué)習(xí)分布模型。一般而言，根據(jù)如何指定和如何學(xué)習(xí)模型，異常檢測的統(tǒng)計(jì)學(xué)方法可以劃分成兩個主要類型：參數(shù)方法和非參數(shù)方法。4.4異常檢測1014.4.1基于統(tǒng)計(jì)的檢測方法

參數(shù)方法假定正常的數(shù)據(jù)對象由一個以q為參數(shù)的參數(shù)分布產(chǎn)生。該參數(shù)分布的概率密度函數(shù)f(x,q)給出對象x被該分布產(chǎn)生的概率。該值越小，概率越低，x越可能是異常。

非參數(shù)方法并不假定先驗(yàn)統(tǒng)計(jì)模型，而是試圖從輸入數(shù)據(jù)確定模型。

注意，大多數(shù)非參數(shù)方法并不假定模型是完全無參的（完全無參假定將使得從數(shù)據(jù)學(xué)習(xí)模型是不可能的）。相反，非參數(shù)方法通常假定參數(shù)的個數(shù)和性質(zhì)都是靈活的，不預(yù)先確定。

非參數(shù)方法的例子包括直方圖和核密度估計(jì)。4.4異常檢測1024.4.1基于統(tǒng)計(jì)的檢測方法（1）參數(shù)方法

異常檢測的參數(shù)方法有許多，其中有些方法簡單、實(shí)用。a)基于正態(tài)分布的一元異常點(diǎn)檢測

僅涉及一個屬性或變量的數(shù)據(jù)稱為一元數(shù)據(jù)。早期的一元異常探測方法大多都依賴假設(shè)：數(shù)據(jù)的基本分布是已知的、相同的、獨(dú)立的。

而且，探測一元異常點(diǎn)的許多不一致的檢驗(yàn)進(jìn)一步假定，分布參數(shù)和異常點(diǎn)的期望類型也是已知的。

簡單起見，通常假定數(shù)據(jù)由一個正態(tài)分布產(chǎn)生。然后，可以由輸入數(shù)據(jù)學(xué)習(xí)正態(tài)分布的參數(shù)，并把低概率的點(diǎn)識別為異常點(diǎn)。4.4異常檢測1034.4.1基于統(tǒng)計(jì)的檢測方法利用統(tǒng)計(jì)學(xué)中最常用的正態(tài)分布來檢測異常點(diǎn)。標(biāo)準(zhǔn)正態(tài)分布N(0.1)的概率密度函數(shù)如圖所示。來自N(0.1)分布的對象出現(xiàn)在分布兩端尾部的機(jī)會很小。例如，數(shù)據(jù)落在±3標(biāo)準(zhǔn)差的中心區(qū)域以外的概率僅有0.0027。更一般地，如果x是屬性值，c是給定的正數(shù)，則

的概率隨c增加而迅速減小。4.4異常檢測1044.4.1基于統(tǒng)計(jì)的檢測方法

設(shè)

，部分的c值和a值的對應(yīng)表ca10.31731.50.133620.04552.50.012430.00273.50.000540.00014.4異常檢測1054.4.1基于統(tǒng)計(jì)的檢測方法如果一個感興趣的（正常對象的）屬性的分布是具有均值μ和標(biāo)準(zhǔn)差σ的正態(tài)分布，即N(μ,σ2)分布，則可通過變換z=(x-μ)/σ轉(zhuǎn)換為標(biāo)準(zhǔn)正態(tài)分布N(0,1)。通常，m和s是可以通過樣本均值和樣本標(biāo)準(zhǔn)差來估計(jì)的。實(shí)際情況下，當(dāng)觀測數(shù)據(jù)很多時，這種估計(jì)的效果很好；另一方面，由概率統(tǒng)計(jì)中的大數(shù)定律可知，在大樣本的情況下可以用正態(tài)分布近似其他分布。4.4異常檢測1064.4.1基于統(tǒng)計(jì)的檢測方法

這種思想在質(zhì)量控制中廣泛應(yīng)用，下圖是質(zhì)量控制示意圖，中心線是觀測值的預(yù)測值，μ±3σ對應(yīng)上下控制線，μ±2σ對應(yīng)上、下警告線。4.4異常檢測1074.4.1基于統(tǒng)計(jì)的檢測方法對于觀測樣本

：如果此點(diǎn)在上、下警告線之間的區(qū)域內(nèi)，則表示生產(chǎn)或測定過程處于受控狀態(tài)，生產(chǎn)過程或樣本分析結(jié)果有效。如果此點(diǎn)超出上、下警告線，但仍在上、下控制線之間的區(qū)域內(nèi)，提示質(zhì)量開始變劣，可能存在“失控”傾向，應(yīng)進(jìn)行初步檢查，并采取相應(yīng)的校正措施。如此點(diǎn)落在上、下控制線外的區(qū)域，表示生產(chǎn)或測定過程“失控”，生產(chǎn)的是廢品或觀測樣本無效。應(yīng)立即檢查并糾正。4.4異常檢測1084.4.1基于統(tǒng)計(jì)的檢測方法示例：假設(shè)某城市過去10年中8月份的平均氣溫按增序排列為23.0℃、28.6℃、28.6℃、28.7℃、28.9℃、28.9℃、29.0℃、29.0℃、29.1℃和29.2℃。假定平均溫度服從正態(tài)分布，由兩個參數(shù)決定：均值μ和標(biāo)準(zhǔn)差σ。4.4異常檢測1094.4.1基于統(tǒng)計(jì)的檢測方法計(jì)算得到4.4異常檢測1104.4.1基于統(tǒng)計(jì)的檢測方法

由此，有

最大偏離值為23.0℃，偏離估計(jì)的均值5.3℃。在正態(tài)分布的假定下，區(qū)域

包含99.73%的數(shù)據(jù)。由于5.2/1.78=2.97>2.7，23.0℃被該正態(tài)分布產(chǎn)生的概率小于0.135%，因此它被識別為異常點(diǎn)。

另一種使用正態(tài)分布的一元異常點(diǎn)檢測的統(tǒng)計(jì)學(xué)方法是Grubb檢驗(yàn)（又稱為最大標(biāo)準(zhǔn)殘差檢驗(yàn)）。對于數(shù)據(jù)集中的每個對象x，定義z分?jǐn)?shù)（z-score）為是輸入的均值，s是標(biāo)準(zhǔn)差。4.4異常檢測1114.4.1基于統(tǒng)計(jì)的檢測方法如果對象x滿足

則對象x被判為異常點(diǎn)。其中，

是顯著水平α/(2N)下的t分布的值，N是數(shù)據(jù)集中對象的個數(shù)。4.4異常檢測1124.4.1基于統(tǒng)計(jì)的檢測方法b)多元異常點(diǎn)檢測

涉及兩個或多個屬性或變量的數(shù)據(jù)稱為多元數(shù)據(jù)。大部分多元數(shù)據(jù)的處理方法可以由一元異常點(diǎn)檢測方法擴(kuò)充得到。其核心思想是把多元異常點(diǎn)檢測任務(wù)轉(zhuǎn)換成一元異常點(diǎn)檢測問題。

示例：使用Mahalanobis距離檢測多元異常點(diǎn)。

對于一個多元數(shù)據(jù)集，設(shè)

為均值向量。對于數(shù)據(jù)集中的對象o，從o到

的Mahalanobis距離為

，S是協(xié)方差矩陣。

4.4異常檢測1134.4.1基于統(tǒng)計(jì)的檢測方法是一元變量，可對它進(jìn)行Grubb檢驗(yàn)。因此，可以按如下方法對多源異常點(diǎn)檢測任務(wù)進(jìn)行變換：計(jì)算多元數(shù)據(jù)集的均值向量。對于每個對象o，計(jì)算從o到

的Mahalanobis距離

。在變換后的一元數(shù)據(jù)集

中檢測異常點(diǎn)。如果

被確定為異常點(diǎn)，則o也被視作異常點(diǎn)。4.4異常檢測1144.4.1基于統(tǒng)計(jì)的檢測方法

示例：使用χ2統(tǒng)計(jì)量的多元異常點(diǎn)檢測。

在正態(tài)分布的假定下，χ2統(tǒng)計(jì)量也可用來捕獲多元異常點(diǎn)。對對象o，χ2統(tǒng)計(jì)量是：

oi是o在第i維上的值

Ei是所有對象在第i維上的均值，

n是維度。

如果對象的χ2統(tǒng)計(jì)量很大，則該對象是異常點(diǎn)。4.4異常檢測1154.4.1基于統(tǒng)計(jì)的檢測方法c)使用混合參數(shù)分布

假定數(shù)據(jù)是由正態(tài)分布產(chǎn)生的，這種假定在許多情況下很有效。然而，實(shí)際數(shù)據(jù)有時是很復(fù)雜的，這時該假定過于簡單，則假定數(shù)據(jù)是由混合參數(shù)分布產(chǎn)生的。下圖是一個復(fù)雜的數(shù)據(jù)集，有兩個大簇C1和C2。4.4異常檢測1164.4.1基于統(tǒng)計(jì)的檢測方法

這時，假定數(shù)據(jù)是由一個正態(tài)分布產(chǎn)生的效果不好。因?yàn)槿羰沁@樣假設(shè)，分布估計(jì)的均值將落在這兩個簇之間，而不是任何一個簇的內(nèi)部。此時，這兩個簇之間的對象離均值很近，不可能被檢測為異常點(diǎn)。

為了克服這一困難，假定正常的數(shù)據(jù)對象由多個正態(tài)分布產(chǎn)生（這里是兩個）。也就是說，假定兩個正態(tài)分布θ(μ1,σ1)和θ(μ2,σ2)。對于數(shù)據(jù)集中的任意對象o，o被這兩個分布產(chǎn)生的概率為和分別是θ1和θ2的概率密度函數(shù)。4.4異常檢測1174.4.1基于統(tǒng)計(jì)的檢測方法可使用期望最大化（EM）算法，由該數(shù)據(jù)學(xué)習(xí)參數(shù)m1,s1,m2,s2。每個簇都用學(xué)習(xí)得到的正態(tài)分布表示。如果一個對象o不屬于任何簇，即它被這兩個分布的組合產(chǎn)生的概率很低，則被檢測為異常點(diǎn)。一般而言，期望最大化算法（Expectation-Maximization，EM）算法是一種框架，它逼近統(tǒng)計(jì)模型參數(shù)的最大后驗(yàn)或最大似然估計(jì)。4.4異常檢測1184.4.1基于統(tǒng)計(jì)的檢測方法在模糊或基于概率模型的聚類的情況下，EM算法從初始參數(shù)集出發(fā)，并且迭代直到聚類收斂或改變充分?。ㄐ∮谝粋€預(yù)先設(shè)定的閾值）為止。每次迭代包括兩個步驟：期望步（E步）：給定當(dāng)前的簇中心，每個對象都被指派給簇中心離該對象最近的簇。這里，期望每個對象都屬于離它最近的簇。最大化步（M步）：給定簇指派，對于每個簇，算法調(diào)整其中心，使得指派到該簇的對象到該新中心的距離之和最小化。也就是說，將指派到一個簇的對象的相似度最大化。4.4異常檢測1194.4.1基于統(tǒng)計(jì)的檢測方法示例：使用EM算法計(jì)算圖中混合參數(shù)分布數(shù)據(jù)集的均值和標(biāo)準(zhǔn)差。假設(shè)存在有兩個簇，隨機(jī)地選擇兩個點(diǎn)作為兩個簇的初始中心，如c1=a，c2=b。4.4異常檢測1204.4.1基于統(tǒng)計(jì)的檢測方法

每一次迭代執(zhí)行期望步和最大化步的細(xì)節(jié)如下：

在E步中，對于每個點(diǎn)，計(jì)算它屬于每個簇的隸屬度。對于任意點(diǎn)o，分別以隸屬權(quán)重

把o指派到c1和c2，其中dist(x,y)是歐式距離。

其理由是，如果dist(o,c1)比dist(o,c2)小，表明o更靠近c(diǎn)1，則o

關(guān)于c1的隸屬度高。也可以規(guī)范化隸屬度，使得一個對象的隸屬度之和等于1。4.4異常檢測1214.4.1基于統(tǒng)計(jì)的檢測方法

對于點(diǎn)a，有=1，=0，即a互斥地屬于c1，其中，

表示對象a在簇c1的隸屬度。對于點(diǎn)b，有=0，=1。對于點(diǎn)c，有=41/(45+41)=0.48，=45/(45+41)=0.52。其他點(diǎn)的隸屬度顯示在劃分矩陣中迭代E步M步1234.4異常檢測1224.4.1基于統(tǒng)計(jì)的檢測方法

在M步中，根據(jù)劃分矩陣重新計(jì)算簇的中心，使得指派到該簇的對象到新中心的距離之和最小化。新的中心應(yīng)該調(diào)整為其中，N為數(shù)據(jù)集中數(shù)據(jù)的個數(shù)，j=1,2。在這個例子中4.4異常檢測1234.4.1基于統(tǒng)計(jì)的檢測方法

重復(fù)該迭代，每次迭代包含一個E步和一個M步。下表顯示了前3次迭代的結(jié)果。當(dāng)簇中心收斂或變化足夠小時，算法停止。此時兩個簇收斂中心點(diǎn)的位置即為兩個正態(tài)分布的均值向量。迭代E步M步1234.4異常檢測1244.4.1基于統(tǒng)計(jì)的檢測方法

每個簇可以用學(xué)習(xí)得到的正態(tài)分布表示，對于單個簇，可以用多元異常點(diǎn)檢測方法檢測對象是否屬于該簇。當(dāng)對象o不屬于任何簇，將被檢測為異常點(diǎn)，即它被這兩個分布的組合產(chǎn)生的概率很低。

圖中，大部分?jǐn)?shù)據(jù)對象都在簇C1或C2中。其他對象代表噪聲，均勻地分布在數(shù)據(jù)空間中。一個小簇C3非?？梢?，因?yàn)樗豢拷鼉蓚€主要的簇C1和C2中的任何一個。C3中的對象也將被檢測為異常點(diǎn)。4.4異常檢測1254.4.1基于統(tǒng)計(jì)的檢測方法

注意，無論假定給定的數(shù)據(jù)集服從一個正態(tài)分布，還是服從多個分布的混合分布，識別C3中的點(diǎn)為異常點(diǎn)都是非常困難的。這是因?yàn)橛捎?/p>