基于Hellinger 距離的正態(tài)云相似性度量方法及應(yīng)用研究

許昌林，徐浩

（1. 北方民族大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，寧夏 銀川 750021; 2. 北方民族大學(xué) 寧夏智能信息與大數(shù)據(jù)處理重點(diǎn)實(shí)驗(yàn)室，寧夏 銀川 750021）

隨著信息技術(shù)不斷進(jìn)步，信息過(guò)載問(wèn)題日益突出推薦系統(tǒng)是解決過(guò)載問(wèn)題的一種手段，由Goldberg 等[1]提出的協(xié)同過(guò)濾推薦系統(tǒng)是應(yīng)用最廣泛的一種，已被阿里巴巴、亞馬遜等電商平臺(tái)廣泛應(yīng)用。云模型作為研究不確定性的一種工具，能有效處理推薦系統(tǒng)中的不確定信息[2-4]，同時(shí)云模型在用戶識(shí)別[5]、多屬性決策與優(yōu)化[6-7]、綜合評(píng)價(jià)[8]等領(lǐng)域也得到廣泛應(yīng)用，其中云概念相似度扮演重要角色。因此，構(gòu)造合適的相似度不僅能夠降低計(jì)算復(fù)雜度而且能夠提升運(yùn)行效率。如張光衛(wèi)等[3]將云概念數(shù)字特征作為向量構(gòu)造夾角余弦得到云概念相似性比較方法(likeness comparing method based on cloud model，LICM)，并將其應(yīng)用于協(xié)同過(guò)濾推薦。但LICM 將各數(shù)字特征賦予相同權(quán)重，而數(shù)字特征中期望往往大于熵和超熵，導(dǎo)致LICM 區(qū)分能力較弱。李海林等[9]利用云概念幾何特征提出了基于期望曲線的云模型(expectation based cloud model，ECM)相似度和基于最大邊界曲線的云模型(maximum boundary based cloud model，MCM)相似度，區(qū)分度較好但當(dāng)云概念數(shù)量增加時(shí)，ECM 和MCM 計(jì)算復(fù)雜度會(huì)急劇增加。汪軍等[10]將云概念形狀相似性和距離相似性結(jié)合構(gòu)建了云概念綜合相似度量PDCM(shape and distance based on cloud model)，并將其應(yīng)用到分類問(wèn)題中取得了一定效果，而參數(shù)擬合和選擇會(huì)影響精度。此外，有學(xué)者從貼近度、概念躍升、散度和多粒度等方面給出云概念相似度[11-14]，取得一定效果。Li 等[15]從區(qū)分性、有效性、穩(wěn)定性和可解釋性方面分析了以上相似度方法優(yōu)缺點(diǎn)。

基于此，本文主要工作：1) 從正態(tài)云的特征曲線(如期望曲線、內(nèi)外包絡(luò)曲線等)出發(fā)，融合正態(tài)云的分布特性，利用Hellinger 距離刻畫概率分布間相似性的特點(diǎn)，提出了一種基于Hellinger距離的正態(tài)云相似性度量方法，該方法兼顧了云概念的數(shù)字特征和分布特性，并討論了所提方法的性質(zhì)；2)設(shè)計(jì)了兩種正態(tài)云相似度算法，即基于Hellinger 距離及期望曲線的正態(tài)云相似性度量方法(Hellinger distance based expectation curve of cloud model，HECM)和基于Hellinger 距離及特征曲線的正態(tài)云相似性度量方法(Hellinger distance based characteristic curve of cloud model，HCCM)，并將這2 種方法與已有LICM、ECM、MCM 和PDCM 方法從3 個(gè)方面進(jìn)行對(duì)比分析。首先進(jìn)行數(shù)值模擬仿真實(shí)驗(yàn)，利用云概念差異度指標(biāo)驗(yàn)證了本文方法具有較好的區(qū)分能力和可行性；其次，在時(shí)間序列數(shù)據(jù)集上進(jìn)行分類實(shí)驗(yàn)，結(jié)合分類錯(cuò)誤率和CPU 時(shí)間代價(jià)進(jìn)行對(duì)比分析，結(jié)果表明本文方法具有較好的分類性能且時(shí)間代價(jià)較低；最后，將本文方法應(yīng)用于協(xié)同過(guò)濾推薦系統(tǒng)，在電影數(shù)據(jù)集MovieLens 100k 上進(jìn)行實(shí)驗(yàn)分析，采用平均絕對(duì)偏差和均方根誤差指標(biāo)進(jìn)行精度度量，實(shí)驗(yàn)結(jié)果表明本文方法在用戶評(píng)分?jǐn)?shù)據(jù)極端稀疏的情況下，仍能取得較理想的推薦質(zhì)量。

