高斯核密度估計(jì)方法檢測健康數(shù)據(jù)異常值

王 康，周治平

江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

1 引言

隨著人們越來越關(guān)注更加健康的生活方式，運(yùn)動手環(huán)佩戴者的數(shù)量也在不斷增加。運(yùn)動手環(huán)可以監(jiān)控和跟蹤用戶日常活動，如運(yùn)動、睡眠以及卡路里等[1]。用戶通過呈現(xiàn)的數(shù)據(jù)信息，了解自身的活動情況。Lim等[2]發(fā)現(xiàn)一些特定疾病患者的手環(huán)數(shù)據(jù)與健康佩戴者數(shù)據(jù)存在差異，且特定的指標(biāo)與某種疾病的關(guān)聯(lián)較大。對于正常佩戴者而言，并不知曉其身體的疾病隱患，在缺乏對這些數(shù)據(jù)進(jìn)行有效分析的情況下，僅從簡單的手環(huán)數(shù)據(jù)呈現(xiàn)中也無法判斷得知。對于手環(huán)采集的活動數(shù)據(jù)，異常是指數(shù)據(jù)以及關(guān)聯(lián)某些特定疾病的指標(biāo)偏離個體基準(zhǔn)的情況。因此，對運(yùn)動手環(huán)采集的健康數(shù)據(jù)進(jìn)行有效挖掘，判斷數(shù)據(jù)異常關(guān)聯(lián)，分析導(dǎo)致數(shù)據(jù)異常的因素，對改善用戶生活方式，提升用戶健康狀況具有重要作用。

異常檢測也被稱作離群檢測，目的是發(fā)現(xiàn)在不同機(jī)制下，那些區(qū)別于大部分?jǐn)?shù)據(jù)，且足夠引起懷疑的少部分?jǐn)?shù)據(jù)。學(xué)者們使用多種機(jī)器學(xué)習(xí)方法致力于提高離群檢測的效率。Knorr 等[3-4]提出基于距離的離群點(diǎn)檢測方法，擺脫了離群點(diǎn)檢測算法中對數(shù)據(jù)的分布模型和分布參數(shù)的限制。隨后，Boriah 等[5]基于K-近鄰算法衡量對象的離群度，該方法可以處理大規(guī)模數(shù)據(jù)集。朱利等[6]提出一種快速K-近鄰的最小生成樹離群檢測方法，該方法基于距離比值的加權(quán)排序離群因子，能大幅降低時間復(fù)雜度，提高計(jì)算效率。Breunig 等[7]提出基于密度的離群點(diǎn)檢測算法，給出對象是離群點(diǎn)的程度定量度量，通過考察對象與其近鄰“密度”的差異來判斷該對象是否為離群點(diǎn)，這種差異通過局部離群因子（local outlier factor，LOF）衡量。但由于LOF算法基于歐氏距離，當(dāng)數(shù)據(jù)點(diǎn)之間存在特殊分布時，對象之間的相似程度無法由歐式距離準(zhǔn)確反映出；并且此方法不適用于高維數(shù)據(jù)，高維空間數(shù)據(jù)的高度稀疏性使得數(shù)據(jù)點(diǎn)之間幾乎是等距離的，每個數(shù)據(jù)點(diǎn)在密度的意義上都可以看作是一個異常點(diǎn)。Ghoting 等[8]針對處理高維數(shù)據(jù)集的問題，提出二段算法RBRP（recursive binning and reprojection）。該算法基于索引提高計(jì)算效率，循環(huán)嵌套減少操作I/O次數(shù)，降低時間復(fù)雜度。Tang等[9]引入鏈?zhǔn)骄嚯x的概念，通過計(jì)算對象與其K-近鄰的邊長度加權(quán)和，提出基于連通性的離群因子（connectivity-based outlier factor，COF）。He 等[10]基于聚類提出聚類離群因子（cluster based local outliers factor，CBLOF）算法，一方面能夠檢測出離群簇，另一方面又提高了局部離群點(diǎn)的檢測精度。Zhu 等[11]結(jié)合最小生成樹提出KNMOD（K-nearest neighbor and minimum spanning tree-based outliers detection）算法，降低時間復(fù)雜度，提高檢測效率。錢景輝等[12]采用多示例學(xué)習(xí)（multi-instance learning，MIL）框架，結(jié)合退化策略和權(quán)重調(diào)整方法檢測局部離群點(diǎn)。Xu等[13]基于核密度估計(jì)（kernel density estimation，KDE）提出一種新的離群檢測算法，該算法在利用KDE 計(jì)算數(shù)據(jù)概率密度函數(shù)最優(yōu)估計(jì)的基礎(chǔ)上，建立信度函數(shù)檢測離群點(diǎn)。楊宜東等[14]利用核密度估計(jì)方法，實(shí)現(xiàn)全局?jǐn)?shù)據(jù)的離群點(diǎn)檢測。Ngan等[15]驗(yàn)證了核密度估計(jì)方法在大規(guī)模的數(shù)據(jù)集上比One-Class SVM 具有更好的離群檢測效果。Tang 等[16]考慮反向最近鄰并且共享對象的最近鄰以進(jìn)行核密度分布估計(jì)，提出基于相對密度的離群值得分（relative density-based outlier score，RDOS）來測量對象的局部離群程度。胡彩平等[17]引用信息熵的概念，同時利用加權(quán)距離來代表各對象之間的距離，提出基于密度的局部離群點(diǎn)（density-based local outlier factor，DLOF）算法。Xia 等[18]通過網(wǎng)格劃分和擴(kuò)展，提出CRF（complete random forest）算法，并引入投票機(jī)制，更有效地分離離群點(diǎn)，但網(wǎng)格的數(shù)量隨著維數(shù)呈指數(shù)級增長，時間復(fù)雜度會迅速增加，降低了算法的性能。

