基于余切相似度和BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算

喬 非，關(guān)柳恩，王巧玲

（同濟(jì)大學(xué)電子與信息工程學(xué)院，上海201804）

隨著云計(jì)算等信息技術(shù)的發(fā)展，大數(shù)據(jù)日益滲透于金融、醫(yī)療、工業(yè)等各個(gè)行業(yè)領(lǐng)域之中，成為重要的生產(chǎn)因素。因此，對海量數(shù)據(jù)的挖掘和應(yīng)用具有十分重要的現(xiàn)實(shí)意義，然而在實(shí)際生產(chǎn)過程中，大數(shù)據(jù)往往伴隨著數(shù)據(jù)質(zhì)量問題。相似度度量作為數(shù)據(jù)質(zhì)量評估的重要方面，能夠挖掘數(shù)據(jù)集中各數(shù)據(jù)間的相似程度，為數(shù)據(jù)分析提供準(zhǔn)確和有效的依據(jù)。傳統(tǒng)相似性度量方法分為基于距離度量方法和基于相似系數(shù)度量方法，基于距離度量方法主要有歐氏距離、曼哈頓距離、切比雪夫距離和馬氏距離等，而基于相似系數(shù)度量方法主要有余弦相似度、皮爾森相關(guān)系數(shù)、杰卡德相似系數(shù)等。其中，歐氏距離和余弦相似度的應(yīng)用尤為普遍。相比于歐氏距離利用數(shù)據(jù)點(diǎn)的距離作為度量的依據(jù)，余弦相似度更關(guān)注向量之間的夾角，分析數(shù)據(jù)在方向上的差異。作為經(jīng)典相似性度量方法，余弦相似度常用于文本處理［1］、特征選擇［2］、視覺任務(wù)［3］、實(shí)例檢索［4］等領(lǐng)域。只關(guān)注方向的特性使得余弦相似度對噪聲的敏感度較低。文獻(xiàn)［3］提出一種局部加權(quán)余弦相似度來衡量目標(biāo)模板和候選模板的相似度，有效抑制脈沖噪聲導(dǎo)致的負(fù)面影響。文獻(xiàn)［5］在直流線路短路故障中通過余弦相似度來檢測故障端子極性現(xiàn)象，無需考慮幅值問題，從而有良好的抗噪性能。

盡管余弦相似度在多個(gè)應(yīng)用中表現(xiàn)出良好的效果，但由于對絕對數(shù)值不敏感，余弦相似度無法識別方向相同但模長相異的數(shù)據(jù)向量的差異，在需要度量模長的場景中準(zhǔn)確性較差。文獻(xiàn)［6］指出余弦相似度只關(guān)注方向差異的特點(diǎn)會給某些識別任務(wù)帶來比較大的影響，當(dāng)數(shù)據(jù)分布比較密集時(shí)，向量夾角往往趨向于零，相似度普遍較高的情況下分類器無法區(qū)分實(shí)際上不相似的模式。針對上述存在的問題，文獻(xiàn)［7］提出一種改進(jìn)余弦相似度，通過引入數(shù)據(jù)點(diǎn)距離的Lp范數(shù)以及正則項(xiàng)，使得相似度函數(shù)能兼顧數(shù)據(jù)點(diǎn)距離以及向量夾角兩方面。文獻(xiàn)［8］則利用數(shù)據(jù)序列的模長比值來構(gòu)造相似系數(shù)進(jìn)行修正。還有文獻(xiàn)［9］使用調(diào)整余弦相似度進(jìn)行度量，通過減去數(shù)據(jù)均值化原點(diǎn)矩為中心矩，消除各個(gè)維度的量綱差異。當(dāng)前，模糊集、中智集領(lǐng)域中關(guān)于相似性度量的研究工作比較深入，在余弦函數(shù)和余切函數(shù)的基礎(chǔ)上也提出了多種相似度計(jì)算公式［10-12］。但上述研究基本沒有對所提方法如何解決余弦相似度的不足進(jìn)行清晰的文字闡述和相關(guān)的數(shù)學(xué)推算。

除此之外，以往相似度計(jì)算需要逐一遍歷數(shù)據(jù)來計(jì)算數(shù)據(jù)集之間的相似度，適用于小規(guī)模數(shù)據(jù)集，但其運(yùn)算時(shí)間會隨著數(shù)據(jù)集規(guī)模擴(kuò)增呈指數(shù)型增長，不適合應(yīng)用于大規(guī)模數(shù)據(jù)集。為了擺脫高計(jì)算成本的困擾，文獻(xiàn)［13］認(rèn)為實(shí)現(xiàn)高速計(jì)算的方法之一是預(yù)先將計(jì)算所需的一些統(tǒng)計(jì)信息存儲在索引中。文獻(xiàn)［14］通過預(yù)先選擇的代表性查詢圖像和相似度表來評估圖像的相似程度。上述研究中，減少計(jì)算時(shí)間的本質(zhì)是通過預(yù)計(jì)算來減少后繼的冗余計(jì)算。值得注意的是，目前相似性度量的研究中關(guān)于快速計(jì)算這一方面的文獻(xiàn)還比較欠缺。

