英语原文共 8 页

摘要--抽象的多媒体搜索通常返回可分为几个“主题”的项目，允许用户更有效地消除歧义和探索答案。在本文中，我们研究了与多媒体搜索结果相关联的群集标记的方法，其中每个生成的群集表示为特定搜索在线计算的主题。我们特别研究了社区检测算法对搜索结果中的标签图的适用性。这种类型的方法允许我们利用标签相似性，为每个搜索创建特别的主题，而不预先指定集群的数量和大小。

在这项工作中，我们对这一领域的著名算法进行了实验，并提出了两种基于自适应孤岛切割的新方法。使用Social20数据集（从Flickr收集的一个集合），我们评估了几种社区检测方法，对每种算法进行定量分析，以确定它们产生的社区（我们将其解释为主题）的相对数量及其大小，并根据人类判断对主题进行定性分析。我们的评估表明，使用社区检测来提取搜索结果的特别主题是可能的，但是不同的社区检测方法产生的结果是不同的。特别是，与产生更大集群的方法相比，我们提出的方法产生的集群更紧凑、噪声更小，相对回忆也更少。索引词标记聚类；多媒体检索；社区检测；主题检测。

一、介绍

在网络信息检索中，特别是多媒体搜索引擎中，一个主要关注点是如何改进用户与搜索结果的交互。在商业图像搜索引擎（以及其他类型的多媒体搜索）中，帮助用户快速理解结果的一种常见机制是应用聚类，以便将类似的结果组织成组[1]、[2]。例如，结果可以显示在具有相似内容（例如，具有相似配色方案的图像）或具有相似主题的组中。本文主要研究基于主题的聚类，通过对不明确的文本查询（例如，查询“Boxers”可能指狗、斗士或内衣）或同一解释的不同方面（例如，“Boxer Dogs”：小狗、脸等）进行多个解释，帮助用户理解搜索结果。

与依赖于视听功能（如[3]、[4]、[5]）的内容聚类不同，主题相似性聚类传统上依赖于文本功能，如网页中围绕图像的文本，或与多媒体对象相关的人工注释（标记）。利用周围文本扩展LDA[6]的许多方法（在[7]，[8]中描述了更新的工作）。但是，通常会找到多媒体存储库，如Flickr1和Last.fm2，通常只有用户生成的标签可用。

我们关注使用标签的主题集群。具体来说，我们解决了在给定查询的多媒体搜索结果中仅使用标记信息获取主题的问题。我们的目标是提供一种方法，使我们能够在不事先了解多媒体领域或访问完整多媒体收藏的情况下，以在线方式为任何查询提供特别主题。这样做的好处是，允许对主题（即客户端）进行轻量级的分布式计算，同时处理不能在服务器端预先计算的长尾查询。我们的方法可以用于聚合来自多个搜索引擎的结果，使用不同类型的多媒体，只要结果被标记。

对于这个主题聚类，我们研究了著名的社区检测算法在搜索结果的标签图表示上的应用，假设标签共现图（标签为节点和边缘的图表示一个项目上的两个标签共现）中标签的密集连接社区对应于叶状集群[9]。因此，我们提出了一个发现多媒体搜索结果主题的通用框架。我们的框架利用现有的社区检测方法。为了解决初始评估中发现的局限性，我们还提出了两种新的社区提取方法。除了标记的搜索结果，这些方法不需要任何先验知识；同样，它们也不试图“解释”标记，因此我们的方法是语言不可知论的。以Social20数据集为例，我们从产生的簇的数量和大小定量地比较了社区检测技术，并根据人类的判断定性地比较了每个集群中的集群的相关术语。

二、背景

我们总结了多媒体搜索结果聚类、基于标签的聚类和社区检测算法的背景文献。

多媒体搜索结果聚类：网络上大量的多媒体数据使得多媒体搜索引擎需要提供增强用户与搜索结果交互的机制。几项研究表明，主题文档聚类有助于用户快速理解搜索结果。有些方法使用来自网页[2]的文本、来自多媒体共享平台的评论[10]以及与多媒体对象相关的元数据[11]。

考虑到网络上有大量未标记的多媒体对象，许多工作集中在如何自动将标记分配给未标记的多媒体[27]以及如何通过聚合用户生成的内容来优化标记[28]上。Li等人[29]关于本主题的调查相关工作。

除了基于文本的多媒体搜索聚类之外，混合技术还将多媒体内容和上下文数据融合到构建集群中。例如，添加视听功能（例如，颜色分布、纹理）可以增强Web内容和结构（例如，图像周围的文本、图像URL、超链接）[1]或用户生成的与多媒体内容相关的元数据（例如，标题、标记、描述）[12]。然而，由于视听特征提取阶段的计算成本较高，这些方法并不总是可扩展的。因此，基于纯文本分析的应用程序被认为与现代应用程序相关。Moreno和Dias[13]研究了基于文本的多媒体搜索聚类在移动设备网络搜索环境中的应用。