鑒于此，針對運(yùn)動手環(huán)數(shù)據(jù)存在與健康狀況關(guān)聯(lián)異常值且手環(huán)數(shù)據(jù)在高維空間的高度稀疏性降低異常檢測準(zhǔn)確率的問題，本文提出了一種基于高斯核密度估計(jì)的離群點(diǎn)檢測方法。該方法在采用t-SNE（t-distributed stochastic neighbor embedding）算法[19]對數(shù)據(jù)集進(jìn)行特征提取的基礎(chǔ)上，利用高斯核函數(shù)改進(jìn)LOF算法，計(jì)算局部離群因子，據(jù)此檢測出離群點(diǎn)。

2 高斯核密度估計(jì)方法原理

2.1 高斯核密度估計(jì)局部離群因子算法

高斯核密度估計(jì)局部離群因子算法的詳細(xì)描述如下：

（1）高斯核局部密度估計(jì)

設(shè)k為正整數(shù)，則對象m的高斯核局部密度為：

式中，G(?)表示高斯核函數(shù)；||xn-xm||表示對象m和對象n的歐式距離；σ為所有樣本點(diǎn)兩兩之間距離的標(biāo)準(zhǔn)差，整個樣本點(diǎn)之間距離的變化程度可以引用標(biāo)準(zhǔn)差來反映。

式（2）表示對象m和n的高斯核距離。高斯核局部密度基于高斯核距離，對象m的K-近鄰鄰域可以通過計(jì)算各點(diǎn)與m的高斯核距離來確定。同時，對象m和其近鄰點(diǎn)之間距離的衰減程度也可由高斯核距離反映。對于離群點(diǎn)，它們與鄰近點(diǎn)之間距離的衰減程度大于正常點(diǎn)，因此它們的高斯核局部密度較小。相反，正常點(diǎn)與鄰近點(diǎn)之間距離的衰減程度較小，因此它們的高斯核局部密度接近于1。

