社会化标签及其在网络信息搜索中的应用研究

摘要：本文从社会化图片网站flickr上采集下450万条图片信息。分析了图片标签的分布规律，用生物多样性的方法计算出图片的国际化程度值，计算了图片标签的相关度，最后开发出我们的“薏米聚”图片检索系统，提供搜索相关标签并据此检索相关图片的联想式图像检索服务。
关键词：图片检索 社会化标签 相关度

Abstract: This paper gathered 4.5 million informations of every picture from flickr.Analysis of the distribution of image tag.A method of biodiversity is used to calculate the value of the degree of internationalization of  every pictures.Calculated
the correlation of image tags.Finally,we developed our "image" picture retrieval system,providing a associative image retrieval services:search related tags to retrieve relevant images.
Key words:Picture retrieval,Social tag, Correlation

0引言

       Flickr，一个在线照片管理系统，在过去几年迅速流行起来，人们把它用作一个社会化照片分享的网络工具。用户可以上传图片并给这些图片打上标签，还可以和别人分享这些图片。调查显示[1]这些用户生成的标签用来描述图片的内容和语义占的比重最大；用户所用的所有查询词中跟图片内容相关的词最多。这就是说，社会化标签可以用来从语义层面上表示图片；用户可以使用社会化标签作为关键词检索图片。这种大众分类法标签与一般的分类标签比起来词汇更加开放，形式更加自由。
      这些标签有很多特征和规律[2][3]，比如标签的多语言特性[4][5]，标签与基于受控词表的标引词有很大的差别[6]，标签词频可以用来提取相关资源共有的标签[7]，标签的数量与检索速率成正相关关系[8]等。我们统计了每种标签出现的词频，并按词频从大到小画词频的分布图，观察图像我们可以得出词频分布满足齐普夫定律。
      在我们的检索经历中，常常会出现这样一种情况：用户输入的检索词与目标图片相关但是不是最匹配的。例如：用户想要找一个中国很出名的景点“万里长城”时只知道是中国著名景点却想不出具体名称，所以检索时只能输入一个相关的词语“中国”检索的结果中当然就不能或不容易找到目标图像。我们这个工作的主要贡献就是通过计算标签相关度，从而能帮助人们联想目标检索词。我们开发的系统一方面可以检索相关词语，另一方面可以根据联想到的词语进一步检索图片。例如，用户输入“中国”检索相关标签会联想出“万里长城”这个标签，继续输入“万里长城”这个标签检索图片，其结果比输入“中国”检索图片的结果更好。除了找目标检索词外，联想的作用还可用来扩展检索等。
      另外，我们计算了图片的国际化程度值，我们假设图片国际化程度越高则此图被更多国家的人知道，那么检索结果按此值降序排列的结果会满足更多人的需要。所以，系统还可以优化检索结果排序，以便满足更多人的需要。下面，我将对上述内容详细阐释。
1标签分布规律
齐普夫定律[9]是美国学者G.K.齐普夫于本世纪40年代提出的词频分布定律。它可以表述为：如果把一篇较长文章中每个词出现的频次统计起来，按照高频词在前、低频词在后的递减顺序排列，并用自然数给这些词编上等级序号，即频次最高的词等级为1，频次次之的等级为2，……，频次最小的词等级为Ｄ。若用f表示频次，r表示等级序号，则有fr＝C(C为常数)。人们称该式为齐普夫定律。
统计结果发现，标签词频符合齐普夫定律，见图1，2。
 

图1：词频分布图

 
图2：词频齐普夫定律验证图
      图1中，横坐标是词频等级，纵坐标是词频。图2中，横坐标是词频等级，纵坐标是词频与等级的乘积。从图1可以看出词频的分布类似于长尾图，在图2中我们对纵坐标做了乘上横坐标的处理，大致可以看出分布渐渐逼近于一条水平直线。因此可以判定标签词频分布满足齐普夫定律。

