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

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

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

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

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

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

4.1.1對象與屬性類型4.1相似度度量5第五頁，共一百九十五頁，編輯于2023年，星期日

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

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

盡管一個名詞型屬性可以取整數(shù)值，但不能將其視為數(shù)值屬性，因為，并不會定量地去使用這些整數(shù)。名詞型屬性不是定量的，不具備有意義的順序。計算該屬性的均值或中值是沒有意義的。4.1.1對象與屬性類型4.1相似度度量6第六頁，共一百九十五頁，編輯于2023年，星期日（3）二值（Binary）屬性

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

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

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

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

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

4.1.1對象與屬性類型4.1相似度度量12第十二頁，共一百九十五頁，編輯于2023年，星期日如果屬性不是離散的，稱之為連續(xù)的。通常，術(shù)語“數(shù)值屬性”與“連續(xù)屬性”通常可以互換使用。實際上，實數(shù)值一般用有限位數(shù)字表示，而連續(xù)屬性一般用浮點數(shù)表示。4.1.1對象與屬性類型4.1相似度度量13第十三頁，共一百九十五頁，編輯于2023年，星期日

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

大多數(shù)時候，相似度可以標準化為：4.1相似度度量14第十四頁，共一百九十五頁，編輯于2023年，星期日4.1.2相似度度量定義通常，使用相異度（而不是相似度）作為度量標準。相異度用

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

距離也具有對稱性：4.1相似度度量15第十五頁，共一百九十五頁，編輯于2023年，星期日

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

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

4.1.4屬性之間的相似度度量4.1相似度度量18第十八頁，共一百九十五頁，編輯于2023年，星期日

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

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

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

，以空間中的兩個點作為參數(shù)，輸出實數(shù)值。該函數(shù)必須滿足下列準則：1)非負性：d(x,y)≥0，非負。2)同一性：d(x,y)=0，當且僅當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第二十一頁，共一百九十五頁，編輯于2023年，星期日

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

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

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

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

滿足以上準則的距離函數(shù)稱為度量（Metric）。注意非負性被其他三個性質(zhì)所蘊含。4.1.5對象之間的相似度度量4.1相似度度量22第二十二頁，共一百九十五頁，編輯于2023年，星期日

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

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

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

對象之間的相似度計算涉及描述對象的屬性類型，需要將不同屬性上的相似度整合成一個總的相似度來表示。4.2傳統(tǒng)度量方法23第二十三頁，共一百九十五頁，編輯于2023年，星期日

二值（Binary）屬性只有兩種狀態(tài)：0表示屬性不存在，1表示屬性存在。假設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第二十四頁，共一百九十五頁，編輯于2023年，星期日

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

f11+

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

f10為取值不同的屬性個數(shù)計算屬性在兩個對象中都存在和都不存在的情況。如，查找某次考試中學生答案相似的題，即都答對的題和都答錯的題。4.2傳統(tǒng)度量方法25第二十五頁，共一百九十五頁，編輯于2023年，星期日

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

取值1比取值0更重要、更有意義的二值屬性具有不對稱性。常用Jaccard系數(shù)來定義其對象間的相似度：4.2.1二值屬性的相似度度量4.2傳統(tǒng)度量方法26第二十六頁，共一百九十五頁，編輯于2023年，星期日示例：計算下面兩個二值向量之間的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第二十七頁，共一百九十五頁，編輯于2023年，星期日

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

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

兩個點的距離是每維距離的絕對值之和。4.2傳統(tǒng)度量方法30第三十頁，共一百九十五頁，編輯于2023年，星期日4.2.2歐氏距離Minkowski距離（Lr范式）把歐氏距離和曼哈頓距離包含為特例：r為變量。注意不要將參數(shù)r與空間維數(shù)（屬性個數(shù)）n混淆。4.2傳統(tǒng)度量方法31第三十一頁，共一百九十五頁，編輯于2023年，星期日

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

L1范式：

L2范式：L∞范式：

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

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

代表向量的歐氏距離，

4.2傳統(tǒng)度量方法36第三十六頁，共一百九十五頁，編輯于2023年，星期日4.2.3余弦距離余弦距離也是一個距離度量。由于余弦距離定義在0～180度之間，因此，余弦距離非負，當且僅當兩個向量表示同一方向時向量的夾角為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第三十七頁，共一百九十五頁，編輯于2023年，星期日例：計算向量x=(1,-1,2)和向量y=(2,1,1)的余弦距離。計算點乘積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第三十八頁，共一百九十五頁，編輯于2023年，星期日余弦距離常用來比較文檔，或針對給定的查詢詞向量對文檔排序。當屬性是二值屬性時，余弦距離函數(shù)可以用共享特征或?qū)傩越忉尅４藭r，x?y是x和y共同具有的屬性數(shù)，而

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

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

