基于离散哈希的聚类

轩书婷，刘惊雷

（烟台大学计算机与控制工程学院，山东烟台 264005）

0 引言

聚类是一种重要的数据分析技术，它将一个对象的集合分成不同的类从而描述数据。通过聚类，可以识别数据中稀疏和密集的区域，从而发现全局的模式以及数据之间的相互关系。它的目标是将具有相似结构或模式的数据项分类到同一个组中，降低数据的复杂性并促进解释。在计算机视觉［1-2］和数据挖掘领域［3-4］中，数据聚类是基础研究课题，而且聚类分析也应用到了各个领域，包括模式识别、数据分析、图像处理以及市场研究等。

聚类分析指将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程。聚类分析的目标就是在相似的基础上收集数据来分类。聚类源于很多领域，包括数学、计算机科学等。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。它可以作为其他算法的预处理步骤，利用聚类进行数据预处理，获得数据的基本情况，并在此基础上进行数据的抽取选择以提高精确度和挖掘的效率。

传统聚类方法是基于原始数据构造的正规图矩阵来构造拉普拉斯矩阵的，主要是在数据空间进行聚类。限制聚类性能的原因有两个：1）数据的多样性和复杂分布，由于成对策略，普通的图不能全面考虑数据的复杂相关性；2）原始数据通常具有冗余特征，这些冗余严重影响数据的分布。因此，由原始数据构造的拉普拉斯矩阵不能输出可靠的谱表示以及取得最佳的聚类性能。如今，随着数据量史无前例的快速增长，高维数据在许多应用中无处不在，例如图像处理。这对于像Facebook、Instagram 和谷歌这样的照片分享网站的流行来说尤为重要。考虑到网上有海量的照片，如何有效地组织它们是一个有待解决的问题。数据都是从不同的数据源收集出来的，对于这一部分可视化的数据，数据量大，并且数据的维度多，导致对数据进行聚类成为一个挑战性的问题。

Gong 等［5］开发了一种二进制聚类方法，该方法由生成二进制码和二进制进行聚类两个独立阶段组成，其主要缺点是二进制码采用与数据无关的方法获得，同时两步聚类破坏了二进制码与数据分割的关系。经典聚类算法K-means 算法是一种典型的基于距离的算法，它以距离作为评价相似度的指标。两个对象的距离越近，相似度越大。该算法需要不断地对对象进行分类调整，不断计算调整后新的聚类中心点，因此当数据量非常大时，算法的时间开销非常大。

哈希方法以其查询速度快、存储成本低等优势，特别是基于学习的哈希，由于其惊人的存储和搜索效率而受到了相当多的关注，已经成为解决各种大规模计算机视觉和机器学习问题的流行工具，包括目标检测、目标识别、聚类等。该方法的目标是将原始特征空间中的数据点投影后嵌入到汉明空间中，并在汉明空间中保持数据点之间的相似度。在汉明空间中，每个二进制码表示一个数据点。计算二进制码的汉明距离仅涉及的运算，使用短码进行散列，计算速度快，所以将高维特征向量编码为紧凑的二进制码可以节省计算的时间，从而实现快速聚类。图像聚类面临的最大挑战是速度和存储问题，哈希方法不仅可以有效提高图像聚类的效率，还可以在存储和计算性能方面获得显著的提高。

为了解决上述问题，提出了一种基于离散哈希的聚类（Clustering based on Discrete Hashing，CDH）。图1 显示了所提方法的主要框架，主要工作如下：

图1 所提方法的主要框架Fig.1 Main framework of proposed method

1）提出了一个基于离散哈希的聚类框架来解决图像聚类问题。该框架将哈希码学习和二元聚类放到一个联合优化目标中进行。与传统聚类方法相比，所提方法是在对数据进行二进制编码的同时，将转换后的二进制编码在汉明空间进行聚类（如式（10）所示）。

2）使用L21范数的自适应特征选择特性，对输入数据进行数据的自动特征选择，通过多次迭代选择原始数据中最有用的特征，从而完成数据的降维。即将原始数据空间的维度d维降到汉明空间的维度l(l≪d)。

