聚类是一项重要的数据分析技术, 子空间聚类是传统聚类算法的扩展, 试图寻找数据集在不同的特征子集中存在的簇^[1]. 对于给定的数据集, 子空间聚类一般可以找出多种不同的划分方案, 可以利用数据集本身的属性信息或用户提供的有效信息, 来寻找特定需求的子空间划分方案, 并得到对应条件的聚类结果. 例如, 对于DNA序列可以使用子空间聚类算法来识别序列中的隐藏模式(簇), 更重要的是通过无监督的方式执行自动变量选择来揭示感兴趣的潜在生物学概念^[2].

子空间聚类的熵加权K-means算法(EWKM)是由Jing等人^[3]扩展了加权K-means算法引入了权重熵, 从而使得更多维度加入到聚类过程中, 该算法提出后就得到了广泛应用. 目前, 有许多算法都是基于该算法框架利用不同信息或从不同角度进行扩展, 如利用簇间信息来扩展, Xiong等人提出ERKM算法^[4]在统一的子空间中, 通过最大化簇中心与不属于该簇的点之间的距离, 使实例在子空间中保持簇内距离最小, 各个簇之间距离最大的状态. 利用数据集的特征信息来扩展, 例如Yang等人提出的FRFCM算法^[5], 在FCM模型中引入特征权重熵, 同时利用特征的均值-方差比来评估每个特征的重要程度, 利用较小的权值来消除不相关特征给聚类过程带来的干扰. 也有通过修改权重熵的角度来改进, Huang等人^[6]利用 ${l^2} - norm$ 来代替权重熵项以此提高特征选择的有效性, 让更多的特征参与到子空间聚类当中.

上述聚类方法均有应用EWKM算法中的特征加权方法, 并在其基础上进行扩展改进, 已成功应用到很多领域. 但是, 上述聚类算法均没考虑在实例分配过程中各个簇的实例数量是否均衡, 所以无法很好解决平衡聚类问题. 同时, 利用平衡聚类也可以帮助子空间生成保持平衡结构的特征权重. 在许多实际应用中, 用户是希望聚类结果能有较好的平衡性, 应用需求也是研究平衡聚类的一个动机. 例如在无线传感网络中^{[7, 8]}, 理想情况下应当使每个网络节点的样本数量大致相同, 否则会增加能源消耗; 在分布式数据管理中, 为了提高分布式数据管理系统在查询时节点间数据传输的性能, 通常需要尽可能平衡地分配每个节点的数据量, 避免出现负载较大的单个节点^[9]; 在营销活动中, 为保证公平和效率需要将客户平衡划分多个集群, 以保证每个销售人员工作量相同. 除了满足实际需求外, 平衡划分往往会降低初始化的敏感性, 因此即使在不需要平衡的情况下, 也会产生有益的效果^{[10, 11]}.

平衡聚类算法能生成各簇实例数量大致相同的聚类结果, 可以分为软平衡聚类与硬平衡聚类, 前者强调平衡只是一个目标, 而不是强制性的要求; 后者强调聚类大小应当被严格设置为一个固定数目. 现有软平衡聚类的方法有: 文献[12]将算法分成3个部分, 先利用重复事件与更新理论对数据集进行抽样获得代表性较高的抽样集, 再利用被平衡约束修改后的K-means算法对抽样集聚类, 最后将那些未被抽样的点利用稳定婚姻匹配算法逐个分配到合适的簇中. 文献[13]利用实例标签信息构造标签分布熵来评价聚类的平衡度, 然后将该熵、模糊隶属度矩阵与标签矩阵之间的平方损失引入FCM模型中. 硬平衡聚类的方法有文献[14]在最小平方和聚类中对每一个簇大小设置约束, 同时利用可变领域启发式方法来寻找最优划分. 文献[15]采用线性规划的方法把每个簇大小作为约束条件, 从而完成平衡聚类.

本文利用实例分布信息扩展EWKM算法, 定义了一种兼顾平衡划分与特征分布的多目标熵, 同时应用该熵提出基于熵的平衡子空间K-means算法, 来解决子空间聚类算法中聚类结果不均衡的问题.