（2）高斯核局部離群因子

對象m的高斯核局部離群因子記作：

在被檢測樣本點(diǎn)中，那些高斯核局部密度低于近鄰點(diǎn)的樣本點(diǎn)被視作離群點(diǎn)。若m是被檢測的點(diǎn)，n是m的一個鄰近點(diǎn)。由式（1）、式（2）可知，如果m是離群點(diǎn)而n是正常點(diǎn)，那么有Dk(n)＞Dk(m)。由式（3）可知Fk(m)＞1。如果m和n都是正常點(diǎn)，那么Dk(n)≈Dk(m)，F(xiàn)k(m)≈1。通過比較Fk(m)和1的大小可以區(qū)分正常點(diǎn)和離群點(diǎn)。

2.2 穩(wěn)定性分析

對高斯核密度估計(jì)局部離群因子算法判定閾值的穩(wěn)定性進(jìn)行如下分析。首先，對于任意對象m，給出如下定義：

其中，dmin(m)、dmax(m)分別是m的K-近鄰鄰域中距離m最近的點(diǎn)與最遠(yuǎn)的點(diǎn)的距離：imin(m)、imax(m)分別表示m的K-近鄰對象的K-近鄰鄰域內(nèi)距離樣本中心的最小距離和最大距離。假設(shè)對象m為任意數(shù)據(jù)集D中的一個樣本點(diǎn)，正整數(shù)k滿足1 ≤k≤|D|，對象m的Fk(m)滿足：

證明如下：

由式（9）可知，對象m的Dk(m)滿足：

對象o為對象n的K-近鄰鄰域中的一點(diǎn)，對于任意o滿足：

由式（11）可知，對象n的Dk(m)滿足：

由式（10）、式（12）可知，對象m的Fk(m)滿足：

由式（8）可知，對象m的Fk(m)值的上下限較為緊密，如果m為正常對象，則有d≈i，其Fk(m)的上下邊界值均趨近于1，因此對象m的Fk(m)值也趨近于1?？梢杂?作為閾值，判定正常點(diǎn)與離群點(diǎn)。

3 高斯核密度估計(jì)方法實(shí)現(xiàn)流程

3.1 算法實(shí)現(xiàn)

（1）樣本數(shù)據(jù)集預(yù)處理

本方法首先對采集到的手環(huán)樣本數(shù)據(jù)進(jìn)行預(yù)處理。通過運(yùn)動手環(huán)能夠采集到用戶一天內(nèi)步數(shù)、心率（設(shè)定為一分鐘采集一次）、卡路里、全天睡眠時間、深度睡眠時間、淺睡眠時間等一系列數(shù)據(jù)。數(shù)據(jù)集包含M個用戶T天的活動數(shù)據(jù)，經(jīng)過選取i個特征指標(biāo)后，每一條運(yùn)動數(shù)據(jù)可以表示為i維向量X=[x1,x2,…,xi]T。根據(jù)用戶活動類型可將其分為輕運(yùn)動、靜坐、運(yùn)動以及睡眠四類，這樣可以較完整地反映用戶一天的活動情況。因此，本文選取的特征指標(biāo)為總心率均值、總心率峰值、輕運(yùn)動心率均值、輕運(yùn)動心率峰值、靜坐心率均值、靜坐心率峰值、運(yùn)動心率均值、運(yùn)動心率峰值、睡眠心率均值、睡眠心率峰值、步數(shù)、卡路里、全天睡眠時間、深睡眠時間、淺睡眠時間。

（2）特征提取