3）在低维、稀疏的汉明空间对降维后的数据进行低秩矩阵分解和谱嵌入，从而完成二值汉明空间中稀疏数据的快速聚类。

4）在基准数据集上进行实验，与几种经典的聚类方法相比，在聚类精度、标准化互信息和纯度指标上进行分析，CDH 在聚类性能上有提高，实验结果证明了所提方法的优越性。

1 相关定义及方法

1.1 相关符号

在本节中，首先介绍使用到的一些基本符号，随后对所提方法所涉及的相关定义和概念进行简单的介绍。

矩阵用大写字母（例如C）表示，向量用小写字母（例如c）表示。c.j为C的第j列，ci.为C的第i行，ci.j为C的第i行第j列上的元素。具体基本符号表示如表1 所示。

表1 基本符号Tab.1 Basic symbols

1.2 聚类分析

聚类分析是研究数据间逻辑上或物理上相互关系的技术，它通过一定的规则将数据集划分为在性质上相似的数据点构成的若干个类。聚类的结果不仅可以揭示数据间的内在联系与区别，同时也为进一步的数据分析与知识的发现提供重要依据，如数据间的关联规则以及数据的变化趋势等。聚类分析常用于现实生活的不同领域或一些建设性目标［6］中。真实聚类的目标是揭示数据中固有的真实分组，例如系统发育分析和其他生命科学聚类应用程序在数据中寻找真正的分组，因此具有现实的目标。相比之下，无论是否存在固有的聚类结构，当聚类应该发生时，结构聚类都是相关的。然而，聚类的目标是建设性的，例如，虽然聚类分析在市场细分中的应用可能主要是建设性的，但是当数据中存在真实的群体时，用户可能对这些群体感兴趣。

聚类分析固有的模糊性使有效性要求变得复杂。算法对于给定的应用程序是否有效取决于该应用程序的需求［6］。对于高维的数据集，需要将数据的维度降低再进行聚类，这样可以更好地提高聚类的效率。故将高维的数据空间聚类转换到低维的汉明空间，在降维后的空间使用K-means 和谱聚类结合的聚类方式，使聚类效果更佳。

1.2.1 K-means聚类

K-means 算法的主要内容是给定一组含有n个数据点的Y=｛y1，y2，…，yn｝在Rd中，并且给定一个整数k。它要解决的问题是随机选取k个聚类质心点在Rd中，以便使下面的错误函数最小化

K-means 算法有3 个步骤［7-8］：第1 步是为待聚类的点寻找聚类中心；第2 步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中心；第3 步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心。反复执行第2、3 步，直到聚类中心不再进行大范围的移动或者聚类次数达到要求，整个聚类过程则结束。

｛b1，b2，…，bn｝是B的列向量，｛µ1，µ2，…，µk｝为k个质心，当第i个数据点分配给第j个簇(1≤j≤k)时，gi=j。对二进制矩阵B进行K-means 聚类的目标为：

1.2.2 谱聚类

谱聚类作为一种广泛应用的基于图的聚类方法，有着最先进的聚类性能。谱聚类算法的目标是利用捕捉数据非线性结构的相似矩阵来寻找聚类隶属度。谱聚类包括一个两阶段的过程，通过这个过程建立一个相似图，然后利用几个标准对图进行划分。

传统的光谱聚类表示为：

其中矩阵S的每一项表示数据对（i，j）之间的相似性。对于传统的光谱聚类，由于忽略了先验信息，聚类性能在很大程度上取决于所构建的亲和图的质量。

谱聚类的优点有：1）直接通过求解拉普拉斯矩阵的特征向量进行划分，不含有凸球形数据分布的隐性假设，从而能够识别非凸类型的簇；2）谱聚类仅与数据点的数目有关，与维数无关，因此可以避免高维特征向量造成的奇异性问题；3）能在任意形状的样本空间上聚类，且收敛于全局最优。

谱聚类的缺点有：1）谱聚类将原始数据空间映射到低维的线性测度空间，然后再线性测度空间中进行聚类，经常选用传统的K-means 算法进行聚类，从而导致算法具有初始值敏感的问题，将会影响聚类结果；2）谱聚类需要计算矩阵的特征值与特征向量，通常这种计算的代价很大，求解非稀疏矩阵的所有特征向量的标准解法需要O(n3)。当应用到大规模数据时，相似度矩阵也很大，可能会超出计算机的内存。

