左嚴(yán)　白晨

摘 要：當(dāng)今社會(huì)，社交網(wǎng)絡(luò)越來越普遍，Web用戶常常會(huì)在多個(gè)社交網(wǎng)絡(luò)進(jìn)行注冊(cè)，從而留下大量的個(gè)人信息，這就出現(xiàn)了Web應(yīng)用的個(gè)性化領(lǐng)域問題。為了充分利用分布于網(wǎng)絡(luò)上大量的用戶信息集，首先我們考慮的是用戶識(shí)別的問題，解決了用戶識(shí)別的問題，我們才能整合并利用這些用戶信息。然而用戶識(shí)別的重點(diǎn)又在于多屬性權(quán)重的判定，同一屬性權(quán)重的不同，其相似性的判斷結(jié)果也會(huì)有很大差異。文章通過引入熵值確定用戶檔案多個(gè)公共屬性的權(quán)重，然后經(jīng)過相似性度量方法獲得最終結(jié)果。

關(guān)鍵詞：多屬性權(quán)重判定；用戶識(shí)別；熵值；相似性度量

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8937（2015）20-0080-03

1 背景概述

社交網(wǎng)絡(luò)的迅速普及已經(jīng)改變了人們的交流方式。目前網(wǎng)絡(luò)提供可能的方式有很多，例如微博上發(fā)布的信息，在天貓，京東上的購買物品，同時(shí)這些行為也會(huì)在網(wǎng)絡(luò)上留下大量的用戶個(gè)人數(shù)據(jù)信息。一個(gè)用戶可能會(huì)注冊(cè)多個(gè)社交網(wǎng)絡(luò)或應(yīng)用的賬戶進(jìn)行不同的活動(dòng)，這些注冊(cè)信息擴(kuò)展了該用戶的不同的個(gè)性化特征。

對(duì)于一個(gè)單獨(dú)的商業(yè)應(yīng)用而言，就是盡最大努力收集客戶的個(gè)人信息來滿足客戶相應(yīng)的需求，為了獲取用戶更多的信息首先面對(duì)的問題就是跨應(yīng)用的用戶識(shí)別。只有同一用戶被識(shí)別后才能完成用戶信息的整合。本文分析了用戶識(shí)別的關(guān)鍵問題并給出了基于多屬性判定的解決方法。提出了熵值確定公共屬性權(quán)重，并通過相應(yīng)的相似性度量尋找相同用戶。

2 相關(guān)研究

目前用于跨應(yīng)用用戶識(shí)別領(lǐng)域的主要思想是比較不同應(yīng)用的用戶檔案，每個(gè)注冊(cè)用戶有一個(gè)用戶檔案描述自己的個(gè)人信息，如果兩個(gè)用戶檔案相同或在一定程度上類似，就可看作同一用戶。

用戶檔案是由Vosecky等人提出[1]，通過由多個(gè)屬性字段組成的向量來表示，兩個(gè)用戶的相似性是比較向量里不同字段表示的屬性值來計(jì)算。但這種方法設(shè)計(jì)的屬性和領(lǐng)域是緊耦合的，從而導(dǎo)致每一次領(lǐng)域的變化或個(gè)性化應(yīng)用的改變都會(huì)產(chǎn)生權(quán)重的重計(jì)算。

Radd等[2]人提出了一種框架，通過判定算法計(jì)算兩個(gè)檔案的相似度。如果他們的檔案相似度高于預(yù)定閥值，則認(rèn)為是表示同一用戶。

這種方法的主要問題是，一般默認(rèn)所使用的代表用戶唯一標(biāo)識(shí)符IFP（Inverse Functional Property）是用戶的電子郵件地址，該信息是用戶私人的不能被其他人訪問獲取，因此作者也承認(rèn)該方法并沒有解決用戶隱私的問題。

國內(nèi)關(guān)于多屬性決策問題也多用于統(tǒng)計(jì)學(xué)研究上，樊治平等人[3]通過建立主觀和客觀兩個(gè)模型，為保證決策權(quán)重的最優(yōu)，線性集成兩個(gè)模型，并構(gòu)造相應(yīng)的模型函數(shù)，通過求解該函數(shù)最值得出最優(yōu)權(quán)重。但該方法主觀模型部分依賴專家權(quán)重，在跨應(yīng)用用戶識(shí)別上還存在難度。葉娜等人[4]提出的模式無關(guān)的用戶識(shí)別算法則完全舍棄屬性權(quán)重，實(shí)現(xiàn)了無需屬性權(quán)重依然可以進(jìn)行用戶識(shí)別的目的。

3 多屬性的相似性度量

用戶識(shí)別的目的是推斷出兩個(gè)來自不同應(yīng)用的兩個(gè)用戶檔案是否是同一真實(shí)世界的實(shí)體。我們將用戶檔案定義為屬性值對(duì)的向量，如下所示：

其中：

A是用戶所有的屬性集；

P是屬性集對(duì)應(yīng)的屬性；

R是屬性P的值域。

