基于K-近鄰的多元時(shí)序預(yù)測(cè)與三支釋義

侯帥,張智恒,溫佐承,沈少朋

(四川旅游學(xué)院 信息與工程學(xué)院,四川 成都 610100)

0 引言

多元時(shí)序數(shù)據(jù)通常產(chǎn)生于傳感器網(wǎng)絡(luò)。它是物聯(lián)網(wǎng)基礎(chǔ)建設(shè)的重要組成,也是精準(zhǔn)感知目標(biāo)對(duì)象所不可替代的手段。它在各種監(jiān)測(cè)場(chǎng)景,如空氣質(zhì)量和設(shè)備運(yùn)維中廣泛存在。根據(jù)目標(biāo)對(duì)象的歷史數(shù)據(jù)預(yù)測(cè)其在未來(lái)時(shí)刻下的狀態(tài)是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要分支,常見于行為預(yù)測(cè)[1]、風(fēng)險(xiǎn)預(yù)警[2]等重要應(yīng)用場(chǎng)景。

三支決策理論起源于解決分類問(wèn)題的決策粗糙集領(lǐng)域,逐漸演變?yōu)椤叭侄巍钡某墒焖枷隱3]。因此在主動(dòng)學(xué)習(xí)[4]、聚類[5]、模式挖掘[6]、推薦系統(tǒng)[7-8]、形式概念分析[9]、粒計(jì)算[10]等領(lǐng)域得到了極大的擴(kuò)展,也是啟發(fā)本研究工作的重要因素。

作為協(xié)同過(guò)濾[11]原理的一種技術(shù)實(shí)現(xiàn),K近鄰在推薦系統(tǒng)[12]中受到了廣泛關(guān)注和深入研究。此外,由于該技術(shù)所具有的數(shù)據(jù)驅(qū)動(dòng)特性,在分類[13]、聚類[14]等研究領(lǐng)域也扮演著重要角色。然而,該技術(shù)在多元時(shí)序數(shù)據(jù)上的狀態(tài)預(yù)測(cè)技術(shù)還有待豐富。

本文針對(duì)多元時(shí)序數(shù)據(jù)的預(yù)測(cè)問(wèn)題提出了一種新的基于矩陣相似度的K近鄰預(yù)測(cè)算法,受到三支決策思想的啟發(fā)進(jìn)而設(shè)計(jì)了一種基于頻率分布函數(shù)的預(yù)測(cè)結(jié)果三支劃分策略及其釋義。主要貢獻(xiàn)包括以下3個(gè)方面。

(1)提出了一種新的三支決策狀態(tài)預(yù)測(cè)算法。不僅能較為準(zhǔn)確地獲得下一時(shí)刻的預(yù)測(cè)結(jié)果,還能提供更豐富的、可解釋性高的結(jié)果。

(2) 區(qū)別于傳統(tǒng)信息系統(tǒng)中的行樣本形式,假設(shè)當(dāng)前某時(shí)段內(nèi)的數(shù)據(jù)作為目標(biāo)樣本,且關(guān)注它下一時(shí)刻發(fā)生各種狀態(tài)的可能性。該目標(biāo)樣本與其前K個(gè)最相似的矩陣均為具備時(shí)序特性的數(shù)據(jù)矩陣。

(3) 將經(jīng)典的基于向量的相似度擴(kuò)展為能夠度量矩陣相似性的指標(biāo),顯著地豐富了由矩陣第一范式和第二范式定義的距離度量,并通過(guò)實(shí)驗(yàn)討論了各種指標(biāo)的性能表現(xiàn)。

