An approximation polynomial-time algorithm for a sequence bi-clustering problem

详细信息    查看全文

• 作者：A. V. Kel’manov ; S. A. Khamidullin
• 关键词：sequence of Euclidean vectors ; clustering ; minimum of the sum of squared distances ; NP ; hardness ; approximation polynomial ; time algorithm.
• 刊名：Computational Mathematics and Mathematical Physics
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：55
• 期：6
• 页码：1068-1076
• 全文大小：550 KB
• 参考文献：1.A. V. Kel’manov and A. V. Pyatkin, “On the complexity of a search for a subset of “similar-vectors,-Dokl. Math 78 (1), 574-75 (2008).MATH MathSciNet View Article
  2.A. V. Kel’manov and A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis,-Comput. Math. Math. Phys. 49 (11), 1966-971 (2009).MathSciNet View Article
  3.A. V. Kel’manov and A. V. Pyatkin, “On complexity of some problems of cluster analysis of vector sequences,-J. Appl. Ind. Math. 7 (3), 363-69 (2013).MathSciNet View Article
  4.K. Anil and K. Jain, “Data clustering: 50 years beyond k-means,-Pattern Recogn. Lett. 31, 651-66 (2010).View Article
  5.T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Springer, New York, 2001).
  6.D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,-Machine Learning 75 (2), 245-48 (2009).View Article
  7.A. V. Kel’manov and B. Jeon, “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train,-IEEE Trans. Signal Processing 52 (3), 645-56 (2004).MathSciNet View Article
  8.J. A. Carter, E. Agol, at al., “Kepler-36: A pair of planets with neighboring orbits and dissimilar densities,-Science 337 (6094), 556-59 (2012).View Article
  9.J. A. Carter and E. Agol, “The quasiperiodic automated transit search algorithm,-Astrophys. J. 765 (2) (2013); doi:10.1088/0004-637X/765/2/132.
  10.A. V. Kel’manov, “Off-line detection of a quasi-periodically recurring fragment in a numerical sequence,-Proc. Steklov Inst. Math. 263, Suppl. 2, S84–S92 (2008).MathSciNet View Article
  11.M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
  12.A. V. Kel’manov and V. I. Khandeev, “A 2-approximation polynomial algorithm for a clustering problem,-J. Appl. Ind. Math. 7 (4), 515-21 (2013).MathSciNet View Article
  13.A. V. Kel’manov and S. A. Khamidullin, “Posterior detection of a given number of identical subsequences in a quasi-periodic sequence,-Comput. Math. Math. Phys. 41 (5), 762-74 (2001).MATH MathSciNet
  14.A. V. Kel’manov and S. M. Romanchenko, “An approximation algorithm for solving a problem of search for a vector subset,-J. Appl. Ind. Math. 6 (1), 90-6 (2012).MathSciNet View Article
  
• 作者单位：A. V. Kel’manov (1) (2)
  S. A. Khamidullin (1)
  
  1. Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4,, Novosibirsk, 630090, Russia
  2. Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Computational Mathematics and Numerical Analysis
  Russian Library of Science
  
• 出版者：MAIK Nauka/Interperiodica distributed exclusively by Springer Science+Business Media LLC.
• ISSN：1555-6662

文摘

We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in Euclidean space into two clusters using the criterion of the minimal sum of the squared distances from the elements of the clusters to the centers of the clusters. The center of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The center of the other cluster is fixed at the origin. Moreover, the partition is such that the difference between the indices of two successive vectors in the first cluster is bounded above and below by prescribed constants. A 2-approximation polynomial-time algorithm is proposed for this problem.