綜上所述，本文將針對余弦相似度準(zhǔn)確性較低這一不足以及遍歷計(jì)算方法時(shí)效性差的局限性展開相關(guān)的探索和研究。提出2種余切相似度并分析其在相似性度量中的優(yōu)勢，闡述基于BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算方法和流程，針對改進(jìn)方法的實(shí)驗(yàn)結(jié)果進(jìn)行準(zhǔn)確性和時(shí)效性的討論分析，并進(jìn)行總結(jié)與展望。

1 余切相似度計(jì)算公式

首先通過研究余弦相似度的計(jì)算公式揭示其不足，然后提出2種余切相似度計(jì)算公式，通過數(shù)學(xué)推算和實(shí)例說明分析余切相似度在衡量數(shù)據(jù)相似度方面的優(yōu)勢。

1.1 余弦相似度

余弦相似度的原理是通過計(jì)算數(shù)據(jù)向量的夾角余弦來表征兩者的相似程度。假設(shè)有3個(gè)數(shù)據(jù)A、B、C，其 中A=(a1，a2，...，am)，B=(b1，b2，...，bm)，C=(c1，c2，...，cm)，m(m∈N*)表示數(shù)據(jù)維數(shù)。為了方便表述，令M={i∈N*|1≤i≤m，m∈N*}表示維度索引取值范圍。A與B的余弦相似度計(jì)算公式如式（1）：

其中，‖ ·‖2表示數(shù)據(jù)向量·的二范數(shù)。數(shù)據(jù)向量夾角越大，余弦值越小，表示兩者相似程度越低；夾角越小，余弦值越大，表示兩者相似程度越高。式（1）表明余弦相似度實(shí)質(zhì)上等于向量A、B單位化后的乘積，通過將數(shù)據(jù)點(diǎn)映射到單位超球面上，消除了數(shù)據(jù)模長的影響，只關(guān)注數(shù)據(jù)向量的方向。這也是余弦相似度對絕對數(shù)值（即模長差異）不敏感的原因。以m=2為例說明余弦相似度現(xiàn)存的問題，二維數(shù)據(jù)A、B的示意圖如圖1所示，其中θ表示二維向量A、B的夾角。

圖1 二維向量關(guān)系示意圖Fig.1 Schematic diagram of relationship between two-dimensional vectors

當(dāng)相似度度量任務(wù)需要考慮數(shù)據(jù)模長差異的時(shí)候，式（1）仍然存在2個(gè)缺點(diǎn)：

（1） 假 設(shè) A=k·B(k∈N*，k≠1)， 由cos(A，B)=1可以得到數(shù)據(jù)向量A和B方向相同即完全相似的結(jié)論。但實(shí)際如圖1b所示，兩者雖方向相同但模長相異，意味著余弦相似度對此無法作出準(zhǔn)確判斷。

上述問題增大了余弦相似度計(jì)算誤差，無法為數(shù)據(jù)的相似度度量提供一個(gè)準(zhǔn)確的理論依據(jù)。為了能夠更加準(zhǔn)確地評估數(shù)據(jù)集的相似程度，改進(jìn)的相似度計(jì)算公式simi(A，B)必須滿足以下原則：①simi(A，B)需體現(xiàn)出數(shù)據(jù)各個(gè)維度上的差異。②simi(A，B)∈[0，1]，并且當(dāng)simi(A，B)→1，其表征數(shù)據(jù)的相似度越高；當(dāng)simi(A，B)→0，其表征數(shù)據(jù)的相似度越低。③當(dāng)且僅當(dāng)A=B時(shí)，才有simi(A，B)=1。

1.2 余切相似度

數(shù)據(jù)的相似程度取決于各個(gè)維度之間的數(shù)值差異，針對余弦相似度的缺點(diǎn)以及新計(jì)算公式需遵循的原則，提出2種余切相似度計(jì)算公式，該公式側(cè)重于計(jì)算數(shù)據(jù)各維度之間的距離。

1.2.1 兩種余切相似度定義

假設(shè)數(shù)據(jù)A、B進(jìn)行歸一化后得到A′=(a′1，a′2，…，a′m)以 及 B′=(b′1，b′2，…，b′m)，其 中a′i，b′i∈[0，1]，i∈M，有0≤|a′i-b′i|≤1。提出的第1種余切相似度具體公式如式（2）：

第2種余切相似度具體公式如式（3），其中k表示|a′i-b′i|≠0的個(gè)數(shù)。當(dāng)k=0，表明A和B完全相似；當(dāng)k≠0，說明A和B存在差異，則計(jì)算各維度差值的平均值，然后計(jì)算數(shù)據(jù)的相似度。

由式（2）、式（3）可知，第1種余切相似度計(jì)算公式根據(jù)數(shù)據(jù)維度差值的最大值來比較兩者的相似程度，而第2種余切相似度計(jì)算公式則是基于數(shù)據(jù)維度差值的均值來比較兩者的相似程度。2種余切相似度公式從2個(gè)角度來評判數(shù)據(jù)的相似程度，為數(shù)據(jù)集的相似度計(jì)算提供了全面的參考依據(jù)。

