一种基于图像和文本相关性挖掘的Web图像聚类方法

摘要

本发明公开了一种基于图像和文本相关性挖掘的Web图像聚类方法。包括如下步骤：(1)根据查询提取Google图片搜索结果中的图像及其伴随文本；(2)提取伴随文本中名词构成词汇表；(3)计算词汇表中单词的可见度，并将其与TF－IDF方法集成以计算单词和图像相关性关联；(4)计算词汇表中任意两个单词间的主题相关度；(5)利用复杂图对相关性关联建模；(6)应用复杂图聚类算法对图像进行聚类。本发明将单词可见度与TF－IDF方法结合定义单词和图像的相关性关联，突破了TF－IDF方法作为一种文本处理技术不能直接度量单词和图像之间相关性的限制，通过复杂图对单词和图像以及单词和单词相关性关联建模提出了一种Web图像聚类框架，使得图像检索结果根据主题进行归类，方便用户进行检索。

说明书

技术领域

本发明涉及多媒体检索，尤其涉及一种基于图像和文本相关性挖掘的Web图像聚类方法。

背景技术

在Web上，使用关键字搜索图像仍然是有效的常用检索手段，如商业搜索引擎Google和AltaVista的图片搜索。在Web图像检索中，用户提交的关键字往往是视觉多义词，这类单词包含多个不同视觉含义。例如单词“mouse”可表示“computer mouse”、“mouse animal”和“Mickey mouse”等多个主题。因此，用这些视觉多义词查询图像，所返回的图像检索结果会包含多个主题，并且不同主题的图像混合在一起。这就需要提供一种检索后处理过程来对表达不同主题的图像进行归类。近来，很多研究者提出了Web图像聚类方法来解决这个问题。由于图像的底层特征和高层语义之间存在“语义鸿沟”，这些聚类方法往往同时利用了被聚类图像集合所包含的视觉、文本和链接等多模态信息。属于不同特征空间的多模态信息是相互关联的，挖掘和利用这些相关性关联以进行多模态信息融合的学习是近期机器学习研究的一个重点课题，代表性工作有多视角学习和迁移学习。前者同时利用同一数据的多种特征空间表示进行学习，而后者研究训练数据和测试数据有不同分布或属于不同特征空间的学习问题。本发明挖掘文本与图像两种模态信息的相关性关联，通过图模型对其关联关系进行建模，并利用图聚类算法对Web图像进行聚类。

Web图像通常与其伴随文本共存于HTML页面之中，伴随文本以及一些文本标签描述了图像的语义内容。在Web图像检索和标注领域，很多研究利用了图像和文本之间的相关性关联。但是，伴随文本中不同单词对图像语义描述所做贡献不同。对于文本中多个单词，有的单词能够找到合适的图像来形象地描述该单词的含义，例如“chairs”；有的单词比较抽象，则很难找到一个合适图像来形象地描述该单词的含义，例如“statistics”。从形象思维的角度，这种差异反映了单词和图像之间存在不同语义关联，也反映单词具有“可见度”属性。所谓可见度即某个单词可被视觉感知的概率。作为一种文本处理技术，TF-IDF并不能直接度量单词和图像之间的相关性，传统通过TF-IDF方法衡量伴随文本中单词对图像的重要性一定程度上忽略了图像本身具有的视觉特征。因此，本发明提出一种单词可见度模型，并将该模型与TF-IDF方法结合来定义一种新的单词和图像相关性关联。

另一方面，对于包含多个主题的Web图像集合，其伴随文本中的隐含主题信息间接反映了图像间的主题相关性。为了将这种主题相关性引入Web图像聚类，本发明利用隐含狄利克雷分配进行学习以得到分布在每个单词上的隐含主题概率，通过定义的主题相关度函数计算单词和单词主题相关性。隐含狄利克雷分配模型，即Latent Dirichlet Allocation，是近年来提出的一种能提取文本隐含主题的非监督学习模型，作为一种生成概率模型，隐含狄利克雷分配建模在一个离散数据的集合上，如文本数据集。在文本表示领域，隐含狄利克雷分配是主题模型的典型代表，能够对文本数据包含的主题信息进行建模。

因此，本发明通过挖掘图像和伴随文本之间的相关性关联得到两种关联关系：单词和图像相关性关联以及单词和单词主题相关性关联，这种交叉关联可用图模型进行建模。传统的图模型只能对单一类型结点及结点间的同构链接进行建模。二部图能够对两种类型结点进行建模，但是该图模型只包含不同类型结点之间的异构链接。由于本发明涉及的两种关联关系既包含单词和图像两类不同结点之间的异构链接，又包含单词和单词同类型结点之间的同构链接，因此提出用更一般的复杂图模型对这两种关联关系进行建模，并应用复杂图聚类算法对图像进行聚类。

发明内容

本发明的目的是为了对Web图像检索结果进行聚类，使得相同主题图像聚成一类，以方便用户进行检索，提出一种基于图像和文本相关性挖掘的Web图像聚类方法。

基于图像和文本相关性挖掘的Web图像聚类方法包括如下步骤：