1 熵加权K-means算法

对于给定数据集 $X = [{X_1}, {X_2}, \cdots, {X_n}] \in {R^{n \times D}}$ , 其中 $n$ 为实例集中的实例数量, $D$ 表示实例的维度. 假设数据集 $X$ 划分为 $k$ 类, EWKM算法模型为:

$ \left\{ {\begin{split} & \mathop {\min }\limits_{G, F, W} \sum\limits_{j = 1}^k {\sum\limits_{i = 1}^n {{F_{ij}}\sum\limits_{d = 1}^D {{W_{jd}}{{\left\| {{X_{id}} - {G_{jd}}} \right\|}^2}} } } - \tau {H_F}\\ & {\rm{s.t.}}\left\{ \begin{array}{l} {F_{ij}} \in {\{ 0, 1\} ^{n \times k}}, \displaystyle\sum\limits_{j = 1}^k {{F_{ij}} = 1} \\ {H_F} = - \displaystyle\sum\limits_{j = 1}^k {\displaystyle\sum\limits_{d = 1}^D {{W_{jd}}} \log \left( {{W_{jd}}} \right)}\\ 0 \leqslant {W_{jd}} \leqslant 1, \displaystyle\sum\limits_{d = 1}^D {{W_{jd}} = 1} \end{array} \right. \end{split} } \right.$

(1)

其中, 超参数 $\tau $ 主要用于激励在更多维度上聚类. $F = \{ {F_{ij}}\} \in {R^{n \times k}}$ 为0–1实例隶属矩阵, ${F_{ij}} = 1$ , 表示 ${X_i}$ 属于第 $j$ 簇. $W \in {R^{k \times D}}$ 为特征权重矩阵, ${W_j} = \left( {W_{j1}}, {W_{j2}}, \cdots , \right.$ $ \left.{W_{jD}} \right) $ 为第 $j$ 个簇中不同维度的权重, 权值越大则表示此维度对于该簇的贡献也越大. $G$ 表示聚类中心矩阵. 式(1)中第1项表示簇内距离之和, 第2项是权重熵的和, 目的是避免算法通过极个别维度来识别簇.

算法通过迭代的方式来求解模型, 即固定某两个参数值来求解另一个参数. 聚类中心矩阵 $G$ 、特征权重矩阵 $W$ 和实例隶属矩阵 $F$ 的更新公式如下所示.

在更新聚类中心矩阵 $G$ 时, 固定参数 $F, \; W$ 得:

$ {G}_{jt}=\frac{{\displaystyle \sum _{i=1}^{n}{F}_{ij}{X}_{it}}}{{\displaystyle \sum _{i=1}^{n}{F}_{ij}}}, \; 1\leqslant j\leqslant k, \; 1\leqslant t\leqslant D $

(2)

更新特征权重矩阵 $W$ , 固定参数 $G, \; F$ 得:

$ {W_{jt}} = \dfrac{{\exp \left( {\dfrac{{ - Dis{t_{jt}}}}{\tau }} \right)}}{{ \displaystyle\sum\limits_{d = 1}^D {\exp \left( {\dfrac{{ - Dis{t_{jd}}}}{\tau }} \right)} }} $

(3)

其中, $Dis{t_{jd}} = \displaystyle\sum\limits_{i = 1}^n {{F_{ij}}{{\left\| {{X_{id}} - {G_{jd}}} \right\|}^2}}$ , 表示在维度 $d$ 上, 属于第 $j$ 个簇的实例到该簇中心的距离平方和.

更新实例隶属矩阵 $F$ , 固定参数 $G$ , $W$ 得:

$ {F}_{ij}\text=\left\{\begin{array}{ll} \text{1},& \begin{array}{l}{\rm{if}} \; {\displaystyle \sum _{d=1}^{D}{W}_{jd}{\Vert {X}_{id}-{G}_{jd}\Vert }^{2}\leqslant {\displaystyle \sum _{d=1}^{D}{W}_{td}{\Vert {X}_{id}-{G}_{td}\Vert }^{2}}}\text{, }\\ 1\leqslant t\leqslant k\end{array}\\ \text{0},&\;\; {\rm{otherwise}}\end{array}\right. $

(4)

这里给出EWKM算法的具体步骤如算法1.

算法1. EWKM算法

输入: 数据集 $\scriptstyle X$ , 超参数 $\scriptstyle \tau$ , 聚类簇数 $\scriptstyle k$ 输出: 实例隶属矩阵 $\scriptstyle F$

1) 初始化: 随机选择 $\scriptstyle k$ 个簇中心点, 组成中心点矩阵 $\scriptstyle G$ , 并依据维度数量平均分配每一个簇的初始维度权重向量 $\scriptstyle {W_{j, .}}$ .

2) REPEAT

3) 更新实例隶属矩阵 $\scriptstyle F$ , 固定 $\scriptstyle G$ , $\scriptstyle W$ 利用式(4).