CDH 所提出的二元聚类方法是在汉明空间中将K-means 与谱聚类联合到一个框架中，满足了各自的约束条件，在聚类精度和标准互信息指标上都有所提高。

1.2.3 LSC-K聚类

基于地标的K-means 光谱聚类简称为LSC-K（Landmarkbased Spectral Clustering using K-means）［9］。在稀疏编码［10］和可伸缩半监督学习［11］的启发下，为解决大规模的问题提出了一种可伸缩的谱聚类方法——基于界标的谱聚类（Landmark-based Spectral Clustering，LSC）。基于界标的谱聚类的基本思想是设计一种高效的图构造和拉普拉斯矩阵特征分解方法，而该LSC-K 聚类对比方法则是由LSC 衍生出来的一种聚类方式，它的缺点是运行时间比较慢。

1.2.4 CKM聚类

压缩K-means 的简称为CKM（Compressed K-Means），用于快速大规模聚类。具体来说，高维数据被压缩成适合快速聚类的短二进制码。CKM 聚类方法有两个主要的优点：1）通过将数据点表示为二进制码，可以显著减少存储；2）使用汉明度量进行二进制码间的距离计算非常有效。

1.3 哈希码学习

网络上分享的图片会出现维度较高等问题。虽然这些高维度的图像包含的内容较为丰富，但在进行聚类时往往存在噪声、不精确和不完整等问题，导致在高维度图像聚类中性能不理想，并且耗费的时间较长，所以要对哈希码进行学习，在学习过程中进行自动特征选择，选择最有用的特征。

来自高维度图像的标签有两个属性：低秩和错误稀缺性［12-14］。作为文本信息的一种，图像标签也因此具有这种低秩属性。此外，网络上上传的大量照片维度较高，在对照片进行组织时较为困难，有些照片的标签提供得相当准确，注释标签的数量与标签总数相比本质上是稀疏的。因此，图像的标签矩阵的误差是稀疏的。在此基础上，通过将图像的标签矩阵分解为其低秩和稀疏分量，揭示了本征低秩矩阵。然后将低秩矩阵作为语义源进行语义增强，以增强学习到的哈希码的识别能力。对于给定的图像的标签矩阵F，图像标签细化的目的是揭示理想的标签矩阵G和标签错误矩阵E。通过鲁棒主成分分析（Robust Principal Component Analysis，RPCA）的研究［15］，可以将该问题表示为一个矩阵分解问题［16］。

其中λ1为正加权参数。

利用离散的方式来丰富哈希码的语义，对哈希码进行学习，进而对图像进行聚类。为此，引入了标签矩阵W，将哈希码与通过特征选择的图像直接关联，从而转移到哈希码中。其中，W定义为W=[w1，w2，…，wn]∈Rl×n，其中wk∈Rl×n是k位哈希码的语义相关向量，目标是尽量减少二进制哈希码和经过特殊选择的特征之间的差异。为了学习W，并给出了以下优化的问题：

图像哈希就是寻找汉明距离与语义相似度匹配的紧凑二进制码。这表明语义上相似的图像应该在较短的汉明距离内映射到相似的二进制码。为了有效地将图像的语义相似性保存到二值哈希码中，利用图模型来解决这个问题。图像之间的相关性可以简单地用相似矩阵S表示。形式上，计算S的第i行第j列的元素（图像i和图像j之间的语义相似性）为：

其中：Nk(x)表示x的k个最近邻的集合，通过局部缩放自动确定；(xj；)表示特征表示模型，Wˉ表示图模型的参数集。为了保持图像的相似性，寻求最小化加权汉明距离的总和：

其中L=diag(S1n)-S为图的拉普拉斯矩阵。通过上述公式可以得到，如果两个相似的图像相距较远，就会受到更大的影响。因此，相似的图像可以被映射成汉明距离较短的哈希码。

为了避免计算n×n矩阵S和L，将采用锚图的方案，即：