(1)根据用户查询提取Google图片搜索的检索结果中的图像及其伴随文本，提取伴随文本中的名词构成词汇表；

(2)对伴随文本进行文本处理并提取文本特征；

(3)计算词汇表中每个单词的可见度；

(4)将单词的可见度与TF-IDF方法集成以计算单词和图像相关性关联；

(5)根据主题模型对伴随文本集合进行分析，提取隐含主题概率分布以计算词汇表中任意两个单词间的主题相关度；

(6)利用复杂图模型对单词和图像相关性关联以及单词和单词主题相关性关联进行建模；

(7)应用复杂图聚类算法对图像进行聚类。

所述的根据用户查询提取Google图片搜索的检索结果中的图像及其伴随文本，提取伴随文本中的名词构成词汇表的步骤如下：

(1)编写爬虫程序下载Google图片搜索的检索结果中的图像，构成图像集合IMG＝{Image₁，...，Image_Nd}，其中N_d是集合IMG中的图像总数；

(2)下载图像集合IMG中每个图像所在网页，利用页面解析程序对每个网页进行解析，去除HTML标记和标点符号后，保留页面上的文本内容作为图像的伴随文本；

(3)对每个图像的伴随文本进行词性标注，去除非名词单词，保留文本中的名词，构成伴随文本集合D＝{d₁，...，d_Nd}，其中N_d是集合D中的伴随文本总数；

(4)顺序扫描伴随文本集合D中的每个伴随文本d_i中的所有单词，其中i＝1，…，N_d，每个不同单词保留一个，形成单词列表表示的词汇表VOL＝{w_i，…，w_Nw}，其中N_w是词汇表VOL中的单词总数。

所述的对伴随文本进行文本处理并提取文本特征的步骤如下：

(1)对词汇表VOL中的每个单词w_i，其中i＝1，…，N_w，N_w是词汇表中单词总数，顺序扫描伴随文本集合D中的每个伴随文本d_j，统计每个单词w_i在每个文档d_j中出现的次数n_ij，其中j＝1，…，N_d，N_d是伴随文本总数，并统计集合D中包含单词w_i的伴随文本个数num(w_i)；

(2)根据公式(1)计算每个单词w_i在每个伴随文本d_j中的词频freq(w_i，d_j)，其中i＝1，…，N_w，N_w是词汇表中单词总数，j＝1，…，N_d，N_d是集合D中伴随文本总数；

$\mathrm{freq}(w_i,d_j)=n_{\mathrm{ij}}/{\Sigma }_{k=1}^{N_w}{n}_{\mathrm{kj}}.---\left(1\right)$

(3)对词汇表VOL中的每个单词w_i，根据公式(2)计算其逆文档词频idf(w_i)；

idf(w_i)＝log(N_d/num(w_i)).    (2)

(4)根据向量空间模型，将集合D中每个伴随文本d_j表示成N_w维向量，第i维对应词汇表中的单词w_i，其值为tfidf(w_i)，计算公式如下：

tfidf(w_i)＝freq(w_i，d_j)×idf(w_i).    (3)。

所述的计算词汇表中每个单词的可见度的方法是：词汇表VOL中每个单词w_i的可见度值vis(w_i)由公式(4)计算；

$\mathrm{vis}\left(w_i\right)={((C_1+{10}^{-9})/(C_2+{10}^{-9}))}^{-{\mathrm{IDF}}_{\mathrm{Google}}\left(w_i\right)}.---\left(4\right)$

其中，C₁是将单词w_i作为查询提交给Google图片搜索返回的检索结果总数，C₂是将单词w_i作为查询提交给Google文本搜索返回的检索结果总数；指数因子IDF_Google(w_i)的计算公式如下：

IDF_Google(w_i)＝log(|D_Google|/C₂).    (5)

其中，D_Google是Google索引的所有Web页面集合，|D_Google|表示集合D_Google中的页面总数。

所述的将单词的可见度与TF-IDF方法集成以计算单词和图像相关性关联的方法是：单词w_i与图像Image_j的相关性关联r(w_i，Image_i)由公式(6)计算，其中j＝1，…，N_d，N_d是伴随文本总数；

r(w_i，Image_j)＝tfidf(w_i)×vis(w_i).    (6)。

所述的根据主题模型对伴随文本集合进行分析，提取隐含主题概率分布以计算词汇表中任意两个单词间的主题相关度的步骤如下：

(1)以词汇表VOL、伴随文本集合D和集合D中的隐含主题数k作为主题模型隐含狄利克雷分配的输入，输出每个隐含主题z_j的概率分布P(z_j)和z_j在每个单词w_i上的概率分布P(w_i|z_j)，其中j＝1，…，k；

(2)集合VOL中任意两个单词w_s和w_t之间的主题相关度Topic_r(w_s，w_t)由公式(7)所定义的主题相关度函数计算，其中σ是归一化常数，

$\mathrm{Topic}\_r(w_s,w_t)=\underset{j}{\max }P(z=j|w_s)P(z=j|w_t)$

