王 康,周治平
江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122
隨著人們?cè)絹碓疥P(guān)注更加健康的生活方式,運(yùn)動(dòng)手環(huán)佩戴者的數(shù)量也在不斷增加。運(yùn)動(dòng)手環(huán)可以監(jiān)控和跟蹤用戶日常活動(dòng),如運(yùn)動(dòng)、睡眠以及卡路里等[1]。用戶通過呈現(xiàn)的數(shù)據(jù)信息,了解自身的活動(dòng)情況。Lim等[2]發(fā)現(xiàn)一些特定疾病患者的手環(huán)數(shù)據(jù)與健康佩戴者數(shù)據(jù)存在差異,且特定的指標(biāo)與某種疾病的關(guān)聯(lián)較大。對(duì)于正常佩戴者而言,并不知曉其身體的疾病隱患,在缺乏對(duì)這些數(shù)據(jù)進(jìn)行有效分析的情況下,僅從簡單的手環(huán)數(shù)據(jù)呈現(xiàn)中也無法判斷得知。對(duì)于手環(huán)采集的活動(dòng)數(shù)據(jù),異常是指數(shù)據(jù)以及關(guān)聯(lián)某些特定疾病的指標(biāo)偏離個(gè)體基準(zhǔn)的情況。因此,對(duì)運(yùn)動(dòng)手環(huán)采集的健康數(shù)據(jù)進(jìn)行有效挖掘,判斷數(shù)據(jù)異常關(guān)聯(lián),分析導(dǎo)致數(shù)據(jù)異常的因素,對(duì)改善用戶生活方式,提升用戶健康狀況具有重要作用。
異常檢測(cè)也被稱作離群檢測(cè),目的是發(fā)現(xiàn)在不同機(jī)制下,那些區(qū)別于大部分?jǐn)?shù)據(jù),且足夠引起懷疑的少部分?jǐn)?shù)據(jù)。學(xué)者們使用多種機(jī)器學(xué)習(xí)方法致力于提高離群檢測(cè)的效率。Knorr 等[3-4]提出基于距離的離群點(diǎn)檢測(cè)方法,擺脫了離群點(diǎn)檢測(cè)算法中對(duì)數(shù)據(jù)的分布模型和分布參數(shù)的限制。隨后,Boriah 等[5]基于K-近鄰算法衡量對(duì)象的離群度,該方法可以處理大規(guī)模數(shù)據(jù)集。朱利等[6]提出一種快速K-近鄰的最小生成樹離群檢測(cè)方法,該方法基于距離比值的加權(quán)排序離群因子,能大幅降低時(shí)間復(fù)雜度,提高計(jì)算效率。Breunig 等[7]提出基于密度的離群點(diǎn)檢測(cè)算法,給出對(duì)象是離群點(diǎn)的程度定量度量,通過考察對(duì)象與其近鄰“密度”的差異來判斷該對(duì)象是否為離群點(diǎn),這種差異通過局部離群因子(local outlier factor,LOF)衡量。但由于LOF算法基于歐氏距離,當(dāng)數(shù)據(jù)點(diǎn)之間存在特殊分布時(shí),對(duì)象之間的相似程度無法由歐式距離準(zhǔn)確反映出;并且此方法不適用于高維數(shù)據(jù),高維空間數(shù)據(jù)的高度稀疏性使得數(shù)據(jù)點(diǎn)之間幾乎是等距離的,每個(gè)數(shù)據(jù)點(diǎn)在密度的意義上都可以看作是一個(gè)異常點(diǎn)。Ghoting 等[8]針對(duì)處理高維數(shù)據(jù)集的問題,提出二段算法RBRP(recursive binning and reprojection)。該算法基于索引提高計(jì)算效率,循環(huán)嵌套減少操作I/O次數(shù),降低時(shí)間復(fù)雜度。Tang等[9]引入鏈?zhǔn)骄嚯x的概念,通過計(jì)算對(duì)象與其K-近鄰的邊長度加權(quán)和,提出基于連通性的離群因子(connectivity-based outlier factor,COF)。He 等[10]基于聚類提出聚類離群因子(cluster based local outliers factor,CBLOF)算法,一方面能夠檢測(cè)出離群簇,另一方面又提高了局部離群點(diǎn)的檢測(cè)精度。Zhu 等[11]結(jié)合最小生成樹提出KNMOD(K-nearest neighbor and minimum spanning tree-based outliers detection)算法,降低時(shí)間復(fù)雜度,提高檢測(cè)效率。錢景輝等[12]采用多示例學(xué)習(xí)(multi-instance learning,MIL)框架,結(jié)合退化策略和權(quán)重調(diào)整方法檢測(cè)局部離群點(diǎn)。Xu等[13]基于核密度估計(jì)(kernel density estimation,KDE)提出一種新的離群檢測(cè)算法,該算法在利用KDE 計(jì)算數(shù)據(jù)概率密度函數(shù)最優(yōu)估計(jì)的基礎(chǔ)上,建立信度函數(shù)檢測(cè)離群點(diǎn)。楊宜東等[14]利用核密度估計(jì)方法,實(shí)現(xiàn)全局?jǐn)?shù)據(jù)的離群點(diǎn)檢測(cè)。Ngan等[15]驗(yàn)證了核密度估計(jì)方法在大規(guī)模的數(shù)據(jù)集上比One-Class SVM 具有更好的離群檢測(cè)效果。Tang 等[16]考慮反向最近鄰并且共享對(duì)象的最近鄰以進(jìn)行核密度分布估計(jì),提出基于相對(duì)密度的離群值得分(relative density-based outlier score,RDOS)來測(cè)量對(duì)象的局部離群程度。胡彩平等[17]引用信息熵的概念,同時(shí)利用加權(quán)距離來代表各對(duì)象之間的距離,提出基于密度的局部離群點(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ù)級(jí)增長,時(shí)間復(fù)雜度會(huì)迅速增加,降低了算法的性能。
鑒于此,針對(duì)運(yùn)動(dòng)手環(huán)數(shù)據(jù)存在與健康狀況關(guān)聯(lián)異常值且手環(huán)數(shù)據(jù)在高維空間的高度稀疏性降低異常檢測(cè)準(zhǔn)確率的問題,本文提出了一種基于高斯核密度估計(jì)的離群點(diǎn)檢測(cè)方法。該方法在采用t-SNE(t-distributed stochastic neighbor embedding)算法[19]對(duì)數(shù)據(jù)集進(jìn)行特征提取的基礎(chǔ)上,利用高斯核函數(shù)改進(jìn)LOF算法,計(jì)算局部離群因子,據(jù)此檢測(cè)出離群點(diǎn)。
高斯核密度估計(jì)局部離群因子算法的詳細(xì)描述如下:
(1)高斯核局部密度估計(jì)
設(shè)k為正整數(shù),則對(duì)象m的高斯核局部密度為:
式中,G(?)表示高斯核函數(shù);||xn-xm||表示對(duì)象m和對(duì)象n的歐式距離;σ為所有樣本點(diǎn)兩兩之間距離的標(biāo)準(zhǔn)差,整個(gè)樣本點(diǎn)之間距離的變化程度可以引用標(biāo)準(zhǔn)差來反映。
式(2)表示對(duì)象m和n的高斯核距離。高斯核局部密度基于高斯核距離,對(duì)象m的K-近鄰鄰域可以通過計(jì)算各點(diǎn)與m的高斯核距離來確定。同時(shí),對(duì)象m和其近鄰點(diǎn)之間距離的衰減程度也可由高斯核距離反映。對(duì)于離群點(diǎn),它們與鄰近點(diǎn)之間距離的衰減程度大于正常點(diǎn),因此它們的高斯核局部密度較小。相反,正常點(diǎn)與鄰近點(diǎn)之間距離的衰減程度較小,因此它們的高斯核局部密度接近于1。
(2)高斯核局部離群因子
對(duì)象m的高斯核局部離群因子記作:
在被檢測(cè)樣本點(diǎn)中,那些高斯核局部密度低于近鄰點(diǎn)的樣本點(diǎn)被視作離群點(diǎn)。若m是被檢測(cè)的點(diǎn),n是m的一個(gè)鄰近點(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)。
對(duì)高斯核密度估計(jì)局部離群因子算法判定閾值的穩(wěn)定性進(jìn)行如下分析。首先,對(duì)于任意對(duì)象m,給出如下定義:
其中,dmin(m)、dmax(m)分別是m的K-近鄰鄰域中距離m最近的點(diǎn)與最遠(yuǎn)的點(diǎn)的距離:imin(m)、imax(m)分別表示m的K-近鄰對(duì)象的K-近鄰鄰域內(nèi)距離樣本中心的最小距離和最大距離。假設(shè)對(duì)象m為任意數(shù)據(jù)集D中的一個(gè)樣本點(diǎn),正整數(shù)k滿足1 ≤k≤|D|,對(duì)象m的Fk(m)滿足:
證明如下:
由式(9)可知,對(duì)象m的Dk(m)滿足:
對(duì)象o為對(duì)象n的K-近鄰鄰域中的一點(diǎn),對(duì)于任意o滿足:
由式(11)可知,對(duì)象n的Dk(m)滿足:
由式(10)、式(12)可知,對(duì)象m的Fk(m)滿足:
由式(8)可知,對(duì)象m的Fk(m)值的上下限較為緊密,如果m為正常對(duì)象,則有d≈i,其Fk(m)的上下邊界值均趨近于1,因此對(duì)象m的Fk(m)值也趨近于1??梢杂?作為閾值,判定正常點(diǎn)與離群點(diǎn)。
(1)樣本數(shù)據(jù)集預(yù)處理
本方法首先對(duì)采集到的手環(huán)樣本數(shù)據(jù)進(jìn)行預(yù)處理。通過運(yùn)動(dòng)手環(huán)能夠采集到用戶一天內(nèi)步數(shù)、心率(設(shè)定為一分鐘采集一次)、卡路里、全天睡眠時(shí)間、深度睡眠時(shí)間、淺睡眠時(shí)間等一系列數(shù)據(jù)。數(shù)據(jù)集包含M個(gè)用戶T天的活動(dòng)數(shù)據(jù),經(jīng)過選取i個(gè)特征指標(biāo)后,每一條運(yùn)動(dòng)數(shù)據(jù)可以表示為i維向量X=[x1,x2,…,xi]T。根據(jù)用戶活動(dòng)類型可將其分為輕運(yùn)動(dòng)、靜坐、運(yùn)動(dòng)以及睡眠四類,這樣可以較完整地反映用戶一天的活動(dòng)情況。因此,本文選取的特征指標(biāo)為總心率均值、總心率峰值、輕運(yùn)動(dòng)心率均值、輕運(yùn)動(dòng)心率峰值、靜坐心率均值、靜坐心率峰值、運(yùn)動(dòng)心率均值、運(yùn)動(dòng)心率峰值、睡眠心率均值、睡眠心率峰值、步數(shù)、卡路里、全天睡眠時(shí)間、深睡眠時(shí)間、淺睡眠時(shí)間。
(2)特征提取
在高維空間中,隨著數(shù)據(jù)規(guī)模的增加,時(shí)間復(fù)雜度會(huì)迅速增加,性能急劇下降;同時(shí),數(shù)據(jù)在高維空間中具有高度稀疏性,這使得每個(gè)數(shù)據(jù)點(diǎn)之間幾乎等距,從而在密度的意義上都可被視作異常點(diǎn),導(dǎo)致檢測(cè)算法的準(zhǔn)確率大大降低。由文獻(xiàn)[19]可知t-SNE算法將高維數(shù)據(jù)映射在二維空間中,使得高維度下距離較近即相似的數(shù)據(jù)映射后更聚合,較遠(yuǎn)的更疏遠(yuǎn),較好地捕捉了數(shù)據(jù)的整體特性,提高了局部結(jié)構(gòu)能力。因此本文采用t-SNE 算法對(duì)高維數(shù)據(jù)進(jìn)行特征提取,為后續(xù)在二維空間計(jì)算所有樣本的Fk(m)值提供支撐。
(3)計(jì)算每條數(shù)據(jù)的GKDELOF(Gaussian kernel density estimation-based local outlier factor)值
將特征提取后的二維數(shù)據(jù)集作為輸入,由以下公式計(jì)算每個(gè)對(duì)象m的Fk(m)值。
用Fk(m)值對(duì)對(duì)象的離群程度進(jìn)行量化,并與離群程度閾值1比較,輸出樣本數(shù)據(jù)離群點(diǎn)。
輸入:所有數(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。
仿真實(shí)驗(yàn)基于Matlab 2015b、PyCharm 平臺(tái),計(jì)算機(jī)的硬件配置為:Windows 10操作系統(tǒng)、Intel Core i5-5200U CPU、3.2 GHz、16 GB RAM。
本文選取了8個(gè)數(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)行了比較。選取理由為,本文是對(duì)于LOF 算法的改進(jìn),因此選取LOF 算法作為對(duì)比算法;CBLOF 算法是基于聚類的經(jīng)典離群檢測(cè)算法;文獻(xiàn)[16]的算法是基于密度并利用核密度分布估計(jì)從而檢測(cè)離群點(diǎn),本文也是將核密度作為一個(gè)改進(jìn)點(diǎn);IForest算法是目前較新的基于網(wǎng)格劃分的算法,檢測(cè)效果較好,廣泛使用。
本文所用的評(píng)估異常檢測(cè)算法的主要性能指標(biāo)包括正確率(accuracy,ACC)、假負(fù)率(false negative rate,F(xiàn)NR)、假正率(false positive rate,F(xiàn)PR)和AUC(area under curve)。一個(gè)較優(yōu)性能的異常檢測(cè)算法應(yīng)該具有較低的FNR和FPR,以及較高的ACC和AUC。
為驗(yàn)證本文方法的適用性,由本文方法檢測(cè)不同數(shù)據(jù)集后繪制的ROC曲線圖如圖1所示。
Fig.1 ROC curve of different data sets by GKDELOF圖1 GKDELOF算法檢測(cè)不同數(shù)據(jù)集的ROC曲線
從圖1的ROC 曲線結(jié)果圖可以看出,本文提出的高斯核密度估計(jì)異常值檢測(cè)方法在不同數(shù)據(jù)集上都取得了較好的效果。其中,在Shuttle 數(shù)據(jù)集上取得了最好的檢測(cè)效果;僅在Arrhythmia 和Pima 數(shù)據(jù)集上的效果較不理想。對(duì)ROC曲線的定量分析結(jié)果如表2中的AUC值所示。
為驗(yàn)證本文方法中特征提取對(duì)于處理高維數(shù)據(jù)的檢測(cè)準(zhǔn)確率的提高,取文獻(xiàn)[18]中使用的維度較高的兩個(gè)數(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曲線的對(duì)比,對(duì)比結(jié)果如圖2所示。
Fig.2 Comparison of ROC curves before and after dimensionality reduction of high dimensional data圖2 高維數(shù)據(jù)降維前后ROC曲線比較
由圖2對(duì)比結(jié)果可以知道,3個(gè)數(shù)據(jù)集在經(jīng)過特征提取后,檢測(cè)的效果都有一定的提升。根據(jù)ROC曲線下面積AUC值得出,在經(jīng)過降維處理之后,提升最明顯的是Madelon數(shù)據(jù)集,AUC值為0.85。Isolet1234數(shù)據(jù)集次之,AUC值提高了13%。在Arrhythmia 數(shù)據(jù)集上的提升效果并不明顯,主要是由于數(shù)據(jù)集中定類屬性較多,對(duì)于定類屬性值的運(yùn)算不能真實(shí)度量樣本相似性,因此影響了檢測(cè)精度。此實(shí)驗(yàn)說明運(yùn)用t-SNE 算法提取特征后,對(duì)于高維數(shù)據(jù),能夠進(jìn)一步提升檢測(cè)效果。
由于本文算法和LOF 算法以及文獻(xiàn)[16]的算法都需要采用最近鄰方法,因此為了評(píng)估不同k值對(duì)算法性能的影響,本文對(duì)于這3個(gè)算法,作用在Shuttle數(shù)據(jù)集上,取多次不同k值,對(duì)比各個(gè)算法的AUC值,結(jié)果如圖3所示。
從圖3中可以看出本文算法在取不同k值時(shí)的表現(xiàn)都優(yōu)于其他兩種算法,并且當(dāng)k=5時(shí),對(duì)于本文算法性能的提升是最大的,此后的AUC值一直穩(wěn)定在0.96以上。
Fig.3 Performance of AUC with different k values for data set of Shuttle圖3 在Shuttle數(shù)據(jù)集上不同k值時(shí)的AUC值
為驗(yàn)證本文算法的優(yōu)勢(shì),將本文算法與LOF 算法、CBLOF 算法、文獻(xiàn)[16]算法和IForest 算法作對(duì)比,計(jì)算評(píng)估離群檢測(cè)算法的性能指標(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é)果對(duì)比
Table 3 Parameter setting information表3 參數(shù)設(shè)置信息
從表2中的對(duì)比實(shí)驗(yàn)結(jié)果可以看出,除了Arrhythmia和Annthyroid數(shù)據(jù)集之外,基于高斯核密度估計(jì)的異常值檢測(cè)方法相對(duì)于4個(gè)對(duì)比算法對(duì)其余6個(gè)數(shù)據(jù)集具有更高的檢測(cè)準(zhǔn)確率。其AUC值也僅在Arrhythmia和Pima數(shù)據(jù)集上低于其他算法。其中,在Wcd 數(shù)據(jù)集上,檢測(cè)準(zhǔn)確率達(dá)到了98%,遠(yuǎn)高于IForest 的87%。在Breastw 數(shù)據(jù)集上,本文算法的4個(gè)檢測(cè)指標(biāo)都優(yōu)于對(duì)比算法,且AUC值達(dá)到了最高的0.99。當(dāng)數(shù)據(jù)集較小時(shí)(Lym),AUC值達(dá)到了0.94,準(zhǔn)確率為92%,大幅高于其他算法,同時(shí)假正率也是最低的;當(dāng)數(shù)據(jù)集維度較高時(shí)(Arrhythmia),雖然其AUC值不是最高的,但與由IForest 算法取得的最高值0.68接近,且針對(duì)此數(shù)據(jù)集,5個(gè)對(duì)比算法檢測(cè)效果都不理想。在數(shù)據(jù)集較大的情況下,本文方法的優(yōu)勢(shì)也遠(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ù)對(duì)LOF算法進(jìn)行改進(jìn),能夠大幅提高檢測(cè)準(zhǔn)確率。
在驗(yàn)證了算法的性能后,利用該算法在采集到的手環(huán)健康數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),找出異常值。圖4是將數(shù)據(jù)集經(jīng)過特征提取后,采用本文GKDELOF算法進(jìn)行異常檢測(cè)的結(jié)果。其中白色點(diǎn)表示正常數(shù)據(jù),紅色點(diǎn)表示異常數(shù)據(jù)。
Fig.4 Outlier detection result by GKDELOF on health data圖4 GKDELOF算法在健康數(shù)據(jù)上離群檢測(cè)實(shí)驗(yàn)結(jié)果
Fig.5 Outlier detection result by IForest on health data圖5 IForest算法在健康數(shù)據(jù)上離群檢測(cè)實(shí)驗(yàn)結(jié)果
為驗(yàn)證本文算法的優(yōu)勢(shì),圖5為利用檢測(cè)效果僅次于本文算法的IForest算法在同一健康數(shù)據(jù)集上進(jìn)行異常檢測(cè)的實(shí)驗(yàn)結(jié)果。對(duì)比圖4和圖5可以看出,兩種方法對(duì)于明顯的離群樣本點(diǎn)都可以檢測(cè)出來,但I(xiàn)Forest算法在簇群邊緣處存在漏判和誤判。標(biāo)號(hào)為1、5、6的樣本點(diǎn)為漏判,標(biāo)號(hào)為2、3、4的樣本點(diǎn)為誤判。而本文算法在檢測(cè)簇邊緣離群點(diǎn)時(shí),未存在明顯漏判或誤判情況。
本文針對(duì)智能穿戴設(shè)備普及背景下,利用運(yùn)動(dòng)手環(huán)采集的活動(dòng)數(shù)據(jù)存在未知異常數(shù)據(jù)的問題,提出一種基于高斯核密度估計(jì)的健康數(shù)據(jù)異常值檢測(cè)方法。該方法在利用t-SNE算法進(jìn)行特征提取,增強(qiáng)局部結(jié)構(gòu)能力的基礎(chǔ)上,通過高斯核函數(shù)改進(jìn)LOF算法,提出基于高斯核密度估計(jì)離群因子算法,該方法的判定閾值較為穩(wěn)定。在實(shí)驗(yàn)部分,利用異常檢測(cè)具有代表性的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),驗(yàn)證了特征提取的作用;并且對(duì)比了其他4種異常檢測(cè)算法,實(shí)驗(yàn)結(jié)果表明,該方法具有較好的檢測(cè)效果。最后,利用該方法在真實(shí)數(shù)據(jù)集上找出異常值。
在數(shù)據(jù)預(yù)處理方面,選取的特征指標(biāo)是否能夠有效地表現(xiàn)數(shù)據(jù)特征在一定程度上會(huì)影響檢測(cè)的準(zhǔn)確率,因此還可以從數(shù)據(jù)特征指標(biāo)選擇方面做進(jìn)一步研究。