基于改進K-medoids算法的社會化標(biāo)簽聚類研究

郭偉光

（合肥學(xué)院 管理系，安徽 合肥 230061）

基于改進K-medoids算法的社會化標(biāo)簽聚類研究

郭偉光

（合肥學(xué)院 管理系，安徽 合肥 230061）

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

社會化標(biāo)簽；標(biāo)簽聚類；K-medoids聚類算法

1 引言

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

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

2 相關(guān)研究

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

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

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

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ù)的分布情況，這可能會導(dǎo)致算法收斂于局部最優(yōu)解，并很難得到全局最優(yōu)解；第二，必須預(yù)先設(shè)置聚類數(shù)目k，而這個值在缺少先驗知識的情況下是非常難以估計的.

3 基于改進K-medoids算法的社會化標(biāo)簽聚類算法

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

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

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

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

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

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

輸出：K個標(biāo)簽簇

算法流程：

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

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

（3）應(yīng)用定義3中公式，計算標(biāo)簽tj與標(biāo)簽tn之間的相似性ConSimjn，構(gòu)成標(biāo)簽的相似性矩陣ConSimX×X；

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

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

（6）在M中選取兩個最不相似的標(biāo)簽ta和tb（即ConSimab值最?。┓謩e填充到創(chuàng)建的空簇中；

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

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

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

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

（11）輸出聚類后的K個標(biāo)簽簇，算法結(jié)束.

4 實驗與結(jié)果分析

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

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

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

5 結(jié)束語

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

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

〔2〕曹高輝,焦玉英,成全.基于凝聚式層次聚類算法的標(biāo)簽聚類研究 [J].現(xiàn)代圖書情報技術(shù)，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的標(biāo)簽聚類研究[J].計算機應(yīng)用研究,2013,30(5):1316-1319.

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

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

G250.2；TP393.09

A

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

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