基于标签的多媒体聚类：10个多媒体资源缺乏描述性文本；相反，标签已经成为描述和（部分）组织多媒体对象的一种方便方式。尽管基于标签的集群可以被视为基于文本的集群，但是在考虑标签时，我们没有单词位置或邻近度的概念（标签不遵循相关顺序），文档中也没有单词频率（标签最多分配一次）。因此，典型的方法不是应用基于文本的主题提取技术，而是应用基于图形的技术。

大多数关于应用基于图的方法从标签共现中提取结构的文献都集中在构建分类法上。这样的分类法允许用户以直观的方式浏览标记和标记的资源。Strohmier等人[14]调查最常见的分类归纳方法。这种层次方法并不总是适合表示标签之间的关系，因为标签本身是扁平的，没有关于标签宽度或宽度的明确信息。一些建议通过使用外部层次知识源来解决这个问题，例如word-net[15]，或者由用户指定的集合[16]或域本体[17]引起的浅层次分类法。然而，与域无关的数据集通常只包含一般的标记，而不包含专有名词或首字母缩略词，而与域相关的数据集通常不可用。

在这项工作中，我们认为主题分类法的引入与集群的目标是正交的，其中我们希望分组相关的标记和标记的资源，而不必担心哪一个比哪一个更广泛。我们将聚类问题看作是在平面标签共现图中找到紧密结合的社区或社区。

社区检测：社区是一个图中紧密相连的子图。社区检测是一个图形分区问题，其目标是识别构成分区的“最密集”的可能社区集。一种幼稚的方法是应用一种标准的最小切割方法，在将切割成本最小化（例如，切割边缘的数量）的同时对图形进行分割。然而，最小割法通常强制一个固定数量的割或分区，而不是识别“自然”的密集子图。相反，社区检测的主要目标之一是识别最佳社区，而不考虑其数量；这对于我们的场景非常有用，因为它避免了预先提供所需数量的集群。Fortunato[18]和Papadopoulos等人[9]描述解决社区检测问题的各种度量和算法。

许多社区检测方法都致力于优化一个通用的度量标准。模块化是最常见的度量标准，它是图中属于社区的所有边的比率，减去具有相同顶点和边数但随机分配边数的图中的期望值。不幸的是，寻找最优的社区配置是困难的；因此算法采用了近似方法，如局部模块化测量[19]、光谱分析[20]等。另一个问题是模块化的分辨率限制。在大型图中，即使是两个社区之间的单一边缘也被视为“不太可能发生的事件”，导致小社区合并为几个非常大的社区。

除了优化模块化之外，作者还探索了用于社区检测的其他选项，例如应用自顶向下的聚类方法[21]，或者分析图的结构[22]，或者信息如何在图中流动[23]，[24]。

创新性：我们在标签共现图中应用了一组节点，而不需要引入分类法，也不需要外部知识。鉴于在社区检测方面的大量工作，以及缺乏指定多个集群或切割的必要性，我们认为将此类技术应用于集群问题的研究是自然的。因此，我们从数量和质量两方面评估由各种社区检测技术根据用户可识别的主题产生的集群。基于初始结果，我们发现现有的社区检测技术往往返回太少的大集群或太多的小集群等；因此，我们提出了两种基于Island Cuts的新方法[25]，[26]。

三、主题检测框架

我们引入了一个框架来检测与编码用户信息需求的查询相关联的语义相关的标签组（“主题”）。我们的动机是通过只使用结果中的标记对异构多媒体搜索结果进行在线集群的用例。

图1显示了拟议框架，包括以下四个主要阶段：

1）基于特定的

查询：搜索结果是框架的起点。出于通用性的考虑，我们假设输入一组与一组标记关联的项，在这些项上，我们使用标记共存信息执行集群。由于我们将多媒体内容的表示减少为标签，理论上，我们的框架能够将不同类型的多媒体资源。

2）标签共现图的构造（标签图）：标记图是框架工作的关键结构。给定资源r的有限bag3，其中每个资源都表示为一组标记，我们将标记共现图定义为G_lambda; = (V, E, lambda;), 其中 V = cup;risin;R^r 是顶点, E = {(v, vrsquo;) | exist;r isin; R 使visin;r, vlsquo;isin;r 且 v̸=vlsquo;}是边，其中lambda;：E→R是用实数标记E中每个边的加权函数。

lambda;的最简单加权方案计算一对的共现次数。然而，基于基数的权重可能对所考虑的资源数量很敏感，因此我们建议使用一种更为稳健的加权方案，如结构相似性[22]：

其中v和vlsquo;是节点，n(v) = {v′′ | (v, v′′) isin; E} 是无向图中v的邻居，nv(v) = n(v) cup; {v} 包括v，s表示t集合的基数。