在高維空間中，隨著數(shù)據(jù)規(guī)模的增加，時間復(fù)雜度會迅速增加，性能急劇下降；同時，數(shù)據(jù)在高維空間中具有高度稀疏性，這使得每個數(shù)據(jù)點(diǎn)之間幾乎等距，從而在密度的意義上都可被視作異常點(diǎn)，導(dǎo)致檢測算法的準(zhǔn)確率大大降低。由文獻(xiàn)[19]可知t-SNE算法將高維數(shù)據(jù)映射在二維空間中，使得高維度下距離較近即相似的數(shù)據(jù)映射后更聚合，較遠(yuǎn)的更疏遠(yuǎn)，較好地捕捉了數(shù)據(jù)的整體特性，提高了局部結(jié)構(gòu)能力。因此本文采用t-SNE 算法對高維數(shù)據(jù)進(jìn)行特征提取，為后續(xù)在二維空間計(jì)算所有樣本的Fk(m)值提供支撐。

（3）計(jì)算每條數(shù)據(jù)的GKDELOF（Gaussian kernel density estimation-based local outlier factor）值

將特征提取后的二維數(shù)據(jù)集作為輸入，由以下公式計(jì)算每個對象m的Fk(m)值。

用Fk(m)值對對象的離群程度進(jìn)行量化，并與離群程度閾值1比較，輸出樣本數(shù)據(jù)離群點(diǎn)。

3.2 算法偽代碼

輸入：所有數(shù)據(jù)點(diǎn)組成的集合，記為S；特征提取后數(shù)據(jù)點(diǎn)組成的集合，記為T；數(shù)據(jù)集的維度數(shù)，記為D；特征提取維度數(shù)，記為d；所有數(shù)據(jù)點(diǎn)的K-近鄰集。

輸出：數(shù)據(jù)集的離群點(diǎn)集合O。

4 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)基于Matlab 2015b、PyCharm 平臺，計(jì)算機(jī)的硬件配置為：Windows 10操作系統(tǒng)、Intel Core i5-5200U CPU、3.2 GHz、16 GB RAM。

本文選取了8個數(shù)據(jù)集，皆來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫，這些數(shù)據(jù)集包含異常類，根據(jù)數(shù)據(jù)集的特點(diǎn)，將其中一部分?jǐn)?shù)據(jù)作為異常數(shù)據(jù)。數(shù)據(jù)集的數(shù)據(jù)特征見表1。

Table 1 Data set information表1 數(shù)據(jù)集信息表

為檢驗(yàn)算法的準(zhǔn)確性，將本文算法與基于密度的LOF[7]算法、基于聚類的CBLOF[10]算法、基于核密度的文獻(xiàn)[16]算法、基于網(wǎng)格劃分的IForest[20]算法進(jìn)行了比較。選取理由為，本文是對于LOF 算法的改進(jìn)，因此選取LOF 算法作為對比算法；CBLOF 算法是基于聚類的經(jīng)典離群檢測算法；文獻(xiàn)[16]的算法是基于密度并利用核密度分布估計(jì)從而檢測離群點(diǎn)，本文也是將核密度作為一個改進(jìn)點(diǎn)；IForest算法是目前較新的基于網(wǎng)格劃分的算法，檢測效果較好，廣泛使用。

本文所用的評估異常檢測算法的主要性能指標(biāo)包括正確率（accuracy，ACC）、假負(fù)率（false negative rate，F(xiàn)NR）、假正率（false positive rate，F(xiàn)PR）和AUC（area under curve）。一個較優(yōu)性能的異常檢測算法應(yīng)該具有較低的FNR和FPR，以及較高的ACC和AUC。

4.1 實(shí)驗(yàn)結(jié)果對比與分析

為驗(yàn)證本文方法的適用性，由本文方法檢測不同數(shù)據(jù)集后繪制的ROC曲線圖如圖1所示。

Fig.1 ROC curve of different data sets by GKDELOF圖1 GKDELOF算法檢測不同數(shù)據(jù)集的ROC曲線