这里Z∈Rn×m锚图矩阵的相似性计算所有图片和m锚点，并且Λ=diag(ZT1)，锚图的构建减少了离群点噪声的影响，并且对数据的精细结构进行了详细的描述。

1.4 特征选择

特征选择［17-18］也称特征子集选择，是指从全部特征中选取一个特征子集，从原始数据特征中选择最有用的特征，使构造出来的模型更好。同时，在对特征选择时会存在三种策略：单变量统计、基于模型的选择以及迭代选择。

特征选择用到的方法是迭代选择，构建一系列的模型，每一个模型使用不同数量的特征。在特征投影过程中，目标是最大限度地减少原始数据的冗余［19］，因此通过约束条件PTXXTP=I（其中I表示n阶的单位矩阵，若数据集的大小一致，则用I表示）进行特征学习，目的是使低维特征更具鉴别性。主要方法是在低维数据空间中寻找最优的低秩重构矩阵和将原始数据点投影到低维子空间的特征选择投影矩阵。

1.5 二元聚类结构学习

除了哈希二进制码表示学习之外，还考虑到将哈希二进制码进行方差约束之后，将这些二进制码在汉明空间内进行聚类［20］。由于传统的K-means 聚类和矩阵分解的等价性，通过以下方式进行构建哈希二进制码结构学习：

其中：C和G分别是聚类中心和标签矩阵。为了产生高效的代码使每一位的信息最大化，对聚类中心施加平衡约束。对聚类算法在每次迭代中的数据点的分配策略进行修改，达到对每个簇可包含的数据点数目上限进行约束的目的。同时，算法支持用户自定义簇可包含的数据点数目的上限，满足平衡约束聚类需求，使其适应二进制聚类任务。

2 离散哈希的聚类方法

在本章中，将介绍所提出的CDH 方法。首先，详细描述了CDH 方法；然后，给出了CDH 的优化算法。

2.1 CDH方法

本节主要研究基于离散哈希的聚类问题。使用离散哈希的方法对二进制码进行重构，选取数据中的最优特征，完成对数据二进制码的学习。将二进制码对图在汉明空间内进行聚类时，有效提高聚类精度，提高聚类的性能是一个重要研究问题。离散哈希方法能够优化聚类过程中的信息损失，提高聚类精度以及减小存储成本，将离散哈希方法和聚类算法表示集合到一个统一的框架，最终将其结合得到目标函数：

其中：B为哈希码矩阵，C是聚类中心矩阵，L是图的拉普拉斯矩阵，W为图的映射矩阵，G为指标矩阵，α、β、γ、λ为正则化参数。

1）CDH 旨在将图像投射到一个共同的汉明空间中，在投影过程中，为了解决区域位移的非线性问题，所以进一步将所提方法推广到复制再生核希尔伯特空间（Reproducing Kernel Hilbert Space，RKHS）中基于核的非线性框架中，并建立了一个非线性的区域位移框架。令其中的Y=ϕ(x) ∈Rm，R→{-1，1}l×n。

因此，公式第一部分中，输入训练数据集Y后，需要一个哈希函数来有效地将这一个新的训练集Y编码成为二进制代码。采用简单的线性哈希函数：

对训练集进行转换，转换成计算机可识别的二进制代码，这里可以通过可用的训练数据和代码求解一个线性回归系统来进行学习。也就是可以通过式（13）解决。

对于拉普拉斯正则化项，约束在原始数据空间中非常接近的两个数据点xi和xj，那么它们在投影的低维子空间中的映射和表示的系数也使相似的。

3）tr(WY)(WY)T表示对投影后的数据方差进行约束，方差表示两个数据之间的相互关系，方差变大，二进制码更分散，这样就会更好地达到平衡位。这是二进制码学习［22］的典型要求。

5）tr(GLBGT)的调节使为了保持相似度，实现高价平滑，对数据进行投影后，寻找出最小加权的汉明距离。

