概念格稳定性分析及其在Folksonomy中的应用

申 乐，王黎明

（郑州大学 信息工程学院，河南 郑州450001）

0 引 言

2004年，Thomas Vander Wal最先提出Folksonomy一词，它由Folks和Taxonomy组合而成，一般译为大众分类或分众分类，指由网络上的社区成员使用任意关键词共同完成对社会资源的分类［1］。在Folksonomy中，用户可以对自己感兴趣的资源任意的加注标签，这些标签能直接反映出用户的常用词汇和兴趣及其变化［2－3］。但是，由于没有对用户标签进行严格的词汇限制，Folksonomy的使用中还存在语义模糊［4］、资源检索效率低等问题［5－6］。为了解决这些问题，本文采用形一种新的基于概念稳定性度量方法来建立网站Folksonomy的概念分层结构，从而发现那些特殊的热门标签。

关于对Folksonomy的形式化分析研究，国内外学者已经做了一些相关工作。Jschke［7］等提出了一种算法可以直接发现Folksonomy形式背景中的三维频繁概念 （用户，资源，标签，关系），并为之建立Iceberg概念格。Kim［8－9］等利用FCA （formal concept analysis）为博客标签建立语境化的Folksonomy概念层次结构，来为网上社区提供共享标签。他们收集了9个博客的320个标签进行实验，结果概念格太大而无法显示，最后只能划分成小部分进行分析。周鑫［6］等人则从语义角度出发，提出通过界定概念外延挖掘Tag间语义关系来提高信息资源的利用效率。

由于概念格中的概念随着数据集规模呈指数型增长，这会使概念格也变得非常复杂且难以分析。为此，Stumme在2002年引入了一种由闭频繁项集构成的半格——Iceberg概念格［10］，它虽然缩小了概念格的规模，但也可能隐藏了一些不频繁的相关概念。为了能在缩减概念格规模的同时更精确的表示它，1990年Kuznetsov首先提出了概念稳定性这一概念，随后在2007年［11］又对概念稳定性做出了进一步的分析和定义。通过在不同的应用背景上利用稳定性对概念格进行剪枝，可以很容易的获得精确有效的信息，这在文献 ［12－13］中得到了成功的应用。

为了更好的分析和利用Folksonomy中的资源，本文中我们使用形式概念分析的方法来为Folksonomy的分类信息建立层次化结构，利用依赖概念稳定性度量方法来缩减概念格的规模，并使用图形化工具Galicia［14］来实现概念格的可视化。最后，分别在概念格上使用概念稳定性和支持度的度量方法剪枝并进行对比，并且在美味书签网站del.icio.us真实数据集上进行了实验验证。

1 理论基础

形式概念分析通过概念格的形式将数据有机的组织起来，概念格中的每个节点都是一个形式概念，这些节点的层次关系体现出来数据之间的泛化—例化关系，并且反映了概念的内涵与外延的统一。

一个形式背景K＝ （G，M，I）是由对象集合G和属性集合M以及G与M间的关系I组成。对于概念 （A，B），其支持度σ（B）＝‖A‖／‖G‖，阈值minsupp∈ ［0，1］。如果σ（B）≥minsupp，则称概念 （A，B）为频繁概念。由所有频繁概念组成的集合称为Iceberg概念格，即Iceberg概念格是对完备概念格进行支持度剪枝的上半格。

1.1 概念稳定性

通常，在Folksonomy数据中存在大量的噪声数据，这可能是由于用户的表达习惯、拼写错误、同义词或近义词引起的。例如：ad，advertisement，advertisements，advertising，advertizement。因此，有许多概念并没有反映出现实的关系，这就需要我们来进行一定的剪枝来缩减概念格的规模，精确表示概念间的层次关系。

在文献 ［11］第一次提出概念稳定性剪枝技术，并且扩展为一个上下文背景的形式概念［12］。这里我们对原来的定义进行了一定改善，并通过一个具体的例子来进行了说明。

定义1 概念 （A，B）是形式背景K＝ （G，M，I）中的一个概念，则 （A，B）的内涵稳定性［13］为

相应地，其外延稳定性为

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

概念的内涵稳定性和外延稳定性分别度量的是这一概念对一些特定外延和内涵的依赖程度，也就是说当失去一些外延和内涵的时候，这个概念仍然能够保存下来的机率。即使一个稳定内涵的外延是有噪声，当去掉这些噪声数据之后，这个内涵仍然能够保存下来。除了噪声数据之外，如果某些对象成员不再关注它，这个稳定内涵也不会崩溃的。

定义2 假定XG，那么X的等价类 〈X〉定义［13］为

注意，当X为闭项集时，〈X〉中的Y是它的子集。所以式 （1）和式 （2）可以改写为