$=\underset{j}{\max }\frac{p\left(w_s\right|z=j)P(z=j)}{P\left(w_s\right)}·\frac{p\left(w_t\right|z=j)P(z=j)}{P\left(w_t\right)}---\left(7\right).$

$=\underset{j}{\max }\frac{p\left(w_s\right|z=j)p\left(w_t\right|z=j)P(z=j)}{\sigma }.$

所述的利用复杂图模型对单词和图像相关性关联以及单词和单词主题相关性关联进行建模的方法是：复杂图模型包含图像结点和单词结点两种不同类型结点，单词和图像间的异构链接以及单词和单词间的同构链接作为结点间的边，单词和图像链接权重由公式(6)所定义的单词和图像相关性关联r(w_i，Image_i)计算，单词和单词链接权重为公式(7)定义的单词和单词主题相关度函数Topic_r(w_s，w_t)计算，复杂图模型表示为如公式(8)所示的矩阵集合；

{$S\in R_{+}^{N_w\times N_w},$$A\in R_{+}^{N_d\times N_d}$}.    (8)

其中，对称矩阵$S\in R_{+}^{N_w\times N_w}$表示单词和单词相关性矩阵，N_w是词汇表中单词总数，R₊是正实数集合，矩阵元素S_ij(i≠j)表示单词w_i和w_j之间的主题相关度，S_ij＝Topic_r(w_i，w_j)矩阵$A\in R_{+}^{N_w\times N_d}$表示单词和图像相关性矩阵，N_d是图像总数，矩阵元素A_ij表示单词w_i和第j个图像Image_j之间的相关性关联，A_ij＝tfidf(w_i)·vis(w_i)。

所述的应用复杂图聚类算法对图像进行聚类的方法可表示为如公式(9)所定义的优化问题；

$\left(\begin{array}{c}\underset{C^{\left(1\right)},C^{\left(2\right)},D,B}{\min }{\left|\right|S-C^{\left(1\right)}D{\left(C^{\left(1\right)}\right)}^T\left|\right|}^2+{\left|\right|A-C^{\left(1\right)}B{\left(C^{\left(2\right)}\right)}^T\left|\right|}^2\\ s.t.C^{\left(1\right)}\in {\left\{\mathrm{0,1}\right\}}^{N_w\times k_1},C^{\left(2\right)}\in {\left\{\mathrm{0,1}\right\}}^{N_d\times k_2},C^{\left(1\right)}1=1,C^{\left(2\right)}1=1\end{array}\right).---\left(9\right)$

其中，向量1的每个分量都为1，k₁和k₂分别表示单词和图像的聚类个数，类属指示矩阵C⁽¹⁾和C⁽²⁾是复杂图聚类算法的输出，矩阵元素C_pq⁽²⁾表示第p个图像Image_p属于第q类，对公式(9)所定义的优化问题进行求解的复杂图聚类算法如算法1所示：

算法1.复杂图G₁的聚类算法CGC.

输入：矩阵S和A；

输出：类属指示矩阵C⁽¹⁾和C⁽²⁾，k₁和k₂分别是单词和图像的聚类个数；

步骤1.重复迭代步骤2-5直到收敛；

步骤2.计算D＝((C⁽¹⁾)^TC⁽¹⁾)^-1(C⁽¹⁾)^TSC⁽¹⁾(C⁽¹⁾)^TC⁽¹⁾)^-1；

步骤3.计算B＝((C⁽¹⁾)^TC⁽¹⁾)^-1(C⁽¹⁾)^TAC⁽²⁾(C⁽²⁾)^TC⁽²⁾)^-1；

步骤4.固定D，B和C⁽²⁾，逐行更新C⁽¹⁾，使得最小化L，L计算如下：

L＝||S-C⁽¹⁾D(C⁽¹⁾)^T||²+||A-C⁽¹⁾B(C⁽²⁾)^T||²；

步骤5.固定D，B和C⁽¹⁾，逐行更新C⁽²⁾，使得最小化L，L计算如下：

L＝||S-C⁽¹⁾D(C⁽¹⁾)^T||²+||A-C⁽¹⁾B(C⁽²⁾)^T||².

根据算法1输出的类属指示矩阵C⁽²⁾对图像集合IMG进行聚类的方法是，如果矩阵元素$C_{\mathrm{pq}}^{\left(2\right)}=1$则把第p个图像Image_p归为第q类，其中p＝1，…，N_d，N_d表示集合IMG中图像总数，q＝1，…，k₂，k₂表示IMG中图像的聚类个数。

本发明具有的有益的效果是：本发明将单词可见度模型与传统的TF-IDF方法结合定义单词和图像的相关性关联，突破了TF-IDF方法作文一种文本处理技术不能直接度量单词和图像之间相关性的限制；通过复杂图对单词和图像相关性关联以及单词和单词主题相关性关联进行建模提出了一种新的Web图像聚类框架，提高了Web图像聚类精度，使得图像检索结果根据主题进行归类，方便用户进行检索。

附图说明