1 正態(tài)云及現(xiàn)有云概念相似度方法

1.1 正態(tài)云及正態(tài)云變換

云模型由數(shù)字特征描述不確定性概念整體特性。不同概率分布的云構(gòu)成不同云模型，鑒于正態(tài)分布的重要性和鐘型隸屬函數(shù)的普適性[16]，正態(tài)云模型及其相關(guān)應(yīng)用得到了廣泛研究，相關(guān)定義如下。

定義1[2,17]設(shè)U是一個(gè)用精確數(shù)值表示的定量論域，C是論域U上的定性概念，若定量值x∈U，且x是定性概念C的一次隨機(jī)實(shí)現(xiàn)，x對(duì)C的確定度為μ(x)∈[0,1]是具有穩(wěn)定傾向的隨機(jī)數(shù)，則x在論域U上的分布稱為云，每個(gè)x稱為一個(gè)云滴。

定義2[17]設(shè)U是一個(gè)用精確數(shù)值表示的定量論域，C是U上用數(shù)字特征(Ex,En,He)表示的定性概念。若定量值x∈U，且x是定性概念C的一次隨機(jī)實(shí)現(xiàn)，若x滿足：x=RN(Ex,|y|)，其中，y=RN(En,He)，且x對(duì)C的 確定度滿足：

則x在論域U上的分布稱為二階正態(tài)云。這里y=RN(En,He)表示以En為期望，以He為標(biāo)準(zhǔn)差的正態(tài)隨機(jī)數(shù)。

正態(tài)云主要通過(guò)正態(tài)云變換實(shí)現(xiàn)定性概念與定量數(shù)值間的相互轉(zhuǎn)換，其中正向正態(tài)云變換將表征概念內(nèi)涵的數(shù)字特征C(Ex,En,He)轉(zhuǎn)化為定量數(shù)值。根據(jù)定義2，二階正向正態(tài)云變換(the 2ndorder forward normal cloud transformation，2nd-FNCT)見(jiàn)算法1。比如用數(shù)字特征C(25，3，0.5)表征定性概念“年輕人”的內(nèi)涵[17]，Ex=25表示對(duì)“年輕人”的總體期望年齡，由算法1 可得“年輕人”的云圖如圖1 所示。

圖1 概念“年輕人”C(25, 3, 0.5)的云圖Fig. 1 Cloud map of concept “young people” C(25, 3, 0.5)

算法1[17]2nd-FNCT 算法

輸入三個(gè)數(shù)字特征(Ex,En,He)和云滴個(gè)數(shù)n

輸出n樣本點(diǎn)(云滴)xi和μ(xi)(i=1,2,···,n)

1) 以En為期望，He為標(biāo)準(zhǔn)差，生成一個(gè)正態(tài)隨機(jī)數(shù)yi=RN(En,He)；

2) 以Ex為期望， |yi|為標(biāo)準(zhǔn)差，生成一個(gè)正態(tài)隨機(jī)數(shù)xi=RN(Ex,|yi|)；

4) 具有確定度μ(xi)的xi成為數(shù)域中的一個(gè)云滴，重復(fù)步驟1) ～3)，直至產(chǎn)生要求的n個(gè)云滴xi為止。

逆向云變換是將定量數(shù)值有效轉(zhuǎn)換為由數(shù)字特征C(Ex,En,He)表示的定性概念。目前已有多種逆向云變換算法[17]，本文使用基于樣本一階絕對(duì)中心矩和樣本方差的逆向云變換算法(single-step backward cloud transformation algorithm based on the first-order absolutely center moment，SBCT-1stM)，如算法2 所示。

算法2[17]SBCT-1stM 算法

輸入樣本點(diǎn)xi(i=1,2,···,n)

輸出反映定性概念數(shù)字特征的估計(jì)值

1) 根據(jù)樣本點(diǎn)xi計(jì)算樣本均值一階樣本絕對(duì)中心矩和樣本方差S2=

2) 分別計(jì)算期望、熵和超熵的估計(jì)值：

1.2 二階正態(tài)云的特征曲線

特征曲線能夠在一定程度上反映云概念的幾何特征。由定義2 和正態(tài)分布的“ 3σ”原則知：

當(dāng)0 ＜He＜En/3時(shí)，有99.74% 的云滴確定度μ(x)處于曲線μOut(x) 與μIn(x)之間的區(qū)域[17-19]，其中