三支決策是一種對(duì)粗糙集理論中規(guī)則的新解釋。針對(duì)某集合的正域、邊界域和負(fù)域可以分別作出接受、拒絕和延遲決策三種決定。這些決定是分別由各自區(qū)域產(chǎn)生的規(guī)則所驅(qū)動(dòng)的[1]。得益于“三分而治”思想的啟發(fā),人們?cè)诟鱾€(gè)領(lǐng)域先后提出了豐富的、基于三支決策理論的新研究成果。文獻(xiàn)[4]提出的“TALK”主動(dòng)學(xué)習(xí)算法考慮了教師代價(jià)和誤分類代價(jià),并根據(jù)這兩種代價(jià)將所有實(shí)例劃分為三個(gè)區(qū)域,分別對(duì)應(yīng)了機(jī)器標(biāo)注、人工標(biāo)注和延遲標(biāo)注三種策略。文獻(xiàn)[5]將聚類中實(shí)例和類簇之間的關(guān)系分為三類,即確定屬于,不確定屬于,確定不屬于。對(duì)于從屬關(guān)系不確定的實(shí)例,同樣采用了主動(dòng)學(xué)習(xí)的策略向?qū)＜疫M(jìn)行咨詢。文獻(xiàn)[6]提出了一種新的三支模式及其模式匹配條件。原始的符號(hào)表被劃分成強(qiáng)、中、弱三個(gè)區(qū)間,強(qiáng)字符只能構(gòu)成模式,弱字符只能被忽略,中字符兩者皆可。文獻(xiàn)[7]通過(guò)兩個(gè)可優(yōu)化閾值將推薦行為三分為直接推薦,不推薦以及推廣,如給用戶派發(fā)優(yōu)惠券。文獻(xiàn)[9]和文獻(xiàn)[10]則分別在概念格和粒計(jì)算的熱點(diǎn)領(lǐng)域中結(jié)合三支決策提出了新的理論模型。

K-近鄰(Knearest neighbor,K-NN)算法的核心思想是為預(yù)測(cè)目標(biāo)尋找k個(gè)最相似的實(shí)例對(duì)象，并根據(jù)這些對(duì)象的特性來(lái)預(yù)測(cè)目標(biāo)的新特性[11-14]。因此人們提出了一系列經(jīng)典的相似度和距離以度量不同對(duì)象之間近似和差異程度。設(shè)R為一個(gè)m×n的實(shí)數(shù)矩陣，且對(duì)任意i∈[1,m],j∈[1,n]，Rij表示第i行第j列的數(shù)，Ri*表示第i行實(shí)數(shù)構(gòu)成的集合，Ri*表示第i行的行向量，同理可知對(duì)應(yīng)第j列的集合與列向量。給定R中任意兩行a和b，表1給出了已有度量及其計(jì)算公式。皮爾森系數(shù)P(a,b)與修正余弦相似度MC(a,b)之間的區(qū)別在于中心化的方式不同?；卩従蛹系臄?shù)值型數(shù)據(jù)預(yù)測(cè)方法通常為算數(shù)平均或者加權(quán)平均。

針對(duì)數(shù)值型數(shù)據(jù)，常見的評(píng)價(jià)指標(biāo)有平均絕對(duì)誤差(MAE)以及均方根誤差(RMSE)兩類指標(biāo)。設(shè)R中某已知列向量r*v，其預(yù)測(cè)向量p*v，其中v∈[1,n]。則它們的平均絕對(duì)誤差為

(1)

它們的均方根誤差則為

(2)

兩者常被用作衡量機(jī)器學(xué)習(xí)模型針對(duì)數(shù)值型數(shù)據(jù)預(yù)測(cè)性能的評(píng)價(jià)標(biāo)準(zhǔn)。

1 模型和問(wèn)題

本節(jié)主要描述基于K近鄰技術(shù)[15-17]的三支狀態(tài)預(yù)測(cè)模型與算法實(shí)現(xiàn)。

1.1 基本定義

定義1 多元時(shí)序數(shù)據(jù)(Multivariate Time Series,MTS)[18]。一個(gè)多元時(shí)序數(shù)據(jù)可以被描述為一個(gè)四元組：

(3)

(4)

SP={OW,OW+1,…,Om-1},

