王 康，周治平

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

1 引言

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

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

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

2 高斯核密度估計方法原理

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

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

（1）高斯核局部密度估計

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

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

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

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

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

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

2.2 穩(wěn)定性分析

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

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

證明如下：

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

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

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

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

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

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

3.1 算法實現(xiàn)

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

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

（2）特征提取

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

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

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

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

3.2 算法偽代碼

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

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

4 仿真實驗

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

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

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

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

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

4.1 實驗結果對比與分析

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

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

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

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

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

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

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

從圖3中可以看出本文算法在取不同k值時的表現(xiàn)都優(yōu)于其他兩種算法，并且當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ōu)勢，將本文算法與LOF 算法、CBLOF 算法、文獻[16]算法和IForest 算法作對比，計算評估離群檢測算法的性能指標，即ACC、FNR、FPR和AUC，結果放入表2。各算法的參數(shù)設置如表3所示。

Table 2 Comparison of experimental results by different algorithms表2 不同算法實驗結果對比

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

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

以上實驗表明，在經過t-SNE 算法提取特征后，能夠增強樣本間的局部結構能力，解決高維空間中樣本稀疏問題。通過高斯核函數(shù)對LOF算法進行改進，能夠大幅提高檢測準確率。

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

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

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

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

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

5 結束語

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

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