0 引言

随着科学技术的发展, 从不同角度对事物进行描述, 以此得到更多有用信息, 研究者将这些信息看作多个特征集合, 每个特征集合作为一个视图, 即可构成多视图数据。传统的聚类算法只能处理单视图数据, 对多视图数据的聚类结果并不理想, 文献[1]首次提出多视图聚类概念, 提取并结合多个视图的有用信息对数据进行聚类, 以得到更好的聚类结果。之后出现多种改进算法, 如文献[2]提出基于协同训练(Co-training)的多视图聚类算法; 文献[3]提出MVKKM算法, 采用核函数对不同视图进行加权聚类算法; 文献[4-6]提出矩阵和低秩的多视图聚类算法; 文献[7]提出一种分布式的多视图聚类集成算法。随着数据增加的速度越来越快, 引入增量聚类的概念^[8]来处理动态增加的数据, 既降低对资源的浪费, 又节约聚类时间。典型的增量聚类算法有: (1)使用随机抽样从数据集中抽取子样本进行聚类CLARANS算法^[9]; (2)使用增量聚类框架处理流数据, 将数据集分成多个块, 对每个数据块进行聚类:OFCM算法^[10]和SPFCM算法^[11]。文献[12]在SPFCM算法的基础上, 提出IFCM(c+p)算法。

虽然增量聚类算法已经得到广泛的应用, 但针对多视图数据的增量聚类算法还很少。本研究将基于核的MVKKM扩展到增量聚类框架中, 提出基于核K-means的多视图增量聚类算法(incremental multi-view clustering algorithm based on kernel K-means, IMVKKM)^[13]。通过对数据分块的方式进行聚类, 在保证聚类性能的基础上降低运行时间。

1 核函数

定义 (核函数)  设x_k∈R^N(k=1, 2, …, K)是输入空间χ∈Rⁿ内的一组样本, 使用映射函数将这组样本映射到另一个新的高维空间, 在该空间上这组样本可实现线性可分^[14]。该映射函数即为核函数, 其是映射关系的内积, 定义为

$ K\left( {{x_i},{x_j}} \right) = \phi \left( {{x_i}} \right) \cdot \phi \left( {{x_j}} \right), $

(1)

式中:K表示核函数, ϕ(x_i)表示一种非线性变换。

定理 (Mercer定理)  给定一个输入数据集(x₁, x₂, …, x_n)与一个n×n的矩阵A, 其中元素为a_ij=f(x_i, x_j), 如果矩阵A是半正定矩阵, 则f(x_i, x_j)为半正定函数^[15]。但是Mercer定理不是核函数的必要条件, 只是充分条件, 即也有不满足Mercer定理的函数, 但是可作为核函数。

如果某个函数满足Mercer定理, 那么它就可以作为核函数。常用的核函数如下:

(1) 线性核(Linear kernel)

$ K\left( {{x_i},{x_j}} \right) = \left( {{x_i},{x_j}} \right), $

(2)

(2) 多项式核(polynomial kernel)

$ K\left( {{x_i},{x_j}} \right) = {\left( {{x_i} \cdot {x_j} + 1} \right)^d}, $

(3)

(3) 高斯核(RBF Gaussian kernel)

$ K\left( {{x_i}{x_j}} \right) = \exp \left( {\frac{{ - {{\left\| {{x_i} - {x_j}} \right\|}^2}}}{{2{\sigma ^2}}}} \right), $

(4)

式中:d＞0为多项式核函数的阶数; σ＞0是高斯核函数的宽度。

因为现阶段还没有统一的标准来选择核函数, 下面给出一个经验方法:如果样本个数与特征维度个数数量相当, 则线性核函数最为合适; 如果特征维度较小, 则推荐选择高斯核函数; 如果样本个数较多, 最合适的方法是扩容特征维度并选择线性核函数。

2 基于核K-means算法的多视图增量聚类算法 2.1 基于核的多视图聚类算法

多视图数据中, 每个视图中含有的有效信息的数量是不同的, 如果将所有视图平等对待, 包含不相关信息较多的视图会使聚类效果变差。因此文献[3]引入MVKKM算法来处理多视图数据。首先使用核函数将每个视图从低维空间映射到高维空间, 使用核矩阵表示。并对视图进行加权, 用来衡量每个视图对聚类结果的贡献度, 通过算法迭代对贡献度较大的视图赋予更大的权重值, 以得到较好的聚类结果。进行算法的迭代运算自动更新权重值和聚类标签。