4) 更新聚类中心矩阵 $\scriptstyle G$ , 固定 $\scriptstyle W$ , $\scriptstyle F$ 利用式(2).

5) 更新特征权重矩阵 $\scriptstyle W$ , 固定 $\scriptstyle F$ , $\scriptstyle G$ 利用式(3).

6) UNTIL 目标函数(1)前后两次计算结果不再发生变化.

EWKM算法通过优化模型(1)同时刺激更多特征参与聚类, 避免只利用少量甚至单一特征识别簇的问题. 但是, EWKM算法在其优化过程中没有考虑各个簇实例的分布情况, 不适用于平衡聚类的场景.

2 基于熵的平衡子空间K-means算法

针对EWKM算法中实例分布不均的问题, 本文考虑了聚类过程中常用的平衡约束, 利用平衡分布熵与特征权重熵定义了一个多目标熵, 并在EWKM算法基础上建立了结合该熵的一个新的目标函数, 提出基于熵的平衡子空间K-means算法(entropy-based balanced subspace K-means algorithm (EBSKM), 并给出其求解过程.

2.1 适用于平衡子空间的多目标熵

设 ${p_j}$ 为隶属第 $j$ 个簇的实例个数占全体实例个数的比值可以用矩阵 $F$ 表示为:

$ {p}_{j}=\dfrac{{\displaystyle \sum _{i=1}^{n}{F}_{ij}}}{n}\text{, }\text{ 1}\leqslant {j}\leqslant {k} $

(5)

平衡分布熵公式如式(6)所示:

$ {H_B}\left( p \right) = - \sum\limits_{j = 1}^k {{p_j}\log \left( {{p_j}} \right)} $

(6)

当 ${H_B}\left( p \right)$ 取到最小时, 则所有簇的 ${p_j}$ 数值相等, 此时的聚类结果中各簇实例分布最为平衡. 当 ${H_B}\left( p \right)$ 越大, 则意味着划分越不平衡. 在文献[16]中将该熵作为约束项来保证划分平衡.

平衡子空间的多目标熵定义如式(7):

$ H{\text{ = }}\frac{\alpha }{{\log (k)}}{H_B}{\text{ + }}\frac{{1 - \alpha }}{{k\log (D)}}{H_F} $

(7)

其中, $\alpha $ 为权重系数, $\alpha \in \left[ {0, 1} \right]$ , 当 $\alpha = 0$ 时, 退化为特征加权熵, 当 $\alpha = 1$ 时, 退化为平衡分布熵. $\alpha $ 主要起到控制前后两项熵的重要程度. $1/\log (k)$ , $1/k\log (D)$ 主要是用于平衡这两个熵的影响.

2.2 EBSKM算法模型

为了使得EWKM算法能适用于平衡聚类, 我们在其基础上应用上述的多目标熵, 提出EBSKM的目标函数如式(8)所示:

$\left\{ \begin{split} & \mathop {\min }\limits_{G, F, W, p} \sum\limits_{j = 1}^k {\sum\limits_{i = 1}^n {{F_{ij}}} \sum\limits_{d = 1}^D {{W_{jd}}{{\left\| {{X_{id}} - {G_{jd}}} \right\|}^2}} } - \gamma H \\ & {\rm{s.t.}}\left\{ \begin{array}{l} {F_{ij}} \in {\{ 0, 1\} ^{n \times k}}, \displaystyle\sum\limits_{j = 1}^k {{F_{ij}} = 1} \\ 0 \leqslant {W_{jd}} \leqslant 1, \displaystyle\sum\limits_{d = 1}^D {{W_{jd}} = 1} \end{array} \right. \end{split} \right.$

(8)

$\gamma $ 为超参数. 传统的子空间聚类算法往往侧重于对最具有鉴别能力的特征赋予较高权重, 而忽略了平衡性. EBSKM算法通过引入多目标熵来解决传统算法中平衡性的问题, 同时自适应的特征加权也可以用于分析不同特征对聚类平衡性的贡献程度.

2.3 EBSKM模型求解

在EBSKM算法模型中, 需要求解4个变量, 采取迭代方式来优化.

首先固定 $W, F, p$ 求解聚类中心 $G$ . 聚类中心可以利用实例隶属矩阵 $F$ , 计算不同簇所在实例的平均值作为其聚类中心, 更新公式同式(2).

同样的, 固定 $F, G, p$ 求解 $W$ . 被固定的变量可视为常量, 所以可以消去部分含参项. 当 $0 \leqslant \alpha < 1$ 时, 将目标函数(8)转化为:

$\left\{ { \begin{split} & \mathop {\min }\limits_W \sum\limits_{d = 1}^D {{W_{jd}}Dis{t_{jd}}} + \frac{{\gamma \left( {1 - \alpha } \right)}}{{k\log (D)}}\sum\limits_{d = 1}^D {{W_{jd}}\log \left( {{W_{jd}}} \right)} \\ & {\rm{s.t.}}{\text{ }}0 \leqslant {W_{jd}} \leqslant 1, \sum\limits_{d = 1}^D {{W_{jd}} = 1} \end{split} } \right.$

(9)

由于存在约束条件 $\displaystyle \sum\limits_{d = 1}^D {{W_{jd}} = 1}$ , 构造(9)的拉格朗日函数如下:

$ \begin{split} L\left( {W, \alpha } \right){\text{ = }}&\sum\limits_{d = 1}^D {{W_{jd}}Dis{t_{jd}}} {\text{ + }}\frac{{\gamma \left( {1 - \alpha } \right)}}{{k\log (D)}}\sum\limits_{d = 1}^D {{W_{jd}}\log \left( {{W_{jd}}} \right)} \\ & -\alpha \left( {\sum\limits_{d = 1}^D {{W_{jd}} - 1} } \right) \end{split} $

(10)

其中, $\alpha $ 为拉格朗日乘子, 对 $W$ 和 $\alpha $ 分别求偏导令其为零, 得到如下方程:

$ \frac{{\partial L\left( {W, \alpha } \right)}}{{\partial \alpha }} = \sum\limits_{d = 1}^D {{W_{jd}} - 1} = 0 $

(11)

$ \frac{{\partial L\left( {W, \alpha } \right)}}{{\partial {W_{jt}}}}{\text{ = }}Dis{t_{jt}}{\text{ + }}\frac{{\gamma \left( {1 - \alpha } \right)}}{{k\log (D)}}\left( {1{\text{ + }}\log \left( {{W_{jt}}} \right)} \right) - \alpha = 0 $

(12)

求解式(11)、式(12)得特征权重更新公式:

$ {W_{jt}} = \dfrac{{\exp \left( {\dfrac{{ - k\log (D)Dis{t_{jt}}}}{{\gamma \left( {1 - \alpha } \right)}}} \right)}}{{ \displaystyle \sum\limits_{d = 1}^D {\exp \left( {\dfrac{{ - k\log (D)Dis{t_{jd}}}}{{\gamma \left( {1 - \alpha } \right)}}} \right)} }} $

(13)

当 $\alpha = 1$ 时, $H$ 只有平衡分布熵起作用.

在求解实例隶属矩阵 $F$ 以及平衡分布向量 $p$ 时, 利用交替方向乘子法(ADMM)来同时优化这两个参数, 通过引入拉格朗日乘子 ${\lambda _j} \; (j = 1, \cdots , k)$ , 同时固定其他变量, 得到目标函数(8)的增广拉格朗日方程:

$\left\{ { \begin{split} &{L_\mu }\left( {F, p, \lambda } \right){\text{ = }}\sum\limits_{j = 1}^k {\sum\limits_{i = 1}^n {{F_{ij}}} \sum\limits_{d = 1}^D {{W_{jd}}{{\left\| {{X_{id}} - {G_{jd}}} \right\|}^2}} } \\& \qquad\qquad\;\;\; + \frac{{\gamma \alpha }}{{\log (k)}} \displaystyle\sum\limits_{j = 1}^k {{p_j}\log \left( {{p_j}} \right)} {\text{ + }}\sum\limits_{j = 1}^k {{\lambda _j}\left( {{p_j} - \dfrac{{ \displaystyle\sum\limits_{i = 1}^n {{F_{ij}}} }}{n}} \right)} \\& \qquad\qquad\;\;\; + \frac{\mu }{2}\displaystyle\sum\limits_{j = 1}^k {{{\left( {{p_j} - \frac{{\displaystyle\sum\limits_{i = 1}^n {{F_{ij}}} }}{n}} \right)}^2}} \\ &{\rm{s.t.}}{\text{ }}{F_{ij}} \in {\{ 0, 1\} ^{n \times k}}, \sum\limits_{j = 1}^k {{F_{ij}} = 1} \end{split} } \right. $

(14)

其中, $\;\mu > 0$ 为惩罚参数. ADMM算法优化参数的迭代更新式如下:

$ {p^{(t + 1)}} = \arg \mathop {\min }\limits_p {L_\mu }\left( {{F^{(t)}}, p, {\lambda ^{(t)}}} \right) $

(15)

$ {F^{(t + 1)}} = \arg \mathop {\min }\limits_F {L_\mu }\left( {F, {p^{(t + 1)}}, {\lambda ^{(t)}}} \right) $

(16)

更新拉格朗日乘子:

$ \left\{ {\begin{array}{*{20}{l}} {{\lambda _j}^{(t + 1)}{\text{ = }}{\lambda _j}^{(t)}{\text{ + }}{\mu ^{(t)}}\left( {{p_j}^{(t + 1)} - \dfrac{{ \displaystyle\sum\limits_{i = 1}^n {{F_{ij}}^{(t + 1)}} }}{n}} \right), 1 \leqslant j \leqslant k} \\ {{\mu ^{(t + 1)}} = \rho {\mu ^{(t)}}} \end{array}} \right. $

(17)

其中, $\;\rho > 1$ 是一个给定的参数.

求解向量 $p$ , 利用式(15)可将向量 $p$ 分为 $k$ 个子问题, 其中第 $j$ 项为:

$ \mathop {\min }\limits_{{p_j}} \frac{{\gamma \alpha }}{{\log (k)}}{p_j}\log {p_j} + {\lambda _j}{p_j} + \frac{\mu }{2}{p_j}^2 - \mu {p_j}{\beta _j} $

(18)

其中, $\;{\beta _j} = \displaystyle\sum\limits_{i = 1}^n {{F_{ij}}} /n < 1$ . 对式(18)求导令其为0得求解 ${p_j}$ 公式如式(19)所示:

$ \frac{{\gamma \alpha }}{{\log (k)}}\log {p_j} + \mu {p_j} + {\lambda _j} + \frac{{\gamma \alpha }}{{\log (k)}} - \mu {\beta _j} = 0 $

(19)

求解 $F$ 时, 借鉴文献[16]的思想, 采用逐行求解的方式, 即对每一个实例求出当前状态下的最优分配方案. 由式(16)得 ${F_{i.}}$ 求解公式:

$\left\{ { \begin{split} & \mathop {\min }\limits_{{F_{i.}}} \sum\limits_{j = 1}^k {\sum\limits_{i = 1}^n {{F_{ij}}} \sum\limits_{d = 1}^D {{W_{jd}}{{\left\| {{X_{id}} - {G_{jd}}} \right\|}^2}} } \\ & \quad - \sum\limits_{j = 1}^k {\frac{{{\lambda _j}{F_{ij}} + \mu {p_j}{F_{ij}}}}{n}} + \sum\limits_{j = 1}^k {\frac{{\mu {F_{ij}}^2 + \mu {F_{ij}}\displaystyle\sum\nolimits_{i \ne j} {{F_{ij}}} }}{{2{n^2}}}} \\ &{\rm{s.t.}}{\text{ }}{F_{ij}} \in {\{ 0, 1\} ^{n \times k}}, \sum\limits_{j = 1}^k {{F_{ij}} = 1} \end{split} } \right.$

(20)

从约束条件可以看出, 每一个实例只允许被分配到一个簇中. 因此, 在求解 ${F_{i.}}$ 时, 会有 $k$ 个候选项, 每个候选项代表实例i属于第j簇的情况. 然后把这 $k$ 个候选项分别带入式(20)中, 选择函数值最小的那个候选项作为 ${F_{i, .}}$ 的解. 之后不断循环这一过程直到 $F$ 不再变化, 即可得到完整的实例隶属矩阵 $F$ . 在优化 $F$ , $p$ 时, 很难同时对这两个变量进行优化, 因此利用ADMM算法对这两个变量进行分块优化, 其优势在于将大的全局问题分解为多个较小、较容易求解的局部子问题, 并通过协调子问题的解而得到大的全局问题的解, 以此来降低其优化难度.

算法2 ADMM算法求解 $F, p$ 的具体流程.

算法2. ADMM算法求解F, p

输入: X, W, G, 超参数γ, α, 聚类簇数k输出: F, p

1) 初始化: μ, ρ

2) REPEAT

3) 更新p利用式(19).

4) 更新F利用式(20).

5) 更新拉格朗日乘子, 利用式(17).

6) UNTIL 算法收敛

算法2中 $\;\mu $ 初始化值为1, $\;\rho $ 初始化值为1.1.

综合以上, EBSKM算法求解的具体流程如算法3.

算法3. EBSKM算法

输入: 数据集X, 超参数γ, α, 聚类簇数k 输出: 实例隶属矩阵F

1) 初始化: [G, F] = kmeans(X, k)