從圖1的ROC 曲線結(jié)果圖可以看出，本文提出的高斯核密度估計(jì)異常值檢測方法在不同數(shù)據(jù)集上都取得了較好的效果。其中，在Shuttle 數(shù)據(jù)集上取得了最好的檢測效果；僅在Arrhythmia 和Pima 數(shù)據(jù)集上的效果較不理想。對ROC曲線的定量分析結(jié)果如表2中的AUC值所示。

為驗(yàn)證本文方法中特征提取對于處理高維數(shù)據(jù)的檢測準(zhǔn)確率的提高，取文獻(xiàn)[18]中使用的維度較高的兩個數(shù)據(jù)集，分別為Isolet1234（618維）和Madelon（500維）以及表1中的Arrhythmia（274維）數(shù)據(jù)集。分別在經(jīng)過特征提取和未經(jīng)過特征提取的情況下（下標(biāo)有l(wèi)的為經(jīng)過特征提取處理的），利用本文所提出的算法進(jìn)行ROC曲線的對比，對比結(jié)果如圖2所示。

Fig.2 Comparison of ROC curves before and after dimensionality reduction of high dimensional data圖2 高維數(shù)據(jù)降維前后ROC曲線比較

由圖2對比結(jié)果可以知道，3個數(shù)據(jù)集在經(jīng)過特征提取后，檢測的效果都有一定的提升。根據(jù)ROC曲線下面積AUC值得出，在經(jīng)過降維處理之后，提升最明顯的是Madelon數(shù)據(jù)集，AUC值為0.85。Isolet1234數(shù)據(jù)集次之，AUC值提高了13%。在Arrhythmia 數(shù)據(jù)集上的提升效果并不明顯，主要是由于數(shù)據(jù)集中定類屬性較多，對于定類屬性值的運(yùn)算不能真實(shí)度量樣本相似性，因此影響了檢測精度。此實(shí)驗(yàn)說明運(yùn)用t-SNE 算法提取特征后，對于高維數(shù)據(jù)，能夠進(jìn)一步提升檢測效果。

由于本文算法和LOF 算法以及文獻(xiàn)[16]的算法都需要采用最近鄰方法，因此為了評估不同k值對算法性能的影響，本文對于這3個算法，作用在Shuttle數(shù)據(jù)集上，取多次不同k值，對比各個算法的AUC值，結(jié)果如圖3所示。

從圖3中可以看出本文算法在取不同k值時的表現(xiàn)都優(yōu)于其他兩種算法，并且當(dāng)k=5時，對于本文算法性能的提升是最大的，此后的AUC值一直穩(wěn)定在0.96以上。

Fig.3 Performance of AUC with different k values for data set of Shuttle圖3 在Shuttle數(shù)據(jù)集上不同k值時的AUC值

為驗(yàn)證本文算法的優(yōu)勢，將本文算法與LOF 算法、CBLOF 算法、文獻(xiàn)[16]算法和IForest 算法作對比，計(jì)算評估離群檢測算法的性能指標(biāo)，即ACC、FNR、FPR和AUC，結(jié)果放入表2。各算法的參數(shù)設(shè)置如表3所示。

Table 2 Comparison of experimental results by different algorithms表2 不同算法實(shí)驗(yàn)結(jié)果對比

Table 3 Parameter setting information表3 參數(shù)設(shè)置信息

從表2中的對比實(shí)驗(yàn)結(jié)果可以看出，除了Arrhythmia和Annthyroid數(shù)據(jù)集之外，基于高斯核密度估計(jì)的異常值檢測方法相對于4個對比算法對其余6個數(shù)據(jù)集具有更高的檢測準(zhǔn)確率。其AUC值也僅在Arrhythmia和Pima數(shù)據(jù)集上低于其他算法。其中，在Wcd 數(shù)據(jù)集上，檢測準(zhǔn)確率達(dá)到了98%，遠(yuǎn)高于IForest 的87%。在Breastw 數(shù)據(jù)集上，本文算法的4個檢測指標(biāo)都優(yōu)于對比算法，且AUC值達(dá)到了最高的0.99。當(dāng)數(shù)據(jù)集較小時（Lym），AUC值達(dá)到了0.94，準(zhǔn)確率為92%，大幅高于其他算法，同時假正率也是最低的；當(dāng)數(shù)據(jù)集維度較高時（Arrhythmia），雖然其AUC值不是最高的，但與由IForest 算法取得的最高值0.68接近，且針對此數(shù)據(jù)集，5個對比算法檢測效果都不理想。在數(shù)據(jù)集較大的情況下，本文方法的優(yōu)勢也遠(yuǎn)遠(yuǎn)大于其他幾種算法，例如在Shuttle數(shù)據(jù)集上，準(zhǔn)確率為95%，遠(yuǎn)遠(yuǎn)高于CBLOF算法的79%。