1.2.2 余切相似度分析

基于數(shù)學(xué)公式對上述2種余切相似度的有效性進(jìn)行分析。

對于第2種余切相似度而言，當(dāng)且僅當(dāng)?i∈M都有|a′i-b′i|=0，即k=0時(shí)，有cot2(A，B)=1，表征數(shù)據(jù)A和B完全相似；僅當(dāng)，有cot2(A，B)=0，表征數(shù)據(jù)A和B完全不相似；當(dāng)0＜，有cot2(A，B)∈(0，1)。

對2種余切相似度公式進(jìn)行對比分析：

（1）第1種余切相似度以維度差異峰值作為判別相似度的標(biāo)準(zhǔn)，第2種余切相似度則以維度差異均值作為標(biāo)準(zhǔn)。前者希望相似樣本各個(gè)維度的數(shù)值都能夠盡量接近，后者則傾向于相似樣本各個(gè)維度的數(shù)值整體上比較相近，不需要每個(gè)維度都十分貼近。

（2）不失一般性地，假設(shè)數(shù)據(jù)A與B只有前k(k∈M)個(gè)維度不相同，因?yàn)椋钥傆衏ot1(A，B)≤cot2(A，B)成立。3.4節(jié)實(shí)驗(yàn)數(shù)據(jù)能夠佐證這個(gè)特點(diǎn)。

綜上，對比于余弦相似度，2種余切相似度能夠應(yīng)對數(shù)據(jù)向量方向相同模長相異的特殊情況，而具體應(yīng)用哪條公式需要根據(jù)實(shí)際需求進(jìn)行選擇。

1.3 相似度計(jì)算實(shí)例說明

為了更清晰地呈現(xiàn)相似度計(jì)算過程，列舉5個(gè)10維數(shù)據(jù)（已歸一化）加以說明，如表1所示。

表1 5個(gè)10維數(shù)據(jù)實(shí)例Tab.1 Five instances of 10-dimensional data

根據(jù)式（1）、式（2）、式（3）計(jì)算出5個(gè)數(shù)據(jù)的相似度矩陣，如表2～表4。其中，第i行第j列數(shù)值表示第i個(gè)數(shù)據(jù)和第j個(gè)數(shù)據(jù)的相似度。由于每個(gè)數(shù)據(jù)與自身完全相等，矩陣對角線的相似度均為1。表1中，數(shù)據(jù)B在維度1、5、7的取值分別是0.321 2、0.5091、0.314 1，數(shù)據(jù)E在維度1、5、7的取值分別為0.519 0、0.613 1、0.223 5。根據(jù)表2～表4可知：cos(B，E)=0.9880，cot1(B，E)=0.7292，cot2（B，E）=0.912 0。由于B和E夾角只有8.9°，余弦相似度認(rèn)為數(shù)據(jù)B和數(shù)據(jù)E的相似程度非常高；而余切相似度認(rèn)為兩者的相似程度不那么高，尤其是第1種余切相似度認(rèn)為數(shù)據(jù)差異比較大。實(shí)際上，由于數(shù)據(jù)已進(jìn)行歸一化，數(shù)據(jù)B和數(shù)據(jù)E在維度1、5、7的差值都接近甚至超過0.1，意味著兩者的相似程度是比較低的。該計(jì)算實(shí)例反映了余弦相似度的缺點(diǎn)在于其只關(guān)注向量方向差異，當(dāng)向量夾角比較小時(shí)，使用余弦相似度將嚴(yán)重弱化數(shù)據(jù)間的差異，無法準(zhǔn)確判別其相似程度，意味著如果應(yīng)用到分類等任務(wù)中無法對數(shù)據(jù)進(jìn)行正確區(qū)分。而2種余切相似度能夠有效分辨數(shù)據(jù)各維度的差異，不僅能有效彌補(bǔ)上述不足，當(dāng)數(shù)據(jù)向量夾角比較大時(shí)，依然有比較好的相似度衡量能力。

表2 余弦相似度矩陣Tab.2 Similarity matrix by cosine similarity formula

表3 第1種余切相似度矩陣Tab.3 Similarity matrix by first cotangent similarity formula

2 基于BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算

傳統(tǒng)相似度計(jì)算采用遍歷方法，通過計(jì)算所有數(shù)據(jù)之間的相似度得到整個(gè)數(shù)據(jù)集的平均相似度，但面對高維數(shù)據(jù)時(shí)，存在運(yùn)算時(shí)間長、內(nèi)存消耗大的問題。為了提高相似度計(jì)算性能，引入BP神經(jīng)網(wǎng)絡(luò)，旨在建立一個(gè)能夠擬合數(shù)據(jù)集相似度映射關(guān)系的網(wǎng)絡(luò)模型，減少相似度計(jì)算時(shí)間。

表4 第2種余切相似度矩陣Tab.4 Similarity matrix by second cotangent similarity formula