2) REPEAT

3) 更新W, 固定F, G, p利用式(13).

4) 更新G, 固定W, F, p利用式(2).

5) 更新F, p, 利用算法2.

8) UNTIL F 不再变化停止.

3 实验分析

为了验证EBSKM算法的有效性, 本文实验采用4个UCI数据集、10个UCR数据集以及1个公开的图像数据集, 用于比较EBSKM、K-means、EWKM、W-K-means^[17]、OMBC^[15]、FSBC^[16]的聚类性能.

3.1 数据集及预处理

Iris、Wine、Seeds、Digit来自UCI, Trace、Plane、SmoothSubspace (SMS)、Face (four)、Symbols、FacesUCR、ElectricDevices、HandOutlines、Mallat、StarLightCurves来自UCR, Jaffe是来自公开的图像数据集. 因为本文所针对的实际应用场景是平衡聚类问题, 即要求所有的簇的实例个数要相同, 所以本文对每一组数据集中所有类别的实例个数随机删减至相同. 例如Wine数据集原来的样本总量为178, 每个簇的实例数量为59、71、48, 对大于最小规模的簇随机选择实例, 并删减至每个簇大小为48. 每组数据集都采用Z-Score标准化, 实验具体数据如表1所示.

3.2 评价指标

本文通过利用标准互信息(NMI)来评价所有聚类算法的聚类性能, 利用标准熵(NE)来评价聚类结果的平衡性.

