概念格穩(wěn)定性分析及其在Folksonomy中的應(yīng)用

申 樂，王黎明

（鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001）

0 引 言

2004年，Thomas Vander Wal最先提出Folksonomy一詞，它由Folks和Taxonomy組合而成，一般譯為大眾分類或分眾分類，指由網(wǎng)絡(luò)上的社區(qū)成員使用任意關(guān)鍵詞共同完成對社會資源的分類［1］。在Folksonomy中，用戶可以對自己感興趣的資源任意的加注標(biāo)簽，這些標(biāo)簽?zāi)苤苯臃从吵鲇脩舻某Ｓ迷~匯和興趣及其變化［2－3］。但是，由于沒有對用戶標(biāo)簽進(jìn)行嚴(yán)格的詞匯限制，F(xiàn)olksonomy的使用中還存在語義模糊［4］、資源檢索效率低等問題［5－6］。為了解決這些問題，本文采用形一種新的基于概念穩(wěn)定性度量方法來建立網(wǎng)站Folksonomy的概念分層結(jié)構(gòu)，從而發(fā)現(xiàn)那些特殊的熱門標(biāo)簽。

關(guān)于對Folksonomy的形式化分析研究，國內(nèi)外學(xué)者已經(jīng)做了一些相關(guān)工作。Jschke［7］等提出了一種算法可以直接發(fā)現(xiàn)Folksonomy形式背景中的三維頻繁概念 （用戶，資源，標(biāo)簽，關(guān)系），并為之建立Iceberg概念格。Kim［8－9］等利用FCA （formal concept analysis）為博客標(biāo)簽建立語境化的Folksonomy概念層次結(jié)構(gòu)，來為網(wǎng)上社區(qū)提供共享標(biāo)簽。他們收集了9個博客的320個標(biāo)簽進(jìn)行實驗，結(jié)果概念格太大而無法顯示，最后只能劃分成小部分進(jìn)行分析。周鑫［6］等人則從語義角度出發(fā)，提出通過界定概念外延挖掘Tag間語義關(guān)系來提高信息資源的利用效率。

由于概念格中的概念隨著數(shù)據(jù)集規(guī)模呈指數(shù)型增長，這會使概念格也變得非常復(fù)雜且難以分析。為此，Stumme在2002年引入了一種由閉頻繁項集構(gòu)成的半格——Iceberg概念格［10］，它雖然縮小了概念格的規(guī)模，但也可能隱藏了一些不頻繁的相關(guān)概念。為了能在縮減概念格規(guī)模的同時更精確的表示它，1990年Kuznetsov首先提出了概念穩(wěn)定性這一概念，隨后在2007年［11］又對概念穩(wěn)定性做出了進(jìn)一步的分析和定義。通過在不同的應(yīng)用背景上利用穩(wěn)定性對概念格進(jìn)行剪枝，可以很容易的獲得精確有效的信息，這在文獻(xiàn) ［12－13］中得到了成功的應(yīng)用。

為了更好的分析和利用Folksonomy中的資源，本文中我們使用形式概念分析的方法來為Folksonomy的分類信息建立層次化結(jié)構(gòu)，利用依賴概念穩(wěn)定性度量方法來縮減概念格的規(guī)模，并使用圖形化工具Galicia［14］來實現(xiàn)概念格的可視化。最后，分別在概念格上使用概念穩(wěn)定性和支持度的度量方法剪枝并進(jìn)行對比，并且在美味書簽網(wǎng)站del.icio.us真實數(shù)據(jù)集上進(jìn)行了實驗驗證。

1 理論基礎(chǔ)

形式概念分析通過概念格的形式將數(shù)據(jù)有機(jī)的組織起來，概念格中的每個節(jié)點都是一個形式概念，這些節(jié)點的層次關(guān)系體現(xiàn)出來數(shù)據(jù)之間的泛化—例化關(guān)系，并且反映了概念的內(nèi)涵與外延的統(tǒng)一。

一個形式背景K＝ （G，M，I）是由對象集合G和屬性集合M以及G與M間的關(guān)系I組成。對于概念 （A，B），其支持度σ（B）＝‖A‖／‖G‖，閾值minsupp∈ ［0，1］。如果σ（B）≥minsupp，則稱概念 （A，B）為頻繁概念。由所有頻繁概念組成的集合稱為Iceberg概念格，即Iceberg概念格是對完備概念格進(jìn)行支持度剪枝的上半格。

