基于M-distance算法思想的優(yōu)化加權(quán)KNN算法

程 勖， 高 雍 政， 郭 芳

( 大連工業(yè)大學(xué) 管理學(xué)院， 遼寧 大連 116032 )

0 引 言

數(shù)據(jù)特征選擇已成為推薦系統(tǒng)重點(diǎn)研究領(lǐng)域，目的是快速實(shí)現(xiàn)最優(yōu)分類，且要精準(zhǔn)識(shí)別特征信息．?dāng)?shù)據(jù)特征選擇主要通過(guò)兩種途徑實(shí)現(xiàn)：其一，通過(guò)用戶商品數(shù)據(jù)庫(kù)進(jìn)行過(guò)濾，采用矩陣分解[1]、Slope One[2]；其二，學(xué)習(xí)用戶偏好的描述性模型，采用評(píng)分機(jī)制，如貝葉斯網(wǎng)絡(luò)[3]、神經(jīng)網(wǎng)絡(luò)分類[4]等．常見(jiàn)的分類方法有決策樹(shù)、KNN算法、SVM算法、貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)等．傳統(tǒng)KNN算法因其簡(jiǎn)單高效最為常用．它是一種惰性分類算法，特點(diǎn)在于樣本數(shù)據(jù)不需要訓(xùn)練，使用便捷，但是時(shí)間復(fù)雜度較高，且將單一變量(距離)作為相似度衡量標(biāo)準(zhǔn)，導(dǎo)致推薦精度低且體驗(yàn)度不夠完善，如Jaccard相似性[5]、Manhattan距離[6]等．針對(duì)KNN算法的不足，主要解決方案集中在裁剪[7-9]與降維[10-12]兩個(gè)方面．裁剪方法雖然可快速去除噪聲數(shù)據(jù)，但以損失分類精度為代價(jià)；降維方法雖然提高了運(yùn)算速度，但以犧牲特征數(shù)據(jù)為代價(jià)．如何在保證分類精度的前提下，降低時(shí)間復(fù)雜度，提升運(yùn)算速度備受關(guān)注．

本文通過(guò)M-distance算法思想進(jìn)行簇聚類，對(duì)樣本數(shù)據(jù)進(jìn)行預(yù)處理．相對(duì)于k-means方法，它的時(shí)間復(fù)雜度比較小，聚類效果比較顯著[13]．然后對(duì)數(shù)據(jù)進(jìn)行加權(quán)處理，以便縮小數(shù)據(jù)間的距離，并兼顧數(shù)據(jù)之間的相關(guān)性，更加準(zhǔn)確地對(duì)數(shù)據(jù)進(jìn)行分類．最后，通過(guò)簡(jiǎn)諧振動(dòng)原理，計(jì)算數(shù)據(jù)相似度距離，優(yōu)化遍歷數(shù)據(jù)過(guò)程，提高搜索速度．

1 加權(quán)K近鄰算法的特征選擇方法

1.1 K近鄰算法簡(jiǎn)介

在模式識(shí)別中，K近鄰算法的優(yōu)勢(shì)在于簡(jiǎn)單且對(duì)異常值不敏感，泛化能力強(qiáng)．其核心思想內(nèi)容[14-15]：任意樣本在數(shù)據(jù)集中的K個(gè)最相似樣本中，如果大部分樣本歸并為某一類別，那么此樣本也屬于這個(gè)類別．其意義在于通過(guò)待測(cè)樣本周邊的已知數(shù)據(jù)類別來(lái)預(yù)測(cè)此樣本的歸屬問(wèn)題，極大弱化了數(shù)據(jù)集的高維度、高耦合給數(shù)據(jù)特征分析帶來(lái)的困難．優(yōu)點(diǎn)：對(duì)數(shù)據(jù)噪聲有較強(qiáng)的忍耐能力，非常適合零售業(yè)復(fù)雜多變的特征選擇情景；分析數(shù)據(jù)特征時(shí)，只關(guān)注最相鄰的K個(gè)樣本即可，極大地降低了數(shù)據(jù)集的維度．缺點(diǎn)：K近鄰算法屬于惰性算法，不能主動(dòng)學(xué)習(xí)；K值的選擇對(duì)數(shù)據(jù)分析的結(jié)果有影響．