给定的数据集X是样本x_i在视图v中的向量, X={x_i}_i=1^N, x_i={x_i^(v)}_v=1^V x_i^(v)∈R^d(v)。已知需要将数据集X划分为K个簇:{C_k}_m=1^K, 聚类中心为{m_k}_k=1^K。使用一组非线性映射{ϕ^v}_v=1^V, 将V个视图映射到特征空间{H^v}_v=1^V, 使用一组核函数来代替内积运算, 每个视图在计算后可得到一个核矩阵K^v来表示。故多视图数据使用V个核矩阵{K^v}_v=1^V表示, 并使用视图权重w_v(v=1, 2, …, V)对每个视图加权, 将V个核矩阵进行组合得到$\mathit{\boldsymbol{\widetilde K}} = \sum\limits_{v = 1}^V {\mathit{\boldsymbol{w}}_v^p{\mathit{\boldsymbol{K}}^v}} $。则MVKKM算法的目标函数为

$ \begin{array}{l} {J_{\tilde H}}\left( {{\mathit{\boldsymbol{w}}_v},\mathit{\boldsymbol{m}}_k^{\left( v \right)}} \right) = \sum\limits_{v = 1}^V {\mathit{\boldsymbol{w}}_v^p} \sum\limits_{i = 1}^N {\sum\limits_{k = 1}^K {{\mathit{\boldsymbol{\delta }}_{ik}}{{\left\| {{{\pmb\phi} ^{\left( v \right)}}\left( {x_i^{\left( v \right)}} \right) - \mathit{\boldsymbol{m}}_k^{\left( v \right)}} \right\|}^2}} } ,\\ {\rm{s}}.{\rm{t}}.\;{\mathit{\boldsymbol{w}}_v} > 0,\sum\limits_{V = 1}^V {{\mathit{\boldsymbol{w}}_v}} = 1,p \ge 1 \end{array} $

(5)

式中: v为第v个视图; w_v为第v个视图的权重; m^(v)_k为第v个视图中第k个簇的聚类中心; δ_ik是一个指示矩阵, 当x_i∈C_k时, δ_ik=1, 否则δ_ik=0。

其中聚类中心M的计算公式为

$ \mathit{\boldsymbol{m}}_k^{\left( v \right)} = \frac{{\sum\limits_{i = 1}^N {{\mathit{\boldsymbol{\delta }}_{ik}}{{\pmb \phi} ^v}\left( {x_i^{\left( v \right)}} \right)} }}{{\sum\limits_{i = 1}^N {{\mathit{\boldsymbol{\delta }}_{ik}}} }}。$

(6)

根据拉格朗日乘子法, 可以得到权重w_v的更新公式为

$ {\mathit{\boldsymbol{w}}_v} = \frac{1}{{\sum\limits_{v' = 1}^V {{{\left( {\frac{{{\mathit{\boldsymbol{D}}_v}}}{{{\mathit{\boldsymbol{D}}_{v'}}}}} \right)}^{\frac{1}{{p - 1}}}}} }}, $

(7)

式中${\mathit{\boldsymbol{D}}_v} = \sum\limits_{i = 1}^N {{{\sum\limits_{k = 1}^K {{\mathit{\boldsymbol{\delta }}_{ik}}\left\| {{{\pmb \phi} ^{\left( v \right)}}\left( {x_i^{\left( v \right)}} \right) - \mathit{\boldsymbol{m}}_k^{\left( v \right)}} \right\|} }^2}} $。

因为初始聚类中心的设置会对聚类结果造成较大的影响, MVKKM算法使用全局核K-means算法对数据集进行初始聚类, 得到初始聚类中心M^[16]。之后使用迭代算法更新聚类中心和权重值。MVKKM算法具体步骤如下:

算法1  (MVKKM算法)

输入  多视图数据集X; 聚类簇个数K; 收敛参数τ; 最大迭代次数iter,

输出  聚类中心矩阵M, 权重矩阵W。

步骤1  初始化, 运行全局核K-means算法得到初始聚类中心M;

给权重矩阵W赋初值, w_v=$\frac{1}{V}$。

步骤2  Repeat

(1) 固定W, 使用核K-means算法计算得到M;

(2) 固定M, 根据式(7)计算得到W;

至式(5)收敛或达到最大迭代次数。

从文献[16]中可以看出, MVKKM算法在多视图数据上取得了较好的结果, 但因为需要计算数据集中每个视图的核函数, 因此聚类算法的运行时间和存储容量大大增加, 但数据集样本较多时, 该算法的运行时间会大大增加。针对这一问题, 本研究将MVKKM算法与增量聚类框架相结合, 提出IMVKKM算法。

2.2 基于核K-means算法的多视图增量聚类算法