6）从实际应用中收集的数据集通常包含冗余，这很难使聚类总体上取得显著的结果，因此需要降低数据的维数。许多谱聚类方法通常通过子空间学习构造低维谱表示，即将高维数据投影到低维子空间，同时保持数据的结构特征。例如，局部保持投影在子空间学习和谱聚类中被广泛使用，因为它可以保持原始特征数据的最近相关性（即数据的重要相关性）。提出的基于离散哈希的聚类公式如下：

其中的L=D-S是图的拉普拉斯矩阵。D是一个对角矩阵，矩阵中第i个元素定义为。此外，S=也就是说，如果第i个样本是第i个样本的k个最近邻居之一，则相应的sij可以由热核函数［23］定义。例如，其中的σ是一个协调参数。在相似矩阵的约束下，投影矩阵W也保持了样本与原始数据的相似性。

利用超图构造拉普拉斯矩阵，并进一步利用超图拉普拉斯矩阵约束表示，以保持原始数据的复杂高阶关系。所以，式（15）可以改写为：

其中LB是超图拉普拉斯矩阵，它可以由超图构造方法构造。与超图的其他构造方法相比，该方法使用自适应学习方法来获得本质超图结构，从而容易获得鲁棒的拉普拉斯矩阵。

考虑到进一步选择特征以减轻冗余特征的影响，可以学习鲁棒的谱表示，它的公式被定义为：

如果两个相似的图像的距离很远，那么就难以估计。所以，类似的图像可以被映射成汉明距离的较短的哈希码，通过哈希码的稀疏情况，对图像更好地聚类，提高它的速度。

2.2 CDH算法求解

在本节中，将介绍通过在以下3 个子问题之间交替求解联合优化问题（10）的算法：

1）通过输入Y求解二进制哈希码结构来表示问题，而求出W、B、C、G。

2）使用基于离散哈希的方法，对图像进行哈希二进制编码，对投影矩阵进行自动特征选择，将其应用的子问题进行求解，约束矩阵W。

3）利用二元聚类结构学习对二进制码进行聚类，通过对符号函数进行松弛到带符号的量级，将目标函数进行表示。

优化问题（10）涉及离散约束问题。在本节中将使用一种交替优化策略，它将问题分成几个子问题，这样每个子问题都是可处理的。具体地，在优化目标函数时，每个部分分别看作一个变量，固定其他变量，在固定其他变量时交替更新每个变量。迭代步骤的详细内容如下。

更新W通过固定除W之外的所有变量，可以将问题写为：

为了方便计算，可以对式（18）中的单步进行形式转化：

将式（19）代入式（18）得：

去除不含W的项得出：

计算式（21）的导数并设为0，通过求导得到的封闭解

其中Λ是一个对角矩阵，它的对角元素可以写成：

为了保证分母有意义，在分母上添加一个足够小的正常数Δ，此使，Λ转化成Λ′=diag(Λ′11，Λ′22，…，Λ′ll)，对角线元素可以写成：

用Λ′更换Λ时，式（22）可以改写成如下形式：

更新B问题（10）同样涉及B，通过固定除B之外的所有变量，可以将问题简化为：

式（26）可以重写为：

con是一个恒定值，因为tr(BBT)=tr(BTB)是一个常数，同时可将式（26）改为：

它的最优解是：

更新C和G这一部分是在汉明空间中优化二元聚类结构，是将K-means 和谱聚类联合到一个共同的框架中。通过除去不相关性，得到如下二元聚类公式：

式（30）中的C和G中都不是凸的。因此，期望算法找到全局最小值不能现实。本节将介绍用乘法更新规则实现局部极小值的迭代算法。首先讨论如何最小化目标函数式（30），它可以重写为：

由于矩阵具有以下性质：tr(GB)=tr(BG)，tr(B)=tr(BT)，所以可以得到第二个等式。ψik和ϕjk分别为约束cik≥0 和gik≥0 的拉格朗日乘子，并且Ψ=[ψik]，Φ=[ϕjk]，拉格朗日L是：

L关于C和G的偏导是：

使用阶优化条件KKT（Karush-Kuhn-Tucker）使ψikcik=0和ϕjkgjk=0，得到了关于cik和gik的方程：

这些方程导致了以下更新规则：

算法1 总结了所提出的CDH 的主要步骤。