图1是基于图像和文本相关性挖掘的Web图像聚类方法的关键步骤工作流程图，其中(a)是根据查询“bass”从Goole图像搜索返回结果中提取的部分图像和相应的伴随文本，(b)是复杂图模型示例，实线代表单词和图像相关性关联，虚线代表单词和单词主题相关性关联，(c)是输出的聚类结果，处理步骤(1)是对伴随文本进行文本处理并提取文本特征后，挖掘文本和图像间的相关性关联，对得到的单词和图像以及单词和单词两种关联用复杂图进行建模，处理步骤(2)是利用复杂图聚类算法对图1(b)所示复杂图进行聚类；

图2是基于图像和文本相关性挖掘的Web图像聚类方法中Web图像及其伴随文本示意图，图中斜体表示名词；

图3是图2伴随文本中名词可见度计算结果示意图；

图4是对5个查询实例的复杂图聚类结果的互信息对比图；

图5(a)是查询jaguar在没有引入可见度情况下复杂图聚类结果中三个主题类“jaguar car”、“jaguar animal”和“jaguar car”中的前5个图像的示意图，图中红色虚线边框的图像是错误的聚类项；

图5(b)是查询jaguar在引入可见度之后复杂图聚类结果中三个主题类“jaguar car”、“jaguar animal”和“jaguar car”中的前5个图像的示意图，图中红色虚线边框的图像是错误的聚类项；

图6是查询mouse通过本发明聚类方法聚类结果中三个主题类“computermouse”、“mouse animal”和“Mickey mouse”中的前10个图像的示意图，图中红色虚线边框的图像是错误的聚类项。

具体实施方式

本发明提出一种基于图像和文本相关性挖掘的Web图像聚类方法，结合附图，其实施详细说明如下。

基于图像和文本相关性挖掘的Web图像聚类方法包括如下步骤：

(1)根据用户查询提取Google图片搜索的检索结果中的图像及其伴随文本，提取伴随文本中的名词构成词汇表；

(2)对伴随文本进行文本处理并提取文本特征；

(3)计算词汇表中每个单词的可见度；

(4)将单词的可见度与TF-IDF方法集成以计算单词和图像相关性关联；

(5)根据主题模型对伴随文本集合进行分析，提取隐含主题概率分布以计算词汇表中任意两个单词间的主题相关度；

(6)利用复杂图模型对单词和图像相关性关联以及单词和单词主题相关性关联进行建模；

(7)应用复杂图聚类算法对图像进行聚类。

所述的根据用户查询提取Google图片搜索的检索结果中的图像及其伴随文本，提取伴随文本中的名词构成词汇表的步骤如下：

(1)编写爬虫程序下载Google图片搜索的检索结果中的图像，构成图像集合IMG＝{Image₁，...，Image_Nd}，其中N_d是集合IMG中的图像总数；

(2)下载图像集合IMG中每个图像所在网页，利用页面解析程序对每个网页进行解析，去除HTML标记和标点符号后，保留页面上的文本内容作为图像的伴随文本；

(3)对每个图像的伴随文本进行词性标注，去除非名词单词，保留文本中的名词，构成伴随文本集合D＝{d₁，...，d_Nd}，其中N_d是集合D中的伴随文本总数；

(4)顺序扫描伴随文本集合D中的每个伴随文本d_i中的所有单词，其中i＝1，…，N_d，每个不同单词保留一个，形成单词列表表示的词汇表VOL＝{w_i，…，w_Nw}，其中N_w是词汇表VOL中的单词总数。

所述的对伴随文本进行文本处理并提取文本特征的步骤如下：

(1)对词汇表VOL中的每个单词w_i，其中i＝1，…，N_w，N_w是词汇表中单词总数，顺序扫描伴随文本集合D中的每个伴随文本d_j，统计每个单词w_i在每个文档d_j中出现的次数n_ij，其中j＝1，…，N_d，N_d是伴随文本总数，并统计集合D中包含单词w_i的伴随文本个数num(w_i)；

(2)根据公式(1)计算每个单词w_i在每个伴随文本d_j中的词频freq(w_i，d_j)，其中i＝1，…，N_w，N_w是词汇表中单词总数，j＝1，…，N_d，N_d是集合D中伴随文本总数；

$\mathrm{freq}(w_i,d_j)=n_{\mathrm{ij}}/{\Sigma }_{k=1}^{N_w}{n}_{\mathrm{kj}}.---\left(1\right)$

(3)对词汇表VOL中的每个单词w_i，根据公式(2)计算其逆文档词频idf(w_i)；

idf(w_i)＝log(N_d/num(w_i)).    (2)

(4)根据向量空间模型，将集合D中每个伴随文本d_j表示成N_w维向量，第i维对应词汇表中的单词w_i，其值为tfidf(w_i)，计算公式如下：

tfidf(w_i)＝freq(w_i，d_j)×idf(w_i).    (3)。

所述的计算词汇表中每个单词的可见度的方法是：词汇表VOL中每个单词w_i的可见度值vis(w_i)由公式(4)计算；