本研究提出的IMVKKM算法中, 使用将数据集分块并对每个数据块进行聚类的思想处理多视图数据, 节省资源并减少聚类所需时间。

将多视图数据集随机划分为多个数据块, 对每个数据块使用MVKKM算法进行处理, 得到这些多视图数据块的聚类中心。而对当前数据块进行聚类时, 使用的初始聚类中心为前一个数据块的聚类中心。所有数据块处理完成后将聚类结果进行整合, 会得到一组新的多视图数据集, 并再次使用MVKKM算法处理该数据集以得到最终的聚类结果。具体框架见图 1。

给定一个多视图数据集X={x¹, x², …, x^V}∈R^n×d_v, v∈{1, 2, …, V}, V为视图的个数。初始化时给出划分的数据块所占X的比例percent, 即。根据percent将X进行随机划分, 得到L个大小相同的数据块D_l(l=1, …, L), 每个数据块都是样本个数相同、视图个数相同、每个视图中样本维度相同的多视图数据集(可以有一个数据块中样本个数较少, 但视图个数和样本维度均相同)。IMVKKM算法不考虑数据块之间的关系, 只是将每个数据块当作单独的多视图数据集进行处理, 这时默认每个数据块中聚类簇的个数均为K。使用MVKKM算法对数据块D_l进行聚类, 得到的聚类结果保存在矩阵M_l^v中, 使用该结果代表D_l中的有用信息。

处理数据块D₁时, 由于这是第一个数据块, 因此并没有初始聚类中心, IMVKKM算法选择全局核K-means算法对其进行初次聚类, 以此得到初始聚类中心, 再使用MVKKM算法进行聚类, 得到的聚类结果存储在矩阵M₁{M₁¹, …, M₁^V}中。对于之后的数据块D_l(l＞1), 在聚类时使用的初始聚类中心均为前一个数据块D_l-1的聚类结果M_l-1, 之后使用MVKKM算法对聚类中心进行迭代更新。l个数据块都聚类完成后, 合并所有的聚类中心矩阵Q^v=Q^v∪M_l^v (l=1, …, L), 因此Q也可当做一个多视图数据集。使用MVKKM算法再次进行多视图聚类, 得到的聚类结果C^v(v=1, 2, …, V)作为算法的最终聚类结果。最终将数据样本划分到聚类最近的簇中。算法的具体步骤如下:

算法2 (IMVKKM算法)

输入  多视图数据集X, 数据块所占比例percent, 聚类簇个数K, 收敛参数τ, 最大迭代次数iter,

输出  聚类中心矩阵C, 样本划分结果δ。

步骤1  初始化, 根据percent将数据集划分为L个块, 聚类中心矩阵Q^v=ϕ(v=1, …, V)。

步骤2  l=1, 使用全局核K-means算法进行聚类得到初始聚类中心;

使用MVKKM算法聚类得到聚类结果M₁{M₁¹, …, M^V₁}。

步骤3  for l=2：L

初始聚类中心, 矩阵M_l-1;

使用MVKKM算法进行聚类得到矩阵M_l;

for v=1: V

  Q^v=Q^v∪M_l^v

end for;

end for。

步骤4  使用MVKKM算法对聚类中心矩阵Q进行聚类得到最终的聚类中心C;

步骤5  将数据样本重新进行划分

for i=1: N

  $\mathit{\boldsymbol{\delta }}{\rm{ = }}\mathop {\arg \;\min }\limits_{k \in \left\{ {1, 2, \cdots , K} \right\}} \sum\limits_{v = 1}^V {{{\left\| {x_i^v - c_k^v} \right\|}^2}} $,

end for。

3 试验与结果 3.1 试验数据集

本研究选择Animal、Reuters和CiteSeer三个规模较大的数据集^[17]进行试验, 以此来说明IMVKKM算法的聚类效果。Animal数据集具有30 475个样本, 分为6个类别, 包含3种特征对应3个视图, 每个视图中样本维度为2 000; Reuters数据集包含1 200个样本, 包含5种语言对应5个视图, 每个视图中有2 000个样本; CiteSeer数据集包含3 312个样本, 具有2个视图, 对应的维度分别为3 703和3 312。

本研究选择的是MVKKM算法。通过比较两个算法的性能来验证IMVKKM算法的效果^[18], 有关数据集的详细信息见表 1。

试验环境^[17]: MATLAB2012a; Windows10 64位; 8 GB内存; i7-5500U。

3.2 度量标准

本研究选择3种评价指标: F-measure^[18-19]、Acc(Accuracy)^[20]和RI(Rand Index)^[21]来评价聚类算法的性能。另外使用Speedup指标评价算法的运行时间。

3.2.1 F-measure评价指标