算法1 离散哈希的聚类算法CDH。

输入 数据矩阵Y={y1，y2，…，yn}，参数α，β，γ，λ；

输出 标签矩阵G。

3 算法的性质分析

3.1 收敛性分析

提出的CDH 方法可以找到最优解，为了证明其收敛性，在本节中，提供了算法1 的收敛性分析。首先引入一个重要的引理。

引理1给定两个正常数a和b，有以下不等式成立：

证明 给定两个正常数a和b，有

算法1 将迭代地降低问题（10）的目标函数值，即经过多次迭代返回G的解。通过迭代优化，式（10）的目标函数值在每次迭代时都单调递减并向下界靠拢。此外，在图像数据集上的实验也验证了该方法的收敛性。

K-means 和CDH 方法在相同数据集上收敛速度图比较如图2 所示，可以清楚地看到K-means 和CDH 方法的收敛速度非常高，大概在100 次以内迭代值就会达到收敛。

图2 两种方法在COIL20数据集上的收敛曲线Fig.2 Convergence curves of two methods on COIL20 dataset

3.2 复杂性分析

基于离散哈希的聚类方法的计算负担主要由哈希二进制码学习以及在汉明空间中对二进制码聚类两部分组成。首先在数据集预处理部分对原始数据集进行一个锚图构造，锚图的构造包括锚的生成和锚与图像之间的距离计算。该过程的时间复杂度为O(dmn)，d是数据的维度，m是锚点个数，n是原始样本数。为了节省式（10）中的时间，在整个算法主要是在迭代之外，对映射矩阵W进行投影，其代价为O(dmn)。计算离散表示的二进制码B消耗O(lmn+lcn)。因此，对离散哈希二进制码学习的时间复杂度为O(lmn+lcn+dmn)，c表示聚类簇的数目。聚类是在汉明空间对二进制码进行聚类。更新计算K-means 中的每一次迭代运算其实很简单，但由上节的更新C、G中需要注意的一点是A是一个稀疏矩阵，这里需要O(n2d)的时间复杂度来构建p最近邻图。假设更新是在t次之后停止，那么K-means 的时间复杂度是O(tdnc)，这样整个对二进制码进行聚类的时间复杂度是O(tdnc+n2d)。综上可得，整个基于离散哈希的聚类方法所使用的时间复杂度是O((l+d)mn+(l+td)nc+n2d)。

3.3 参数敏感度

根据是否采用离散方法优化二进制码，现有的数据依赖的哈希方法可以进一步分解为连续的哈希方法和离散的哈希方法。在对哈希码进行选择时，短的哈希码表示能力弱，会使得聚类的复杂度较低；而长哈希则表示能力强，其聚类的复杂度高。

基于离散哈希的聚类方法采用的是离散的哈希码学习方式，在对定义哈希码长度时，假设哈希码长度为l，一共有c个聚类中心，则需要满足l>lbc，否则，哈希码将无法区分不同类别，这是哈希码长度的下限。

同时，当一个参数的值发生变化时，其他参数在这些实验中被设置为相同的值，最终的结果也会跟着发生变化。图3显示α和γ值对Caltech101数据集的HOG视图准确度（Accuracy，Acc）［24］、归一化互信息（Normalized Mutual Information，NMI）［25-26］、纯度（Purity）［27］的影响。

图3 α和γ值对Caltech101数据集的HOG视图Acc、NMI、纯度的影响Fig.3 Effects ofα andγ values on HOG view Acc，NMI，Purity for Caltech101 dataset

图4 显示了根据不同的λ相对应的Acc、NMI 和Purity 的变化。

图4 Acc、NMI和纯度相对于不同λ的变化Fig.4 Acc，NMI and Purity changes with respect to differentλ

4 实验与结果分析

在本章中，为了验证CDH 的聚类效果，从聚类性能、计算效率和内存负载等方面评估了所提CDH 方法对于图像聚类任务的有效性。在大量的基准数据集上，实验结果选用三个最常用的评价指标，即Acc［24］、NMI［25-26］和Purity［27］作为评价标准，将其与几种代表性方法进行比较，对于每个评价指标，值越大表示结果越好。

