一种基于概念分解的半监督文档分类方法及系统

摘要

本发明公开了一种基于概念分解的半监督文档分类方法，包括：对原始数据矩阵作分解，将数据转换到低维空间，得到既有邻域保持、相似性保持以及约束保持的原始数据在低维空间的近似矩阵；利用算法接收参数K对原始数据的低维近似矩阵进行聚类，得到聚类结果；利用精确度和互信息两种评价标准对所述聚类结果进行评价。本发明基于概念分解，不仅考虑了原始数据的邻域保持特性，同时还考虑了数据点相似在原始空间和低维流形空间的一致性，以及约束对在原始空间和转换空间的约束保持，使得聚类性能不仅在先验信息较多的时候大大提高，在先验信息很少的时候依然能保持较好的聚类性能。本发明还公开了一种基于概念分解的半监督文档分类系统。

说明书

技术领域

本发明涉及文档分类技术领域，尤其涉及一种基于概念分解的半监督文 档分类方法及系统。

背景技术

近年来矩阵分解技术在模式识别和机器学习中受到越来越广泛的关注。 在许多诸如计算机视觉和模式识别的问题中，数据的维数都很高，处理这类 数据需要更多的时间和空间。更重要的是，高维数据使得原本在低维空间简 单可行的分类、聚类、检索等学习任务也变得困难重重。因此，对高维数据 矩阵进行分解，得到分解后的高维数据的低维表达成为近期的研究热点。非 负矩阵分解(nonnegativematrixfactorization,，NMF)在处理像人脸和文档等 非负数据时有特别的优势。但是非负矩阵分解的一个不足之处是很难在投影 空间如再生核希尔伯特空间有效的执行NMF。

概念分解(conceptfactorization，CF)克服了NMF算法的上述不足同时继 承了NMF方法的优点。概念分解是对矩阵分解，找到两个因子矩阵 和使得WV的乘积尽可能的和原来的矩阵近似，其中V可以 看作是原来矩阵X的低维表示。聚类的结果可以通过低维表达V导出。局部一 致性原理指出，在原空间相邻的两个顶点在转换空间应该也是相邻的，局部 一致性原理在模式识、数据挖掘中有着非常重要的作用。局部一致性概念分 解(LocallyConsistentConceptFactorization，LCCF)把局部一致性原理应用 到CF中，通过在CF框架中嵌入拉普拉斯图作为额外的正则化项，提升算法的 聚类性能。

计算机视觉、模式识别、数据挖掘的实践中，有些数据是有标记的。上 述算法都是无监督学习方法，不能有效的利用已有的带标记数据指导聚类， 所以在聚类性能上会大打折扣。成对约束概念分解(pairwiseconstrained conceptfactorization，PCCF)通过把同类的数据映射到转换空间保持相同的类 别标记，不同类的数据在转换空间中的类别标记依然不同的思想应用到CF中 对原始数据聚类。该方法存在的不足是当已知的标记数据很少时，方法退化 为CF，不能有效的利用原始数据的内部结构，也不同充分的利用同类数据的 相似性，故而聚类性能得不到有效的提升。

发明内容

本发明提供了一种基于概念分解的半监督文档分类方法，该方法基于概 念分解，不仅考虑了原始数据的邻域保持特性，同时还考虑了数据点相似在 原始空间和低维流形空间的一致性，以及约束对在原始空间和转换空间的约 束保持，使得聚类性能不仅在先验信息较多的时候大大提高，在先验信息很 少的时候依然能保持较好的聚类性能。

本发明提供了一种基于概念分解的半监督文档分类方法，包括：

对原始数据矩阵作分解，将数据转换到低维空间，得到既有邻域保持、 相似性保持以及约束保持的原始数据在低维空间的近似矩阵；

利用算法接收参数K对所述原始数据的低维近似矩阵进行聚类，得到聚 类结果；

利用精确度和互信息两种评价标准对所述聚类结果进行评价。

优选地，所述对原始数据矩阵作分解，将数据转换到低维空间，得到既 有邻域保持、相似性保持以及约束保持的原始数据在低维空间的近似矩阵具 体为：