Ayyad等[16]提出一種加權(quán)策略(MKNN)算法，在基因序列分類中，已知類別中心樣本到其他樣本加權(quán)距離，使其待測(cè)樣本的辨別程度不同，但此方法對(duì)權(quán)值的選取并沒(méi)有考慮特征的重要程度．Li等[17]通過(guò)隨機(jī)選擇特征子集，使用KNN算法評(píng)價(jià)其分類準(zhǔn)確率，并計(jì)算其平均值作為置信度的衡量標(biāo)準(zhǔn)．該方法的泛化能力提高了，但是對(duì)權(quán)值貢獻(xiàn)度的衡量有待評(píng)估，且沒(méi)有說(shuō)明權(quán)值是如何影響分類效果的．文獻(xiàn)[18]提出的計(jì)算近鄰算法，通過(guò)設(shè)置安全邊際點(diǎn)來(lái)完善KNN模型，并未考慮樣本之間距離關(guān)系對(duì)模型的影響．文獻(xiàn)[19]提出的移動(dòng)K近鄰查詢算法，采用雙目標(biāo)函數(shù)通過(guò)調(diào)節(jié)兩者之間的作用權(quán)重，來(lái)求解最優(yōu)目標(biāo)函數(shù)值．但是對(duì)于例如零售業(yè)樣本集維度高、參數(shù)調(diào)節(jié)困難等情況，必將直接導(dǎo)致計(jì)算能力失衡．文獻(xiàn)[20]提出的自然鄰居算法，主要將自然鄰居特征值作為所有樣本的近鄰，從而避免了K值的人為設(shè)定，但是其對(duì)所有樣本都采用同樣的K值，會(huì)導(dǎo)致在稀疏矩陣的樣本中，由于分布密度過(guò)高而導(dǎo)致計(jì)算速度大幅下降．為將樣本集按照某種條件進(jìn)行排序，在測(cè)試集參與計(jì)算之前，將離群點(diǎn)或弱相關(guān)樣本直接刪除，再將經(jīng)過(guò)處理的數(shù)據(jù)集按照升序或降序進(jìn)行有規(guī)律的計(jì)算，可能會(huì)更加快速地得到合理的K值．

綜上分析，在特征分析過(guò)程中，不僅要考慮每個(gè)待測(cè)樣本之間的距離對(duì)類別的貢獻(xiàn)，更要把每個(gè)特征對(duì)樣本分類的重要程度融入權(quán)值計(jì)算當(dāng)中．

1.2 基于M-distance思想的加權(quán)K近鄰數(shù)據(jù)特征選擇

本文將樣本特征的重要性作為參數(shù)融入求解權(quán)值當(dāng)中，簡(jiǎn)稱為IFKNN(importance feature integrate intoK-nearest neighbors)算法．首先獲取待測(cè)樣本數(shù)據(jù)，將數(shù)據(jù)中的個(gè)體作為初始數(shù)據(jù)特征，使用IFKNN算法預(yù)測(cè)樣本類別，并設(shè)計(jì)諧振子擺動(dòng)的目標(biāo)函數(shù)，最后通過(guò)經(jīng)典諧振動(dòng)的接受準(zhǔn)則搜索最優(yōu)數(shù)據(jù)特征．

定義樣本數(shù)據(jù)貢獻(xiàn)度，作為樣本最主要的數(shù)據(jù)簇．貢獻(xiàn)度簇集表達(dá)樣本在整個(gè)觀測(cè)數(shù)據(jù)集中作用大?。暙I(xiàn)度越大，樣本特征越顯著，即商品成交概率越大．也就是說(shuō)貢獻(xiàn)度對(duì)商品成交影響是正向的，那么影響貢獻(xiàn)度的主要因素，就可以作為重要的營(yíng)銷特征．

每個(gè)樣本在成交時(shí)，它的評(píng)價(jià)數(shù)量與月成交量的商作為此樣本對(duì)成交的貢獻(xiàn)度，記為A．A={α1，α2，…，αn}(0.005≤αi≤1)，αi=bi/ci．

通過(guò)貢獻(xiàn)度閾值的設(shè)定，可以更加精確地篩選觀測(cè)樣本數(shù)據(jù)，也就是說(shuō)，圍繞在中心點(diǎn)周圍的樣本基本都是線性相關(guān)的，幾乎沒(méi)有異常值．如果αi<0.005(參照相關(guān)系數(shù)設(shè)定)就認(rèn)為此樣本屬于弱相關(guān)或無(wú)關(guān)樣本，直接刪除[21]．