以上實(shí)驗(yàn)表明，在經(jīng)過t-SNE 算法提取特征后，能夠增強(qiáng)樣本間的局部結(jié)構(gòu)能力，解決高維空間中樣本稀疏問題。通過高斯核函數(shù)對LOF算法進(jìn)行改進(jìn)，能夠大幅提高檢測準(zhǔn)確率。

4.2 健康數(shù)據(jù)異常檢測結(jié)果

在驗(yàn)證了算法的性能后，利用該算法在采集到的手環(huán)健康數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，找出異常值。圖4是將數(shù)據(jù)集經(jīng)過特征提取后，采用本文GKDELOF算法進(jìn)行異常檢測的結(jié)果。其中白色點(diǎn)表示正常數(shù)據(jù)，紅色點(diǎn)表示異常數(shù)據(jù)。

Fig.4 Outlier detection result by GKDELOF on health data圖4 GKDELOF算法在健康數(shù)據(jù)上離群檢測實(shí)驗(yàn)結(jié)果

Fig.5 Outlier detection result by IForest on health data圖5 IForest算法在健康數(shù)據(jù)上離群檢測實(shí)驗(yàn)結(jié)果

為驗(yàn)證本文算法的優(yōu)勢，圖5為利用檢測效果僅次于本文算法的IForest算法在同一健康數(shù)據(jù)集上進(jìn)行異常檢測的實(shí)驗(yàn)結(jié)果。對比圖4和圖5可以看出，兩種方法對于明顯的離群樣本點(diǎn)都可以檢測出來，但I(xiàn)Forest算法在簇群邊緣處存在漏判和誤判。標(biāo)號為1、5、6的樣本點(diǎn)為漏判，標(biāo)號為2、3、4的樣本點(diǎn)為誤判。而本文算法在檢測簇邊緣離群點(diǎn)時，未存在明顯漏判或誤判情況。

5 結(jié)束語

本文針對智能穿戴設(shè)備普及背景下，利用運(yùn)動手環(huán)采集的活動數(shù)據(jù)存在未知異常數(shù)據(jù)的問題，提出一種基于高斯核密度估計(jì)的健康數(shù)據(jù)異常值檢測方法。該方法在利用t-SNE算法進(jìn)行特征提取，增強(qiáng)局部結(jié)構(gòu)能力的基礎(chǔ)上，通過高斯核函數(shù)改進(jìn)LOF算法，提出基于高斯核密度估計(jì)離群因子算法，該方法的判定閾值較為穩(wěn)定。在實(shí)驗(yàn)部分，利用異常檢測具有代表性的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了特征提取的作用；并且對比了其他4種異常檢測算法，實(shí)驗(yàn)結(jié)果表明，該方法具有較好的檢測效果。最后，利用該方法在真實(shí)數(shù)據(jù)集上找出異常值。

在數(shù)據(jù)預(yù)處理方面，選取的特征指標(biāo)是否能夠有效地表現(xiàn)數(shù)據(jù)特征在一定程度上會影響檢測的準(zhǔn)確率，因此還可以從數(shù)據(jù)特征指標(biāo)選擇方面做進(jìn)一步研究。