4.2.3余弦距離該函數(shù)也稱為Tanimoto系數(shù)或Tanimoto距離，通常用于信息檢索（網(wǎng)頁查重、新聞查重、作弊檢測、抄襲檢查）與生物學分類中。4.2傳統(tǒng)度量方法39第三十九頁，共一百九十五頁，編輯于2023年，星期日

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

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

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

這兩個問題同時存在時如何計算距離度量呢？這種情況下，采用廣義的歐氏距離，即Mahalanobis距離來解決此類問題。4.2.4Mahalanobis距離4.2傳統(tǒng)度量方法40第四十頁，共一百九十五頁，編輯于2023年，星期日Mahalanobis距離適用于當屬性各量的量綱單位不同且適用于屬性間具有相關(guān)性的情況，其分布是近似高斯分布。通常，對象x和y間的Mahalanobis距離定義如下：4.2.4Mahalanobis距離∑是n×n的協(xié)方差矩陣，∑-1是協(xié)方差矩陣的逆。n是維度（分量數(shù)）。4.2傳統(tǒng)度量方法41第四十一頁，共一百九十五頁，編輯于2023年，星期日4.2.4Mahalanobis距離對傳統(tǒng)的歐氏距離的改進，對線性變換是不變的，克服了歐氏距離受量綱和屬性間的相關(guān)性影響的兩個缺點，是一個很好的判別手段，在分類算法中較常用。但Mahalanobis距離的協(xié)方差矩陣難以確定，計算量較大，不適合大規(guī)模的數(shù)據(jù)集。4.2傳統(tǒng)度量方法42第四十二頁，共一百九十五頁，編輯于2023年，星期日Jaccard距離用來度量兩個對象的重疊程度，其廣泛應用于信息檢索和生物學分類中，在二值屬性情況下簡化為Jaccard系數(shù)，對于向量型對象，其相似度定義如下：4.2.5Jaccard距離4.2傳統(tǒng)度量方法43第四十三頁，共一百九十五頁，編輯于2023年，星期日4.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第四十四頁，共一百九十五頁，編輯于2023年，星期日

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

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

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

示例：待分詞的文本：安保人員在火車站臺獨自強守著崗位。

一般的分詞：公安|人員|在|火車|站臺|獨自|強|守|著|崗位IKAnalyzer：公安|公安人員|人員|在|火車|火車站|站臺|獨自|自強|守著|崗位4.3大數(shù)據(jù)度量方法57第五十七頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling（3）滑動窗口大小的設置Shingle生成是最為關(guān)鍵和最難的的一步?；瑒哟翱诖笮是組成特征元素的詞語組合中字的個數(shù)，它的大小直接決定了文檔的特征元素的總數(shù)，影響算法的時間復雜度。它還影響到字符串的語義包含度，因為多個詞語組合比起一個到兩個詞語的組合，其對主題的反映程度要大。4.3大數(shù)據(jù)度量方法58第五十八頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling（3）滑動窗口大小的設置

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

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

譬如，當窗口大小w=1時，大部分Web網(wǎng)頁中都有很多常見字符，而其它字符很少，此時幾乎所有的Web網(wǎng)頁之間都有較高的文檔相似度。4.3大數(shù)據(jù)度量方法59第五十九頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling

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

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

計算shingle權(quán)重的公式：權(quán)重的歸一化：4.3大數(shù)據(jù)度量方法61第六十一頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling

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

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

為了防止抽取的shingle數(shù)目極少的情況出現(xiàn)，還設置了抽取率n，以保證最后供比對的shingle數(shù)量足夠。4.3大數(shù)據(jù)度量方法62第六十二頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling（5）相似度計算

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