4.1 实验数据集

本节主要总结了实验中使用的数据集的特征，评估使用了Caltech101、Yale、COIL20 和ORL 这4 个数据集。具体数据集总结如图5 所示。

图5 用于实验的数据样本集示例Fig.5 Samples of datasets for experiments

表2 总结了实验中所使用的这些数据集的特征。特别地，把Caltech101 多视图数据集的每一个维度看作成一个单视图。

表2 数据集特征Tab.2 Dataset characteristics

1）Caltech101 数据集由9 144 幅图像组成，包含101 个对象和1 个背景类别。选用文献［28］中Caltech101 数据集的实验特性，将Caltech101 中的六个不同特征分别看作成一个视图，用于实验的数据样本集中。

2）Yale 数据集选用Yale 数据库中的由15 个人组成的4 096 张人脸图像。

3）COIL20 是一个图像数据集，它有1 440 幅图像。数据集包含20 个物体，每个物体水平旋转360°，每5°拍摄一次，每个物体总共72 张图片。

4）ORL 是一个包含10 组400 幅图像的人脸数据集。由40 个不同年龄、性别的对象组成的图像。对于一些受试者，在不同的时间拍摄图像，改变灯光、面部表情（睁开/闭上眼睛、微笑/不微笑）和面部细节（戴眼镜/不戴眼镜）。

4.2 评价指标

本节中将会使用Acc、NMI 以及Purity 三个评价指标对相关的比较方法进行实验性能评价，这些评价指标的具体定义如下。

Acc 定义如下：

其中：map（ri）是一个置换映射函数，用于使簇标签ri与数据集中的等价标签匹配；n为数据点个数，ri是Xi的预测标签，li是对应的真实簇标签；δ(a，b)是一个脉冲函数，如果a=b则函数值为1，其他为0。

H(X)为：

其中p(i)=|X|/N是从X中随机选择的一个对象落在第Xi类中的概率。

Purity 是聚类评价方法，它只需计算正确聚类的数据占总数据的比例：

其中：Ω={ω1，ω2，…，ωk}是聚类的集合，ωk表示第k个聚类的集合；C={c1，c2，…，cj}是文档集合，cj表示第j个文档。N表示聚类数据总数。

4.3 比较方法

为了评价CDH 方法的性能，将会从以下几种聚类方法和CDH 方法作比较：

1）K-means 聚类方法的思想很简单，对于给定的样本集，按照样本之间的距离大小将样本集划分为k个簇，让簇内的点尽量紧密地连在一起，而让簇间的距离尽量大［9］。

2）谱聚类（Spectral Clustering，SC）是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类。谱聚类可以理解为将高维空间的数据映射到低维，然后在低维空间用其他聚类算法（如K-means）进行聚类［28-29］。

3）LSC-K：基于标记表示的大规模谱聚类方法利用K-means 进行地标选择，可以从作者的网站（http：//www.cad.zju.edu.cn/home/dengcai/）下载Matlab 代码［30］。

4）LSH+bk-means：单台机器上的Web 级照片哈希聚类首先使用局部敏感哈希（Locality Sensitive Hash，LSH）生成一个随机高斯矩阵，数据点被哈希成二进制码。将bk-means应用于生成的二进制码进行聚类。这种朴素的两步聚类方法可以被视为基于二进制编码的聚类方法的基线［5，31-33］。

5）CKM 用于大规模聚类［22］。

6）多视图K-means 聚类（Multi-View K-Means clustering，MVKM）［34］，该方法使用典型相关分析（Canonical Correlation Analysis，CCA）将每个视图中的数据投射到一个低维子空间之后再进行聚类［35］。

7）自动加权多重图学习（Auto-weighted Multiple Graph Learning，AMGL），该方法在描述时有相同的实例可以由多个异构特征表示，并且可以自动学习每个图的最优权值［36］。

8）RPCA：称为鲁棒主成分分析，是目前应用最广泛的降维方法［15，37］。

9）非负矩阵分解（Nonnegative Matrix Factorization，NMF）［38］。

10）考虑数据的非线性结构的图正则非负矩阵分解（Graph regularized Nonnegative Matrix Factorization，GNMF），由NMF 演化得到。