(5)

為Om的尋找鄰居的解空間，且該空間的大小為|SP|=m-W。

minΔ(O,O′)

O′∈KSP≥maxΔ(O,O″)

O″∈SP-KSP-{O},

(6)

其中，Δ表示兩個(gè)矩陣之間的相似度。

度量?jī)蓚€(gè)m×n矩陣的距離已有十分成熟的技術(shù)，即矩陣的范數(shù)，其中2范數(shù)最常用。因此，本文接下來(lái)討論矩陣之間的相似度，并在隨后的實(shí)驗(yàn)中與基于范數(shù)理論的矩陣距離進(jìn)行對(duì)比。

根據(jù)定義1到定義3，可給出本文研究問(wèn)題的形式化描述。

問(wèn)題 基于矩陣領(lǐng)域的多元時(shí)序狀態(tài)預(yù)測(cè)。

閱讀意味著改變。閱讀能夠改變我們的一切，改變我們自己，改變我們的學(xué)校，改變我們的城市，改變我們的民族。在第21個(gè)世界圖書日來(lái)臨之際，本刊特此推出“閱讀，最好的教育”專題，希望通過(guò)專家的理論闡釋和學(xué)校的經(jīng)驗(yàn)分享，讓大家看到閱讀對(duì)于教師、學(xué)生的巨大改變力量。閱讀，讓我們的校園變得更美好。

輸出：多元時(shí)序系統(tǒng)在tm+1時(shí)刻的狀態(tài)預(yù)測(cè)值p=(pm+1,1,…,pm+1,n)；

約束條件：領(lǐng)域KSP須滿足式(6)。

該問(wèn)題有兩個(gè)關(guān)鍵步驟：獲得領(lǐng)域以及基于領(lǐng)域預(yù)測(cè)。領(lǐng)域的獲取不僅依賴于參數(shù)k，而且還由算法選擇的相似度指標(biāo)決定。后者是k近鄰算法的基礎(chǔ)與核心。

1.2 新的矩陣相似度

與經(jīng)典的、基于矩陣范數(shù)定義的距離度量指標(biāo)不同，這里給出了以下新的衡量矩陣相似度指標(biāo)。

ΔRC(Oi,Oj)=ΔR×ΔC,

(7)

其中，

(8)

且

(9)

上標(biāo)i和j滿足W≤i,j≤m-1。由表1可知，5種相似度均可被應(yīng)用于式(8)和(9)中，進(jìn)而得到不同的相似度度量指標(biāo)組合。由式(7)可知，總共有35種(單獨(dú)的行列各5種，行列組合25種)相似度組合，具體效果通過(guò)實(shí)驗(yàn)分析和討論。

1.3 預(yù)測(cè)模型

當(dāng)獲得目標(biāo)矩陣O的領(lǐng)域KSP，我們就能通過(guò)快速直接的方法計(jì)算出在tm+1時(shí)刻的狀態(tài)預(yù)測(cè)值。對(duì)領(lǐng)域KSP中的任意矩陣元素Oi，主流的預(yù)測(cè)方法有算數(shù)平均和加權(quán)平均兩種。

(10)

2.加權(quán)平均

(11)

1.4 基于頻率分布的三分策略

對(duì)每個(gè)屬性的歷史數(shù)據(jù)進(jìn)行頻率分布學(xué)習(xí)，得到頻率分布的函數(shù)。該函數(shù)一般通過(guò)計(jì)算極差、計(jì)算組距、決定分點(diǎn)、列分布表等四步獲得。該過(guò)程可通過(guò)現(xiàn)有成熟高效的統(tǒng)計(jì)工具直接實(shí)現(xiàn)。