則稱μOut(x)和 μIn(x)分別為二階正態(tài)云的外包絡(luò)曲線和內(nèi)包絡(luò)曲線(如圖2)。當(dāng)超熵He=0 時(shí)，云滴確定度聚集分布在曲線上， 稱μExp(x)為二階正態(tài)云的期望曲線(如圖2)。因此，對(duì)定性概念有貢獻(xiàn)的云滴99.74%都落在區(qū)間[En-3He,En+3He]中，本文正是基于這一特點(diǎn)來(lái)構(gòu)建云概念相似度量。

圖2 二階正態(tài)云概念C(25, 3, 0.5)的特征曲線Fig. 2 Characteristic curve of 2nd- order normal cloud concept C (25, 3, 0.5)

1.3 現(xiàn)有正態(tài)云概念相似度算法

根據(jù)前文所述，下面對(duì)已有正態(tài)云概念相似度算法LICM、ECM、MCM 和PDCM 進(jìn)行簡(jiǎn)要介紹。

算法3[3]LICM 算法

輸入數(shù)字特征和

輸出相似度SLICM(C1,C2)

1) 令U1=(Ex1,En1,He1),U2=(Ex2,En2,He2)

2) 計(jì)算C1,C2之間的相似度：He2)

算法4[9]ECM 算法

輸入數(shù)字特征C1(Ex1,En1,He1)和C2(Ex2,En2,

輸出相似度SECM(C1,C2)

1) 若Ex1≤Ex2且初始設(shè)置S=0，計(jì)算兩云概念期望曲線μExp(x1)與μExp(x2)的交點(diǎn)與，設(shè)

否則執(zhí)行4)；

算法5[9]MCM 算法

輸入數(shù)字特征C1(Ex1,En1,He1)和C2(Ex2,En2,He2)

輸出相似度SMCM(C1,C2)

1) 若Ex1≤Ex2且初始設(shè)置S=0，計(jì)算兩云概念外包絡(luò)曲線μOut(x1)與μOut(x2)的交點(diǎn)與，設(shè)令

否則，執(zhí)行4)。

算法6[10]PDCM 算法

輸入數(shù)字特征C1(Ex1,En1,He1)和C2(Ex2,En2,He2)

輸出相似度SPDCM(C1,C2)

1) 根據(jù)熵En和超熵He，計(jì)算形狀相似度：

3) 將查找到的擬合參數(shù)a、b、c代入距離相似度：

4) 計(jì)算綜合相似度：

上述算法中，由于LICM 算法直接由數(shù)字特征通過(guò)夾角余弦計(jì)算相似度，所以復(fù)雜度較低且在協(xié)同過(guò)濾實(shí)驗(yàn)中有一定的效果，但大多數(shù)情況下，由于數(shù)字特征的期望值或絕對(duì)值遠(yuǎn)大于熵和超熵，此時(shí)對(duì)數(shù)字特征仍采用相同權(quán)重，會(huì)導(dǎo)致該方法區(qū)分能力較弱，后續(xù)實(shí)驗(yàn)仿真也得到了驗(yàn)證。在ECM 和MCM 算法中，當(dāng)云概念數(shù)量增加時(shí)，期望曲線和外包絡(luò)曲線交疊區(qū)域較復(fù)雜，從而使這兩種算法時(shí)間復(fù)雜度較高。在PDCM 算法中，與θ近似正態(tài)分布關(guān)系，對(duì)參數(shù)θ、a、b、c進(jìn)行擬合，選取合適擬合參數(shù)值計(jì)算距離相似度雖然參數(shù)擬合選取方法降低了時(shí)間復(fù)雜度，但參數(shù)近似選取以及參數(shù)與距離相似度的擬合過(guò)程會(huì)導(dǎo)致計(jì)算誤差增大，從而使PDCM算法精度不夠高。

2 基于Hellinger 距離的正態(tài)云相似性度量方法

針對(duì)現(xiàn)有云概念相似度計(jì)算方法不足，基于正態(tài)云特征曲線從整體上表征正態(tài)云概念的分布和Hellinger 距離刻畫概率分布間相似程度的特點(diǎn)[20]，本文構(gòu)造了正態(tài)云相似性度量方法。

2.1 兩正態(tài)分布間的Hellinger 距離

Hellinger 距離是兩個(gè)統(tǒng)計(jì)樣本或總體之間重疊量的度量，在概率統(tǒng)計(jì)理論中，Hellinger 距離常被用于度量?jī)蓚€(gè)概率分布的相似度。具體來(lái)說(shuō)，連續(xù)型隨機(jī)變量概率分布P和Q的Hellinger 距離[20]定義為

