拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法

An Entropy Clustering Method for the Model and Its Algorithm of the Maximizing a Submodular Function Subject to a Matroid Constraint

摘要: 本文提出了一个新的带有信息熵的聚类目标函数，它是由基于图论的随机路径的熵率和平衡项两部分组成。熵率有利于形成紧凑和均匀的聚类，平衡函数鼓励相似度比较高的对象才能聚类，并惩罚那些相似度比较低的对象。首先构造了与数据关联的赋权无向图，并发现这种构造诱导出一个拟阵，它是一个组合在向量空间中推广线性独立概念的结构。接着得到了拟阵约束下最大化子模函数的模型。最后根据目标函数的单调性、递增性和下模性，开发了一个高效的贪婪算法并讨论了它的性能保证。最后根据数值实验，与已有的算法做了比较，说明了该算法的有效性。

Abstract: This paper proposes a new clustering objective function with information entropy, which is composed of entropy rate of random path based on graph theory and balance item. Entropy rate is conducive to compact and uniform clustering, the balance function encourages objects with high similarity to cluster, and punishes those objects with low similarity. First, the weighted undirected graph associated with data is constructed, and it is found that this structure induces a matroid, a combination of the structure of linear independent concept in vector space. Then, the model of which is maximizing a submodular function under the constraints of the matroid is obtained. Finally, according to the monotonicity, increment and submodular of the objective function, an efficient greedy algorithm is developed and its performance guarantee is discussed.

1. 引言

聚类是在机器学习中的一种无监督学习方式，既是数据挖掘的重要部分，又是模式识别领域的基础问题 [1] [2] ，在统计学里也有广泛的引用。在几乎每个处理经验数据的科学领域里，研究人员试图通过识别相似字符组的数据获得第一印象。在不同的领域已经提出了很多种聚类方法，并且都有性能保证。然而，它们通常是基于不同的假设，而且很难在同一个标准下比较。此外，最理想的标准会导致成NP-hard问题。因此聚类的进一步发展就是对存在理论证明或更新的问题的目标函数的精细化设计。

在各种各样的聚类算法中，一些使用单个目标函数，一些递归地使用中间成本函数，以及一些基于数据点的投影(子空间，流形)。制定聚类问题作为一个图拓扑选择问题，当数据点及其对应关系分别映射到图中的顶点和边。然后通过查找图拓扑来解决聚类问题。主要考虑紧凑的、均匀的、平衡的类别。在一个紧凑的类别中，数据点彼此接近。为了获得以上这些性质，我们提出了一个新的由两部分组成的目标函数：一是图上的随机路径的熵率；二是类分布的平衡项。熵率 [3] 有利于形成紧凑和均匀的聚类，平衡函数鼓励相似度比较高的聚类，并惩罚那些相似度比较差的对象。根据图中的随机路径和类别的分布有很大的不确定性，构造一个图拓扑。

本文把聚类作为一个图划分问题，将图划分为 $k$ 个群，研究具有 $k$ 连通子图的图拓扑，并最大化所提出的目标函数。

2. 模型

2.1. 基础知识

图：无向图表示为 $G=\left(V,E\right)$ ，其中 $V$ 是顶点的集合， $E$ 是边的集合。 $v_i$ 和 $e_{i,j}$ 表示顶点与边。 $w_{i,j}$ 表示顶点 $v_i$ 和 $v_j$ 之间边 $e_{i,j}$ 上的权重。在无向图中边的权重是对称的，即 $w_{i,j}=w_{j,i}$ 。

图的划分 [4] ：在 $G=\left(V,E\right)$ 中，如果 $V=\left\{V_1,V_2,\cdots ,V_K\right\}$ ，且满足：

(1) $V_i\cap V_j=\Phi ,i\ne j$ ；(2) ${\displaystyle \underset{i=1}{\overset{K}{\cup }}{V}_i}=V$ ，

则称 $V_1,V_2,\cdots ,V_K$ 为 $V$ 的一个划分。图的顶点的子集的选择问题就是图的划分问题。

本文的目标是选择边的子集 $A\in E$ ，使得子图 $\left(V,A\right)$ 是K-连通的。

熵：用来度量随机变量的不确定性。设离散随机变量 $X$ ，概率密度函数为 $p_X$ ，则它的熵定义为：

