Robust Optimization for Clustering

详细信息    查看全文

• 关键词：Robust optimization ; Clustering ; DC programming ; DCA
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9622
• 期：1
• 页码：671-680
• 全文大小：214 KB
• 参考文献：1.Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)CrossRef MATH
  2.Bradley, P.S., Mangasarian, O.L., Street, W.N.: Clustering via concave minimization. In: Mozer, M.C., Jordan, M.I., Petsche, T. (eds.) NIPS 9, pp. 368–374. MIT Press, Cambridge, MA (1997)
  3.Hubert, L., Arabie, P.: Comparing partitions. J CLASSIF 2, 193–218 (1985)CrossRef MATH
  4.Gullo, F., Tagarelli, A.: Uncertain centroid based partitional clustering of uncertain data. Proc. VLDB Endowment (ACM) 5(7), 610–621 (2012)CrossRef
  5.Le Thi, H.A., Le, H.M., Nguyen, V.V., Pham, D.T.: A DC programming approach for feature selection in support vector machines learning. J. Adv. Data Anal. Classif. 2, 259–278 (2008)MathSciNet CrossRef MATH
  6.Le Thi, H.A., Le, H.M., Pham, D.T.: Fuzzy clustering based on nonconvex optimisation approaches using difference of convex (DC) functions algorithms. J. Adv. Data Anal. Classif. 2, 1–20 (2007)MathSciNet MATH
  7.Le Thi, H.A., Le, H.M., Pham, D.T., Huynh, V.N.: Binary classification via spherical separator by DC programming and DCA. J. Global Optim. 56(4), 1393–1407 (2013)MathSciNet CrossRef MATH
  8.An, L.T.H., Cuong, N.M.: Efficient algorithms for feature selection in multi-class support vector machine. In: Nguyen, N.T., van Do, T., Thi, H.A. (eds.) ICCSAMA 2013. SCI, vol. 479, pp. 41–52. Springer, Heidelberg (2013)CrossRef
  9.Le Thi, H.A., Vo, X.T., Pham, D.T.: Robust feature selection for SVMs under uncertain data. In: Perner, P. (ed.) ICDM 2013. LNCS, vol. 7987, pp. 151–165. Springer, Heidelberg (2013)
  10.Le Thi, H.A., Le, H.M., Pham, D.T.: Feature selection in machine learning: an exact penalty approach using a difference of convex function algorithm. MachineLearning (published online 04.07.14). doi:10.​1007/​s10994-014-5455-y
  11.Le Thi, H.A., Le, H.M., Pham, D.T.: New and efficient DCA based algorithms for minimum sum-of-squares clustering. Pattern Recogn. 47(1), 388–401 (2014)CrossRef MATH
  12.Le Thi, H.A., Vo, X.T., Pham, D.T.: Feature selection for linear SVMs under uncertain data: robust optimization based on difference of convex functions algorithms. Neural Netw. 59, 36–50 (2014)CrossRef MATH
  13.Le Thi, H.A., Nguyen, M.C., Pham, D.T.: A DC programming approach for finding communities in networks. Neural Comput. 26(12), 2827–2854 (2014)MathSciNet CrossRef
  14.Le Thi, H.A., Pham, D.T., Le, H.M., Vo, X.T.: DC approximation approaches for sparse optimization. Eur. J. Oper. Res. 244(1), 26–46 (2015)MathSciNet CrossRef
  15.Le Thi, H.A., Pham, D.T.: The DC (difference of convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)MathSciNet CrossRef MATH
  16.Le Thi, H.A., Belghiti, T., Pham, D.T.: A new efficient algorithm based on DC programming and DCA for clustering. J. Glob. Optim. 37, 593–608 (2006)MathSciNet MATH
  17.Le Thi, H.A., Le, H.M., Pham, D.T.: Optimization based DC programming and DCA for hierarchical clustering. Eur. J. Oper. Res. 183, 1067–1085 (2007)MathSciNet CrossRef MATH
  18.Pham, D.T., Le Thi, H.A.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnamica 22(1), 289–357 (1997)MATH
  19.Le Thi, H.A., Le, H.M., Pham, D.T.: New and efficient DCA based algorithms for minimum sum-of-squares clustering. Pattern Recogn. 47(1), 388–401 (2014)CrossRef MATH
  20.MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of Berkeley Symposium on Mathematical Statistics and Probability, pp. 281–297 (1967)
  21.Pham, D.T., Le Thi, H.A.: DC optimization algorithms for solving the trust region subproblem. SIAM J. Oppt. 8, 476–505 (1998)CrossRef MATH
  22.Xu, H., Caramanis, C., Mannor, S.: Robustness and regularization of support vector machines. J. Mach. Learn. Res. 10, 1485–1510 (2009)MathSciNet MATH
  
• 作者单位：Xuan Thanh Vo (17)
  Hoai An Le Thi (17)
  Tao Pham Dinh (18)
  
  17. Laboratory of Theoretical and Applied Computer Science EA 3097, University of Lorraine, Ile de Saulcy, 57045, Metz, France
  18. Laboratory of Mathematics, INSA - Rouen, University of Normandie, 76801, Saint-Etienne-du-Rouvray Cedex, France
  
• 丛书名：Intelligent Information and Database Systems
• ISBN：978-3-662-49390-8
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this paper, we investigate the robust optimization for the minimum sum-of squares clustering (MSSC) problem. Each data point is assumed to belong to a box-type uncertainty set. Following the robust optimization paradigm, we obtain a robust formulation that can be interpreted as a combination of MSSC and k-median clustering criteria. A DCA-based algorithm is developed to solve the resulting robust problem. Preliminary numerical results on real datasets show that the proposed robust optimization approach is superior than MSSC and k-median clustering approaches.