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

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

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

在各种各样的聚类算法中，一些使用单个目标函数，一些递归地使用中间成本函数，以及一些基于数据点的投影(子空间， 流形)。

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

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

2. 模型 2.1. 基础知识 图：无向图表示为(), GV E=， 其中V 是顶点的集合，E 是边的集合。iv 和, i je表示顶点与边。

, i jw表