计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 | 
计算数学  2018, Vol. 40 Issue (4): 354-366    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
一种连续的谱聚类优化模型
刘歆1,2, 吴国宝3, 张瑞1,2, 张在坤4
1. 中国科学院数学与系统科学研究院, 科学与工程计算国家重点实验室, 北京 100190;
2. 中国科学院大学, 北京 100190;
3. 香港浸会大学数学系;
4. 香港理工大学应用数学系
A NEW CONTINUOUS OPTIMIZATION MODEL FOR SPECTRAL CLUSTERING
Liu Xin1,2, Michael Ng3, Zhang Rui1,2, Zhang Zaikun4
1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;
2. University of Chinese Academy of Sciences, Beijing 100190, China;
3. Hong Kong Baptist University, China;
4. Hong Kong Polytechnic University, China
 全文: PDF (582 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 聚类与图的划分问题在大数据分析中有着重要的应用.这类问题一般被描述为组合优化问题,因此较难快速求解.本文设计了一种新的连续优化模型,并提出了一种块坐标下降算法,数值实验显示我们的新方法在求解聚类与图的划分问题上很有潜力.我们还更进一步分析了我们的连续优化模型和组合优化模型的关系.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词聚类   图的划分   块坐标下降     
Abstract: Clustering and graph partition play an important role in big data analysis. These problems are often formulated as combinatorial optimization models. Consequently, to solve them efficiently is difficult. In this paper, we propose a novel continuous optimization model, and a block coordinate decent method to solve it. Numerical experiments show that the new approach has great potential in dealing with clustering and graph partition problems. We also give preliminary analysis on the relationship between our model and the original combinatorial optimization model.
Key wordsClustering   graph partition   block coordinate decent   
收稿日期: 2018-03-06;
基金资助:

国家自然科学基金项目(11622112,11471325,91530204和11688101);国家数学与交叉科学中心;香港研究资助局(RGC)基金项目(PolyU 253012/17P,N_PolyU504/14,HKBU RC-ICRS/16-17/03);香港理工大学科研启动基金项目1-ZVHT资助.

引用本文:   
. 一种连续的谱聚类优化模型[J]. 计算数学, 2018, 40(4): 354-366.
. A NEW CONTINUOUS OPTIMIZATION MODEL FOR SPECTRAL CLUSTERING[J]. Mathematica Numerica Sinica, 2018, 40(4): 354-366.
 
[1] Chung F. Spectral Graph Theory. Number 92 in Regional Conferences in Mathematics. American Mathematical Society, Providence, 1997.
[2] Donath W E and Hoffman A J. Algorithms for partitioning graphs and computer logic based on eigenvectors of connection matrices[J]. IBM Technical Disclosure Bulletin, 1972, 15(3):938-944.
[3] Donath W E and A. J. Hoffman A J. Lower bounds for the partitioning of graphs[J]. IBM Journal of Research and Development, 1973, 17(5):420-425.
[4] Hagen L and Kahng A B. New spectral methods for ratio cut partition and clustering[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992, 11(9):1074- 1085.
[5] Lütkepohl H. Handbook of matrices. John Wiley & Sons, New York, 1996.
[6] Mohar B. The Laplacian spectrum of graphs. In Y. Alavi, G. Chartrand, O. R. Oellermann, and J. Schwenk, A, editors, Graph Theory, Combinatorics, and Applications:Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, volume 2, pages 871-898. Wiley, New York, 1991.
[7] Mohar B. Some applications of Laplace eigenvalues of graphs. In G. Hahn and G. Sabidussi, editors, Graph Symmetry:Algebraic Methods and Applications, volume 497 of Nato Science Series C, pages 225-275. Springer Netherlands, Dordrecht, 1997.
[8] Ng A Y, Jordan M I, and Weiss Y. On spectral clustering:Analysis and an algorithm. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 849-856. MIT Press, 2002.
[9] Shi J and Malik J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905.
[10] von Luxburg U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4):395-416.
[11] von Luxburg U, Bousquet O, and Belkin M. On the convergence of spectral clustering on random samples:the normalized case. In International Conference on Computational Learning Theory, pages 457-471. Springer, 2004.
[1] 石子烨, 梁恒, 白峰杉. 数据分割的分子动力学算法[J]. 计算数学, 2014, 36(3): 325-334.
[2] 陈旭玲, 楼佩煌. 改进层次聚类算法在文献分析中的应用[J]. 计算数学, 2009, 30(4): 277-287.
[3] 张文军,冯永军,古德祥. 统计显著性标记的聚类分析算法与网络实现[J]. 计算数学, 2005, 26(3): 232-240.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10