2图像国际化程度

      图片标签就是一个小生态系统，这里面含有多个语种，每个语种出现的次数不一样，每个语种反应的国际化程度不一样。它们分别就对应了生态系统中有多个物种，每个物种数量不一样，每个物种的生物量不一样。因此，我们采用了公式（1）度量标签国际化程度。生物学中生物量取代指数方程式[10]的丰度公式H”。这个公式既考虑生物个体数量，又考虑了生物个体质量，还考虑了生物种类分布均匀度，在度量生物多样性上有很好的效果。具体公式见公式（1）：
（1）
 s样品所包含的种数，对应一张图片的语种数
 w样品中第 i 种生物量，对应每种语种的数量
 w'样品总生物量，对应一张图片的标签数
效果见图3：
 
图3：图片信息及国际化程度值
      图3描述了两张国际化程度值差异较大的两张图片，其中上图描述的是一种日本美食团子，下图描述的是含有菊花、玫瑰等的花束。可以看出，上图可能仅仅被日本等少数国家的人知道，而下图能被更为广泛的人熟知，因此用生活经验的比较结果可以印证我们国际化程度值的正确性。

3标签相关度

3.1相似度计算原理

      以中英文为例[11]，给定中文标签C和英文标签E，双语标签C与E的相关度计算主要方法有MI、Dice、?2统计值以及LogL、Jaccard、Cosine值等。
表1 双语标签出现频次联立表

表1 双语标签出现频次联立表