其中，p(x)、q(x)分別為分布P、Q的概率密度函數(shù)典型。情況下，P表示數(shù)據(jù)真實(shí)分布，Q表示數(shù)據(jù)理論分布、模型分布或P的近似分布。DH(P,Q)越大表示兩分布差異性越大。根據(jù)式(5)易得如下結(jié)論。

定理1設(shè)則P和Q的Hellinger 距離為

由定理1 知，對(duì)任意兩正態(tài)分布，其Hellinger距離都可轉(zhuǎn)為由期望與方差的代數(shù)運(yùn)算，無(wú)需進(jìn)行積分運(yùn)算，這一特點(diǎn)會(huì)將大大降低計(jì)算復(fù)雜度，而且進(jìn)一步可得到滿足如下性質(zhì)。

性質(zhì)1設(shè)則

3) 若P和Q同分布于正態(tài)分布，即當(dāng)且僅當(dāng)

證明1) 由距離對(duì)稱性知

化簡(jiǎn)得：

從而有μ1=μ2,σ1=σ2。

2.2 兩正態(tài)云概念間的Hellinger 距離與相似度

由文獻(xiàn)[21]知，二階正態(tài)云概率密度不存在解析解，故直接利用概率密度無(wú)法得到DH(P,Q)的解析式。而正態(tài)云還可由特征曲線刻畫其整體分布，并且將特征曲線按其不確定性特征(熵、超熵) 進(jìn)行縮放時(shí)不會(huì)改變?cè)聘拍顜缀涡再|(zhì)，故本文間接采用正態(tài)云特征曲線計(jì)算DH(P,Q)。首先將特征曲線μExp(x) 、μIn(x)與 μOut(x)分別乘相應(yīng)系數(shù)正態(tài)化，得到對(duì)應(yīng)特征曲線的密度函數(shù)，分別為

根據(jù)定理1，由式(8)～(10)，容易得到基于期望曲線μExp(x)、內(nèi)包絡(luò)曲線μIn(x)和外包絡(luò)曲線μOut(x)的Hellinger 距離。

定理2設(shè)U是用精確數(shù)值表示的定量論域，C1(Ex1,En1,He1)和C2(Ex2,En2,He2)是U上的兩個(gè)二階正態(tài)云概念，則基于期望曲線、內(nèi)包絡(luò)曲線和外包絡(luò)曲線的Hellinger 距離分別為

根據(jù)距離和相似度轉(zhuǎn)換關(guān)系，由此得到兩二階正態(tài)云概念的相似度度量如下。

定理3設(shè)U是用精確數(shù)值表示的定量論域，C1(Ex1,En1,He1)和C2(Ex2,En2,He2)是U上的兩個(gè)二階正態(tài)云概念，那么基于期望曲線、內(nèi)包絡(luò)曲線和外包絡(luò)曲線的相似度分別為

性質(zhì)2設(shè)C1(Ex1,En1,He1)和C2(Ex2,En2,He2)是論域U上的兩個(gè)二階正態(tài)云概念，則

證明由定義5 和性質(zhì)1 容易得證(略)。

2.3 基于Hellinger 距離和特征曲線的相似度算法

根據(jù)具體應(yīng)用領(lǐng)域，由期望曲線、內(nèi)/外包絡(luò)曲線的不同組合，通過(guò)加權(quán)求和形式計(jì)算其相似度，這種方法體現(xiàn)了云概念整體的分布特性。基于此，設(shè)計(jì)了兩種相似度算法，分別見(jiàn)算法7 和算法8。

算法7HECM 算法

輸入數(shù)字特征C1(Ex1,En1,He1)和C2(Ex2,En2,He2)

輸出相似度SHECM(C1,C2)

2) 計(jì)算相似度SHECM(C1,C2)=1-DEHxp(C1,C2)。

算法8HCCM 算法

輸入數(shù)字特征C1(Ex1,En1,He1)和C2(Ex2,En2,He2)

輸出相似度SHCCM(C1,C2)

2) 計(jì)算相似度SHCCM(C1,C2)=1-DHCCM(C1,C2)。

3 實(shí)驗(yàn)對(duì)比分析

