基于改進K-medoids算法的社會化標簽聚類研究

郭偉光

（合肥學院 管理系，安徽 合肥 230061）

基于改進K-medoids算法的社會化標簽聚類研究

郭偉光

（合肥學院 管理系，安徽 合肥 230061）

為了對社會化標注系統(tǒng)中的標簽進行有效聚類，并針對傳統(tǒng)K-medoids算法存在的聚類結果易受初始聚類中心影響的問題，本文提出了一種改進的K-medoids標簽聚類算法.該算法應用社會化標簽的余弦相似值進行初始聚類中心的選擇，然后進行標簽聚類.對Delicious標簽數(shù)據(jù)集的實驗結果表明算法具有較強的的可行性和有效性.

社會化標簽；標簽聚類；K-medoids聚類算法

1 引言

社會化標注系統(tǒng)是允許用戶對網(wǎng)絡資源（如照片、博客、網(wǎng)址、地圖、視頻等）賦予個性化的標簽，并通過標簽的聚合和相關度來實現(xiàn)信息組織的系統(tǒng).標簽是一種用戶標注的關鍵詞，該關鍵詞隱性反饋了用戶興趣.近年來，Youtube、Flickr、Last.fm和delicious.com等一大批基于社會化標注系統(tǒng)的網(wǎng)站取得了巨大的商業(yè)成功和社會影響力.

在社會化標注系統(tǒng)中，用戶可以自由地選擇詞語對其感興趣的內(nèi)容進行標注，由于用戶認知程度不同，不同用戶在標注同一網(wǎng)絡資源時使用了不同的標簽，但是系統(tǒng)卻無法創(chuàng)建這些標簽之間的聯(lián)系，從而導致了標簽的多樣性和模糊性.因而，有必要采取一定的分析方法，尋找標簽間的相互關系，識別可能存在的相關標簽組或標簽群，進行標簽或其標注的資源的自動聚類，這對于改善網(wǎng)絡搜索、個性化信息推薦服務和實現(xiàn)標簽間的語義關系的自動提取都具有重要意義.

2 相關研究

在社會化標注（Socialtagging）系統(tǒng)中，包括了三個主要要素：用戶、資源和標簽，其中資源主要是網(wǎng)絡URL.社會化標注系統(tǒng)模型如圖1所示.在圖1中，資源R2分別被用戶User1、User3使用，進行了標注，我們可以說用戶User1，User3都使用標簽t1標注了相同資源R2.Folksonomy表示的是大量社會化標注所產(chǎn)生的結果，使信息資源浮現(xiàn)出類別的特征，稱為大眾分類.

圖1 社會化標注系統(tǒng)模型

聚類是一個將整體的數(shù)據(jù)對象劃分為以類或簇存在的包含局部數(shù)據(jù)對象的過程.目前常用的聚類算法主要有劃分聚類算法和層次聚類算法.標簽的聚類是利用標簽統(tǒng)計學規(guī)律以及相關聚類算法，將標簽或其標注的資源劃分為不同的子集，聚類結果一般有兩種，一種是同類（或相關）標簽的聚合，這是非層次聚類的結果；另一種是同類（或相關）標簽間的概念空間，這是層次聚類的結果.韓敏[1]提出一種基于TFIDF的標簽相似度計算方法和基于該相似度的聚類算法；曹高輝等人利用凝聚式層次聚類方法將用戶標簽進行聚類，從而實現(xiàn)對用戶標簽的重新組織[2]；Begeman等人[3]提出了利用自動標簽聚類的方法來改善自由分類法的檢索和瀏覽；吳志媛等人[4]提出使用概率潛在語義索引模型對標簽進行潛在語義分析，經(jīng)回火期望最大化法訓練得到在潛在語義下的條件概率，生成概率向量并在此基礎上，提出凝聚式層次k中心點聚類算法對概率向量進行聚類；熊回香等人[5]提出運用關聯(lián)規(guī)則挖掘標簽間的相互關系，并結合典型的劃分聚類算法K-medoids進行Tag資源自動聚類，從而實現(xiàn)對Tag資源重新組織.總體來說，目前主要集中于對社會標簽之間聚類算法的研究以及基于社會標簽進行相似用戶的發(fā)現(xiàn)和資源推薦，而在基于社會標簽改善資源聚類效果方面的研究相對較少.

