跨應用多屬性權重的判定及用戶識別

左嚴　白晨

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

關鍵詞：多屬性權重判定；用戶識別；熵值；相似性度量

中圖分類號：TP391 文獻標識碼：A 文章編號：1006-8937（2015）20-0080-03

1 背景概述

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

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

2 相關研究

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

用戶檔案是由Vosecky等人提出[1]，通過由多個屬性字段組成的向量來表示，兩個用戶的相似性是比較向量里不同字段表示的屬性值來計算。但這種方法設計的屬性和領域是緊耦合的，從而導致每一次領域的變化或個性化應用的改變都會產生權重的重計算。

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

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

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

3 多屬性的相似性度量

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

其中：

A是用戶所有的屬性集；

P是屬性集對應的屬性；

R是屬性P的值域。

我們認為用戶識別是在一個應用的用戶集中找到一個可以匹配另一應用用戶Us的用戶Ud，在選取比較屬性的時候，我們將用戶模型分為公共屬性部分和個性化屬性部分，在比較屬性相似度時我們選取公共屬性部分進行比較。

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

兩個用戶的相似性是由公共屬性的相似性決定的，其公式如公式1，式中，分別表示源用戶與目標用戶的第i個屬性，表示該屬性的權重。

3.1 屬性相似性度量方法

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

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

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

3.2 待選用戶的篩選

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

3.3 多屬性用戶相似性度量

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

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

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

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

4 熵值確定屬性權重

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

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

其中：

Ej表示第j個事件。

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

（5）

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

Ij=1/Ej（6）

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

具體過程如下：

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

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

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

確定相似性權重？棕j。

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

5 算 例

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

根據(jù)源用戶數(shù)據(jù)進行標準化后的待選用戶數(shù)據(jù)見表2。

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

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

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

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，求得每一種屬性的權重分別是：

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

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

6 結 語

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

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

參考文獻：

[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] 樊治平，張全，馬建.多屬性決策中權重確定的一種集成方法[J].管理科學學報，1998，（3）.

[4] 葉娜，趙銀亮，邊根慶，等.模式無關的社交網(wǎng)絡用戶識別算法[J].西安交通大學學報，2013，（12）.

[5] 張宇，劉宇東，計釗.向量相似度測度方法[J].聲學技術，2009，（4）：.

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