F-measure是常用的评价指标:

$ {F_\beta } = \frac{{\left( {1 + {\beta ^2}} \right)pr}}{{{\beta ^2}p + r}}, $

(9)

式中: $p = \frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FP}}}}$; $r = \frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FN}}}}$; TP表示被正确划分的样本个数; FP表示样本属于不同簇, 却被划分到相同的簇中的样本个数; FN表示样本属于相同的簇, 但被划分到不同簇的样本个数。

3.2.2 正确率Accuracy

最常用的评价指标

$ {\rm{Accuracy}} = \frac{{{\rm{Num}}}}{N}, $

(8)

式中: Num表示被正确划分的样本个数; N表示样本总个数。

3.2.3 RI评价指标

RI用来评价两个聚类划分的相似性:

$ {\rm{RI}} = \frac{{{L_a} + {L_d}}}{{{L_a} + {L_b} + {L_c} + {L_d}}}, $

(10)

式中:L_a指属于不同簇且划分到不同簇的样本个数; L_b指属于不同簇但被划分到同一个簇中的样本个数; L_c指属于同一个簇但被划分到不同簇中的样本个数; L_d指属于同一个簇且划分到一个簇中的样本个数。

上面3种指标的最终结果均为一个[0, 1]之间的小数, 数值越接近1表示聚类效果越好。

3.2.4 Speedup性能指标

Speedup反映增量聚类算法与对应的普通聚类算法在处理同一数据集时运行时间的对比情况^[12]:

$ {\rm{Speedup}}\left( {{\rm{sp}}} \right) = \frac{{{\rm{Full}}}}{{{\rm{International}}}}, $

(11)

式中: Full表示使用与增量算法相对应的普通聚类算法对数据集进行聚类所运行的时间; International表示使用增量聚类算法对数据集进行聚类所运行的时间。Speedup越大说明增量聚类算法运行时间越短。

3.3 试验结果及分析

在将数据分块时, 本研究采用的是每个数据块所占比例为5%、10%、20%、25%和50%五种划分方式, 且数据分块采用的是随机划分的方式。而为了避免初始化条件等对算法的影响, 本章中的所有试验结果均为算法运行30次后所计算的平均值。表 2~4分别为Animal、Reuters和CiteSeer数据集上的试验结果。

首先对IMVKKM算法的聚类性能进行分析, 从表 2~4可以看出, IMVKKM算法在3个数据集上都具有较高的Accuracy和RI值, 在Animal和Cite-Seer2个数据集上具有较高的F-measure值, 在Reuters数据集上, IMVKKM算法与MVKKM算法的F-measure值相差并不大。说明IMVKKM算法相较于MVKKM算法不仅可以保障聚类性能, 还有所提升。

在此基础上讨论IMVKKM算法是否能够降低运行时间。图 2给出在不同数据集上, 将数据集划分为不同大小数据块时, IMVKKM算法与MVKKM算法运行时间的Speedup值变化过程。

从图 2可以看出, 当数据块大小为整个数据集的5%时, IMVKKM算法的Speedup值最大。随着数据块所占比例增加, IMVKKM算法的Speedup值迅速下降, 当数据块所占比例为25%与50%时, Speedup值相差较小, 基本趋于稳定并趋近于1。主要原因是随着数据块所占比例的增加, IMVKKM算法在处理每个数据块时计算量增加, 因此聚类时间成倍增长。而数据块所占比例越大, IMVKKM算法越类似于MVKKM算法, 因此Speedup值逐渐趋近于1。所以, 在数据块所占比例越小, 即所分的数据块个数越大时, IMVKKM算法越能有效减少聚类算法运行的时间。

4 结论

针对现有多视图聚类算法中运行时间过长的问题, 本研究提出将多视图加权核K-means聚类算法与增量聚类框架相结合的概念。核函数将线性不可分的数据实现线性可分, 而多视图加权核K-means算法大大提高聚类算法的性能。另一方面, 当样本个数很多时, 核函数的运算时间成倍数增长, 且占用大量的资源, 而引入增量聚类框架的概念, 通过将数据集分块, 对每个数据块进行核函数计算可大大降低算法的运行时间, 也可节省资源。

本研究基于MATLAB平台分别对Animal、Reuters和Citerseer 3个数据集进行试验, 根据F-measure、Accuracy、RI 3个评价指标和Speedup性能指标可以看出, 与MVKKM算法相比, IMVKKM算法的聚类性能没有降低, 而运行时间大大减少。因此在处理大规模多视图数据时, 本研究提出的方法是可行且高效的, 因此在多视图聚类领域具有较高的应用价值和研究价值。