給定兩個(gè)頻率閾值α,β且0≤α≤β≤1，可將所得任意屬性的分布表劃分為三個(gè)互不相交的區(qū)域POS，BND以及NEG，并分別賦予“罕見”，“少見”，以及“常見”的語(yǔ)義。為了描述的簡(jiǎn)潔性，令統(tǒng)計(jì)所得頻率分布函數(shù)為c(fi,j)，其中i∈[1,m],j∈[1,n]。該分布函數(shù)為MTS中任意取值到其對(duì)應(yīng)的頻率值的映射。因此可得基于頻率信息的三分策略。

(12)

盡管對(duì)于不同的屬性需要設(shè)置不同的α,β組合，但為了實(shí)驗(yàn)的便捷性，本文經(jīng)驗(yàn)性地參考取頻率中位數(shù)的方式確定α和β的取值。即對(duì)MTS中任意屬性aj的頻率分布c(fi,j)而言，都有(1)按照升序排列所有頻率，并將其數(shù)量四等分，也就是等頻劃分為四份；(2)令α為四分之一處的等分值，而β則是二分之一處的等分值，即是所有頻率的中位數(shù)。由于α和β均為頻率閾值，因此對(duì)于所有屬性而言，都有α=0.25且β=0.5。值得注意的是，可能存在某些具體的值域區(qū)間所屬區(qū)域沖突的現(xiàn)象，本文統(tǒng)一將這種區(qū)間劃分到“相對(duì)更常見”的域中。即是說(shuō)，如果某個(gè)值域區(qū)間跨POS和BND域，則將其劃分到BND域中。

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

算法1給出了多元時(shí)序數(shù)據(jù)上的一種基于K-近鄰技術(shù)的狀態(tài)預(yù)測(cè)方法。算法的輸入包括多元時(shí)序數(shù)據(jù)S，滑動(dòng)窗口大小W，以及矩陣鄰域大小k。輸出則為下一時(shí)刻狀態(tài)的預(yù)測(cè)值pm+1,*，表示在m+1時(shí)刻所有屬性的預(yù)測(cè)值所構(gòu)成的向量。式(10)和(11)的不同之處在于預(yù)測(cè)值的計(jì)算方法，而預(yù)測(cè)結(jié)果的形式化描述在問(wèn)題的形式化描述中是完全統(tǒng)一的。

Algorithm 1 K-NN-based State Prediction with Tri-Partition StrategyInput:S=(T,A,V=∪a∈AVa ,f), W, k;Output:pm+1,*);∥各分量形式詳見式(10)或(11)Begin1.Obtain Om and SP with Equations (4) and (5);2.For (each O∈SP) Do;∥遍歷所有可能成為K近鄰的矩陣3.Compute the similarity between O and Om with Equation (7);4.End For5.Find out KSP of Om;∥保留前k個(gè)相似度最高的矩陣6.Compute the prediction for each attribute, namely pm+1,*;∥基于式(10)和(11)獲得預(yù)測(cè)結(jié)果7.Obtain occurrence information with tri-partition strategy with Equation (10);∥三支劃分及其釋義End

3 運(yùn)行實(shí)例

給定一個(gè)如表2所示的空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)集，這里設(shè)置參數(shù)W=2，k=2。將用"**"號(hào)標(biāo)注的時(shí)間點(diǎn)7作為被預(yù)測(cè)的時(shí)刻，它所對(duì)應(yīng)的目標(biāo)矩陣O6則是5、6時(shí)間點(diǎn)下三種指標(biāo)所對(duì)應(yīng)的矩陣，由"*"號(hào)標(biāo)注。此外，我們事先指定行向量為杰卡爾德相似度，列向量采用三角形相似度進(jìn)行計(jì)算。

表2 多元時(shí)序數(shù)據(jù)實(shí)例

第一步：確定目標(biāo)矩陣O6的搜索空間SP={O2,O3,O4,O5}，其中O2表示時(shí)間點(diǎn)1、2下三種指標(biāo)取值所構(gòu)成的矩陣。

第二步：在SP中求解領(lǐng)域KSP。表3給出了目標(biāo)矩陣O6與SP中所有候選矩陣之間的相似度。