在初步過(guò)濾樣本數(shù)據(jù)時(shí)，將樣本觀測(cè)數(shù)據(jù)集按照樣本貢獻(xiàn)度的大小降序排列．這樣在遍歷樣本的過(guò)程中，不僅減少了求樣本中心點(diǎn)的迭代次數(shù)，同時(shí)，也減小了近鄰樣本點(diǎn)之間的信息增益，提高了運(yùn)算速度．

計(jì)算相關(guān)參數(shù)：

(4)定義特征權(quán)重向量wf=(wf1wf2…

wfN}，將每個(gè)樣本的貢獻(xiàn)度融入特征權(quán)重中，即wfa=wfa·α′i，設(shè)樣本數(shù)據(jù)xi與xj之間的距離為dij，融入貢獻(xiàn)度的特征權(quán)重的歐幾里得距離公式為

(1)

(5)通過(guò)距離公式可以分析出，距離越小，屬于同一類別的概率越大．運(yùn)用距離倒數(shù)加權(quán)方法對(duì)權(quán)值進(jìn)行加權(quán)作用．距離加權(quán)函數(shù)為

W(d)=e-d

(2)

樣本特征進(jìn)行加權(quán)后的樣本預(yù)測(cè)數(shù)據(jù)集為

(3)

定義損失函數(shù)L(yi，Pi)，使用預(yù)測(cè)數(shù)據(jù)集P與目標(biāo)數(shù)據(jù)集Y的差(曼哈頓距離表示)，即：

L(yi，Pi)=|yi-Pi(wf)|

(4)

(5)

1.2.2 模擬諧振子運(yùn)動(dòng) 簡(jiǎn)諧振動(dòng)系統(tǒng)中諧振子的振動(dòng)軌跡總是從勢(shì)能最大(離平衡點(diǎn)距離最遠(yuǎn))的一端運(yùn)動(dòng)到平衡點(diǎn)，再運(yùn)動(dòng)到另一端勢(shì)能最大處，這樣持續(xù)作往返運(yùn)動(dòng)．

(1)初始狀態(tài)[22]

(6)

(2)設(shè)定振幅Sl

Sl=max(f(dil))-min(f(djl))

(7)

(3)求解振動(dòng)能量級(jí)

(8)

(4)描述問(wèn)題轉(zhuǎn)換思想

假定將在求的目標(biāo)函數(shù)所有過(guò)程解(計(jì)算每個(gè)過(guò)程的最優(yōu)解)均映射到簡(jiǎn)諧振動(dòng)的能量級(jí)中．其中，所有區(qū)間的過(guò)程解都雜亂無(wú)規(guī)律地分布其中．設(shè)最大解fmax與最小解fmin之差等于最大勢(shì)能UdS．隨機(jī)計(jì)算兩個(gè)過(guò)程解fi、fj，則Δf=|fi-fj| 表示兩個(gè)樣本點(diǎn)的過(guò)程解之間的相對(duì)距離．為了可視化方便，將其作歸一化處理，即：

(9)

假定fi就是最優(yōu)解，那么在不斷計(jì)算的過(guò)程中，也就是逐漸靠近最優(yōu)解的過(guò)程．所以Δf/f就是新解與最優(yōu)解的相對(duì)距離．確定了新解的能量區(qū)間，就可以確定新解的選擇策略(特征值選擇方法)．經(jīng)典簡(jiǎn)諧振動(dòng)能級(jí)選擇策略為將fend-fi近似看作簡(jiǎn)諧振動(dòng)的最大勢(shì)能．

(10)

其中L0為初始步長(zhǎng)．綜上分析，搜索最優(yōu)數(shù)據(jù)特征采用經(jīng)典諧振子算法來(lái)遍歷樣本特征空間，就是求解min(Δf)最優(yōu)的過(guò)程，最終確定最優(yōu)特征權(quán)值，從而得到最優(yōu)樣本數(shù)據(jù)特征．