$\mathrm{vis}\left(w_i\right)={((C_1+{10}^{-9})/(C_2+{10}^{-9}))}^{-{\mathrm{IDF}}_{\mathrm{Google}}\left(w_i\right)}.---\left(4\right)$

其中，C₁是将单词w_i作为查询提交给Google图片搜索返回的检索结果总数，C₂是将单词w_i作为查询提交给Google文本搜索返回的检索结果总数；指数因子IDF_Google(w_i)的计算公式如下：

IDF_Google(w_i)＝log(|D_Google|/C₂).    (5)

其中，D_Google是Google索引的所有Web页面集合，|D_Google|表示集合D_Google中的页面总数。

所述的将单词的可见度与TF-IDF方法集成以计算单词和图像相关性关联的方法是：单词w_i与图像Image_j的相关性关联r(w_i，Image_i)由公式(6)计算，其中j＝1，…，N_d，N_d是伴随文本总数；

r(w_i，Image_j)＝tfidf(w_i)×vis(w_i).    (6)。

所述的根据主题模型对伴随文本集合进行分析，提取隐含主题概率分布以计算词汇表中任意两个单词间的主题相关度的步骤如下：

(1)以词汇表VOL、伴随文本集合D和集合D中的隐含主题数k作为主题模型隐含狄利克雷分配的输入，输出每个隐含主题z_j的概率分布P(z_j)和z_j在每个单词w_i上的概率分布P(w_i|z_j)，其中j＝1，…，k；

(2)集合VOL中任意两个单词w_s和w_t之间的主题相关度Topic_r(w_s，w_t)由公式(7)所定义的主题相关度函数计算，其中σ是归一化常数，

$\mathrm{Topic}\_r(w_s,w_t)=\underset{j}{\max }P(z=j|w_s)P(z=j|w_t)$

$=\underset{j}{\max }\frac{p\left(w_s\right|z=j)P(z=j)}{P\left(w_s\right)}·\frac{p\left(w_t\right|z=j)P(z=j)}{P\left(w_t\right)}---\left(7\right).$

$=\underset{j}{\max }\frac{p\left(w_s\right|z=j)p\left(w_t\right|z=j)P(z=j)}{\sigma }.$

所述的利用复杂图模型对单词和图像相关性关联以及单词和单词主题相关性关联进行建模的方法是：复杂图模型包含图像结点和单词结点两种不同类型结点，单词和图像间的异构链接以及单词和单词间的同构链接作为结点间的边，单词和图像链接权重由公式(6)所定义的单词和图像相关性关联r(w_i，Image_i)计算，单词和单词链接权重为公式(7)定义的单词和单词主题相关度函数Topic_r(w_s，w_t)计算，复杂图模型表示为如公式(8)所示的矩阵集合；

{$S\in R_{+}^{N_w\times N_w},$$A\in R_{+}^{N_d\times N_d}$}.(8)

其中，对称矩阵$S\in R_{+}^{N_w\times N_w}$表示单词和单词相关性矩阵，N_w是词汇表中单词总数，R₊是正实数集合，矩阵元素S_ij(i≠j)表示单词w_i和w_j之间的主题相关度，S_ij＝Topic_r(w_i，w_j)矩阵$A\in R_{+}^{N_w\times N_d}$表示单词和图像相关性矩阵，N_d是图像总数，矩阵元素A_ij表示单词w_i和第j个图像Image_j之间的相关性关联，A_ij＝tfidf(w_i)·vis(w_i)。

所述的应用复杂图聚类算法对图像进行聚类的方法可表示为如公式(9)所定义的优化问题；

$\left(\begin{array}{c}\underset{C^{\left(1\right)},C^{\left(2\right)},D,B}{\min }{\left|\right|S-C^{\left(1\right)}D{\left(C^{\left(1\right)}\right)}^T\left|\right|}^2+{\left|\right|A-C^{\left(1\right)}B{\left(C^{\left(2\right)}\right)}^T\left|\right|}^2\\ s.t.C^{\left(1\right)}\in {\left\{\mathrm{0,1}\right\}}^{N_w\times k_1},C^{\left(2\right)}\in {\left\{\mathrm{0,1}\right\}}^{N_d\times k_2},C^{\left(1\right)}1=1,C^{\left(2\right)}1=1\end{array}\right).---\left(9\right)$

其中，向量1的每个分量都为1，k₁和k₂分别表示单词和图像的聚类个数，类属指示矩阵C⁽¹⁾和C⁽²⁾是复杂图聚类算法的输出，矩阵元素C_pq⁽²⁾表示第p个图像Image_p属于第q类，对公式(9)所定义的优化问题进行求解的复杂图聚类算法如算法1所示：

算法1.复杂图G₁的聚类算法CGC.

输入：矩阵S和A；

输出：类属指示矩阵C⁽¹⁾和C⁽²⁾，k₁和k₂分别是单词和图像的聚类个数；

步骤1.重复迭代步骤2-5直到收敛；

步骤2.计算D＝((C⁽¹⁾)^TC⁽¹⁾)^-1(C⁽¹⁾)^TSC⁽¹⁾(C⁽¹⁾)^TC⁽¹⁾)^-1；