2.1 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)是一種按照誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的前饋神經(jīng)網(wǎng)絡(luò)，具有比較優(yōu)秀的非線性逼近、自學(xué)習(xí)、自適應(yīng)和泛化能力，其應(yīng)用十分廣泛。根據(jù)萬能逼近定理［15］可知，一個(gè)前饋神經(jīng)網(wǎng)絡(luò)如果具有線性輸出層以及至少一層具有“擠壓”性質(zhì)激活函數(shù)的隱藏層，只要有足夠多隱藏神經(jīng)元，可以以任意精度逼近有限維空間內(nèi)的任意連續(xù)函數(shù)。由于必須考慮計(jì)算時(shí)間與空間的開銷，實(shí)際上使用的多層神經(jīng)網(wǎng)絡(luò)通常是放棄苛刻的精確表示，而是在近似表示的基礎(chǔ)上尋找合適的參數(shù)對數(shù)據(jù)集與標(biāo)簽集之間的非線性映射關(guān)系進(jìn)行逼近。這為使用BP神經(jīng)網(wǎng)絡(luò)進(jìn)行相似度快速計(jì)算提供理論基礎(chǔ)。

2.2 相似度快速計(jì)算實(shí)現(xiàn)

相似度計(jì)算公式選定之后，數(shù)據(jù)的數(shù)值與數(shù)據(jù)之間的相似度可以構(gòu)成確定的多輸入多輸出的非線性映射關(guān)系，因此可以采用BP神經(jīng)網(wǎng)絡(luò)擬合這種映射關(guān)系。為了減少遍歷計(jì)算的時(shí)間，基于部分樣本的相似度對模型進(jìn)行訓(xùn)練，用精度換速度，在誤差允許范圍內(nèi)表征完備數(shù)據(jù)集的非線性相似度映射關(guān)系，從而計(jì)算出完備數(shù)據(jù)集的近似相似度。

基于余切相似度和BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算方法主要分為4個(gè)部分：訓(xùn)練樣本提取、訓(xùn)練樣本相似度計(jì)算、網(wǎng)絡(luò)模型訓(xùn)練以及完備數(shù)據(jù)集仿真，具體流程如圖2。假設(shè)數(shù)據(jù)集P共有n個(gè)m維數(shù)據(jù)，P={p1，p2，...，pn}。為 了 簡 化 表 述，令N={j∈N*|1≤j≤n，n∈N*}表示數(shù)據(jù)索引取值范圍。相似度快速計(jì)算的算法偽代碼如圖3所示，具體步驟如下。

（1）對數(shù)據(jù)集P進(jìn)行歸一化處理得到P′={p′1，p′2，...，p′n}，其中p′j(j∈N )表示經(jīng)過歸一化后的數(shù)據(jù)集P′的第j個(gè)數(shù)據(jù)。

圖2 基于余切相似度和BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算流程Fig.2 Flowchart of fast similarity calculation based on cotangent similarity and BP neural network

（2）隨機(jī)從歸一化數(shù)據(jù)集P′中抽取10%的數(shù)據(jù)作為訓(xùn)練樣本。該訓(xùn)練集表示為P′x={p′x1，p′x2，...，p′xk}，x1，x2，...，xk∈N。應(yīng)根據(jù)數(shù)據(jù)集大小以及維數(shù)合理地調(diào)整百分比。

（3）使用余切相似度計(jì)算訓(xùn)練集P′x中每一個(gè)數(shù)據(jù)與其他數(shù)據(jù)的相似度的平均值，以此作為期望輸出 ，設(shè) 為 Yx=(yx1，yx2，...，yxk)，其 中 yxt=(p′xt，p′j)，表示數(shù)據(jù)p′xt的平均相似度，xt∈{x1，x2，...，xk}。

（4）向初始化后的神經(jīng)網(wǎng)絡(luò)輸入訓(xùn)練集Px′和期望輸出Yx，訓(xùn)練網(wǎng)絡(luò)模型，直至誤差精度達(dá)到要求。

（5）將完備數(shù)據(jù)集輸入訓(xùn)練好的網(wǎng)絡(luò)模型進(jìn)行仿真，求得所有近似平均相似度，設(shè)為Y=(y1，y2，...，yn)，其 中yj表 示 數(shù) 據(jù)p′j的 近 似 平 均 相似度。

（6）通過式（4）求所有數(shù)據(jù)的近似平均相似度的均值，得到完備數(shù)據(jù)集P的相似度。

圖3 基于余切相似度和BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算偽代碼Fig.3 Pseudocode of fast similarity calculation based on cotangent similarity and BP neural network

2.3 快速計(jì)算復(fù)雜度分析

提出的相似度快速計(jì)算方法建立在對訓(xùn)練樣本集進(jìn)行精確的相似度遍歷計(jì)算的基礎(chǔ)上。全數(shù)據(jù)集遍歷計(jì)算是一個(gè)緩慢且低效的操作：如果存在n個(gè)m維數(shù)據(jù)，計(jì)算兩兩數(shù)據(jù)之間的相似度共需要0.5n(n-1)次相似度計(jì)算，每次計(jì)算遍歷m個(gè)維度的算法復(fù)雜度為O(m)，因此遍歷計(jì)算時(shí)間復(fù)雜度為O(0.5×n(n-1)m)～O(mn2)，運(yùn)算時(shí)間隨著數(shù)據(jù)量的增加呈指數(shù)型增長。但是實(shí)際上，在相似度公式確定以及數(shù)據(jù)量足夠的前提條件下，只需要部分?jǐn)?shù)據(jù)的相似度即可擬合相似度映射關(guān)系，其余的遍歷計(jì)算可謂冗余計(jì)算。換句話說，只要神經(jīng)網(wǎng)絡(luò)的參數(shù)設(shè)置合理，在誤差允許的范圍內(nèi)，對部分?jǐn)?shù)據(jù)的遍歷計(jì)算可以取代對全部數(shù)據(jù)的遍歷計(jì)算。