1.2.3 數(shù)據(jù)特征選擇 將樣本數(shù)據(jù)集X按照貢獻(xiàn)度數(shù)據(jù)集A的索引順序，排列既有前驅(qū)也有后繼．即每當(dāng)遍歷一個(gè)樣本數(shù)據(jù)時(shí)，它能接受前驅(qū)的樣本特征信息，并將該信息處理完畢直接傳遞給后繼樣本，這樣求最優(yōu)解(最優(yōu)特征)可表達(dá)成一個(gè)序列：φ1→φ2→…→φn．即整個(gè)解空間D的規(guī)模變?yōu)?n-1)!/2．同時(shí)，這樣構(gòu)建數(shù)據(jù)結(jié)構(gòu)的好處是，在求解最優(yōu)特征權(quán)值的過(guò)程中，保存的最優(yōu)解向量的索引會(huì)一起傳遞，最終形成最優(yōu)特征序列，也就是所要挖掘的消費(fèi)者所關(guān)注的消費(fèi)理念與行為數(shù)據(jù)．

IFKNN算法特征選擇方法具體流程為

Input：具有M個(gè)樣本和N個(gè)特征的數(shù)據(jù)集X

Output：最優(yōu)特征

(1)按照前文描述，初始化數(shù)據(jù)集，求解貢獻(xiàn)度數(shù)據(jù)集A．樣本數(shù)據(jù)集X按照樣本的貢獻(xiàn)度數(shù)據(jù)集A中的索引順序從大到小依次排列，并且首尾相連，構(gòu)建成鏈狀數(shù)據(jù)結(jié)構(gòu)，樣本都擁有前驅(qū)與后繼．

(2)計(jì)算貢獻(xiàn)度數(shù)據(jù)集A的均值與方差．

(3)進(jìn)行迭代操作：設(shè)迭代次數(shù)為T