按照表1所示的双语标签出现频次联立表，以上方法的计算公式分别如下。
MI(C，E)= log2 (N*a/ ((a+b)*(a+c)))                      （2）
Dice(C，E)=2*a/((a+b)*(a+c))                             （3）
?2(C，)= N*(a*d-b*c)/((a+b)*(a+c)*(b+d)*(c+d))           （4）
LogL(C，E)=2* ( a*log2(a*N/((a+b)*(a+c))+b*log2(b*N/((a+b)*(b+d))+ c*log2(c*N/((c+d)*(a+c))+ d*log2(d*N/((c+d)*(b+d)))         （5）
Jaccard(C,E)=a/(a+b+c)                                  （6）
Cosine(C,E)=a/((a+b)*(a+c))                             （7）

3.2算法描述

 
图4：系统实现流程图
      相关度计算的算法如图4所示。具体说明如下：
Step1：采集数据预处理：
      简单过滤一些含有HTML标签的数据（采集出错的数据的一种），从原始数据的2000000条压缩到只有1932070条。利用生物多样性计算的一种方法：生物量取代H ‘( S )指数方程式的丰度来计算出国际化程度值得到预处理的数据。
Step2：得到单词表：
      将预处理的数据中的标签字段中的每个单词提取出来，识别语种和字符数，并记下它的记录号生成有重单词表。在有重单词表的基础上计算出每个单词的词频生成无重单词表。
Step3：得到二元组表：
      将预处理的数据中的标签字段中的每个单词提取出来，依次与同一条记录的其它单词生成有重二元组表。在有重元组表的基础上计算出每个单词的词频生成无重元组表。
Step4：计算词语相似度:
      在以上生成的表的基础之上，分别计算几个相似度指标MI、Dice、?2 统计值以及LogL、Jaccard、Cosine值，得到最后的参数表。
上述计算结果如图5所示：
 
图5：查询标签结果页面
计算的这几个相关度指标都可以度量图片标签的相关度，我们根据观察结果取排序结果较好的LogL值，结果默认按LogL值降序排序最相关的词在最上面显示，以下按相关度降序排列。从图5可以看出我们检索的关键词“春天”相关的词语都列出了，其中最相关的就是“spring”。这个结果有力的支持了我们的研究。

4图像联想检索

      为了演示我们的分析结果，我们开发了自己的图片检索系统，对输入的查询词我们可以有两种返回结果：一种是含有此标签的图片，一种是跟此标签相关的标签。配合二者的使用就可实现目标检索词联想以及扩大检索范围的目的。检索“中国”的相关标签和相关图片的查询结果分别见图
5、图6所示：
 
图6：相关标签可视化展示页面
 
图7：查询图片结果页面
      图6与图5结果一致，只是采用了一个标签云的可视化效果提高用户体验，从检索框中输入检索词，可以点击搜标签按钮得到相关标签，在相关标签云图中继续点击可以得到被点击词语的相关标签。找到目标标签之后，可以从检索框中输入检索词并点击搜图片按钮可以得到含有这个标签的所有图片。

5结论展望

      本项目在对flickr图片标签的处理过程中。计算了图片的国际化程度，得到标签之间的相关度，并开发图片检索系统为用户提供检索相关图片和相关标签的服务。但是，在很多方面仍然有很多缺陷，总结如下：
（1）语种识别的问题，本项目采用的识别方法主要是依赖于lang-detect工具，而该工具在检测网页的语种方面的独到的优势正确率极高。而在检测单词或者短语上10个词以下的准确度就会急剧下降，在被测语言检测结果为：英语、中文繁体、中文简体和日语就还具有很高的准确度，但对其他小语种以及上述主要语种检测为其他语种时准确度很难保证。以后可以结合Unicode编码的方法识别语种，以提高准确度。
（2）原始数据的过滤仅仅是对采集出错信息过滤，并没有过滤垃圾标签，而且何为垃圾标签也还需要准确定义。日后还可以研究标签过滤算法，在预处理阶段就除去更多噪音。
（3）在开发的系统中为了提高用户的体验，所以并没有使用所有的原始数据。而是只取了之中比较有代表性的数据集。所以，为了真实并且全面准确的反应图片标签之间的相关性还可以加大网站后台数据量，甚至可以使用所有处理过的数据，这个是今后研究的一个内容。
（4）原始数据现有的社会化并没有完全发挥出作用来，因为我们的处理仅仅是使用了图像-标签-用户三角关系的其中一个角度。今后可以利用起图像的用户信息，还可以借鉴一些图像处理技术。从用户相似，图像相似的基础上推出标签相似度。这样也就可以实现一些图像的自动标引。
（5）在数据展示的方面，目前仅仅使用了一个标签云的效果，还可以结合D3插件的强大功能，做出更完美的数据可视化效果，这个工作正在研究中，相信不久的未来可以有不错的结果。
      另外，目前的测试语料所用图片记录也只有450万记录的规模。我们还想将在社会化图像标签研究的方法技术和结论扩展到其他领域，并开发一些其他比较实用的网站。

6参考文献

[1] Bischo, K., Firan, C.S., Nejdl, W., Paiu, R.: Can all tags be used for search? In:CIKM 2008, pp. 193–202 (2008)
[2] B?rkur Sigurbj?rnsson , Roelof van Zwol. Flickr Tag Recommendation based on Collective Knowledge[C]. In: Proceedings of the 17th International Conference on World Wide Web. Beijing, China,2008:327-336.
[3] Golbeck J, Koepfler J, Emmerling B. An Experimental Study of Social Tagging Behavior and Image Content[J]. Journal of the American Society for Information Science & Technology,2011,62(9):1750-1760.
[4] Eleta I. Art Images and Multilingual Social Tagging:A Museum Without Borders[R]. USA, Maryland: University of Maryland, 2011: 1-7.
[5]Jung J. Cross-Lingual Query Expansion in Multilingual Folksonomies: A Case Study on Flickr[J]. Knowledge-Based Systems.2013,42:60-67.
[6]Rorissa A. A Comparative Study of Flickr Tags and Index Terms in a General Image Collection[J]. Journal of the American Society for Information Science and Technology,2010,61(11):2230-2242.
[7]Chen X, Shin H. Tag Recommendation by Machine Learning with Textual and Social Features[J].Journal of Intelligent Information Systems,2013,40(2):261-282.
[8]Callegari J, Morreale P. Assessment of the Utility of Tag Clouds for Faster Image Retrieval[C].In: Proceedings of the International Conference on Multimedia Information Retrieval. Philadelphia, PA, USA,2010: 437-440.
[9]邱均平.信息计量学(五)第五讲文献信息词频分布规律——齐普夫定律[J].情报理论与实践.2000,05:396-400
[10]陈宽智.介绍四种多样性指数及均匀度测量[J].环境科学.1979,2:64-70
[11]章成志.多语言领域本体学习研究[M].南京：南京大学出版社.2012:145