3）基于社区检测算法的标签聚类：我们采用社区检测算法来避免预先指定集群数量。在这种方法下，不需要额外的多媒体资源知识来检测相关的标签组（除了标签共存）。最初的经验表明，使用现有的社区检测算法[9]对来自Flickr图像搜索引擎的搜索结果进行聚类通常会导致不明确的主题（例如，我们发现聚类太大，并且分组了不相关的术语）。因此，我们还提出了两种基于孤岛切割的新社区检测算法[25]。

4）使用标签的主题表示：理想情况下，不需要对社区检测算法的输出应用任何额外的过程。但是，对于返回大型社区的算法，我们需要应用一些排名技术，以便获得标签的可管理子集。对社区内的标签进行排序的最简单方法是按频率或程度对它们进行排序。

我们的框架的主要特点是：

-多媒体类型独立性：我们在标签图构建过程中不使用基于内容的功能。我们的模型可能以透明的方式发现不同类型多媒体资源中的主题。

–标记和主题独立性：我们的框架不需要任何培训数据，它不固定于域或语言，也不固定于有限或固定数量的主题。

–查询特定：标记图是针对特定查询构建的，这有助于消除（非查询）多段标记的歧义；例如，查询结果中出现的标记Jaguar“Zoo”只（可能）指的是cat，而不是car4。

–在线概念检测：考虑到足够的物理框架结构和优化的社区检测算法，可以在线方式（例如，在客户端）执行多媒体主题检测。

四、图形聚类方法

我们新的图形聚类方法是基于Zaversˇnik amp; Batagelj首次提出的岛屿[26]。

孤岛：孤岛是一个子图，对于图[25]、[26]的给定属性，它在其邻域中是最大的。Zaversˇnik amp; Batagelj考虑了两种类型的岛屿：顶点岛和边缘岛。孤岛是相对于某个顶点（或边）属性P定义的，在该属性中，没有一个岛的外部邻居的p值高于孤岛中的任何顶点（或边）。另外，如果没有一个这样的邻居具有与岛内顶点（或边）相等的p值，则该岛是规则的。

孤岛是根据“贪婪”算法构建的，该算法首先使用给定属性值最高的顶点（或边）对孤岛进行初始化，然后通过从这些起点遍历图以包括其邻居来放大和/或组合这些孤岛。这个过程类似于构建生成树，只是它记录了顶点（或边）添加到解决方案中的顺序。

识别岛屿：我们遵循Zaversˇnik amp; Batagelj [25]，[26]提出的提取岛屿的高级算法。

基于顶点的岛层次结构：我们首先初始化层次结构H = (VH , EH )。给定G，我们按给定顶点属性p值的降序迭代其顶点V，其中对于每个visin;V，我们首先将其添加到VH。接下来，我们将v连接到H中所有与G中v相邻的现有岛屿的端口vrsquo;（最后一个添加到岛屿的顶点）：我们将边缘（vi，virsquo;）添加到eh，其中v现在将每个这样的vrsquo;替换为新的更大岛屿的端口。如果顶点岛是规则的，那么它在E_h中不能有直接连接两个节点的边，而p的值相同。

例1.假设我们将pagerank[30]作为顶点属性p。如果我们计算图2中标记图中每个顶点的pagerank并对其进行排序（降序），我们得到：

V = (baseball, detroit, orange, cat, . . . , color)

我们从H = (VH , EH )空白开始。迭代V，我们首先在VH中添加棒球。接下来，我们添加detroit，它是G中baseball的邻居。由于baseball是H的一个港口，我们将定向边缘（baseball，detroit）添加到EH。接下来，我们添加orange，但不要将它连接到任何东西，因为它在H中已经没有邻居了。图3显示了最终的层次结构。

基于边缘的岛层次：我们从H = (VH , EH )开始，其中VH包含表示岛的顶点集，以及EH sube; VH times; VH 。我们初始化所有单点顶点的VH , EH为空。给定g，我们按照给定属性p的降序迭代其边E。对于每个边，我们检索包含两个节点的VH中最大的岛。如果它们不相同，我们将创建一个新的岛，它是两个岛的联合，并将新岛的定向边添加到两个旧的子岛上。一旦对所有边进行了分析，H是一个树，其中VH中的所有节点都是边孤岛，EH中非冗余边的一个子集表示子岛关系。对于规则边岛，它不能具有从具有相同权重的边派生的H中的传入边。

五、评价

这个评估的目的是找出社区检测算法是否产生连贯的语义主题，并测量每个算法产生的主题的质量。在这种情况下，内聚性很难度量，因为它必须评估特定集群中的标记是否在语义上相关。这是一个主观的任务，因此我们寻求人类的判断。此外，完整的评估数据集非常庞大，包括数千个主题（集群）。因此，我们通过抽样得出的主题来解决这个问题，只评估得出的样本。

资料编号：[5270]