$H\left(X\right)=-{\displaystyle \sum p_X}\left(x\right)\log p_X\left(x\right),$ (1)

相应的，条件熵 $H\left(X|Y\right)$ 的定义为：

$\begin{array}{c}H\left(X|Y\right)=-{\displaystyle \sum p_Y}\left(y\right)H\left(X|Y=y\right)\\ =-{\displaystyle \sum p_Y}\left(y\right){\displaystyle \sum p_{X|Y}}\left(x|y\right)\log p_{X|Y}\left(x|y\right),\end{array}$ (2)

其中 $p_{X|Y}$ 是条件概率密度函数 [5] [6] 。

熵率：用来度量随机过程 $X=\left\{X_t|t\in T\right\}$ 的不确定性。对于一个离散的随机过程，熵率定义为一个渐近测度 [7] ：

$H\left(X\right)=\underset{t\to \infty }{\lim }H\left(X_t|X_{t-1},X_{t-2},\cdots ,X_1\right),$ (3)

对于一阶平稳的马尔可夫过程，熵率有一个简单的形式 [8] [9] ：

$H\left(X\right)=\underset{t\to \infty }{\lim }H\left(X_t|X_{t-1}\right)=\underset{t\to \infty }{\lim }H\left(X_2|X_1\right)=H\left(X_2|X_1\right).$ (4)

第一个等式是由于一阶马尔可夫性，而第二个等式是平稳性的结果。有关更多详细信息，可以参考 [10] 。

图上的随机路径：设 $X=\left\{X_t|t\in T,X_t\in V\right\}$ 是带有非负的相似权 $\omega$ 的图 $G=\left(V,E\right)$ 上的随机路径。转移概率定义为：

$p_{i,j}=\mathrm{P}\left(X_{t+1}=v_j|X_t=v_i\right)=\frac{{\omega }_{i,j}}{{\omega }_i},$ (5)

其中 ${\omega }_i={\displaystyle {\sum }_{k:e_{i.k\in E}}{\omega }_{i,k}}$ 是顶点 $v_i$ 发生事件之和，并且平稳分布为：

$\mu ={\left({\mu }_1,{\mu }_2,\cdots ,{\mu }_{\left|V\right|}\right)}^{\text{T}}={\left(\frac{{\omega }_1}{{\omega }_T},\frac{{\omega }_2}{{\omega }_T},\cdots ,\frac{{\omega }_{\left|V\right|}}{{\omega }_T}\right)}^{\text{T}},$ (6)

其中 ${\omega }_T={\displaystyle {\sum }_{i=1}^{\left|V\right|}{\omega }_i}$ 是归一化常数。对于一个非连通图，平稳分布不是唯一的。但是，(6)式中的 $\mu$ 总是

平稳分布，容易证明得到 $\mu =P^{\text{T}}\mu$ ，其中 $P=\left[p\right]{}_{i,j}$ 是转移矩阵。随机路径的熵率为：

$\begin{array}{c}H\left(X\right)=H\left(X_2|X_1\right)={\displaystyle {\sum }_i{\mu }_i}H\left(X_2|X_1=v_i\right)\\ =-{\displaystyle {\sum }_i{\displaystyle {\sum }_j\frac{{\omega }_{i,j}}{{\omega }_T}}}\log \frac{{\omega }_{i,j}}{{\omega }_T}+{\displaystyle {\sum }_i\frac{{\omega }_i}{{\omega }_T}}\log \frac{{\omega }_i}{{\omega }_T}\end{array}$ (7)

下模性 [11] ：设 $E$ 是有限集，函数 $f:2^E\to R$ 是下模函数当且仅当 $\forall A,B\subseteq E,\forall a_1,a_2\in E$ ，有

$f\left(A\right)+f\left(B\right)\ge f\left(A\cup B\right)+f\left(A\cap B\right).$

或 $f\left(A\cup \left\{a_1\right\}\right)-f\left(A\right)\ge f\left(A\cup \left\{a_1,a_2\right\}\right)-f\left(A\cup \left\{a_2\right\}\right)$ (8)

等价于： $\delta f_{a_1}\left(A\right)\ge \delta f_{a_1}\left(A\cup \left\{a_2\right\}\right)$ ，对于所有的 $A\subseteq E$ 和 $a_1,a_2\in E\backslash A$ ，其中