現(xiàn)在探討神經(jīng)網(wǎng)絡(luò)方法的時(shí)間復(fù)雜度，分為精確計(jì)算部分和訓(xùn)練測試網(wǎng)絡(luò)部分。在精確計(jì)算過程中，設(shè)b是訓(xùn)練集比例，0＜b＜1。bn條訓(xùn)練數(shù)據(jù)的平均相似度需要進(jìn)行0.5bn(n-1+n-bn)=0.5bn[(2-b)n-1]次相似度計(jì)算，總時(shí)間復(fù)雜度為O(0.5bmn[(2-b)n-1])～O(mn2)，但由于數(shù)據(jù)量遠(yuǎn)少于全遍歷計(jì)算，所以精確計(jì)算過程的實(shí)際耗時(shí)接近遍歷計(jì)算的b倍（0＜b＜1）。在測試n個(gè)m維數(shù)據(jù)時(shí)，假設(shè)單隱層全連接神經(jīng)網(wǎng)絡(luò)的輸入神經(jīng)元數(shù)量為m，隱層神經(jīng)元數(shù)量為t，輸出神經(jīng)元數(shù)量為1（輸入1條m維數(shù)據(jù)，輸出1個(gè)相似度），神經(jīng)網(wǎng)絡(luò)方法的時(shí)間復(fù)雜度［16］為O(n(12×1×mt+12×1×t×1))～O(mnt)，在海量高維數(shù)據(jù)中往往t?mn。因此，當(dāng)數(shù)據(jù)量大或者數(shù)據(jù)維度高時(shí)，神經(jīng)網(wǎng)絡(luò)方法在效率上優(yōu)于遍歷計(jì)算方法。

3 實(shí)驗(yàn)與討論

首先對比2種余切相似度和余弦相似度公式的計(jì)算結(jié)果以驗(yàn)證余切相似度的準(zhǔn)確性。其次，對比基于BP神經(jīng)網(wǎng)絡(luò)和基于遍歷計(jì)算這2種計(jì)算方法檢驗(yàn)前者的時(shí)效性。其中，相似度算法準(zhǔn)確性是指該算法是否能夠準(zhǔn)確表征數(shù)據(jù)的相似程度，以相似度計(jì)算誤差表征；時(shí)效性是計(jì)算給定數(shù)據(jù)集平均相似度的效率，用總運(yùn)算耗時(shí)作為評價(jià)指標(biāo)。實(shí)驗(yàn)基于MATLAB平臺完成。

3.1 數(shù)據(jù)集介紹

3.1.1 UCI數(shù)據(jù)集

實(shí)驗(yàn)首先采用標(biāo)準(zhǔn)數(shù)據(jù)庫UCI Machine Learning Repository［17-18］中的Iris、Modeling、Eledeal這3個(gè)數(shù)據(jù)集驗(yàn)證2種余切相似度的準(zhǔn)確性，數(shù)據(jù)集具體信息如表5。由于Iris和Modeling數(shù)據(jù)集比較小，若只抽取10%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，很可能因?yàn)橛?xùn)練樣本不具備表征整個(gè)數(shù)據(jù)集數(shù)據(jù)分布的能力，致使網(wǎng)絡(luò)模型欠擬合而無法提供高精度的相似度計(jì)算結(jié)果。而且，數(shù)據(jù)維度的增加使得數(shù)據(jù)集的分布特征更加復(fù)雜。因此，這里對Iris和Modeling數(shù)據(jù)分別抽取75和150個(gè)數(shù)據(jù)作為訓(xùn)練樣本。除了數(shù)據(jù)集規(guī)模和數(shù)據(jù)維度，在實(shí)際應(yīng)用中，還需要根據(jù)實(shí)際情況和生產(chǎn)需求作調(diào)整。

表5 UCI數(shù)據(jù)集基本信息Tab.5 Basic information of UCI datasets

3.1.2 CWRU數(shù)據(jù)集