步骤3.计算B＝((C⁽¹⁾)^TC⁽¹⁾)^-1(C⁽¹⁾)^TAC⁽²⁾(C⁽²⁾)^TC⁽²⁾)^-1；

步骤4.固定D，B和C⁽²⁾，逐行更新C⁽¹⁾，使得最小化L，L计算如下：

L＝||S-C⁽¹⁾D(C⁽¹⁾)^T||²+||A-C⁽¹⁾B(C⁽²⁾)^T||²；

步骤5.固定D，B和C⁽¹⁾，逐行更新C⁽²⁾，使得最小化L，L计算如下：

L＝||S-C⁽¹⁾D(C⁽¹⁾)^T||²+||A-C⁽¹⁾B(C⁽²⁾)^T||².

根据算法1输出的类属指示矩阵C⁽²⁾对图像集合IMG进行聚类的方法是，如果矩阵元素$C_{\mathrm{pq}}^{\left(2\right)}=1$则把第p个图像Image_p归为第q类，其中p＝1，…，N_d，N_d表示集合IMG中图像总数，q＝1，…，k₂，k₂表示IMG中图像的聚类个数。

实施例

选择了5个视觉多义词作为查询，它们是：“apple”，“bass”，“jaguar”，“mouse”和“tower”。编写了爬虫程序，根据提交的关键字作为查询自动提取Goolge ImageSearch^TM的返回结果。对返回结果中的每个图像，下载了图像文件以及该图像所在的Web页面。由于Google限制了搜索实际返回的结果数量，数据集共包含约4000个数据项。为了提取图像的伴随文本，对图像所在的Web页面进行解析，提取图像周围的单词的文本作为该图像的伴随文本。所有的伴随文本通过词性标注，提取其中的名词。对于每个查询其伴随文本的名词词汇表规模为1000～2000个单词。为了获得基准类属列表向量，我们手工对数据集中的图像类别进行了标注。

本发明关键步骤的工作流程图如图1所示，以用户提交查询“bass”为例，具体实施步骤为：

1.编写爬虫程序下载Google图片搜索的检索结果中的所有图像以及图像所在网页，通过页面解析器对每个HTML页面进行解析，去除HTML标记和标点符号，得到如图1(a)所示的图像集合IMG＝{Image₁，...，Image_Nd}和伴随文本集合D＝{d₁，...，d_Nd}，N_d是伴随文本总数，同时也是图像总数；

2.利用词性标注程序对每个伴随文本d_i进行词性标注，其中i＝1，…，N_d，去除文本中的非名词单词，保留文本中的名词；

3.顺序扫描伴随文本集合D中的每个伴随文本d_i中的所有单词，每个不同单词保留一个，形成单词列表表示的词汇表VOL＝{w_i，…，w_Nw}，其中N_w是词汇表VOL中的单词总数，对词汇表VOL中的每个单词w_i统计每个单词w_i在每个文档d_j中出现的次数n_ij，以及集合D中包含单词w_i的伴随文本个数num(w_i)；

4.对每个伴随文本d_j(j＝1，…，N_d)提取其文本特征，具体步骤为：

(1)对词汇表VOL中每个单词w_i，其中i＝1，…，N_w，N_w是词汇表中单词总数，计算w_i在伴随文本d_j中的词频$\mathrm{freq}(w_i,d_j)=n_{\mathrm{ij}}/{\Sigma }_{k=1}^{N_w}{n}_{\mathrm{kj}};$

(2)对词汇表VOL中每个单词w_i，计算w_i的逆文档词频idf(w_i)＝log(N_d/num(w_i))；

(3)根据向量空间模型，将文档d_j表示成N_w维向量：$d_j=(\mathrm{tfidf}\left(w_1\right),...,\mathrm{tfidf}\left(w_{N_w}\right)),$第i维对应词汇表中的单词w_i，其值为tfidf(w_i)＝freq(w_i，d_j)×idf(w_i)；

5.对词汇表VOL中每个单词w_i计算其可见度$\mathrm{vis}\left(w_i\right)={((C_1+{10}^{-9})/(C_2+{10}^{-9}))}^{-{\mathrm{IDF}}_{\mathrm{Google}}\left(w_i\right)},$其中，C₁是将单词w_i作为查询提交给Google图片搜索返回的检索结果总数，C₂是将单词w_i作为查询提交给Google文本搜索返回的检索结果总数；指数因子IDF_Google(w_i)的计算公式如下：

IDF_Google(w_i)＝log(|D_Google|/C₂)

其中，D_Google是Google索引的所有Web页面集合，|D_Google|表示集合D_Google中的页面总数，本实施例中|D^Google|＝5×10¹¹。