表3 目標(biāo)矩陣與其他矩陣間的相似度

以矩陣O6和O3的相似度計(jì)算為例。首先，分別用O3與O6矩陣的三列分別對(duì)應(yīng)計(jì)算三角相似度，并將它們累乘；其次，用它們的兩行分別對(duì)應(yīng)計(jì)算杰卡爾德相似度，并將它們累加；最后，將三角形相似度和杰卡爾德相似度相乘，就可得到O6和O3的相似度。同理可分別得到O6和O2、O3、O4、O5的相似度。由表3可知，目標(biāo)矩陣O6的領(lǐng)域KSP={O4,O5}。

第三步：根據(jù)領(lǐng)域KSP計(jì)算時(shí)刻7的預(yù)測(cè)值。將時(shí)序5、6的對(duì)應(yīng)數(shù)據(jù)進(jìn)行求和再除以k=2，重復(fù)以上過(guò)程，得到所有屬性的算數(shù)平均預(yù)測(cè)值。將時(shí)序5、6的對(duì)應(yīng)數(shù)據(jù)分別乘以O(shè)4、O5的相似度再相加，最后再除以O(shè)4、O5相似度的和，重復(fù)以上過(guò)程，可得到每個(gè)指標(biāo)的加權(quán)預(yù)測(cè)值。結(jié)果如表4所示。

表4 平均和加權(quán)預(yù)測(cè)結(jié)果

4 實(shí)驗(yàn)分析

本節(jié)通過(guò)實(shí)驗(yàn)討論以下2個(gè)問(wèn)題。1.哪些相似度組合在不同的預(yù)測(cè)模型和數(shù)據(jù)集上優(yōu)于矩陣1范數(shù)或2范數(shù)定義的基準(zhǔn)線？2.預(yù)測(cè)結(jié)果基于給定的三支劃分策略有哪些更豐富的語(yǔ)義？

4.1 數(shù)據(jù)集

本文基于北京市奧體、昌平和懷柔三個(gè)地區(qū)的空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)，如PM2.5、PM10、SO2等，進(jìn)行相關(guān)實(shí)驗(yàn)，數(shù)據(jù)集概要信息如表5所示。

表5 數(shù)據(jù)集概要

4.2 問(wèn)題分析與討論

1) 預(yù)測(cè)性能評(píng)價(jià)(問(wèn)題1)

圖1描述了算法在奧體空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)上的預(yù)測(cè)性能。子圖(a)表示算數(shù)平均預(yù)測(cè)技術(shù)的MAE，其中最小值為0.102 633，對(duì)應(yīng)的k值為2，對(duì)應(yīng)了Triangle(行)Jaccard(列)、Triangle(行)M-Consine(列)、Triangle(行)Pearson(列)相似度指標(biāo)。子圖(b)表示算數(shù)平均預(yù)測(cè)技術(shù)的RMSE，其中最小值為0.136 29，對(duì)應(yīng)的k值為2，有Jaccard(行)Triangle(列)、Triangle(行)Jaccard(列)、Triangle(行)M-Consine(列)、Triangle(行)Pearson(列)等相似度指標(biāo)。子圖(c)表示加權(quán)平均的MAE，其中最小值為0.083 767，對(duì)應(yīng)的k值為4，有Triangle(行)Jaccard(列)等相似度指標(biāo)。子圖(d)表示加權(quán)平均的RMSE，其中最小值為0.118 277，對(duì)應(yīng)的k值為4，有Triangle(行)Jaccard(列)等相似度指標(biāo)。在這四種情況下性能表現(xiàn)均優(yōu)于基準(zhǔn)線的有Triangle(行)Jaccard(列)等相似度指標(biāo)。

