计算机科学与应用    Vol.7 No.10 (October 2017)

拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法
An Entropy Clustering Method for the Model and Its Algorithm of the Maximizing a Submodular Function Subject to a Matroid Constraint

作者: 梁国宏 ：西北工业大学计算机学院，陕西 西安;空军工程大学理学院，陕西 西安; 李 映 ：西北工业大学计算机学院，陕西 西安; 叶 萌 ：94826部队，上海; 李炳杰 ：空军工程大学理学院，陕西 西安;

关键词: 聚类； 图理论； 信息理论； 子模函数； 离散优化； Clustering； Graph Theory； Information Theory； Submodular Function； Discrete Optimization

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

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.

文章引用: 梁国宏 , 李 映 , 叶 萌 , 李炳杰 (2017) 拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法。 计算机科学与应用， 7， 994-1001. doi: 10.12677/CSA.2017.710112

参考文献

[1] Liu, M.Y., Tuzel, O., Ramalingam, S. and Chellappa, R. (2014) Entropy-Rate Clustering: Cluster Analysis via Maximizing a Submodular Function Subject to a Matroid Constraint. IEEE Transactions on Pattern Analysis and Machine Intelligence.

[2] Ye, X. and Guo, L.J. (2012) Consructing Affinity Matrix in Spectral Clustering Based on Neighbor Propagation. Neu-rocomputing.

[3] Lin, H. and Bilmes, J. (2011) Word Alignment via Submodular Maximization over Matroids. Proceedings of the 49th Annual Meeting of the Association Computational Linguistics: Human Language Technologies—Short Papers, 2, 170-175.

[4] Cao, J., Chen, P., Zheng, Y. and Dai, Q. (2013) A Max-Flow-Based Similarity Measure for Spectral Clustering. ETRI Journal, 35.

[5] Chakrabarti, A. and Kale, S. (2013) Submodular Maximization Meets Streaming: Matchings, Matroids, and More. Data Structures and Algorithms.

[6] Liu, M.Y., Tuzel, O., Ramalingam, S. and Chellappa, R. (2011) Entropy Rate Superpixel Segmentation. IEEE Conference on Compute Vision and Pattern Recognition.

[7] Zhang, X., Li, J. and Yu, H. (2011) Local Density Adaptive Similarity Measurement for Spectral Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32, 352-358.

[8] Cover, T.M. and Thomas, J.A. (1991) Elements of Information Theory. 2nd Edition, John Wiley & Sons.
https://doi.org/10.1002/0471200611

[9] Hua, L. (2014) Application of Spectral Clustering and Entropy in Clustering. Zhejiang University, 25-29.

[10] Liu, M.-Y., Tuzel, O., Ramalingam, S. and Chellappa, R. (2014) Entropy-Rate Clustering: Cluster Analysis via Maximizing a Submodular Function Subject to a Matroid Constraint. Pattern Analysis and Machine Intelligence, 36, 99-105.

[11] Nemhauser, G.L., Wolsey, L.A. and Fisher, M.L. (1978) An Analysis of the Approximations for Maximizing Submodular Set Functions. Mathematical Programming, 14, 265-294.
https://doi.org/10.1007/BF01588971

[12] Oxley, J. (1992) Matroid Theory. Oxford Univ. Press, Oxford.

[13] Badanidoyuri, A. and Vondrak, J. (2014) Fast Algorithms for Maximizing Submodular Functions. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 1497-1514.
https://doi.org/10.1137/1.9781611973402.110

[14] Fisher, M.L., Nemhauser, G.L. and Wolsey, L.A. (1978) An Analysis of the Approximations for Maximizing Submodular Set Functions. Mathematical Programming, 8, 73-87.
https://doi.org/10.1007/BFb0121195

[15] Oliva, A. and Torralba, A. (2001) Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope. International Journal of Computer Vision, 42, 145-175.
https://doi.org/10.1023/A:1011139631724

[16] Frey, B.J. and Dueck, D. (2007) Clustering by Passing Messages between Data Points. Science, 315, 972-976.
https://doi.org/10.1126/science.1136800

分享
Top