$\delta f_{a_1}\left(A\right)=f\left(A\cup \left\{a_1\right\}\right)-f\left(A\right)$

进一步地，如果 $f\left(A\right)\le f\left(A\cup \left\{a_1\right\}\right)$ ，则称 $f$ 是单调递增函数 [12] 。

拟阵：设 $E$ 是有限集， $I$ 是 $E$ 的子集组成的集合，拟阵是一个有序对 $M=\left(E,I\right)$ ，并且满足：

1) $\Phi \in I$ 。

2) 如果 $I_1\in I$ 且 $I^{\prime }\subseteq I_1$ ，则 $I^{\prime }\in I$ 。

3) 如果 $I_1\in I,I_2\in I$ 且 $\left|I_1\right|<\left|I_2\right|$ ，则存在元素 $e\in I_2-I_1$ ，使得 $I_1\cup e\in I$ 。

我们提出聚类作为一个图的划分问题。将图划分为 $k$ 个类，搜索图具有 $k$ 连通子图的拓扑，然后最大化提出的目标函数。

2.2. 图的构造

将数据集映射到图 $G=\left(V,E\right)$ ，顶点表示该数据点和边权重表示两数据点之间的相似性。为了聚类，将数据集映射成K-最近邻域图。目标是划分图成为几个连通分支。选择一个边的子集 $A\subseteq E$ ，产生一个子图 $G^{\prime }=\left(V,A\right)$ ，包含K-连通子图。再者，我们也假设每个顶点具有自环。虽然自环不影响图的划分，但它们对提出的随机路径模型是必要的。当某边不包含在 $A$ 内时，增加与该边关联顶点的自环的权重，这样每个顶点的总发生的权保持常数。

如果边 $e_{i,j}$ 是被聚类时选择了，则顶点 $v_i$ 的自环的权为 ${\omega }_{i,i}$ ，顶点 $v_j$ 的自环的权为 ${\omega }_{j,j}$ ，边 $e_{i,j}$ 的权为 ${\omega }_{i,j}$ 。

如果边 $e_{i,j}$ 是被聚类时未选择，则顶点 $v_i$ 的自环的权为 ${\omega }_{i,i}\to {\omega }_{i,i}+{\omega }_{i,j}$ ，顶点 $v_j$ 的自环的权为 ${\omega }_{j,j}\leftarrow {\omega }_{j,j}+{\omega }_{i,j}$ ，边 $e_{i,j}$ 的权为 ${\omega }_{i,j}\leftarrow 0$ 。

2.3. 平衡函数

利用平衡函数鼓励大小相似的数据点分到同一个聚类中。设 $A$ 是已经被选择的边集， $N_A$ 是图中被划分部分的数量， $Z_A$ 是聚类的分布。例如，设图对边集 $A$ 的划分是 $S_A=\left\{S_1,S_2,\cdots ,S_{N_A}\right\}$ ，有

$p_{Z_A}\left(i\right)=\frac{\left|S_i\right|}{\left|V\right|},i=\left\{1,2,\cdots ,N_A\right\},$ (9)

并且平衡项为：

${\rm B}\left(A\right)\equiv H\left(Z_A\right)-N_A=-{\displaystyle {\sum }_i{p}_{Z_A}\left(i\right)}\log \left(p_{Z_A}\left(i\right)\right)-N_A.$ (10)

熵 $H\left(Z_A\right)$ 将大小相似的聚为一类，同时通过类与类数据点之间的最小化可以得到聚类数目 $N_A$ 。

推论2：2.2中构造的图上的平衡函数 ${\rm B}:2^E\to R$ 是一个单调递增的下模函数。

2.4. 聚类函数

目标函数是熵率和平衡函数的结合，因此得到了更加紧凑的、均匀的和平衡的聚类。

$\begin{array}{l}\underset{A\subseteq E}{\max }F\left(A\right)\\ \text{s}\text{.t}\text{.}{N}_A\ge K\end{array}$ (11)

其中 $F\left(A\right)=H\left(A\right)+\lambda {\rm B}\left(A\right)$ 是目标函数。参数 $\lambda \ge 0$ 是平衡项的权重。目标函数也是单调递增的下模函数。

推论3：设 $E$ 是边集， $I$ 是边集的集合， $A\subseteq E$ 满足：1) $A$ 是无循环的；2) $A$ 构成一个大于或等于K-连通分支的图划分，则 $M=\left(E,I\right)$ 是一个拟阵。