1.1 概念穩(wěn)定性

通常，在Folksonomy數(shù)據(jù)中存在大量的噪聲數(shù)據(jù)，這可能是由于用戶的表達(dá)習(xí)慣、拼寫錯誤、同義詞或近義詞引起的。例如：ad，advertisement，advertisements，advertising，advertizement。因此，有許多概念并沒有反映出現(xiàn)實的關(guān)系，這就需要我們來進(jìn)行一定的剪枝來縮減概念格的規(guī)模，精確表示概念間的層次關(guān)系。

在文獻(xiàn) ［11］第一次提出概念穩(wěn)定性剪枝技術(shù)，并且擴(kuò)展為一個上下文背景的形式概念［12］。這里我們對原來的定義進(jìn)行了一定改善，并通過一個具體的例子來進(jìn)行了說明。

定義1 概念 （A，B）是形式背景K＝ （G，M，I）中的一個概念，則 （A，B）的內(nèi)涵穩(wěn)定性［13］為

相應(yīng)地，其外延穩(wěn)定性為

顯然，γ（A，B）∈ ［0，1］。

概念的內(nèi)涵穩(wěn)定性和外延穩(wěn)定性分別度量的是這一概念對一些特定外延和內(nèi)涵的依賴程度，也就是說當(dāng)失去一些外延和內(nèi)涵的時候，這個概念仍然能夠保存下來的機(jī)率。即使一個穩(wěn)定內(nèi)涵的外延是有噪聲，當(dāng)去掉這些噪聲數(shù)據(jù)之后，這個內(nèi)涵仍然能夠保存下來。除了噪聲數(shù)據(jù)之外，如果某些對象成員不再關(guān)注它，這個穩(wěn)定內(nèi)涵也不會崩潰的。

定義2 假定XG，那么X的等價類 〈X〉定義［13］為

注意，當(dāng)X為閉項集時，〈X〉中的Y是它的子集。所以式 （1）和式 （2）可以改寫為

穩(wěn)定的概念是在現(xiàn)實世界中有具體的解釋，即使其中是存在噪聲的。而且，一個概念外延的等價類越大，那么這個概念就越穩(wěn)定。同時，一個概念的穩(wěn)定性常常取決于其子概念的穩(wěn)定性。

引理1 （A，B）是形式背景K＝ （G，M，I）中的概念，對于 H G，令I(lǐng)H＝I∩ （H×M）且KH＝ （H，M，IH），則

證明：所有C A的形式背景定義為

FC（K）＝ ｛KH｜C H G，A∩H＝C｝

顯然，如果C≠D，那么FC（K）∩FD（K）＝。FC（K）是K的子背景中的一部分，它們具有相同的屬性集，所以FC（K）與它的勢也相同：｜FC（K）｜＝2｜G｜－｜A｜。對于KH∈FC（K），B″＝C′；因此，在形式背景 KH∈FC（K）中當(dāng)且僅當(dāng)C′＝B，B是閉項集。因此

證畢。

總之，一個概念的穩(wěn)定性是指當(dāng)形式背景中的一些概念外延離開后，這個概念內(nèi)涵仍被保存下來的可能性。穩(wěn)定概念的內(nèi)涵是由數(shù)據(jù)集中的大量子集產(chǎn)生的，即子背景規(guī)模越小其產(chǎn)生的概念也越不穩(wěn)定。

例1 假定形式背景如下：K （U，T，I），U＝ ｛U1，U2，U3，U4｝，T＝ ｛T1，T2，T3，T4｝。形式背景見表1，概念格見圖1。

表1 例1中的形式背景

圖1 例1形式背景的概念格

1.2 概念穩(wěn)定性計量算法

在這里，我們提出一個簡單的計算概念穩(wěn)定性算法CCS（compute concept stability），只是對概念穩(wěn)定性的計算做出一個概括介紹。

輸入：概念格K （U，T，I）

初始化：concepts＝ 底層概念集合