為了探討改進(jìn)方法對于高維大數(shù)據(jù)的準(zhǔn)確性和時(shí)效性，采用美國凱斯西儲大學(xué)的軸承故障數(shù)據(jù)集［19-20］（Case Western Reserve University，CWRU數(shù)據(jù)集），將其按照不同數(shù)據(jù)量和數(shù)據(jù)維度進(jìn)行切分成相應(yīng)子數(shù)據(jù)集，在數(shù)據(jù)分布相似的前提下，說明和分析當(dāng)數(shù)據(jù)量和數(shù)據(jù)維度增加時(shí)所得相似度誤差和計(jì)算時(shí)間的變化。設(shè)CWRU-N-M表示包含N個(gè)M維數(shù)據(jù)的子數(shù)據(jù)集，例如CWRU-512-100表示512個(gè)100維數(shù)據(jù)集。實(shí)驗(yàn)中數(shù)據(jù)量取值512、1 024、5 120、10 240，特征維數(shù)取值100、500、1 000、2 000，共有16個(gè)子數(shù)據(jù)集。根據(jù)10%抽取訓(xùn)練樣本原則，設(shè)定各數(shù)據(jù)量對應(yīng)的訓(xùn)練樣本數(shù)分別為100、102、512、1 024，其中為了保證模型精度，512數(shù)據(jù)量訓(xùn)練集比例約20%。

3.2 數(shù)據(jù)集歸一化

在計(jì)算相似度之前先進(jìn)行歸一化處理，避免由數(shù)據(jù)度量標(biāo)準(zhǔn)不統(tǒng)一引起的誤差。令數(shù)據(jù)集P的第j 個(gè)數(shù)據(jù) pj=(pj，1，pj，2，…，pj，m)， 其中pj，i(i∈M，j∈N )表示數(shù)據(jù)pj的第i個(gè)維度的數(shù)值。令歸一化數(shù)據(jù)集P’的第j個(gè)數(shù)據(jù)p′j=(p′j，1，p′j，2，…，p′j，m)，其中p′j，i(i∈M，j∈N )表示歸一化數(shù)據(jù)p′j的第i個(gè)維度的數(shù)值?？紤]到各個(gè)維度的值域范圍有可能差異過大，為了保留數(shù)據(jù)的原始特征，采用min-max標(biāo)準(zhǔn)化分別對每個(gè)維度進(jìn)行處理，保持?jǐn)?shù)據(jù)與最小值的距離比例，計(jì)算如式（5）所示：

3.3 實(shí)驗(yàn)設(shè)置與結(jié)果

根據(jù)2.1節(jié)所述，可知具有單隱層、線性輸出層以及足夠多隱藏神經(jīng)元的前饋神經(jīng)網(wǎng)絡(luò)能夠無限逼近任意連續(xù)函數(shù)。因此在對訓(xùn)練時(shí)間成本和模型精度做出權(quán)衡后，實(shí)驗(yàn)采用單隱層全連接神經(jīng)網(wǎng)絡(luò)，模型訓(xùn)練的部分超參數(shù)設(shè)置如下：隱層神經(jīng)元個(gè)數(shù)為10，學(xué)習(xí)率為0.01，迭代停止精度為0.000 1，最大迭代次數(shù)分別為500次（UCI數(shù)據(jù)集）和1 000 000次（CWRU數(shù)據(jù)集）。準(zhǔn)確性實(shí)驗(yàn)驗(yàn)證結(jié)果如表6和圖4，時(shí)效性實(shí)驗(yàn)驗(yàn)證結(jié)果如表7。為了簡化表述，下文圖表使用cos、cot1、cot2分別表示基于余弦相似度、2種余切相似度的實(shí)驗(yàn)結(jié)果。

3.4 準(zhǔn)確性分析

算法準(zhǔn)確性的驗(yàn)證對于不同規(guī)模的數(shù)據(jù)集都有重要意義，而且確保算法的準(zhǔn)確性是分析其時(shí)效性的前提?；诒?和圖4對UCI數(shù)據(jù)集和CWRU數(shù)據(jù)集2次實(shí)驗(yàn)的準(zhǔn)確性進(jìn)行分析驗(yàn)證。

表6 基于神經(jīng)網(wǎng)絡(luò)和遍歷計(jì)算的相似度計(jì)算結(jié)果（UCI數(shù)據(jù)集）Tab.6 Similarity calculation results based on BPnetwork and traversal method（UCI datasets）

3.4.1 相似度公式差異分析

以表6中Iris數(shù)據(jù)集為例，cos(PIris)=0.8958，cot1(PIris)=0.484 4，cot2(PIris)=0.544 1，顯然余弦相似度判定數(shù)據(jù)走向趨勢相近，過高估計(jì)了該數(shù)據(jù)集的平均相似度，因而準(zhǔn)確性比較差；而余切相似度從維度上判別Iris數(shù)據(jù)集的差異比較大，其平均相似度比較低。不難發(fā)現(xiàn)，表6中3個(gè)數(shù)據(jù)集都有cot1(P)＜cot2(P)（P表示數(shù)據(jù)集名稱），這是由于第1種余切相似度側(cè)重于比較數(shù)據(jù)維度差異的峰值，第2種余切相似度傾向于比較數(shù)據(jù)維度差異的均值。

在相同數(shù)據(jù)集的情況下，前者的計(jì)算值總是不超過后者的計(jì)算值。

圖4是以遍歷計(jì)算的相似度為基準(zhǔn)2種計(jì)算方法之間的相似度誤差。第1種余切相似度具有最大的計(jì)算誤差，而余弦相似度和第2種余切相似度的計(jì)算誤差比較小，這是由于第1種余切相似度使用max函數(shù)，擬合難度相對較大，但可通過調(diào)整模型超參數(shù)進(jìn)一步提升。