為說(shuō)明算法HECM 和HCCM 有效性和可行性，1) 通過(guò)數(shù)值仿真實(shí)驗(yàn)驗(yàn)證HECM 和HCCM算法的可行性；2) 在UCI 數(shù)據(jù)庫(kù)時(shí)間序列數(shù)據(jù)集上檢驗(yàn)算法的分類性能和計(jì)算時(shí)間代價(jià)；3) 將算法應(yīng)用于協(xié)同過(guò)濾推薦系統(tǒng)中，并在電影數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比分析。開(kāi)發(fā)工具為Python3.8，運(yùn)行環(huán)境為Windows 10-64 位操作系統(tǒng)，CPU 為AMD Ryzen 54600U with Radeon Graphics 2.10 GHz，16 GB 內(nèi)存。

3.1 數(shù)值仿真實(shí)驗(yàn)

本文在文獻(xiàn)[3,9-10]給出的4 個(gè)正態(tài)云概念上進(jìn)行數(shù)值仿真實(shí)驗(yàn)，并將所提出的HECM 和HCCM 算法與算法LICM[3]、ECM[9]、MCM[9]和PDCM[10]進(jìn)行比較，其中正態(tài)云概念分別為:C1(1.5，0.626 66，0.339)，C2(4.6，0.601 59，0.308 62)，C3(4.4，0.751 99，0.276 76)和C4(1.6，0.601 59，0.308 62)，對(duì)應(yīng)云圖如圖3 所示，不同算法計(jì)算結(jié)果如表1 所示。

表1 不同相似度算法下云概念Ci(i=1,2,3,4)的相似度Table 1 Cloud concept Ci(i=1,2,3,4)similarity under different similarity algorithms

圖3 二階正態(tài)云概念C1、C2、C3、C4云圖Fig. 3 Cloud map of 2nd- order normal cloud conceptC1,C2,C3,C4

由表1 看出，HECM、HCCM 與ECM、MCM和PDCM 算法都得到C1與C4最相似，C2與C3最相似，S(C1，C4)和S(C2，C3)遠(yuǎn)大于其他任意兩概念的相似度，且S(C1，C4)＞S(C2，C3)，而LICM 得到的這4 個(gè)云概念間的相似度都較接近，均在0.95 以上。若將這4 個(gè)云概念進(jìn)行二分類，那么可以認(rèn)為概念C1、C4屬于同一類，概念C2、C3屬于同一類。

為比較各方法區(qū)分能力，借鑒文獻(xiàn)[12]云概念差異度思想，即對(duì)某個(gè)云概念來(lái)說(shuō)，若與它屬同類的云概念相似度越大，而與它屬不同類的云概念相似度越小，說(shuō)明該度量方法能有效區(qū)分不同類的云概念云概念，Ci差異度定義為

其中：Cj代表與Ci屬同類的云概念，Ck代表與Ci屬不同類的云概念。例如云概念C1的差異度為

根據(jù)式(14)，各云概念在不同相似度算法下的差異度如表2。由表2 可看出，HECM 算法得到的概念差異度均高于其他算法，這說(shuō)明HECM算法的區(qū)分能力較強(qiáng)，而LICM 算法得到的概念差異度都最小，相似度區(qū)分能力最差。與HECM算法一樣，ECM 算法得到概念差異度均高于LICM、MCM、PDCM、HCCM 算法得到的概念差異度，說(shuō)明基于期望曲線得到的概念相似度對(duì)這4 個(gè)云概念區(qū)分能力較強(qiáng)，但期望曲線中沒(méi)有體現(xiàn)He的作用。在同時(shí)考慮數(shù)字特征Ex、En、He的相似度算法中，PDCM 和HCCM 得到的概念差異度均高于MCM 和LICM 算法得到的概念差異度。若從計(jì)算復(fù)雜角度分析，HECM 與HCCM 算法只需進(jìn)行代數(shù)運(yùn)算，計(jì)算復(fù)雜度遠(yuǎn)小于ECM、MCM 以及PDCM。所以綜合對(duì)比看，HECM 和HCCM 具有較好地性能，在度量云概念相似度方面具有可行性，且計(jì)算復(fù)雜度較低。

表2 不同相似度算法下云概念Ci(i=1,2,3,4)的差異度δCiTable2CloudconceptCi(i=1,2,3,4)differencedegree δCiunder different similarity algorithms

3.2 時(shí)間序列數(shù)據(jù)分類