这里包含了最为经典的K-means 聚类方式，以及单视图聚类方法：SC、LSC-K 和两种现有的二元聚类方法：LSH+bkmeans 和CKM。同时，AMGL 和MVKM 代表了对大规模的数据进行聚类的方式，与CDH 方法进行了比较。经过实验比较可以得出不同方法在数据集上的精度、NMI 以及纯度，如表3～8 所示。

表3 不同方法在Caltech101数据集上的精度对比Tab.3 Accuracy comparison of different methods on Caltech101 dataset

表4 不同方法在Caltech101数据集上的NMI对比Tab.4 NMI comparison of different methods on Caltech101 dataset

表5 不同方法在Caltech101数据集上的纯度对比Tab.5 Purity comparison of different methods on Caltech101 dataset

表6 不同方法在不同数据集的精度对比Tab.6 Accuracy comparison of different methods on different datasets

表7 不同方法在不同数据集的NMI对比Tab.7 NMI comparison of different methods on different datasets

表8 不同方法在不同数据集的纯度对比Tab.8 Purity comparison of different methods on different datasets

4.4 实验设计与分析

在与其他先进的单视图聚类相比，从表3～8 中可以观察到基于离散哈希的聚类在大多数情况下优于所比较的实值和二元聚类方法。具体来说，CDH 通过对自动特征选择，选取最有用的信息进行哈希学习可以在单个视图上获得更好的结果，这表明通过哈希学习的离散表示对于聚类是有效的。对于单视图方法，如K-means、SC 和LSC-K，可以发现直接对未进行任何处理的数据进行聚类，在大多数情况下可能导致冗余信息。由于哈希二进制码学习和二元聚类结构构建在一个更好的统一框架上，CDH 明显优于现有的二进制聚类方法，例如SC 和LSC-K。

同时，基于离散哈希的聚类方法的时间效率与其他聚类方法相比更具有优势，它比其他聚类方法快得多，例如：Caltech101 数据集的Gabor 视图，K-means 需要27 s，SC 需要200 s，CDH 只需要3.4 s。主要原因是基于离散哈希的聚类算法受益于使用汉明距离来测量而不是欧几里德距离测量的高效距离计算［39］。基于离散哈希的聚类算法比其他所有的比较方法花费更少的时间，这也证明了所提出的高效离散优化算法的优越性。

表3～8 中的结果表明，与真实值聚类方法相比，基于离散哈希的聚类有更高的聚类性能，主要原因是该聚类方法所提出的有效的离散优化方法，其中的自动特征选择可以很好地消除了原始实值特征中的一些冗余和噪声信息，同时，使用二进制码进行聚类可以更高效地处理高维数据。

通过实验可以得到CDH 方法的4 个优点：

1）CDH 方法使用哈希学习，将数据投影成二进制码，对数据在汉明空间中进行聚类，运行速度快，减少存储空间。

3）对转化成二进制码的数据约束，进行特征选择，选择更有价值的信息，这样能够提高聚类的聚类精度。

3）离散哈希码优化直接求解哈希码，没有量化误差。

4）利用相关图像标签中有价值的语义增强图像哈希码的识别能力，同时去除其中可能降低聚类性能的不利噪声。

5 结语

在现有的一些聚类方法中，将原始数据在数据空间中聚类，对数据聚类时存在噪声情况，存在一些信息精度不高问题，提出的一种二值聚类方法——基于离散哈希的聚类方法。在聚类过程中，将哈希码学习和二元聚类结构放到同一个框架中，该方法可以直接学习二进制哈希码，并将数据投影到汉明空间中进行聚类，计算的效率高，存储成本较低，适合用于高维度的图像聚类。建立了一个基于离散哈希的学习模型，可以使用哈希函数来解决离散化的问题，实现高维数据集的数据聚类。此外，提出的一种基于离散哈希的聚类优化方法可以直接求解二进制码，可以更有效地提高聚类的效率。实验结果表明，基于离散哈希的聚类方式与传统的聚类方法相比更具有优势。接下来考虑将本文方法进行拓展应用于多视图聚类任务。