圖2描述了算法在昌平空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)上的預(yù)測(cè)性能。子圖(a)表示的MAE最小值為0.179 508，對(duì)應(yīng)的k值為5，有Triangle(行)Jaccard(列)相似度。子圖(b)的RMSE最小值為0.226 803，對(duì)應(yīng)的k值為5，有Triangle(行)Jaccard(列)相似度。

圖1 奧體數(shù)據(jù)集Fig.1 Aoti Dataset

圖2 昌平數(shù)據(jù)集Fig.2 Changping Dataset

子圖(c)的MAE最小值為0.184 15，對(duì)應(yīng)的k值為9，有Triangle(行)Jaccard(列)相似度。子圖(d)表示RMSE最小值為0.282 485，對(duì)應(yīng)的k值為10，有Triangle(行)Jaccard(列)相似度。在這四種情況下性能表現(xiàn)均優(yōu)于基準(zhǔn)線的有Triangle(行)Jaccard(列)等相似度指標(biāo)。

圖3描述了算法在懷柔空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)上的預(yù)測(cè)性能。子圖(a)的MAE最小值為0.140 209，對(duì)應(yīng)的k值為39，有Jaccard(行)Triangle(列)相似度。子圖(b)RMSE最小值為0.191 908，對(duì)應(yīng)的k值為42，有Jaccard(行)Triangle(列)相似度。子圖(c)的MAE最小值為0.158 846，對(duì)應(yīng)的k值為6，有Jaccard(行)Triangle(列)相似度。子圖(d)的RMSE最小值為0.244 758，對(duì)應(yīng)的k值也為6，有Jaccard(行)Triangle(列)相似度。在這四種情況下性能表現(xiàn)均優(yōu)于基準(zhǔn)線的有Jaccard(行)Triangle(列)等相似度指標(biāo)。

2) 基于三分策略的語(yǔ)義解釋(問(wèn)題2)

為了描述的簡(jiǎn)潔性，本節(jié)僅以?shī)W體空氣質(zhì)量觀測(cè)數(shù)據(jù)為例對(duì)三支劃分及其釋義進(jìn)行說(shuō)明。表6和表7分別給出了2.4節(jié)在奧體數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。表6僅展示了三個(gè)具有代表性的檢測(cè)指標(biāo)。

由表6可知，每種屬性對(duì)應(yīng)的三分策略都不一樣，這是由于各自的分布規(guī)律不同所導(dǎo)致的。所幸閾值對(duì)于每個(gè)屬性都是一致的，保證了劃分策略的易用性。

由表7可知，盡管算數(shù)平均和加權(quán)平均預(yù)測(cè)的結(jié)果有一定的出入，但三支語(yǔ)義是一致的。這種對(duì)結(jié)果的統(tǒng)一描述能夠有效減少歧義，提高本文算法的決策支持能力。

5 結(jié)論與展望

本文提出了一種面向多元時(shí)序數(shù)據(jù)的K-近鄰預(yù)測(cè)模型。該模型能夠融合現(xiàn)階段絕大部分向量相似度指標(biāo)并用于目標(biāo)矩陣領(lǐng)域的求解。在三個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明基于Triangle和Jaccard的組合相似度具有更強(qiáng)的泛化能力?；陬l率分布直方圖的三支語(yǔ)義解釋策略能夠直觀地提高測(cè)量結(jié)果的可讀性，提供更加豐富的決策支持信息。未來(lái)的研究工作主要包括以下三個(gè)方面：

圖3 懷柔數(shù)據(jù)集Fig.3 Huairou Dataset

表6 奧體數(shù)據(jù)集上的三分策略

表7 奧體數(shù)據(jù)集上的三支釋義

研究適用于符號(hào)型多元時(shí)序數(shù)據(jù)的三支K-近鄰預(yù)測(cè)模型與算法。

研究基于強(qiáng)化學(xué)習(xí)的數(shù)值型和符號(hào)型多元時(shí)序預(yù)測(cè)模型與算法。

研究更加合理的三支劃分策略以及更豐富的三支語(yǔ)義解釋策略。