時(shí)間序列數(shù)據(jù)由于其高維性，能夠較好檢驗(yàn)分類算法的性能，采用UCI 數(shù)據(jù)庫(kù)中時(shí)間序列數(shù)據(jù)集(synthetic control chart time series)[22]，該數(shù)據(jù)集分6 類(共600 行60 列)，每行數(shù)據(jù)代表一個(gè)時(shí)間序列，每100 行為一類(如表3)，其中Timei代表600 條時(shí)間序列數(shù)據(jù)，Numj代表60 個(gè)維度。實(shí)驗(yàn)選取每類后10 行為測(cè)試集，前90 行為訓(xùn)練集。為提高分類效率，將每個(gè)時(shí)間序列降維分段處理，訓(xùn)練集和測(cè)試集降維后的維數(shù)分別為2、3、4、5、6、10、12、20 維。具體時(shí)間序列數(shù)據(jù)分類過(guò)程見(jiàn)算法9。

表3 時(shí)間序列數(shù)據(jù)集Dm×nTable 3 Time series dataset Dm×n

算法9時(shí)間序列數(shù)據(jù)分類算法

輸入時(shí)間序列數(shù)據(jù)集Dm×n

輸出分類錯(cuò)誤率和計(jì)算相似度CPU 時(shí)間代價(jià)

1) 劃分?jǐn)?shù)據(jù)集。取每類數(shù)據(jù)前90 行作為訓(xùn)練集， 每類數(shù)據(jù)的后10 行為測(cè)試集，即訓(xùn)練集為540 個(gè)時(shí)間序列數(shù)據(jù)，測(cè)試集為60 個(gè)時(shí)間序列數(shù)據(jù)，并將時(shí)間序列數(shù)據(jù)集分段降維處理， 降維后維數(shù)分別為2、3、4、5、6、10、12、20 維， 即分割后數(shù)據(jù)的分段數(shù)為2、3、4、5、6、10、12、20 段。

2) 對(duì)分割后的每一段數(shù)據(jù)按照類別進(jìn)行逆向云變換，得到相應(yīng)云概念數(shù)字特征。

3) 在同一維數(shù)段上云概念，分別利用LICM、ECM、MCM、PDCM、HECM 和HCCM 算法計(jì)算每一類訓(xùn)練集云概念與其他類測(cè)試集云概念的相似度，得到相似度矩陣。

4) 根據(jù)最近鄰思想，在每一維度矩陣下取相似度最大的類作為分類結(jié)果(例如2 維時(shí)，共2×6=12 類；3 維時(shí)，共3×6=18 類，依此類推)，并根據(jù)分類結(jié)果計(jì)算分類錯(cuò)誤率和計(jì)算相似度CPU時(shí)間代價(jià)。

由算法9，LICM、ECM、MCM、PDCM、HECM和HCCM 算法在不同維數(shù)下分類錯(cuò)誤率、分類錯(cuò)誤率平均值和標(biāo)準(zhǔn)差分別如圖4 和表4 所示，同時(shí)各算法相似度計(jì)算CPU 時(shí)間代價(jià)如圖5 所示。

表4 不同維數(shù)下不同算法的分類錯(cuò)誤率均值和標(biāo)準(zhǔn)差Table 4 Mean value and standard deviation of classification error rate of different algorithms under different dimensions

圖4 各算法時(shí)間序列數(shù)據(jù)分類錯(cuò)誤率Fig. 4 Classification error rate for time series data of each algorithm

圖5 各算法相似度計(jì)算CPU 時(shí)間代價(jià)Fig. 5 CPU time cost of each algorithm to calculate similarity

由圖4 可知，維數(shù)為2、3、4、5 維時(shí)，各算法的分類錯(cuò)誤率均有波動(dòng)。根據(jù)表4 分類錯(cuò)誤率標(biāo)準(zhǔn)差，LICM 算法穩(wěn)定性較差，其他幾種算法的分類錯(cuò)誤率較穩(wěn)定。從分類錯(cuò)誤率來(lái)看，PDCM 算法在不同維數(shù)下分類錯(cuò)誤率都較高，LICM 算法隨維數(shù)增加分類錯(cuò)誤率呈現(xiàn)增加趨勢(shì)，ECM、HECM和HCCM 算法相比其他幾種算法分類錯(cuò)誤率都較低，且HECM 算法平均分類錯(cuò)誤率和標(biāo)準(zhǔn)差都最小，說(shuō)明HECM 算法分類性能和穩(wěn)定性更好。此外，除ECM 和HECM 算法外，HCCM 與LICM、MCM 和PDCM 算法相比有更低的錯(cuò)分率和穩(wěn)定性。盡管ECM 和MCM 算法的分類錯(cuò)誤率整體低于LICM 和PDCM 算法，但由圖5 知，ECM 與MCM 算法的時(shí)間復(fù)雜度遠(yuǎn)高于HECM與HCCM 算法，且隨云概念個(gè)數(shù)增加，ECM 與MCM 算法CPU 時(shí)間代價(jià)呈現(xiàn)增大趨勢(shì)。因此，綜合看，HECM 和HCCM 算法在時(shí)間序列數(shù)據(jù)集上都具有較好的分類性能。