NMI定义如下:

$ MI(X, Y){\text{ = }}\sum\limits_{{x_i} \in X, {y_j} \in Y} {p({x_i}, {y_j})\log \left( {\frac{{p({x_i}, {y_j})}}{{p({x_i})p({y_j})}}} \right)} $

(21)

$ {\textit{NMI}}(X, Y){\text{ = }}2\frac{{MI(X, Y)}}{{H(X) + H(Y)}} $

(22)

其中, H(X), H(Y)表示类集X, Y的熵, $p(\cdot)$ 表示概率. NMI的值越大说明算法的聚类性能越好.

NE定义如下:

$ NE = - \frac{1}{{\log \left( k \right)}}\sum\limits_{i = 1}^k {{p_i}\log \left( {{p_i}} \right)} $

(23)

NE=1时表明聚类结果完全平衡, NE=0表示聚类结果完全不平衡. 例如一个含有3个簇的数据集, 其聚类实例分布数量比例为1/3, 1/2, 1/6, 可以认为该结果是不平衡的, 此时的NE为0.9206.

3.3 实验结果

本文提出的算法在实验中设置参数 $\alpha $ 为0.6, $\gamma $ 为200, 对于其他比较方法, EWKM $\gamma {\text{ = 0}}{\text{.5}}$ , W-K-means $\beta {\text{ = }} 8$ , FSBC $\lambda {\text{ = }}{n^2} \times {10^2}, \tau = {10^2}$ . 上述算法参数设置都是基于其论文中所给建议设置的. 在算法的对比实验中, 实验结果为10次5折交叉验证的平均值. 对比实验的NMI结果如表2所示, NE结果如表3所示.