3.4.2 計(jì)算方法差異分析

表6中Iris數(shù)據(jù)集基于遍歷計(jì)算和基于神經(jīng)網(wǎng)絡(luò)的余弦相似度誤差為0.424 2%，第1種余切相似度誤差為2.456 6%，第2種余切相似度誤差為1.984 9%?？傮w來說計(jì)算誤差都比較小，均在容許范圍內(nèi)。這很好地說明了網(wǎng)絡(luò)模型能夠較好擬合訓(xùn)練樣本的相似度映射關(guān)系，并且具備一定的泛化能力，對完備數(shù)據(jù)集的輸入具有良好的魯棒性。圖4中2種計(jì)算方法在CWRU數(shù)據(jù)集的計(jì)算誤差都小于4%，對于大部分應(yīng)用場景均在誤差允許范圍內(nèi)，說明在高維數(shù)據(jù)集中，神經(jīng)網(wǎng)絡(luò)方法依然保有足夠的準(zhǔn)確度，為后文的時(shí)效性分析提供前提條件。綜上所述，基于余切相似度和BP神經(jīng)網(wǎng)絡(luò)的相似度計(jì)算方法應(yīng)用在數(shù)據(jù)集相似度評估中具有令人滿意的準(zhǔn)確性。

圖4 基于神經(jīng)網(wǎng)絡(luò)和遍歷計(jì)算的相似度計(jì)算誤差（CWRU子數(shù)據(jù)集）Fig.4 Similarity calculation error based on neural network and traversal calculation(CWRU subdatasets)

3.5 時(shí)效性分析

一般來說，計(jì)算量少時(shí)不同算法之間的效率差異比較小，運(yùn)算復(fù)雜度大的算法或程序才更有統(tǒng)計(jì)耗時(shí)的必要。由于CWRU數(shù)據(jù)集的“大規(guī)?！?、“高維”特性相比于UCI數(shù)據(jù)集更加明顯，因此著重分析改進(jìn)方法在CWRU數(shù)據(jù)集的時(shí)效性能。為了更清晰地對比分析基于不同計(jì)算公式以及基于不同計(jì)算方法的相似度計(jì)算效率，將表7數(shù)據(jù)依據(jù)不同相似度公式以及依據(jù)不同的計(jì)算方法分別繪制相關(guān)趨勢圖像，如圖5、6所示，注意縱坐標(biāo)均經(jīng)過對數(shù)縮放操作。

3.5.1 相似度公式差異分析

參照表7和圖5，CWRU-512-100子數(shù)據(jù)集在遍歷計(jì)算的基礎(chǔ)上3種相似度的耗時(shí)分別為0.184 8s、0.077 4s、0.189 8s，由于數(shù)據(jù)量和特征維數(shù)相對其他子數(shù)據(jù)集而言較低，運(yùn)算效率差異比較小。但隨著數(shù)據(jù)維度和數(shù)據(jù)量的增長，差異逐漸顯現(xiàn)：

（1）如果數(shù)據(jù)量固定為512，當(dāng)特征維數(shù)從100增長到2 000時(shí)，大體上呈現(xiàn)出余弦相似度的計(jì)算時(shí)間最長、第2種余切相似度次之、第1種余切相似度最短的規(guī)律。

（2）如果特征維數(shù)固定為100，當(dāng)數(shù)據(jù)量從512增長到10 240時(shí)，同樣呈現(xiàn)出第（1）點(diǎn)所述規(guī)律。

而在神經(jīng)網(wǎng)絡(luò)方法的基礎(chǔ)上，當(dāng)數(shù)據(jù)量和特征維數(shù)比較少時(shí)，不同相似度在運(yùn)算效率上沒有絕對的優(yōu)劣。根據(jù)表7，CWRU-512-100這3種相似度耗時(shí)分別為0.517 7s、0.973 6s、0.247 6s，CWRU-512-500則是0.389 0s、1.708 0s、0.480 2s，此時(shí)3種相似度公式還沒有必然的大小關(guān)系。由于訓(xùn)練樣本少，因此遍歷計(jì)算部分少，此時(shí)主要由神經(jīng)網(wǎng)絡(luò)的訓(xùn)練決定運(yùn)算時(shí)間。當(dāng)數(shù)據(jù)量和特征維數(shù)增大時(shí)，遍歷計(jì)算部分逐漸主導(dǎo)運(yùn)算時(shí)間的長短。表7中，當(dāng)數(shù)據(jù)量達(dá)到1 024及以上，神經(jīng)網(wǎng)絡(luò)方法的運(yùn)算時(shí)間同樣呈現(xiàn)出余弦相似度耗時(shí)最長、第2種余切相似度次之、第1種余切相似度最短的規(guī)律。

上述現(xiàn)象是由于余弦相似度計(jì)算了2次L2范數(shù)，時(shí)間復(fù)雜度最大；第2種余切相似度因比第1種余切相似度多1個(gè)統(tǒng)計(jì)非零維數(shù)步驟，運(yùn)算速度相對較慢?？傮w而言，無論是基于遍歷計(jì)算還是基于神經(jīng)網(wǎng)絡(luò)方法，2種余切相似度較余弦相似度都有一定的時(shí)效優(yōu)勢，尤其是針對海量高維數(shù)據(jù)。