K-medoids算法(Kmeansclusteringalgorithm，K-medoids)是基于劃分的經(jīng)典聚類算法之一[6].該算法的基本思路是：選取數(shù)據(jù)集里的實際對象來代表簇，每個簇使用一個代表對象，聚類過程有兩個主要步驟，首先任意指定每個簇的代表對象，計算其余對象和K個聚類代表對象間的距離，并將其分配到與之最后近的代表對象所在的簇中；接著計算、更新K個簇的代表對象，這兩步迭代執(zhí)行下去，直到簇不再改變.K-medoids使用一個準則函數(shù)來衡量聚類效果，E值越小聚類效果越好：

P為簇Cj中的非代表對象，oj為簇Cj的中心對象，|p-oj|表示兩個對象間的距離.

K-medoids算法易于實現(xiàn)，但K-medoids算法仍然有一些缺點：第一，它對初始聚類中心敏感，如果隨機選擇的初始聚類中心分布過于密集，或選擇噪音數(shù)據(jù)和邊緣數(shù)據(jù)，則不能很好的代表整個數(shù)據(jù)集中數(shù)據(jù)的分布情況，這可能會導致算法收斂于局部最優(yōu)解，并很難得到全局最優(yōu)解；第二，必須預先設置聚類數(shù)目k，而這個值在缺少先驗知識的情況下是非常難以估計的.

3 基于改進K-medoids算法的社會化標簽聚類算法

K-medoids算法需要事先確定聚類個數(shù)K和K個初始聚類中心，特別是對于K個初始聚類中心的選擇，K-medoids算法極其的敏感，其所獲得的聚類結果將會隨著初始聚類中心的不同而不同，容易使算法陷入局部最優(yōu).為了改善這一問題，我們所提出的算法首先計算標簽的相似值，并應用標簽相似值輔助選擇聚類中心.在標簽K-medoids聚類時，相似的標簽會往聚類中心移動，如此一來能提高聚類中心的穩(wěn)定性并提高分群結果的精確度.

定義1（數(shù)據(jù)集D）：設數(shù)據(jù)集D（uitj,rk)，（i=1KM，j=1KX，k=1KY）表示用戶ui用標簽tj標注了網(wǎng)絡資源rk.數(shù)據(jù)集的標簽經(jīng)過一定的清冼（如標簽小寫化，符號、亂碼清理等）都具有一定的語義標識能力.