3.3 不同算法在協(xié)同過(guò)濾推薦中的應(yīng)用

3.3.1 協(xié)同過(guò)濾推薦算法描述

協(xié)同過(guò)濾(collaborative filtering，CF)推薦假設(shè)相似用戶可能喜歡相似項(xiàng)目，通過(guò)分析用戶的歷史行為數(shù)據(jù)對(duì)目標(biāo)用戶行為進(jìn)行預(yù)測(cè)并進(jìn)行有效推薦，詳細(xì)步驟見(jiàn)算法10。

算法10協(xié)同過(guò)濾推薦算法

輸入用戶評(píng)分表

輸出目標(biāo)用戶UID 對(duì)項(xiàng)目IID 的推薦評(píng)分

1) 計(jì)算用戶-項(xiàng)目矩陣Rm×n。根據(jù)用戶評(píng)分詳情，列出用戶-項(xiàng)目評(píng)分矩陣Rm×n，共m行用戶，n列項(xiàng)目，則第i行第j列元素rij表示第i個(gè)用戶對(duì)j個(gè)項(xiàng)目的評(píng)分，即

2) 計(jì)算用戶評(píng)分頻度向量。根據(jù)1)中用戶項(xiàng)目矩陣Rm×n，統(tǒng)計(jì)出每個(gè)用戶的評(píng)分頻度向量Ui=[u1u2···uG](1 ≤i≤m)，其中ug(g=1,2,···,G)代表用戶i對(duì)每個(gè)項(xiàng)目評(píng)分為g的頻數(shù)，G為項(xiàng)目評(píng)分最高分值。

3) 計(jì)算用戶評(píng)分特征向量。根據(jù)用戶評(píng)分頻度向量Ui，將用戶的每一次評(píng)分視為云滴，通過(guò)逆向云變換算法計(jì)算得到每個(gè)用戶的評(píng)分特征向量Vi=[Exi Eni Hei],(1 ≤i≤m)。

4) 計(jì)算用戶相似度矩陣。用戶相似度矩陣表示為

其中，S(i,l)表示用戶i與l的相似度(1 ≤i,l≤m)，分別由LICM、ECM、MCM、PDCM、HECM 和HCCM 算法計(jì)算。

5) 形成推薦。根據(jù)目標(biāo)用戶UID、用戶相似矩陣Sm×m和用戶-項(xiàng)目矩陣Rm×n，在用戶空間中查找對(duì)該項(xiàng)目有評(píng)價(jià)記錄且與目標(biāo)用戶最接近的k個(gè)最相似鄰居用戶，得到最近鄰居集Neih=其中，Neih1與目標(biāo)用戶相似度最高，Neih2與目標(biāo)用戶相似度次之，依次類推。根據(jù)最近鄰集合Neih形成推薦，預(yù)測(cè)目標(biāo)用戶UID對(duì)待推薦項(xiàng)目IID 的評(píng)分PUID→IID。本文采用加權(quán)平均策略得到預(yù)測(cè)評(píng)分PUID→IID[4]，計(jì)算方法如下：

式中：rui→IID為用戶ui對(duì)待推薦項(xiàng)目IID 的評(píng)分，S(UID,ui)為目標(biāo)用戶UID 對(duì)近鄰用戶ui的相似度。

3.3.2 協(xié)同過(guò)濾推薦算法在影評(píng)數(shù)據(jù)集上的比較

MovieLens100k 數(shù)據(jù)集[23]是收集用戶對(duì)電影評(píng)分信息，并通過(guò)歷史打分信息將預(yù)測(cè)評(píng)分較高的電影推薦給目標(biāo)用戶。數(shù)據(jù)集從1997 年9 月19 日至1998 年4 月22 日收集943 個(gè)用戶對(duì)1 682部電影的評(píng)分記錄，共100 000 條，該數(shù)據(jù)集用戶評(píng)分?jǐn)?shù)據(jù)稀疏等級(jí)為1-(100 000/9 431 682)=0.937。將數(shù)據(jù)集以80%和20%比例劃分訓(xùn)練集和測(cè)試集，推薦質(zhì)量評(píng)價(jià)指標(biāo)采用平均絕對(duì)偏差(mean absolute error，MAE)和均方根誤差(root mean squared error，RMSE)。