单词的可见度体现了单词，尤其是名词，所蕴含语义可用图像来描述的程度。从认知心理学和形象思维的角度，高可见度的单词，如“banana”，要比低可见度的单词，如“Bayesian”，更易在人脑中形成直接视觉形象。可将可见度作为单词一种新的属性，用来表达单词与图像之间的语义关联。在Web页面中，图像周围每个单词具有不同程度的可见度，高可见度单词对图像的语义有更强的描述能力。以C₁/C₂值作为量化指标可以从一定程度上衡量不同单词的可见度，例如单词“banana”的C₁/C₂值大于“Bayesian”。以图2为例，该图像是该图像是用关键字“bass”作为查询，由Google图像搜索引擎返回的前5个结果中的一个。伴随文本中名词C₁和C₂值于2009年5月从Google上检索得到，如表1所示。如图3所示，“legend”、“record”、“scale”等词的C₁/C₂的值大于“largemouth”和“fishermen”。但是，根据可见度定义，由于“largemouth”和“fishermen”是这幅图像中两个主要对象，它们应有更高可见度。造成这种结果的原因是，“record”等主题较宽泛单词大量地出现在Web页面上，同时也大量地出现在图像的伴随文本中，从而提高了它们的C₁/C₂值。主题宽泛单词的C₂值往往很大，因此本发明所提出的可见度模型利用“逆文档词频因子”IDF_Google(w_i)＝log(|D_Google|/C₂)来对其可见度进行抑制，|D_Google|是Google索引的所有Web页面总数。图3中名词的vis(w)值如图3所示，“largemouth”和“fishermen”的vis(w)值最大，可见本发明所提可见度模型的合理性。

表1

6.计算VOL中每个单词w_i与图像Image_j的相关性关联r(w_i，Image_j)＝tfidf(w_i)×vis(w_i)；构造单词和图像相关性矩阵$A\in R_{+}^{N_w\times N_d},$矩阵元素A_ij表示单词w_i和第j个图像Image_j之间的相关度，A_ij＝r(w_i，Image_j).

7.对词汇表VOL中任意两个单词w_s和w_t计算其主题相关度，并构造单词和单词相关性矩阵，具体步骤如下：

(1)以词汇表VOL、伴随文本集合D和隐含主题数k作为主题模型隐含狄利克雷分配的输入，输出每个隐含主题z_j(j＝1，…，k)的概率分布P(z_j)和z_j在每个单词w_i上的概率分布P(w_i|z_j)；

(2)任意两个单词w_s和w_t之间的主题相关度Topic_r(w_s，w_t)计算如下，σ是归一化常数。

$\mathrm{Topic}\_r(w_s,w_t)=\underset{j}{\max }P(z=j|w_s)P(z=j|w_t)$

$=\underset{j}{\max }\frac{p\left(w_s\right|z=j)P(z=j)}{P\left(w_s\right)}·\frac{p\left(w_t\right|z=j)P(z=j)}{P\left(w_t\right)}$

$=\underset{j}{\max }\frac{p\left(w_s\right|z=j)p\left(w_t\right|z=j)P(z=j)}{\sigma }.$

(3)构造单词和单词相关性矩阵为对称矩阵$S\in R_{+}^{N_w\times N_w},$矩阵元素S_ij(i≠j)表示单词w_i和w_j之间的主题相关度，S_ij＝Topic_r(w_i，w_j)。

8.经过以上步骤得到如图1(b)所示的复杂图模型，该复杂图模型可表示为矩阵集合{$S\in R_{+}^{N_w\times N_w},$$A\in R_{+}^{N_d\times N_d}$}.应用复杂图聚类算法可对图像集合IMG进行聚类，复杂图聚类算法表示为如下优化问题；

$\left(\begin{array}{c}\underset{C^{\left(1\right)},C^{\left(2\right)},D,B}{\min }{\left|\right|S-C^{\left(1\right)}D{\left(C^{\left(1\right)}\right)}^T\left|\right|}^2+{\left|\right|A-C^{\left(1\right)}B{\left(C^{\left(2\right)}\right)}^T\left|\right|}^2\\ s.t.C^{\left(1\right)}\in {\left\{\mathrm{0,1}\right\}}^{N_w\times k_1},C^{\left(2\right)}\in {\left\{\mathrm{0,1}\right\}}^{N_d\times k_2},C^{\left(1\right)}1=1,C^{\left(2\right)}1=1\end{array}\right).$

其中，向量1的每个分量都为1，k₁和k₂分别表示单词和图像的聚类个数，类属指示矩阵C⁽¹⁾和C⁽²⁾是复杂图聚类算法的输出，矩阵元素C_pq⁽²⁾表示第p个图像Image_p属于第q类，复杂图聚类算法的具体步骤如算法1所示：

算法1.复杂图G₁的聚类算法CGC.

输入：矩阵S和A；

输出：类属指示矩阵C⁽¹⁾和C⁽²⁾，k₁和k₂分别是单词和图像的聚类个数；

步骤1.重复迭代步骤2-5直到收敛；

步骤2.计算D＝((C⁽¹⁾)^TC⁽¹⁾)^-1(C⁽¹⁾)^TSC⁽¹⁾(C⁽¹⁾)^TC⁽¹⁾)^-1；

步骤3.计算B＝((C⁽¹⁾)^TC⁽¹⁾)^-1(C⁽¹⁾)^TAC⁽²⁾(C⁽²⁾)^TC⁽²⁾)^-1；

