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

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.