步驟1 當(dāng)概念格非空，從concepts中取出一個概念（A，B），subsets（A，B）中記錄概念 （A，B）的子概念集合，count用來記錄其子概念數(shù)。

步驟2 依次取出 （A，B）的子概念 （C，D），如果｜B｜＞｜D｜，那么count－1。

步驟3 stability ［（A，B）］＝count／2｜A｜。

步驟4 將 （A，B）移出概念格。

步驟5 令concepts＝相鄰的上一層概念集合，重復(fù)執(zhí)行步驟1～步驟4。

由于本文是基于概念內(nèi)涵的研究，所以算法自底向上層次遍歷所有概念，同時計算概念的穩(wěn)定性。為了確定概念（A，B）的穩(wěn)定性，將所有C A且C′＝B的概念都存儲在subsets中，用變量count來對subsets中概念進(jìn)行計數(shù)。

2 實驗結(jié)果及分析

本文的實驗數(shù)據(jù)來源于美國的美味書簽網(wǎng)站del.icio.us［15］，通過隨機(jī)抓取網(wǎng)頁信息，并提取出其中的書簽 （URL）和標(biāo)簽 （Tag）。利用這些信息組成了形如（URL，Tag，I）的三元組記錄，其中共包括67條URL，3673個標(biāo)簽。然后，手工簡單去除其中的部分噪聲數(shù)據(jù)，最終得到記錄2400條，如表2所示。

表2 URL和Tag組成的部分記錄

在實驗中，我們使用概念格可視化工具Galicia來計算概念和實現(xiàn)概念格的可視化。同時，通過對Galicia做了一定的修改，使它可以進(jìn)行概念穩(wěn)定性計算。最后，將生成的Iceberg概念格和經(jīng)過穩(wěn)定度剪枝的概念格進(jìn)行對比，如圖2和圖3所示。我們發(fā)現(xiàn)雖然結(jié)果呈現(xiàn)相似性，但是仍然有很大的不同。圖2中可以看到Iceberg概念格相對較寬但并不深，這是由于形式背景比較稀疏和數(shù)據(jù)之間的相關(guān)性較弱的關(guān)系。圖3與圖2最明顯的區(qū)別是在最下層的兩個概念，它們就是被支持度剪枝所忽略的稀疏穩(wěn)定概念，這些稀疏穩(wěn)定概念比其它的內(nèi)涵更能描述出對象之間的相似性。

在實驗過程中，我們了解到在Iceberg概念格中最小支持度的選擇對概念格有重要影響。一方面，最小支持度必須足夠的低才能覆蓋那些意義的概念；另一方面，最小支持度的設(shè)置也需要保持在一定的程度，這樣才能保證獲得概念格的可讀性。支持度是通過頻繁模式來過濾概念，但是在網(wǎng)絡(luò)中某些特殊情況下，一些低支持度、高置信度的事物出現(xiàn)時，雖然它不是頻繁概念，但它有可能是用戶感興趣的概念。這時，我們就可以通過概念穩(wěn)定性來發(fā)現(xiàn)這樣的概念。在一定程度上穩(wěn)定性是獨立于支持度的，它可以用來辨別那些支持度較低，但與其它強(qiáng)相關(guān)的一些概念。這樣，將穩(wěn)定性和支持度相結(jié)合可以發(fā)現(xiàn)那些低支持度高置信度的稀疏穩(wěn)定概念和高支持度低置信度的頻繁不穩(wěn)定概念。

實驗結(jié)果表明，雖然在Folksonomy上使用FCA工具來進(jìn)行分析具有一定的可行性，但是它還是有很多不足的地方。首先，用戶使用標(biāo)簽的不規(guī)范性使得Folksonomy語義模糊，對Folksonomy的概念挖掘帶來了一定的難度。再者，實驗中對選擇的合適閾值也很困難，通常會帶有一定的主觀性，直接影響到實驗的效果。

3 結(jié)束語

本文使用新的方法來嘗試建立一種基于形式概念分析的網(wǎng)站Folksonomy的概念分層結(jié)構(gòu)，其中利用概念穩(wěn)定度來作為剪枝的方法。我們發(fā)現(xiàn)這種方法不僅能縮減概念格的規(guī)模。并且能夠幫我們?nèi)コ渲械囊徊糠衷肼?，從而使整個概念格的表達(dá)更為精確。也就是說，它能更好地挖掘Folksonomy的概念關(guān)系，更真實地反映Folksonomy社區(qū)團(tuán)體中的共同興趣。