其中：預(yù)測(cè)用戶評(píng)分為pi，實(shí)際用戶評(píng)分為qi。一般情況下，MAE 與RMSE 越小推薦質(zhì)量越高。文獻(xiàn)[3]已說(shuō)明LICM 算法推薦效果優(yōu)于余弦相似性、修正余弦相似性和BP-CF(back propagationcollaborative filtering)方法，故此次實(shí)驗(yàn)只將HECM和HCCM 算法與LICM、ECM、MCM 和PDCM 算法的推薦效果進(jìn)行對(duì)比。其中最近鄰居數(shù)k分別取10、20、30、40、50、60，各算法在k不斷增加時(shí)推薦效果的MAE 和RMSE 變化分別見(jiàn)圖6 和圖7，不同算法在k取不同值時(shí)的MAE 和RMSE 平均值如表5 所示。

表5 不同算法在最近鄰居個(gè)數(shù)k 取不同值時(shí)對(duì)應(yīng)的MAE均值和RMSE 均值Table 5 MAE mean and RMSE mean corresponding to different algorithms when the nearest neighbor k takes different values

圖6 最近鄰居個(gè)數(shù)k 增加時(shí)各算法的MAE 取值Fig. 6 MAE value of each algorithm when the nearest neighbor number k increases

圖7 最近鄰居個(gè)數(shù)k 增加時(shí)各算法的RMSE 取值Fig. 7 RMSE value of each algorithm when the nearest neighbor number k increases

從圖6 和圖7 看出，隨著k從10 增加至60，6 種相似度算法的MAE 和RMSE 均呈現(xiàn)下降趨勢(shì)。結(jié)合表5 可看出，LICM、MCM 和PDCM 算法相比ECM、HECM 和HCCM 算法得到的MAE 和RMSE 都較高，推薦質(zhì)量相對(duì)較差。相比之下，E C M、H E C M 和H C C M 算法得到的MAE 和RMSE 在6 種算法中比較小且取值接近，且HCCM 算法得到MAE 和RMSE 是最小的，擁有更準(zhǔn)確的推薦效果，推薦質(zhì)量最優(yōu)，說(shuō)明HCCM 算法擁有一定的優(yōu)越性。

根據(jù)上述實(shí)驗(yàn)結(jié)果，本文方法與其他方法相比有如下優(yōu)勢(shì): 1) 從計(jì)算角度和效果看，同時(shí)考慮云概念3 個(gè)數(shù)字特征，且通過(guò)3 條特征曲線研究正態(tài)云相似性，綜合考慮了云概念的幾何特性，并綜合量化云概念間的差異，考慮了更多的信息，信息損失少，所以概念區(qū)分度和分類性能都較好；2) 從計(jì)算過(guò)程看，利用數(shù)字特征只進(jìn)行簡(jiǎn)單的代數(shù)運(yùn)算而無(wú)需進(jìn)行較為復(fù)雜的積分運(yùn)算，與ECM、MCM、PDCM 算法相較而言更為簡(jiǎn)單，所以具有較低的計(jì)算復(fù)雜度；3) 從推廣角度看，由于Hellinger 距離是一種f 散度且滿足距離公理化定義，所以由此得到的云概念相似度具有較好的性質(zhì)，容易推廣至高階正態(tài)云和高維云模型中，具有普遍適用性。

4 結(jié)束語(yǔ)

本文主要針對(duì)現(xiàn)有正態(tài)云相似性方法存在問(wèn)題，結(jié)合正態(tài)云特征曲線幾何特性和Hellinger 距離刻畫概率分布相似性特點(diǎn)，提出了基于Hellinger距離的正態(tài)云相似性度量方法，并構(gòu)造了2 種正態(tài)云概念相似度計(jì)算算法。通過(guò)數(shù)值仿真、時(shí)間序列數(shù)據(jù)分類實(shí)驗(yàn)，將本文方法與已有方法進(jìn)行對(duì)比，最后將本文方法應(yīng)用于協(xié)同過(guò)濾推薦，實(shí)驗(yàn)結(jié)果均表明本文方法擁有良好性能和推薦質(zhì)量。基于Hellinger 距離和正態(tài)云特征曲線構(gòu)造的云概念相似度為云概念相似度的測(cè)量提供了一種新思路，容易將其推廣至高階正態(tài)云和高維云模型中。與此同時(shí)，結(jié)合領(lǐng)域問(wèn)題，如何選擇合適的特征曲線構(gòu)造相應(yīng)的Hellinger 距離，將是下一步需要進(jìn)行研究的主要工作。