我們認(rèn)為用戶識(shí)別是在一個(gè)應(yīng)用的用戶集中找到一個(gè)可以匹配另一應(yīng)用用戶Us的用戶Ud，在選取比較屬性的時(shí)候，我們將用戶模型分為公共屬性部分和個(gè)性化屬性部分，在比較屬性相似度時(shí)我們選取公共屬性部分進(jìn)行比較。

但因?yàn)椴煌瑧?yīng)用的異構(gòu)性和語義的差異，例如不同的社交網(wǎng)絡(luò)有不同的數(shù)據(jù)表示形式，即使是同一個(gè)屬性，以生日為例，一些應(yīng)用程序使用的形式DDMMYY而其他應(yīng)用使用MMDDYY，所以屬性相似度度量之前，用戶數(shù)據(jù)應(yīng)先進(jìn)行標(biāo)準(zhǔn)化。此外由于屬性值中可能存在近義詞或相同意思不同表述的情況，所以在比較之前應(yīng)該進(jìn)行統(tǒng)一的語義映射。

兩個(gè)用戶的相似性是由公共屬性的相似性決定的，其公式如公式1，式中，分別表示源用戶與目標(biāo)用戶的第i個(gè)屬性，表示該屬性的權(quán)重。

3.1 屬性相似性度量方法

目前用于屬性相似性度量的方法多種多樣，如Cosin，Euc-

lidean Distance，TF-IDF，simEditDistance，Dice[5]等。對(duì)于不同的屬性的數(shù)據(jù)類型必須選擇合適的度量方法才能大大增加運(yùn)算結(jié)果的效率和準(zhǔn)確率。

如何根據(jù)不同的屬性數(shù)據(jù)動(dòng)態(tài)的變換屬性相似性度量方法目前依舊沒有確定的結(jié)果。本文中我們選取Dice系數(shù)作為公共屬性相似性的度量方法。

3.2 待選用戶的篩選

在進(jìn)行用戶識(shí)別時(shí)，我們要做的是比較源應(yīng)用的某個(gè)用戶與目標(biāo)應(yīng)用的所有候選用戶，但眾所周知的是很多大型社交網(wǎng)站注冊(cè)用戶數(shù)都是非常龐大的，如Facebook擁有超過7.5億的活躍用戶，逐一比較是不現(xiàn)實(shí)的。根據(jù)觀察，社交網(wǎng)絡(luò)上用戶經(jīng)常使用相同的昵稱或全名以方便互相聯(lián)系。所以我們?cè)诤Y選候選用戶集時(shí)以昵稱或全名作為關(guān)鍵字進(jìn)行。

3.3 多屬性用戶相似性度量

對(duì)于相似性度量我們依據(jù)并擴(kuò)展了Dice系數(shù)，Dice系數(shù)法的計(jì)算方式：兩個(gè)候選集合X，Y的交集信息的2倍除以X，Y的元素的總和。公式如下：

對(duì)于本文中屬性值都是字符串的相似性的計(jì)算，（2）式可擴(kuò)展為如下表示：

對(duì)于單值屬性，我們定義N為一組字符形式的雙字母組，他們是字符串S中相鄰的雙字符。因此公式計(jì)算兩個(gè)單值字符串S1和S2的相似性：共同的雙字母組字符個(gè)數(shù)的2倍除以兩個(gè)字符串雙字母組字符集的總和，而對(duì)于多值屬性，N是字符串S中的詞集，兩個(gè)多值字符串S1和S2的相似性可以通過兩個(gè)字符串共同單詞數(shù)的2倍除以兩個(gè)字符串單詞數(shù)的總和。

例如對(duì)于單值的字符串Tom和Tomy的相似性，Tom相鄰的字母對(duì)是{‘To，‘om}，而Tomy是{‘To，‘om，‘my}。這兩集合共同的字符對(duì)是2，所以這兩個(gè)字符串相似性就是2×2/5=0.8。兩個(gè)多值屬性”red green white”和”blue yellow red”共同詞的數(shù)目是1，所以相似性是2×1/6=0.33。

4 熵值確定屬性權(quán)重

多屬性權(quán)重的確定大致可分為兩類：一類是主觀賦權(quán)法，評(píng)價(jià)人員根據(jù)主觀上對(duì)各屬性的重視程度來決定權(quán)系數(shù)；另一類是客觀賦權(quán)法，即根據(jù)各屬性間的相關(guān)關(guān)系或各值的變異程度來確定權(quán)數(shù)。劉業(yè)政等人[6]提出的自適應(yīng)方法結(jié)合主客觀賦權(quán)法，在專家決策的前提下，根據(jù)熵權(quán)系數(shù)計(jì)算屬性權(quán)重，并根據(jù)該權(quán)重計(jì)算新的決策結(jié)果與之前結(jié)果比較，重復(fù)多次后得出最優(yōu)值。