For(i=0；i

For：對(duì)每個(gè)樣本進(jìn)行數(shù)據(jù)處理

計(jì)算數(shù)據(jù)集X中的預(yù)測(cè)值P

計(jì)算損失函數(shù)，將損失函數(shù)作為選擇最優(yōu)特征權(quán)重的目標(biāo)函數(shù)f，進(jìn)行迭代操作，使得目標(biāo)函數(shù)的值最小，也就是最接近最優(yōu)解，即在遍歷數(shù)據(jù)集時(shí)，求解目標(biāo)函數(shù)最小值．

計(jì)算Δf，按照經(jīng)典簡(jiǎn)諧振動(dòng)的選擇策略進(jìn)行篩選．獲得最優(yōu)解．

2 實(shí)驗(yàn)與性能分析

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

以2020年“雙11購(gòu)物節(jié)”部分重要日常生活用品(衛(wèi)生紙)數(shù)據(jù)為主要研究對(duì)象，以2020-11-30為終點(diǎn)抓取消費(fèi)者購(gòu)買衛(wèi)生紙的相關(guān)數(shù)據(jù)．衛(wèi)生紙品牌選擇具有代表性的兩個(gè)品牌，作為集合Y={維達(dá)，心相印}，對(duì)集合Y作Map處理：Y={維達(dá)：0，心相?。?}．每種售出商品向前抓取2 500 個(gè)用戶留言，即共收集5 000個(gè)樣本進(jìn)行分析．在分析用戶留言時(shí)，利用分詞方法，隨機(jī)抓取頻繁出現(xiàn)的關(guān)鍵詞120個(gè)記錄到特征數(shù)據(jù)集F中．每個(gè)關(guān)鍵詞出現(xiàn)的次數(shù)記為n，按照降序排列，如果次數(shù)相同，按照先后順序，依次存入特征數(shù)據(jù)集F中．將每個(gè)顧客留言出現(xiàn)特征數(shù)據(jù)的次數(shù)除以5 000的商，按照特征數(shù)據(jù)集F中樣本特征出現(xiàn)的順序依次記錄到數(shù)據(jù)集X中，數(shù)據(jù)集X共存儲(chǔ)5 000條樣本信息．

2.2 實(shí)驗(yàn)結(jié)果及性能分析

從圖1可以直觀地看出IFKNN算法準(zhǔn)確率比較高．圖2表明每個(gè)鄰居樣本數(shù)據(jù)都被特征的選擇數(shù)量所影響，當(dāng)特征數(shù)量小于30的時(shí)候，預(yù)測(cè)出的數(shù)據(jù)不太符合真實(shí)的情景，當(dāng)樣本數(shù)據(jù)大于100的時(shí)候，又會(huì)發(fā)生過(guò)擬合，同樣也不太適合．所以，選擇樣本特征數(shù)量對(duì)于能否成功得到分類結(jié)果是非常關(guān)鍵的．圖3為5種算法的召回率分布情況．樣本特征數(shù)量從30到70，召回率下降比較快而且數(shù)值比較高，然后召回率緩慢下降最后趨于一致．

圖1 5種算法分類的準(zhǔn)確率Fig.1 Classification accuracy of five algorithms

圖2 不同樣本特征數(shù)量的5種算法的精準(zhǔn)率Fig.2 Precision of five algorithms with different samplefeature numbers

圖3 不同樣本特征數(shù)量的5種算法的召回率Fig.3 Recall rates of five algorithms with differentsample feature numbers

表1分別列出5種算法獲得的最高分類性能(F-Measure)和特征數(shù)量(N)，可以看出，IFKNN算法的分類性能比其他幾種算法好，不僅達(dá)到的指標(biāo)最高，而且使用的特征數(shù)量也最少．由圖4可以直觀地分析出，IFKNN算法分類性能最高，而且在很多求解過(guò)程中都能最快獲取最高分類性能．當(dāng)選取前20個(gè)特征時(shí)IFKNN算法相對(duì)其他4種算法能明顯快速達(dá)到最好分類性能．在樣本特征數(shù)量為30～50時(shí)，步調(diào)基本趨于一致，這可能是由于在模擬簡(jiǎn)諧振動(dòng)的某部分能量級(jí)中陷入了局部最優(yōu)．當(dāng)樣本特征數(shù)量在40～60時(shí)，IFKNN 算法的效果又顯著增強(qiáng)．這也許是由于跳出了局部最優(yōu)(其他4個(gè)算法有明顯先下降之后顯著上升的過(guò)程)，最后5種算法結(jié)果趨于一致．由圖5可以分析出：在其他參數(shù)都是最優(yōu)值，選擇的鄰居數(shù)量K小于20的情況下，分類效果是逐步增強(qiáng)的，尤其是當(dāng)訓(xùn)練數(shù)據(jù)集比較少的情況下，變動(dòng)幅度比較大．當(dāng)鄰居數(shù)量K大于20時(shí)，分類效果開(kāi)始逐步降低，最后趨于穩(wěn)定．實(shí)驗(yàn)表明，樣本鄰居數(shù)量K選擇在20左右作分類預(yù)測(cè)時(shí)，分類結(jié)果比較好．由圖6可以看出，消費(fèi)者最關(guān)注的特征是物流服務(wù)，而且關(guān)注度非常顯著．售后服務(wù)質(zhì)量與商品質(zhì)量關(guān)注度相差不多，而對(duì)大家極為看好的紅包特征并沒(méi)有明顯關(guān)注．因此，擬訂營(yíng)銷策略時(shí)，首先要完善物流服務(wù)，其次是重視售后服務(wù)與商品質(zhì)量，也就是企業(yè)在網(wǎng)商平臺(tái)上要介紹商品信息，做好售后服務(wù)，而并非把注意力放在紅包上．

表1 5種算法指標(biāo)對(duì)比Tab.1 Index comparison of five algorithms

圖4 不同樣本特征數(shù)量的F-Measure指標(biāo)分布Fig.4 F-Measure index distribution of differentsample feature numbers

圖5 樣本鄰居數(shù)量選擇對(duì)指標(biāo)F-Measure的影響Fig.5 Influence of sample neighbors number selectionon index F-Measure

圖6 消費(fèi)者關(guān)注前10特征序列分布Fig.6 Distribution of top 10 feature sequences ofconsumer concern

3 結(jié) 語(yǔ)

本文提出基于M-distance思想的加權(quán)K近鄰特征選擇算法，在模擬簡(jiǎn)諧振動(dòng)算法基礎(chǔ)上搜索最優(yōu)特征權(quán)重向量進(jìn)行精確分類．實(shí)驗(yàn)表明：IFKNN算法分類性能最好、速度最快、使用特征向量最少，并且鄰居數(shù)量K值在20左右效果比較理想．構(gòu)建的樣品特征向量集有助于分析消費(fèi)者日常關(guān)注的消費(fèi)理念與行為，輔助構(gòu)建消費(fèi)策略．在未來(lái)的工作中，可以使用其他的計(jì)算距離公式提高普適性，利用其他的遍歷矩陣方法來(lái)搜索最優(yōu)特征向量，提高分類精度及速度．