定義2（標簽向量）：設數(shù)據(jù)集D中，標簽tj的標簽向量Tj=(wj1KwjkKwjY)，其中wjk只能取值為c (c=1,2K），若wjk=c表示用標簽tj標注了網(wǎng)絡資源rk總共c次，否則wjk=0.

定義3（標簽的相似性）：設數(shù)據(jù)集D中，標簽tj與標簽tn之間的相似性為；標簽兩兩進行相似性計算，構成標簽的相似性矩陣ConSimX×X=（ConSimj1,Λ,ConSimjn,ΛConSimjX）（j=1KX, n=1KX）

算法名稱：基于改進K-medoids的社會化標簽聚類算法

輸入：數(shù)據(jù)集D，資源聚類數(shù)目K；

輸出：K個標簽簇

算法流程：

（1）根據(jù)定義1構建數(shù)據(jù)集D；

（2）抽取數(shù)據(jù)集D中標簽和資源，分別形成標簽集T，則|T|=X，資源集R，則|R|=Y，即數(shù)據(jù)集中共X個標簽，Y個資源.以標簽為行，以資源為列構建標簽向量矩陣TRX×Y，其中等j行為標簽tj的標簽向量Tj=(wj1KwjkKwjY)；

（3）應用定義3中公式，計算標簽tj與標簽tn之間的相似性ConSimjn，構成標簽的相似性矩陣ConSimX×X；

（4）建立K個空心簇，并將其中一個初始化為標簽集T；

（5）計算各個簇中包含標簽的個數(shù)，選擇標簽最多的一個簇，記為M；

（6）在M中選取兩個最不相似的標簽ta和tb（即ConSimab值最小）分別填充到創(chuàng)建的空簇中；

（7）分別以ta和tb為聚類中心，根據(jù)M中剩用標簽分別與ta和tb的相似性，將這些標簽分別歸并入與ta和tb相似度最大的那一個類別之中；

（8）檢查是否將數(shù)據(jù)集T劃分為K個類簇，是則轉第10步，將得到K個聚類中心，否則轉第5步；

（9）根據(jù)第8步得到的K個中心點，重新進行K-medoids聚類；

（10）重新計算每一個標簽簇新的中心點，比較新的中心點與上一次計算得到的中心點，如果中心點不變轉第11步，否轉到第9步；

（11）輸出聚類后的K個標簽簇，算法結束.

4 實驗與結果分析

實驗數(shù)據(jù)來源于社會化標注的典型應用delicious.com.數(shù)據(jù)集是明尼蘇達大學計算機科學系GroupLens實驗室收集整理的hetrec2011-delicious-2k數(shù)據(jù)集（下載地址：http://grouplens.org/ datasets/hetrec-2011/），該數(shù)據(jù)集主要收集了2010年437593個[user,tag,URL]標簽標注記錄.我們的實驗使用了其中2010年11月份的數(shù)據(jù)共10660個[user,tag,URL]記錄，經(jīng)過清理剩下9268個[user,tag, URL]標注記錄作為實驗數(shù)據(jù)集D.

由于所提出的方法是按照Folksonomy的方式去進行標簽資源分群，所以請網(wǎng)絡用戶評價一些標簽是否應分在一群是比較是合理的.但直接評價標簽分在一組是否合理有一定的困難，我們的思路是選擇該組標簽標注網(wǎng)絡資源的相似性來評價標簽的聚類結果，如果該組網(wǎng)址有較高的相似性，說明該組標簽一定有內(nèi)在的關聯(lián)性.我們的評價方法是從各標簽群標注的網(wǎng)絡資源中分別找出一些網(wǎng)址資源請用戶去評價其相似性并打分，評分結果分為非常認同（得4分）、認同（得3分）、一般（得2分）、不認同（得1分）、非常不認同（得0分）.例如：http: //cn.reuters.com/與http://www.hexun.com這兩個網(wǎng)址為相似網(wǎng)站，您的評價是：非常認同、認同、一般、不認同、非常不認同.

我們的實驗方法是請40名大學生，在同一時間根據(jù)提供網(wǎng)址資源上網(wǎng)瀏覽后給出評價.實驗分2次進行，分別確定K值為3和5，即網(wǎng)址資源分3群和5群，我們分別從每次實驗結果的每群中找出用戶標注次數(shù)的10個網(wǎng)址資源兩兩一組讓用戶評價.第一次的平均分數(shù)為58.3%，第二次的平均認同分數(shù)為67.6%，說明用戶對這樣的分群結果是有近65%的認同率，可見認同率是較高的.

5 結束語

Folksonomy是一種大眾化的分類機制，簡單來說就是由用戶自發(fā)使用標簽定義信息類別，不像Taxonomy要按照事先規(guī)定的類別框架進行分類.為從群體智慧中獲取有用信息，我們從Delicious中提取標簽進行聚類研究，并且利用改進的K-medoids算法以達到更好的聚類結果.但還有一些問題需進一步研究，比如最終的聚類數(shù)目K的值會直接影響聚類的結果，那么如何確定最佳K呢？再如什么樣的標簽必須過濾，哪些看似無意義卻是聚類中重要的連結中繼點的標簽應當保留等.

〔1〕韓敏,唐常杰,段磊，等.基于TF-IDF相似度的標簽聚類方法[J].計算機科學與探索,2010,4(3): 240－245.

〔2〕曹高輝,焦玉英,成全.基于凝聚式層次聚類算法的標簽聚類研究 [J].現(xiàn)代圖書情報技術，2008 (04):23－28.

〔3〕BEGEMAN G，KELLER P，SMADJIA F．Automatedtagclustering:improvingsearchand explorationinthetagspace［C］//Procof Collaborative Web Tagging Workshop at WorldWideWeb．2006:22－26．

〔4〕吳志媛,錢雪忠.基于PLSI的標簽聚類研究[J].計算機應用研究,2013,30(5):1316-1319.

〔5〕熊回香,王學東.社會化標注系統(tǒng)中基于關聯(lián)規(guī)則的Tag資源聚類研究[J].情報科學,2013,31(9): 73－77.

〔6〕王勇,唐靖,饒勤菲等.高效率的K-medoids最佳聚類數(shù)確定算法 [J].計算機應用，2014，34(5): 1331－1335.

G250.2；TP393.09

A

1673-260X（2014）12-0017-03

安徽省教育廳自然科學基金一般項目“基于社會化標簽的用戶興趣建模與個性化信息推薦研究”（KJ2012B155）；合肥學院科研發(fā)展基金重點項目“基于社會化標注的電子商務商品個性化推薦模型及算法研究”（13KY08ZD）