从表2对比实验可知, EBSKM在大部分数据集中都表现出最佳效果. 可以证明所提出的模型在聚类任务中是有效的. 从表3可知由于OMBC算法是硬平衡聚类, 所以它的平衡性都达到了1. 本文所出的算法相比传统算法在平衡性的表现上都是最好水平. 可以分析出加入平衡约束有助于算法模型更均匀划分. 数据集不平衡划分会导致在划分独立子空间时, 由于各簇样本数量不同, 对于样本数量较少的簇会产生偏差从而影响聚类精度.

3.4 实验参数设置

本节主要讨论算法中超参数 $\alpha $ 与 $\gamma $ 的选择情况.

(1)讨论 $\alpha $ 的取值

探究超参数 $\alpha $ 对算法性能的影响, 我们在0到1之间, 间距设置为0.01, 测试 $\alpha $ 不同取值对算法性能的影响. 分别在Wine、Seeds和Digit数据集进行测试.

图1为 $\alpha $ 不同取值对EBSKM算法的影响情况. 横坐标为 $\alpha $ 的取值, 纵坐标为对应的NMI值. 从图中可见 $\alpha $ 取值过大或过小都会使算法性能产生波动, 可以看出平衡约束和特征选择同时起作用的时候算法才可以趋向更好的性能. 因此, 本文将超参数 $\alpha $ 统一取为0.6.

(2)讨论 $\gamma $ 的取值

研究超参数 $\gamma $ 对算法性能的影响, 我们在1到500之间, 间距设置为10, 测试 $\gamma $ 的不同取值对算法性能的影响.分别在Wine、Seeds和Digit数据集进行测试.

图2为 $\gamma $ 不同取值对EBSKM算法的影响情况. 其横坐标为 $\gamma $ 的取值, 纵坐标为对应的NMI值. 从图中可以看出 $\gamma $ 取值过小时, 会使算法性能产生不稳定的结果. 因此, 本文将超参数 $\gamma $ 统一取为200.

4 结论与展望

针对EWKM算法, 聚类结果不平衡的问题, 本文提出将平衡约束加入到原本算法模型中, 提出在独立子空间上的软平衡聚类算法EBSKM算法, 通过UCI和UCR等数据集上进行实验, 所提出的算法在聚类性能和平衡性能上均展现出更好的效果. 但是, 实验过程中参数选择会直接影响算法性能, 因此如何合理选取算法中的参数, 是进一步要解决的问题.