在无循环的约束下，图的划分问题变成了在拟阵约束下子模函数的最大化问题，即：

$\begin{array}{l}\underset{A\subseteq E}{\max }F\left(A\right)\\ \text{s}\text{.t}\text{.}A\in I\end{array}$ (12)

3. 算法

对于求解模型(12)的贪婪算法如下：

拟阵约束的下模函数的最大化问题是组合优化研究中活跃的领域 [13] ，Fisher [14] 等给出了单调递增下模函数的最大化问题的以 $\frac{1}{2}$ 近似上界的贪婪算法。同样地，我们也给出如下的性能保证：

定理：设 $A_{opt}$ 是问题(15)的最优解， $A_{greedy}$ 是应用上述算法得到的一个近似解，则

$\frac{F\left(A_{greedy}\right)-F(\varnothing )}{F\left(A_{opt}\right)-F(\varnothing )}\ge \frac{1}{2}$

证明利用 [14] theorem2.1直接得到。

4. 实验

在聚类方面我们进行了大量的实验来评估所提出的算法方法，在整个实验中，使用了 ${\lambda }^{\prime }=0.5$ 来测定平衡权重。该算法需要成对相似性数作为输入，这里使用的是高斯核 $\omega \left(v_i,v_j\right)=\exp \left(-\frac{d{\left(v_i,v_j\right)}^2}{2{\sigma }^2}\right)$ ，这里 $d\left(v_i,v_j\right)$ 是样本 $i$ 和 $j$ 之间的距离， $\sigma$ 是核带宽。然后构造一个邻域图1，其中在群集之前，每个示例都连接到其30个最近的邻域。

在实验中，我们设置了聚类的个数对于所有算法的数字K，为了比较，使用以下两个标准的群集性能指标：1) 聚类精度(ca)和2) rand指数(ri)：

聚类精度是一种分类精度性能指标。设 $ℂ=\left\{C_1,C_2,\cdots ,C_K\right\}$ 是聚类的真分布。类似地，设 $S=\left\{S_1,S_2,\cdots ,S_K\right\}$ 是计算的聚类的分布。聚类精度为：

$CA=\underset{J}{\max }\frac{1}{n}{\displaystyle \underset{i}{\sum }\left|C_i\cap S_{J\left(i\right)}\right|},$

其中 $n$ 是数据中的样本总数和 $J$ 表示任意可能的排列 $\left\{1,2,\cdots ,K\right\}$ 。

聚类指数是两者之间的相似性度量。设TP是相同的样本对的数量群集的真实性和估计聚类，设TN是在中的样本对的数目真实与估计的不同聚类聚类，设FP是对的示例对的数量在不同的集群中为真实的集群在同一个组中进行估计聚类，FN是样本对的数目这在同一个群中是真实的聚类，但在不同的集群中估计的聚类输出。聚类指数为：

$RI=\frac{\text{TP}+\text{TN}}{\text{TP}+\text{TN}+\text{FP}+\text{FN}}$

我们比较我们的结果和已有的聚类算法包括AP、k-means、ncut，以及平面最大间隔聚类算法(cpmmc) [16] ，它们代表了各种各样的聚类，结果如下：

Figure 1. The image comes from the natural scene recognition dataset [15] . From left to right, the image is coast, forest, highway, inner city, mountains, open country, streets and tall buildings. Because of different imaging conditions, the same kind of image shows a great change place and season

图1. 图像来自自然场景识别数据集 [15] 。从左到右，图像类是海岸、森林、高速公路、内部城市，山，开放的乡村，街道和高楼。由于不同的成像条件，相同类的图像表现出很大的变化地点和季节

Table 1. Clustering performance comparison: clustering accuracy

表1. 聚类性能比较：聚类精度

Table 2. Clustering performance comparison: clustering index

表2. 聚类性能比较：聚类指数

从表1和表2，我们看到了所提出的算法在聚类中产生略好的性能。根据聚类精度度量，在12个数据集中的7个数据集上的算法优于其它算法。我们还获得更好的性能索引：在12个数据集中有8个更好。

基金项目

陕西省自然科学基金资助项目(20125153025)；中国高等教育博士生研究基金资助项目(20126102110041)。