令所有数据组成的集合为其中x_i∈R^m，n是图像的总个数，m是图 像样本的维数，并假设图像数据中有N_M个must-link约束对和N_C个 cannot-link约束对；

构造由所有顶点构成的p-邻域图，顶点由所有数据点组成，其中，边上 的权重定义为：

构造由同类顶点构成的相似图，其中顶点由所有数据点组成，其中，边 上的权重定义为：

$S_{ij}=\left(\begin{array}{cc}\frac{x_i^T{x}_j}{\left|\right|x_i\left|\right|\left|\right|x_j\left|\right|}& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0,& otherwise\end{array}\right);$

依据must-link约束对，构成矩阵M：

$m_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0& otherwise\end{array}\right);$

依据cannot-link约束对，构成矩阵C：

$c_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{CL}\end{array}\\ 0& otherwise\end{array}\right);$

利用公式$\left(\begin{array}{c}\min \left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{c}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{c}_{jc}{c}_{ij}\\ s.t.U\ge 0,V\ge 0\end{array}\right)$对非负矩阵分 解进行优化，得到投影以后的新空间的基W和原始数据在新空间的投影V， 其中，λ_W和λ_S均为参数；

定义$\begin{array}{c}F=\left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{v}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{v}_{jc}{c}_{ij}\end{array},$简化后得到：

F＝tr(K)-2tr(VW^TK)+tr(VW^TKWV^T)+tr(V^TLV)+tr(V^TMVA)，其中，

$A=\left(\begin{array}{cccc}0& 1& \mathrm{...}& 1\\ 1& 0& \mathrm{...}& 1\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ 1& 1& \mathrm{...}& 0\end{array}\right),L={\lambda }_H{L}_H+{\lambda }_S{L}_S+C,K=X^{T}X;$

利用拉格朗日最小二乘法，分别对W和V求偏导，得到U和V的迭代公式；

利用迭代公式求U和V直至收敛。

优选地，所述利用精确度和互信息两种评价标准对所述聚类结果进行评 价具体为：

对数据点d_i，令l_i和α_i分别代表数据的原始标记和非负矩阵分解算法得 到的标记，定义精确度：

其中，n是数据集的数据总数，函数map(l_i)把得到 的类别标记l_i映射为数据集中相应的标记α_i，δ(x,y)是delta函数，定义为：

定义互信息：