稳定的概念是在现实世界中有具体的解释，即使其中是存在噪声的。而且，一个概念外延的等价类越大，那么这个概念就越稳定。同时，一个概念的稳定性常常取决于其子概念的稳定性。

引理1 （A，B）是形式背景K＝ （G，M，I）中的概念，对于 H G，令IH＝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）中当且仅当C′＝B，B是闭项集。因此

证毕。

总之，一个概念的稳定性是指当形式背景中的一些概念外延离开后，这个概念内涵仍被保存下来的可能性。稳定概念的内涵是由数据集中的大量子集产生的，即子背景规模越小其产生的概念也越不稳定。

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

表1 例1中的形式背景

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

1.2 概念稳定性计量算法

在这里，我们提出一个简单的计算概念稳定性算法CCS（compute concept stability），只是对概念稳定性的计算做出一个概括介绍。

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

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

步骤1 当概念格非空，从concepts中取出一个概念（A，B），subsets（A，B）中记录概念 （A，B）的子概念集合，count用来记录其子概念数。

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

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

步骤4 将 （A，B）移出概念格。

步骤5 令concepts＝相邻的上一层概念集合，重复执行步骤1～步骤4。

由于本文是基于概念内涵的研究，所以算法自底向上层次遍历所有概念，同时计算概念的稳定性。为了确定概念（A，B）的稳定性，将所有C A且C′＝B的概念都存储在subsets中，用变量count来对subsets中概念进行计数。

2 实验结果及分析

本文的实验数据来源于美国的美味书签网站del.icio.us［15］，通过随机抓取网页信息，并提取出其中的书签 （URL）和标签 （Tag）。利用这些信息组成了形如（URL，Tag，I）的三元组记录，其中共包括67条URL，3673个标签。然后，手工简单去除其中的部分噪声数据，最终得到记录2400条，如表2所示。

表2 URL和Tag组成的部分记录

在实验中，我们使用概念格可视化工具Galicia来计算概念和实现概念格的可视化。同时，通过对Galicia做了一定的修改，使它可以进行概念稳定性计算。最后，将生成的Iceberg概念格和经过稳定度剪枝的概念格进行对比，如图2和图3所示。我们发现虽然结果呈现相似性，但是仍然有很大的不同。图2中可以看到Iceberg概念格相对较宽但并不深，这是由于形式背景比较稀疏和数据之间的相关性较弱的关系。图3与图2最明显的区别是在最下层的两个概念，它们就是被支持度剪枝所忽略的稀疏稳定概念，这些稀疏稳定概念比其它的内涵更能描述出对象之间的相似性。

在实验过程中，我们了解到在Iceberg概念格中最小支持度的选择对概念格有重要影响。一方面，最小支持度必须足够的低才能覆盖那些意义的概念；另一方面，最小支持度的设置也需要保持在一定的程度，这样才能保证获得概念格的可读性。支持度是通过频繁模式来过滤概念，但是在网络中某些特殊情况下，一些低支持度、高置信度的事物出现时，虽然它不是频繁概念，但它有可能是用户感兴趣的概念。这时，我们就可以通过概念稳定性来发现这样的概念。在一定程度上稳定性是独立于支持度的，它可以用来辨别那些支持度较低，但与其它强相关的一些概念。这样，将稳定性和支持度相结合可以发现那些低支持度高置信度的稀疏稳定概念和高支持度低置信度的频繁不稳定概念。

实验结果表明，虽然在Folksonomy上使用FCA工具来进行分析具有一定的可行性，但是它还是有很多不足的地方。首先，用户使用标签的不规范性使得Folksonomy语义模糊，对Folksonomy的概念挖掘带来了一定的难度。再者，实验中对选择的合适阈值也很困难，通常会带有一定的主观性，直接影响到实验的效果。

3 结束语

本文使用新的方法来尝试建立一种基于形式概念分析的网站Folksonomy的概念分层结构，其中利用概念稳定度来作为剪枝的方法。我们发现这种方法不仅能缩减概念格的规模。并且能够帮我们去除其中的一部分噪声，从而使整个概念格的表达更为精确。也就是说，它能更好地挖掘Folksonomy的概念关系，更真实地反映Folksonomy社区团体中的共同兴趣。

虽然本文中提到的这种方法具有一定的可行性，但是要提高Folksonomy中的资源利用率，还有很多需要改进和解决的地方。比如：如何更高效的计算概念稳定性；使用其它剪枝方法是否能更好地挖掘Folksonomy的概念关系；怎么样将这种方法应用到现实中去，从而发现不同社区团体的共同兴趣。这些都将成为以后继续努力的方向。

［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）.［黄国彬.大众标注研究进展 ［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的服务发现研究 ［J］.计算机工程与设计，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）. ［毛军.元数据、自由分类法 （Folksonomy）和大众的因特网 ［J］.现代图书情报技术，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语义关系挖掘方法 ［J］.现代图书情报技术，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.