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

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

作　　者：梁国宏 李映[1] 叶萌[3] 李炳杰 

机构地区：[1]西北工业大学计算机学院,陕西西安 [2]空军工程大学理学院,陕西西安 [3]94826部队,上海

出　　处：《计算机科学与应用》2017年第10期994-1001,共8页Computer Science and Application

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

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

关 键 词：聚类 图理论 信息理论 子模函数 离散优化 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]