$MI\left(C,C^{\prime }\right)=\underset{c_i\in C,c_j^{\prime }\in C}{\Sigma }p\left(c_i,c_j^{\prime }\right)·{\log }_2\frac{p\left(c_i,c_j^{\prime }\right)}{p\left(c_i\right)p\left(c_j^{\prime }\right)},$其中，p(c_i)和p(c'_j)分别表示从数据 集中随机抽取的数据属于聚类c_i和c'_j的概率，p(c_i,c'_j)表示数据同时属于聚类c_i和c'_j的联合概率；

利用归一化互信息，定义其中，H(C)和H(C') 分别是C和C'的熵。

一种基于概念分解的半监督文档分类系统，包括：

转换模块，用于对原始数据矩阵作分解，将数据转换到低维空间，得到 既有邻域保持、相似性保持以及约束保持的原始数据在低维空间的近似矩阵；

聚类模块，用于利用算法接收参数K对所述原始数据的低维近似矩阵进 行聚类，得到聚类结果；

评价模块，用于利用精确度和互信息两种评价标准对所述聚类结果进行 评价。

优选地，所述转换模块对原始数据矩阵作分解，将数据转换到低维空间， 得到既有邻域保持、相似性保持以及约束保持的原始数据在低维空间的近似 矩阵具体为：

令所有数据组成的集合为其中x_i∈R^m，n是图像的总个数，m是图 像样本的维数，并假设图像数据中有N_M个must-link约束对和N_C个 cannot-link约束对；

构造由所有顶点构成的p-邻域图，顶点由所有数据点组成，其中，边上 的权重定义为：

构造由同类顶点构成的相似图，其中顶点由所有数据点组成，其中，边 上的权重定义为：

$S_{ij}=\left(\begin{array}{cc}\frac{x_i^T{x}_j}{\left|\right|x_i\left|\right|\left|\right|x_j\left|\right|}& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0,& otherwise\end{array}\right);$

依据must-link约束对，构成矩阵M：

$m_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0& otherwise\end{array}\right);$

依据cannot-link约束对，构成矩阵C：

$c_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{CL}\end{array}\\ 0& otherwise\end{array}\right);$

利用公式$\left(\begin{array}{c}\min \left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{c}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{c}_{jc}{c}_{ij}\\ s.t.U\ge 0,V\ge 0\end{array}\right)$对非负矩阵分 解进行优化，得到投影以后的新空间的基W和原始数据在新空间的投影V， 其中，λ_W和λ_S均为参数；

定义$\begin{array}{c}F=\left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{v}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{v}_{jc}{c}_{ij}\end{array},$简化后得到：

F＝tr(K)-2tr(VW^TK)+tr(VW^TKWV^T)+tr(V^TLV)+tr(V^TMVA)，其中，

$A=\left(\begin{array}{cccc}0& 1& \mathrm{...}& 1\\ 1& 0& \mathrm{...}& 1\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ 1& 1& \mathrm{...}& 0\end{array}\right),L={\lambda }_H{L}_H+{\lambda }_S{L}_S+C,K=X^{T}X;$

利用拉格朗日最小二乘法，分别对W和V求偏导，得到U和V的迭代公式；

利用迭代公式求U和V直至收敛。

优选地，所述评价模块利用精确度和互信息两种评价标准对所述聚类结 果进行评价具体为：

对数据点d_i，令l_i和α_i分别代表数据的原始标记和非负矩阵分解算法得 到的标记，定义精确度：

其中，n是数据集的数据总数，函数map(l_i)把得到 的类别标记l_i映射为数据集中相应的标记α_i，δ(x,y)是delta函数，定义为：

定义互信息：

$MI\left(C,C^{\prime }\right)=\underset{c_i\in C,c_j^{\prime }\in C}{\Sigma }p\left(c_i,c_j^{\prime }\right)·{\log }_2\frac{p\left(c_i,c_j^{\prime }\right)}{p\left(c_i\right)p\left(c_j^{\prime }\right)},$其中，p(c_i)和p(c'_j)分别表示从数据 集中随机抽取的数据属于聚类c_i和c'_j的概率，p(c_i,c'_j)表示数据同时属于聚类c_i和c'_j的联合概率；

利用归一化互信息，其中，H(C)和H(C') 分别是C和C'的熵。

由上述方案可知，本发明提供的一种基于概念分解的半监督文档分类方 法，首先通过对原始数据矩阵作分解，将数据转换到低维空间，得到既有邻 域保持、相似性保持以及约束保持的原始数据在低维空间的近似矩阵，然后 利用算法接收参数K对低维近似矩阵进行聚类，得到聚类结果，最后利用精 确度和互信息两种评价标准对所述聚类结果进行评价，本发明基于概念分解， 不仅考虑了原始数据的邻域保持特性，同时还考虑了数据点相似在原始空间 和低维流形空间的一致性，以及约束对在原始空间和转换空间的约束保持， 使得聚类性能不仅在先验信息较多的时候大大提高，在先验信息很少的时候 依然能保持较好的聚类性能。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实 施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面 描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲， 在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明公开的一种基于概念分解的半监督文档分类方法的流程图；

图2为本发明公开的一种基于概念分解的半监督文档分类系统的结构示 意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行 清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而 不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做 出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

如图1所示，本发明公开的一种基于概念分解的半监督文档分类方法， 包括：

S101、对原始数据矩阵作分解，将数据转换到低维空间，得到既有邻域 保持、相似性保持以及约束保持的原始数据在低维空间的近似矩阵；

S102、利用算法接收参数K对所述原始数据的低维近似矩阵进行聚类， 得到聚类结果；

其次，用得到的原始数据在低维空间的近似矩阵V，利用kmeans进行聚 类。

S103、利用精确度和互信息两种评价标准对所述聚类结果进行评价。

最后，利用两种评价标准精确度(accuracy，AC)和互信息(mutual information，MI)对所得的聚类结果进行评价。

综上所述，本发明提供的一种基于非负矩阵分解的半监督聚类方法，首 先通过对原始数据矩阵作分解，将数据转换到低维空间，得到既有邻域保持、 相似性保持以及约束保持的原始数据在低维空间的近似矩阵，然后利用算法 接收参数K对低维近似矩阵进行聚类，得到聚类结果，最后利用精确度和互 信息两种评价标准对所述聚类结果进行评价，本发明基于概念分解，不仅考 虑了原始数据的邻域保持特性，同时还考虑了数据点相似在原始空间和低维 流形空间的一致性，以及约束对在原始空间和转换空间的约束保持，使得聚 类性能不仅在先验信息较多的时候大大提高，在先验信息很少的时候依然能 保持较好的聚类性能。

具体的，上述实施例中，步骤101对原始数据矩阵作分解，将数据转换 到低维空间，得到既有邻域保持、相似性保持以及约束保持的原始数据在低 维空间的近似矩阵具体为：

令所有数据组成的集合为其中x_i∈R^m，n是图像的总个数，m是图 像样本的维数，并假设图像数据中有N_M个must-link约束对和N_C个 cannot-link约束对；

构造由所有顶点构成的p-邻域图，顶点由所有数据点组成，其中，边上 的权重定义为：

构造由同类顶点构成的相似图，其中顶点由所有数据点组成，其中，边 上的权重定义为：

$S_{ij}=\left(\begin{array}{cc}\frac{x_i^T{x}_j}{\left|\right|x_i\left|\right|\left|\right|x_j\left|\right|}& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0,& otherwise\end{array}\right);$

依据must-link约束对，构成矩阵M：

$m_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0& otherwise\end{array}\right);$

依据cannot-link约束对，构成矩阵C：

$c_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{CL}\end{array}\\ 0& otherwise\end{array}\right);$

利用公式$\left(\begin{array}{c}\min \left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{c}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{c}_{jc}{c}_{ij}\\ s.t.U\ge 0,V\ge 0\end{array}\right)$对非负矩阵分 解进行优化，得到投影以后的新空间的基W和原始数据在新空间的投影V， 其中，λ_W和λ_S均为参数；

定义$\begin{array}{c}F=\left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{v}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{v}_{jc}{c}_{ij}\end{array},$简化后得到：

F＝tr(K)-2tr(VW^TK)+tr(VW^TKWV^T)+tr(V^TLV)+tr(V^TMVA)，其中，

$A=\left(\begin{array}{cccc}0& 1& \mathrm{...}& 1\\ 1& 0& \mathrm{...}& 1\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ 1& 1& \mathrm{...}& 0\end{array}\right),L={\lambda }_H{L}_H+{\lambda }_S{L}_S+C,K=X^{T}X;$

利用拉格朗日最小二乘法，分别对W和V求偏导，得到U和V的迭代公式；

利用迭代公式求U和V直至收敛。

具体的，上述实施例中，步骤103利用精确度和互信息两种评价标准对 所述聚类结果进行评价具体为：

对数据点d_i，令l_i和α_i分别代表数据的原始标记和非负矩阵分解算法得 到的标记，定义精确度：

其中，n是数据集的数据总数，函数map(l_i)把得到 的类别标记l_i映射为数据集中相应的标记α_i，δ(x,y)是delta函数，定义为：

定义互信息：

$MI\left(C,C^{\prime }\right)=\underset{c_i\in C,c_j^{\prime }\in C}{\Sigma }p\left(c_i,c_j^{\prime }\right)·{\log }_2\frac{p\left(c_i,c_j^{\prime }\right)}{p\left(c_i\right)p\left(c_j^{\prime }\right)},$其中，p(c_i)和p(c'_j)分别表示从数据 集中随机抽取的数据属于聚类c_i和c'_j的概率，p(c_i,c'_j)表示数据同时属于聚类c_i和c'_j的联合概率；

利用归一化互信息，定义其中，H(C)和H(C') 分别是C和C'的熵。

为了更好的说明本发明的有益效果，对本发明在PIE数据集中进行了测 试，求出PIE数据集表示的高维矩阵的的低维表达，并通过对数据的低维表 达实施聚类检测低维表达的性能。该实验使用的PIE人脸数据库包含68个大 小为32×32的灰度人脸图像，每个人在42种光照条件下的照片。从数据集中 随机选择N_M个must-link约束对，和N_C个cannot-link约束对。

从图像中随机抽取15个簇，再从这些数据中随机抽取t×n×(n-1)个约束 对。在这里，n＝364，第一个实验选择t＝0.01，共有474个must-link约束对 和847个cannot-link约束对。第二个实验选择t＝0.2，共有9965个must-link 约束对和16391个cannot-link约束对

表1为本发明第一个实验与CF，LCCF以及semiCF算法在相同的数据集 上做比较的结果。

表1CF，LCCF，semiCF和本发明方法的聚类性能对比(t＝0.01)

0.01 CF LCCF semiCF 本发明 AC 0.74304 0.79067 0.80367 0.84811 NMI 0.78284 0.82666 0.85932 0.88229

表2为本发明第二个实验与CF，LCCF以及semiCF算法在相同的数据集 上做比较的结果。

表2CF，LCCF，semiCF和本发明方法的聚类性能对比(t＝0.2)

0.2 CF LCCF semiCF 本发明 AC 0.74304 0.79067 0.87184 0.89297 NMI 0.78284 0.82666 0.90084 0.92974

通过实验结果可以看出本发明对于先验知识有较强的鲁棒性，不管约束对 是多还是少，本发明的效果明显优于其他方法。

如图2所示，为本发明公开的一种基于概念分解的半监督文档分类系统， 包括：

转换模块201，用于对原始数据矩阵作分解，将数据转换到低维空间，得 到既有邻域保持、相似性保持以及约束保持的原始数据在低维空间的近似矩 阵；

聚类模块202，用于利用算法接收参数K对所述原始数据的低维近似矩 阵进行聚类，得到聚类结果；

通过聚类模块202用投影模块201得到的原始数据在低维空间的近似矩 阵V，利用kmeans进行聚类。

评价模块203，用于利用精确度和互信息两种评价标准对所述聚类结果进 行评价。

通过评价模块203利用两种评价标准精确度(accuracy，AC)和互信息 (mutualinformation，MI)对所得的聚类结果进行评价。

综上所述，本发明提供的一种基于非负矩阵分解的半监督聚类系统，首先 通过转换模块对原始数据矩阵作分解，将数据转换到低维空间，得到既有邻 域保持、相似性保持以及约束保持的原始数据在低维空间的近似矩阵，然后 通过聚类模块利用算法接收参数K对低维近似矩阵进行聚类，得到聚类结果， 最后评价模块利用精确度和互信息两种评价标准对所述聚类结果进行评价， 本发明基于概念分解，不仅考虑了原始数据的邻域保持特性，同时还考虑了 数据点相似在原始空间和低维流形空间的一致性，以及约束对在原始空间和 转换空间的约束保持，使得聚类性能不仅在先验信息较多的时候大大提高， 在先验信息很少的时候依然能保持较好的聚类性能。

具体的，上述实施例中，转换模块201对原始数据矩阵作分解，将数据 转换到低维空间，得到既有邻域保持、相似性保持以及约束保持的原始数据 在低维空间的近似矩阵具体为：

令所有数据组成的集合为其中x_i∈R^m，n是图像的总个数，m是图 像样本的维数，并假设图像数据中有N_M个must-link约束对和N_C个 cannot-link约束对；

构造由所有顶点构成的p-邻域图，顶点由所有数据点组成，其中，边上 的权重定义为：

构造由同类顶点构成的相似图，其中顶点由所有数据点组成，其中，边 上的权重定义为：

$S_{ij}=\left(\begin{array}{cc}\frac{x_i^T{x}_j}{\left|\right|x_i\left|\right|\left|\right|x_j\left|\right|}& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0,& otherwise\end{array}\right);$

依据must-link约束对，构成矩阵M：

$m_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{ML}\end{array}\\ 0& otherwise\end{array}\right);$

依据cannot-link约束对，构成矩阵C：

$c_{ij}=\left(\begin{array}{cc}1& \begin{array}{cc}if& (x_i,x_j)\in C_{CL}\end{array}\\ 0& otherwise\end{array}\right);$

利用公式$\left(\begin{array}{c}\min \left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{c}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{c}_{jc}{c}_{ij}\\ s.t.U\ge 0,V\ge 0\end{array}\right)$对非负矩阵分 解进行优化，得到投影以后的新空间的基W和原始数据在新空间的投影V， 其中，λ_W和λ_S均为参数；

定义$\begin{array}{c}F=\left|\right|X-{\mathrm{XWV}}^T|{|}^2+\frac{{\lambda }_H}{2}\underset{i,j=1}{\overset{n}{\Sigma }}||v_i-v_j|{|}^2{H}_{ij}+\frac{{\lambda }_S}{2}\underset{i,j=1}{\overset{n}{\Sigma }}\left|\right|v_i-v_j|{|}^2{S}_{ij}\\ +\underset{c}{\Sigma }\underset{s.t.l_i\ne l_j}{\underset{x_i,x_j\in C_{ML}}{\Sigma }}{v}_{ic}{v}_{jc}{m}_{ij}+\underset{c}{\Sigma }\underset{s.t.l_i=l_j}{\underset{x_i,x_j\in C_{CL}}{\Sigma }}{v}_{ic}{v}_{jc}{c}_{ij}\end{array},$简化后得到：

F＝tr(K)-2tr(VW^TK)+tr(VW^TKWV^T)+tr(V^TLV)+tr(V^TMVA)，其中，

$A=\left(\begin{array}{cccc}0& 1& \mathrm{...}& 1\\ 1& 0& \mathrm{...}& 1\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ 1& 1& \mathrm{...}& 0\end{array}\right),L={\lambda }_H{L}_H+{\lambda }_S{L}_S+C,K=X^{T}X;$

利用拉格朗日最小二乘法，分别对W和V求偏导，得到U和V的迭代公式；

利用迭代公式求U和V直至收敛。

具体的，上述实施例中，评价模块203利用精确度和互信息两种评价标 准对所述聚类结果进行评价具体为：

对数据点d_i，令l_i和α_i分别代表数据的原始标记和非负矩阵分解算法得 到的标记，定义精确度：

其中，n是数据集的数据总数，函数map(l_i)把得到 的类别标记l_i映射为数据集中相应的标记α_i，δ(x,y)是delta函数，定义为：

定义互信息：

$MI\left(C,C^{\prime }\right)=\underset{c_i\in C,c_j^{\prime }\in C}{\Sigma }p\left(c_i,c_j^{\prime }\right)·{\log }_2\frac{p\left(c_i,c_j^{\prime }\right)}{p\left(c_i\right)p\left(c_j^{\prime }\right)},$其中，p(c_i)和p(c'_j)分别表示从数据 集中随机抽取的数据属于聚类c_i和c'_j的概率，p(c_i,c'_j)表示数据同时属于聚类c_i和c'_j的联合概率；

利用归一化互信息，定义其中，H(C)和H(C') 分别是C和C'的熵。

本实施例方法所述的功能如果以软件功能单元的形式实现并作为独立的 产品销售或使用时，可以存储在一个计算设备可读取存储介质中。基于这样 的理解，本发明实施例对现有技术做出贡献的部分或者该技术方案的部分可 以以软件产品的形式体现出来，该软件产品存储在一个存储介质中，包括若 干指令用以使得一台计算设备(可以是个人计算机，服务器，移动计算设备 或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前 述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-OnlyMemory)、 随机存取存储器(RAM，RandomAccessMemory)、磁碟或者光盘等各种可 以存储程序代码的介质。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都 是与其它实施例的不同之处，各个实施例之间相同或相似部分互相参见即可。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用 本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易 见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下， 在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例， 而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。