表7 基于神經(jīng)網(wǎng)絡(luò)和遍歷計(jì)算的相似度計(jì)算時(shí)間（CWRU子數(shù)據(jù)集）Tab.7 Running time of similarity calculation based on neural network and traversal calculation(CWRU subdatasets) s

圖5 基于不同計(jì)算公式的相似度計(jì)算時(shí)間對比Fig.5 Comparison of running time of similarity calculation based on different calculation formulas

圖6 基于不同計(jì)算方法的相似度計(jì)算時(shí)間對比Fig.6 Comparison of running time of similarity calculation based on different calculation methods

3.5.2 計(jì)算方法差異分析

參照表7和圖6，當(dāng)數(shù)據(jù)量和維數(shù)比較小的情況下，遍歷計(jì)算的速度比神經(jīng)網(wǎng)絡(luò)方法要快但相差不大。以第1種余切相似度為例，表7中CWRU-512-100基于遍歷計(jì)算的耗時(shí)0.077 4s比神經(jīng)網(wǎng)絡(luò)方法0.973 7s略少。隨著數(shù)據(jù)集規(guī)模的擴(kuò)大，遍歷計(jì)算的耗時(shí)開始超過神經(jīng)網(wǎng)絡(luò)方法，其增長速度也遠(yuǎn)遠(yuǎn)高于后者，如CWRU-5120-100的遍歷計(jì)算耗時(shí)8.590 0s，是神經(jīng)網(wǎng)絡(luò)耗時(shí)2.573 1s的3倍多，相對于CWRU-512-100，前者增長了100多倍，后者僅增長了2倍多。由于工業(yè)大數(shù)據(jù)的數(shù)據(jù)量一般都十分龐大，可以預(yù)想，當(dāng)數(shù)據(jù)量和維數(shù)繼續(xù)增加到一定程度時(shí)，遍歷計(jì)算將因?yàn)榫薮蟮目臻g和時(shí)間代價(jià)而無法繼續(xù)直接計(jì)算，而此時(shí)神經(jīng)網(wǎng)絡(luò)方法的計(jì)算成本依然能被接受。因此，神經(jīng)網(wǎng)絡(luò)方法有效提高了相似度計(jì)算效率，在評估大規(guī)模數(shù)據(jù)集相似度時(shí)比遍歷計(jì)算方法更加適用。

根據(jù)上述分析，相比于遍歷計(jì)算，神經(jīng)網(wǎng)絡(luò)計(jì)算方法在時(shí)效性方面有了很大的提升，更適用在大數(shù)據(jù)相似度評估工作中。至此，基于BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算方法的時(shí)效性得以驗(yàn)證。

4 結(jié)語

從大數(shù)據(jù)相似度評估工作切入，針對余弦相似度準(zhǔn)確性較差、遍歷計(jì)算方法時(shí)間復(fù)雜度大的問題，提出了2種余切相似度公式以及基于BP神經(jīng)網(wǎng)絡(luò)的相似度快速計(jì)算方法，并基于Iris等經(jīng)典數(shù)據(jù)集進(jìn)行驗(yàn)證。實(shí)驗(yàn)證明，改進(jìn)相似度計(jì)算方法在面對小規(guī)模低維數(shù)據(jù)集和海量高維數(shù)據(jù)集時(shí)都能保持良好的準(zhǔn)確性和時(shí)效性。作為對傳統(tǒng)余弦相似度計(jì)算方法的一種改進(jìn)和補(bǔ)充，本文提出的余切相似度快速計(jì)算方法既能改善傳統(tǒng)余弦相似度只關(guān)注數(shù)據(jù)向量夾角而忽略模長的局限性，又在大規(guī)模高維數(shù)據(jù)集相似度計(jì)算方面表現(xiàn)出較好的適應(yīng)性。

提出的改進(jìn)相似度計(jì)算方法主要應(yīng)用于結(jié)構(gòu)化數(shù)據(jù)，因此未來的研究工作應(yīng)該對非結(jié)構(gòu)化數(shù)據(jù)和半結(jié)構(gòu)化數(shù)據(jù)提出更加有針對性的相似度度量方法。其次，改進(jìn)算法針對以二維數(shù)組描述的數(shù)據(jù)集，但不適用于以樹、鏈表等復(fù)雜數(shù)據(jù)結(jié)構(gòu)表達(dá)的數(shù)據(jù)集，今后的工作會考慮向復(fù)雜數(shù)據(jù)結(jié)構(gòu)的相似度度量領(lǐng)域開展。最后，可以考慮引入卷積神經(jīng)網(wǎng)絡(luò)等深度學(xué)習(xí)方法進(jìn)行計(jì)算，進(jìn)一步提高算法的運(yùn)算效率。

作者貢獻(xiàn)申明：

喬 非：研究工作的思路與全程指導(dǎo)。

關(guān)柳恩：研究工作的完善與總結(jié)。

王巧玲：初步的研究工作。