文檔A和文檔B中相同的shingle數(shù)目與他們總的shingle數(shù)目的比值，該值越接近于1，說明兩文檔間的相似度就越高。4.3大數(shù)據(jù)度量方法63第六十三頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling記w-shingleS(D,w)={S1,S2,L

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

Pn}為{S1,S2,L

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

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

fki：第k個shingle在第i個文檔中出現(xiàn)的次數(shù)。4.3大數(shù)據(jù)度量方法64第六十四頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling

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

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

Na為A中的shingle數(shù)目，根據(jù)上式計算相似度所得的結(jié)果大于或等于l時直接取1，而小于l的保持不變。4.3大數(shù)據(jù)度量方法65第六十五頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling

假設A包含在B中，如果簡單地按照Jaccard系數(shù)的計算方法，相似度就不會是l，即反應不出A包含在B中；

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

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

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

endififS`i的維度≥n*r

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

計算di和dj的包含相似度Simij和SimjiifSimij≥Simmin

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

并輸出判定結(jié)果endifendforendfor4.3大數(shù)據(jù)度量方法68第六十八頁，共一百九十五頁，編輯于2023年，星期日4.3.1文檔的shingling算法只需在抽取shingle時計算權(quán)重，對以后的準確度影響較小，且只要存儲每個文檔被抽取出的shingle即可，不需額外存儲空間。因為shingling算法是從N個文檔中兩兩比較文檔的相似度，因此其時間復雜度是O(N2)。4.3大數(shù)據(jù)度量方法69第六十九頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希

有100萬篇文檔，約有

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

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

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

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

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

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

。

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

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

，則

；

，則

。其中，p1,p2,r1,r2

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

。4.3大數(shù)據(jù)度量方法73第七十三頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希

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

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

，其中

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

中隨機、獨立的選擇L個函數(shù)g1,g2,…,gL利用這一組函數(shù)創(chuàng)建哈希索引。4.3大數(shù)據(jù)度量方法74第七十四頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希

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

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

，再隨機從i=1,2,…L，再隨機地從所組成的哈希函數(shù)組中選擇L個局部敏感哈希函數(shù)g1,g2,…,gL對訓練集合中的每一個向量x∈P進行散列，將其哈希鍵值存儲在函數(shù)值gi(x)對應的桶中，建立哈希表索引。在此過程中，需要合理地選擇k和L，算法如下。4.3大數(shù)據(jù)度量方法75第七十五頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希算法：局部敏感哈希算法的數(shù)據(jù)處理存儲過程。輸入：點集合P{p1,p2,…,pn}，初始化L和k。輸出：哈希表Ti，i=1,2,…,L。方法：fori=1toLdo

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

通過gi初始化哈希表Ti

endforfori=1toLdoforj=1tondo

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

endforendfor

4.3大數(shù)據(jù)度量方法76第七十六頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希算法：局部敏感哈希算法的查詢過程。輸入：待查詢點q，哈希表Ti，i=1,2,…,L，初始化Simmin。輸出：與q關(guān)聯(lián)的數(shù)據(jù)。方法：

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

fori=1toLdo

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

endfor

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

forj=i+1tondo

計算si和q的相似度Simi

ifSimi≥Simmin

判定si和q是相似的報出siendifendforendfor4.3大數(shù)據(jù)度量方法77第七十七頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希

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

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

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

典型的局部敏感哈希函數(shù)族分別是：面向海明距離的哈希函數(shù)族、面向歐式距離的哈希函數(shù)族、面向Jaccard距離的哈希函數(shù)族、面向余弦距離的哈希函數(shù)族。4.3大數(shù)據(jù)度量方法78第七十八頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希（1）面向海明距離的哈希函數(shù)族定義：i是向量x中一個隨機坐標，對于每一個點，將它轉(zhuǎn)換到海明空間。

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

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

這樣，向量v(x)就成為了海明空間Hmd中的點。例：若最大指標值是7，一個三維點x的坐標是(3,5,7)，則向量v(x)4.3大數(shù)據(jù)度量方法79第七十九頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希

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

，函數(shù)族g就是

式中

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

顯然，面向海明距離下的哈希函數(shù)族對高維數(shù)據(jù)進行散列的過程就是將多維空間點嵌入到海明空間的過程。采用這種局部敏感哈希函數(shù)族，過程簡單容易實現(xiàn)是其優(yōu)點，但當輸入數(shù)據(jù)集和最大坐標值比較大時，嵌入后得到的集合的維數(shù)相對較大，這會消耗很大的內(nèi)存和處理成本。4.3大數(shù)據(jù)度量方法80第八十頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希（2）面向Jaccard距離的哈希函數(shù)族

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

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

即集合A中的所有元素具有相同的概率轉(zhuǎn)化為集合A在P下的最小的元素。此時有Jaccard局部敏感哈希函數(shù)為4.3大數(shù)據(jù)度量方法81第八十一頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希示例：

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

時，才認為向量A和B沖突即z=h(A)=h(B)，在Jaccard距離定義的相似度下，向量A和B沖突的概率為4.3大數(shù)據(jù)度量方法82第八十二頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希（3）面向歐氏距離的哈希函數(shù)族

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

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

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

，已證是有效的。對于任意的d，須從d穩(wěn)定分布中隨機選取變量構(gòu)成向量r，并用上述方式對高維數(shù)據(jù)降維處理。4.3大數(shù)據(jù)度量方法83第八十三頁，共一百九十五頁，編輯于2023年，星期日4.3.2局部敏感哈希（4）面向余弦距離的哈希函數(shù)族

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

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

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

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

異常檢測問題可概括為度量數(shù)據(jù)偏離的程度和有效發(fā)現(xiàn)異常的問題。4.3大數(shù)據(jù)度量方法86第八十六頁，共一百九十五頁，編輯于2023年，星期日

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

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

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

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

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

一般而言，根據(jù)異常判斷的標準以及異常和其他數(shù)據(jù)之間的關(guān)系，可以將異常分為三類，分別是：點異常、情境異常（條件異常）和聚集異常。4.4異常檢測89第八十九頁，共一百九十五頁，編輯于2023年，星期日（1）點異常

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

在許多應用中，點異常檢測都是非常重要的。4.4異常檢測90第九十頁，共一百九十五頁，編輯于2023年，星期日（2）情境異常

“今天的溫度是2℃。這是一個異常嗎？”這依賴于時間和地點。如圖，如是在南京的冬天，這是正常溫度，而如是南京的夏天，這是異常。與點異常不同，溫度是否是異常依賴于情境——時間、地點和可能的其他因素。4.4異常檢測91第九十一頁，共一百九十五頁，編輯于2023年，星期日

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

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

情境異常又稱為條件異?；蚯榫畴x群點，因為情境異常需要考慮的不僅僅是數(shù)據(jù)的屬性值本身，而且考慮了數(shù)據(jù)出現(xiàn)的情境。

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

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

點異常檢測是情境異常檢測的一個特例，即情境屬性集為空，點異常檢測使用整個數(shù)據(jù)集作為情境。情境異常分析為用戶提供了靈活性，因為用戶可以在不同的情境下考慮異常，這在許多應用中是非常需要的。

4.4異常檢測93第九十三頁，共一百九十五頁，編輯于2023年，星期日示例：在信用卡欺騙檢測中，除點異常外，分析人員還可考慮不同情境下的異常。如一位顧客使用了信用卡額度的90%，其屬于具有低信用額度的顧客群，則不應視作異常。而高收入人群顧客的類似行為可被視為異常，可帶來商機——提高其信用額度可能帶來新的收益。

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

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

聚集異常檢測有許多應用。

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

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

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

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

非參數(shù)方法的例子包括直方圖和核密度估計。4.4異常檢測102第一百零二頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法（1）參數(shù)方法

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

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

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

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

的概率隨c增加而迅速減小。4.4異常檢測104第一百零四頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法

設

，部分的c值和a值的對應表ca10.31731.50.133620.04552.50.012430.00273.50.000540.00014.4異常檢測105第一百零五頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法如果一個感興趣的（正常對象的）屬性的分布是具有均值μ和標準差σ的正態(tài)分布，即N(μ,σ2)分布，則可通過變換z=(x-μ)/σ轉(zhuǎn)換為標準正態(tài)分布N(0,1)。通常，m和s是可以通過樣本均值和樣本標準差來估計的。實際情況下，當觀測數(shù)據(jù)很多時，這種估計的效果很好；另一方面，由概率統(tǒng)計中的大數(shù)定律可知，在大樣本的情況下可以用正態(tài)分布近似其他分布。4.4異常檢測106第一百零六頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法

這種思想在質(zhì)量控制中廣泛應用，下圖是質(zhì)量控制示意圖，中心線是觀測值的預測值，μ±3σ對應上下控制線，μ±2σ對應上、下警告線。4.4異常檢測107第一百零七頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法對于觀測樣本

：如果此點在上、下警告線之間的區(qū)域內(nèi)，則表示生產(chǎn)或測定過程處于受控狀態(tài)，生產(chǎn)過程或樣本分析結(jié)果有效。如果此點超出上、下警告線，但仍在上、下控制線之間的區(qū)域內(nèi)，提示質(zhì)量開始變劣，可能存在“失控”傾向，應進行初步檢查，并采取相應的校正措施。如此點落在上、下控制線外的區(qū)域，表示生產(chǎn)或測定過程“失控”，生產(chǎn)的是廢品或觀測樣本無效。應立即檢查并糾正。4.4異常檢測108第一百零八頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法示例：假設某城市過去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ù)決定：均值μ和標準差σ。4.4異常檢測109第一百零九頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法計算得到4.4異常檢測110第一百一十頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法

由此，有

最大偏離值為23.0℃，偏離估計的均值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%，因此它被識別為異常點。

另一種使用正態(tài)分布的一元異常點檢測的統(tǒng)計學方法是Grubb檢驗（又稱為最大標準殘差檢驗）。對于數(shù)據(jù)集中的每個對象x，定義z分數(shù)（z-score）為是輸入的均值，s是標準差。4.4異常檢測111第一百一十一頁，共一百九十五頁，編輯于2023年，星期日4.4.1基于統(tǒng)計的檢測方法如果對象