雖然本文中提到的這種方法具有一定的可行性，但是要提高Folksonomy中的資源利用率，還有很多需要改進(jìn)和解決的地方。比如：如何更高效的計算概念穩(wěn)定性；使用其它剪枝方法是否能更好地挖掘Folksonomy的概念關(guān)系；怎么樣將這種方法應(yīng)用到現(xiàn)實中去，從而發(fā)現(xiàn)不同社區(qū)團(tuán)體的共同興趣。這些都將成為以后繼續(xù)努力的方向。

［1］Thomas Vander Wal.Folksonomy definition and wikipedia［ EB／OL ］. http：／／www.vanderwal.net／random／entrysel.php？blog＝1750，2005.

［2］ Noruzi A.Folksonomies： Uncontrolled vocabulary ［J］.Knowledge Organization，2006，33 （4）：199－203.

［3］HUANG Guobin.Renew of study on Folksonomy at home and abroad ［J］.Library and Information Service，2008，52 （1）：13－55（in Chinese）.［黃國彬.大眾標(biāo)注研究進(jìn)展 ［J］.圖書情報工作，2008，52 （1）：13－55.］

［4］LI Xiang，LI Jianhua.Study on Folksonomy－based web service discovery ［J］.Computer Engineering and Design，2010，31（23）：5008－5011 （in Chinese）. ［李向，李建華.基于 Folksonomy的服務(wù)發(fā)現(xiàn)研究 ［J］.計算機(jī)工程與設(shè)計，2010，31（23）：5008－5011.］

［5］MAO Jun.Metadata Folksonomy and internet for the people［J］.New Technology of Library and Information Service，2006，27 （2）：1－3 （in Chinese）. ［毛軍.元數(shù)據(jù)、自由分類法 （Folksonomy）和大眾的因特網(wǎng) ［J］.現(xiàn)代圖書情報技術(shù)，2006，27 （2）：1－3.］

［6］ZHOU Xin，WANG Jun.Semantic relations mining in Folksonomy based on extensions of concepts ［J］.New Technology of Library and Information Service，2008，29 （10）：6－10 （in Chinese）.［周鑫，王軍.基于概念外延的Folksonomy語義關(guān)系挖掘方法 ［J］.現(xiàn)代圖書情報技術(shù)，2008，29 （10）：6－10.］

［7］Jaschke R，Hotho A，Schmitz C，et al.TRIAS：An algorithm for mining iceberg tri－lattices ［C］.Hong Kong：IEEE ICDM，2006：907－911.

［8］Kim H L，HWANG S H，Kim H G.Fca－based approach for mining contextualized Folksonomy ［C］.Korea：ACM Symposium on Applied Computing，2007.

［9］Kim H，Hwang S，Kang Y，et al.An agent environment for contextualizing Folksonomies in a triadic context［C］.Poland：AMSTA，2007：728－737.

［10］Martin B，Eklund P W.From concepts to concept lattice：A border algorithm for making covers explicit［G］.LNCS 4933：Formal Concept Analysis. Heidelberg：Springer，2008：78－89.

［11］Kuznetsov S O.On stability of a formal concept［M］.Annals of Mathematics and Atificial Intelligence，2007：101－115.

［12］Camille Roth，Sergei Obiedkov，Derrick Kourie.Towards concise representation for taxonomies of epistemic communities［C］.Berlin：CLA 4th International Conference on Concept Lattices and their Applications，2006：205－218.

［13］Sergei Kuznetsov，Sergei Obiedkov，Camille Roth.Reducing the representation complexity of lattice－based taxonomies［G］.LNCS 4604：Reducing the Representation Complexity of Lattice－Based Taxonomies，2007：241－254.

［14］Galicia lattice builder ［EB／OL］.http：／／iro.umntreal.ca／～galicia／，2010.

［15］Del.icio.us ［EB／OL］.Del.icio.us website.http：／／del.icio.us，2006.