步骤4.固定D，B和C⁽²⁾，逐行更新C⁽¹⁾，使得最小化L，L计算如下：

L＝||S-C⁽¹⁾D(C⁽¹⁾)^T||²+||A-C⁽¹⁾B(C⁽²⁾)^T||²；

步骤5.固定D，B和C⁽¹⁾，逐行更新C⁽²⁾，使得最小化L，L计算如下：

L＝||S-C⁽¹⁾D(C⁽¹⁾)^T||²+||A-C⁽¹⁾B(C⁽²⁾)^T||².

根据算法1输出的类属指示矩阵C⁽²⁾对图像集合IMG进行聚类的方法是，如果矩阵元素$C_{\mathrm{pq}}^{\left(2\right)}=1$则把第p个图像Image_p归为第q类，其中p＝1，…，N_d，N_d表示集合IMG中图像总数，q＝1，…，k₂，k₂表示IMG中图像的聚类个数。

如图1所示，经过步骤(2)得到聚类结果，该示例中图像被归为3个主题类，分别是“bass fishing”、“bass fish”和“bass guitar”。

为了表明本发明核心内容的有效性和聚类框架的整体性能，我们进行以下聚类结果对比：

(1)区分r(w_i，Image_j)＝tfidf(w_i)和r(w_i，Image_j)＝tfidf(w_i)×vis(w_i)两种情况进行聚类；

(2)将单词间的主题相关性关联Topic_r(w_s，w_t)和单词共生相关性关联P(w_s，w_t)对比，图像的伴随文本中，任意两个单词w_s和w_t的共生相关性定义为它们同时出现在某个图像的伴随文本中的概率P(w_s，w_t)＝num(w_s，w_t)/N_d，num(w_s，w_t)是其伴随文本中同时包含单词w_s和w_t的图像的个数。结合主题相关性和共生相关性关联，单词和单词同构链接权重定义为：λ·p(w_s，w_t)+(1-λ)Topic_r(w_s，w_t)，其中λ(0＜λ＜1)是可调参数。

聚类性能评价标准采用归一化的聚类互信息，即Normalized MutualInformation。归一化的聚类互信息的定义为：给定聚类个数k，类属列表向量λ＝(λ₁，...，λ_K)中λ_i的取值范围为λ_i＝1，...k，λ_i＝j表示第i个数据项属于第C_j类。用λ^(a)和λ^(b)分别表示结果的和基准类属列表向量，则λ^(a)和λ^(b)的归一化聚类互信息φ^(NMI)定义为：

${\phi }^{\left(\mathrm{NMI}\right)}({\lambda }^{\left(a\right)},{\lambda }^{\left(b\right)})=\frac{{\Sigma }_{h-1}^k{\Sigma }_{l-1}^k{n}_{\mathrm{hl}}\log \left(\frac{n·n_{\mathrm{hl}}}{n_h^{\left(a\right)}{n}_l^{\left(b\right)}}\right)}{\sqrt{\left({\Sigma }_{h-1}^k{n}_h^{\left(a\right)}\log \frac{n_h^{\left(a\right)}}{n}\right)\left({\Sigma }_{l-1}^k{n}_l^{\left(b\right)}\log \frac{n_l^{\left(b\right)}}{n}\right)}}.$

其中，n_h^(a)是对应于λ^(a)的类C_h中的数据项个数，n_l^(b)是对应于λ^(b)的类C_l中的数据项个数。C_hl表示同时被聚在λ^(a)的类C_h中和λ^(b)的类C_l中的数据项的个数。某次聚类结果的λ^(a)和基准类属λ^(b)之间的互信息值φ^(NMI)(λ^(a)，λ^(b))越大，表示本次聚类效果越好。理想的聚类是φ^(NMI)(λ^(a)，λ^(b))＝1.

对于参数λ，考虑三种情况：

1)λ＝1；

2)λ＝0；

3)λ＝0.15；

如图4所示：对于所有5个查询复杂图聚类的NMI值都在λ＝0时达到最好，因此可表明本发明所提出的单词和单词主题相关度的合理性。

如图4所示：“λ＝0(vis(w))”表示单词和图像链接权重采用A_ij＝tfidf(w_i)×vis(w_i)。由聚类互信息结果可以看到，在复杂图聚类中，将单词的可见度引入单词和图像链接权重使得高可见度单词向与之关联的图像结点传递更多的主题相关性信息，提高了聚类性能。

以图5所示对查询“jaguar”检索图像聚类结果为例，对比(a)、(b)图可以看得在引入可见度增强某些描述图像特定对象的单词与图像链接权重情况下，聚类性能得到改善。

如图6所示是采用本发明基于图像和文本相关性挖掘的Web图像聚类方法对查询mouse提交给Google图片搜索所返回结果进行聚类所得三个主题中的前10个图像，第一列是主题“computer mouse”，第二列是主题“mouse animal”，第三列是主题“Mickey mouse”；红色虚线边框的图像是错误的聚类项。