拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法
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