傳統(tǒng)的系統(tǒng)論中的熵越大說明系統(tǒng)越混亂，攜帶的信息越少，熵越小說明系統(tǒng)越有序，攜帶的信息越多，當(dāng)系統(tǒng)可能處于幾種不同狀態(tài)，每種狀態(tài)出現(xiàn)的概率為Pi（i=1，…，n）時(shí)，則系統(tǒng)的熵為：

其中：

Ej表示第j個(gè)事件。

本文中我們要根據(jù)待選用戶各屬性的相似度確定該屬性的權(quán)重，所以熵值越大，信息越混亂，該屬性對(duì)用戶識(shí)別的判斷就越模糊，其權(quán)重應(yīng)該越小，所以在這里我們對(duì)公式（4）做了擴(kuò)展，將Pi替換成屬性相似度指標(biāo)概率。那么擴(kuò)展后的公式就變成式（5）。其中表示第i個(gè)用戶第j個(gè)屬性的相似度。

（5）

通過擴(kuò)展后的公式我們計(jì)算出待選用戶每種屬性的熵值，為了確保熵值最小，我們構(gòu)建擴(kuò)展熵值Ij：

Ij=1/Ej（6）

通過構(gòu)建擴(kuò)展熵值我們確定待選用戶的每個(gè)公共屬性結(jié)果，最后我們根據(jù)該擴(kuò)展熵值構(gòu)建最終權(quán)重？棕：

具體過程如下：

構(gòu)建屬性相似度矩陣A，其中A中的元素aij代表候選用戶Xi與源用戶之間公共屬性的相似度。

拆分矩陣A，組成單屬性相似度矩陣B，其中B中元素代表候選用戶Xi與源用戶之間單個(gè)公共屬性的相似度。

根據(jù)矩陣B計(jì)算出每種屬性熵值Ej，最終得到變種最小熵值Ij。

確定相似性權(quán)重？棕j。

帶入公式（1），并確定最相似用戶。

5 算 例

本節(jié)中我們提供了一個(gè)來說明如何根據(jù)上述方法進(jìn)行權(quán)重判定及用戶識(shí)別，源用戶數(shù)據(jù)見表1。

根據(jù)源用戶數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化后的待選用戶數(shù)據(jù)見表2。

我們先計(jì)算待選用戶屬性相似度矩陣A，以U1為例，通過式（3）我們求得Nickname的相似度：2×3/（4+3）=0.8571，interest屬性相似度：2×2/（3+2）=0.8。

完成用戶相似度矩陣并拆分后可得四組單屬性相似度矩陣：

將單屬性相似矩陣中的值帶入式（5），求得每一組屬性的熵值Ej，其結(jié)果為：

E1=0.7722，E2=0.7067，E3=0.5786，E4=0.5749。

再根據(jù)式（6）求得：

I1=1.2950，I2=1.4150，I3=1.7283，I4=1.7394。

最后我們根據(jù)公式7，求得每一種屬性的權(quán)重分別是：

得出各屬性權(quán)重后，依據(jù)公式1，得用戶相似度矩陣：

通過比較U1的相似度最大，所以我們認(rèn)定在待選y用戶中，與Us成功匹配的是U1，也就是說，U1與Us是同一用戶。

6 結(jié) 語

本文提出了一種解決用戶識(shí)別中多屬性權(quán)重判定的方法，并給出了具體算例。通過相似值計(jì)算熵值，通過熵值求得屬性權(quán)重并得出最終的用戶識(shí)別結(jié)果。

這里需要單純的使用Dice系數(shù)在復(fù)雜的多個(gè)社交網(wǎng)絡(luò)中進(jìn)行用戶屬性相似度的計(jì)算并不是特別準(zhǔn)確，所以我們下一步工作的重點(diǎn)就是研究如何動(dòng)態(tài)調(diào)整不同類型屬性的相似性度量。

參考文獻(xiàn)：

[1] Vosecky J，hong D，shen V Y.User Identification Across Multiple Social Networks[A].Proceedings of the 1st International Conference on Networked Digital Technologies：July 28-31，2009. Ostrava，Czech Republic[C].2009.[2]RAAD E，CHBEIR R，DIPANDA A.User Profile Matching in Social Networks[A].Proceedings of the 13th International Conference on Network-Based Information Systems：September 14-16，2010[C].Takayama， Gifu，Japan.IEEE Press，2010.

[3] 樊治平，張全，馬建.多屬性決策中權(quán)重確定的一種集成方法[J].管理科學(xué)學(xué)報(bào)，1998，（3）.

[4] 葉娜，趙銀亮，邊根慶，等.模式無關(guān)的社交網(wǎng)絡(luò)用戶識(shí)別算法[J].西安交通大學(xué)學(xué)報(bào)，2013，（12）.

[5] 張宇，劉宇東，計(jì)釗.向量相似度測(cè)度方法[J].聲學(xué)技術(shù)，2009，（4）：.

[6] 劉業(yè)政，徐德鵬，姜元春.多屬性群決策中權(quán)重自適應(yīng)調(diào)整的方法[J].系統(tǒng)工程與電子技術(shù)，2007，（1）.