IDEAS home Printed from https://ideas.repec.org/a/spr/jclass/v37y2020i3d10.1007_s00357-019-09349-x.html
   My bibliography  Save this article

A Note on the Formal Implementation of the K-means Algorithm with Hard Positive and Negative Constraints

Author

Listed:
  • Igor Melnykov

    (University of Minnesota - Duluth)

  • Volodymyr Melnykov

    (The University of Alabama)

Abstract

The paper discusses a new approach for incorporating hard constraints into the K-means algorithm for semi-supervised clustering. An analytic modification of the objective function of K-means is proposed that has not been previously considered in the literature.

Suggested Citation

  • Igor Melnykov & Volodymyr Melnykov, 2020. "A Note on the Formal Implementation of the K-means Algorithm with Hard Positive and Negative Constraints," Journal of Classification, Springer;The Classification Society, vol. 37(3), pages 789-809, October.
    • Handle: RePEc:spr:jclass:v:37:y:2020:i:3:d:10.1007_s00357-019-09349-x
    DOI: 10.1007/s00357-019-09349-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00357-019-09349-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00357-019-09349-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wayne DeSarbo & Vijay Mahajan, 1984. "Constrained classification: The use of a priori information in cluster analysis," Psychometrika, Springer;The Psychometric Society, vol. 49(2), pages 187-215, June.
    2. Marek Śmieja & Magdalena Wiercioch, 2017. "Constrained clustering with a complex cluster structure," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 11(3), pages 493-518, September.
    3. Melnykov, Volodymyr & Chen, Wei-Chen & Maitra, Ranjan, 2012. "MixSim: An R Package for Simulating Data to Study Performance of Clustering Algorithms," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 51(i12).
    4. Geoffrey Barbier & Reza Zafarani & Huiji Gao & Gabriel Fung & Huan Liu, 2012. "Maximizing benefits from crowdsourced data," Computational and Mathematical Organization Theory, Springer, vol. 18(3), pages 257-279, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dolnicar, Sara & Grün, Bettina & Leisch, Friedrich, 2016. "Increasing sample size compensates for data problems in segmentation studies," Journal of Business Research, Elsevier, vol. 69(2), pages 992-999.
    2. Giuseppe RICCIARDO LAMONICA, 2002. "La funzionalita' nelle zone omogenee delle Marche," Working Papers 165, Universita' Politecnica delle Marche (I), Dipartimento di Scienze Economiche e Sociali.
    3. Yu Ding & Wayne S. DeSarbo & Dominique M. Hanssens & Kamel Jedidi & John G. Lynch & Donald R. Lehmann, 2020. "The past, present, and future of measurement and methods in marketing analysis," Marketing Letters, Springer, vol. 31(2), pages 175-186, September.
    4. Zhu, Xuwen & Melnykov, Volodymyr, 2018. "Manly transformation in finite mixture modeling," Computational Statistics & Data Analysis, Elsevier, vol. 121(C), pages 190-208.
    5. Renato Cordeiro Amorim, 2016. "A Survey on Feature Weighting Based K-Means Algorithms," Journal of Classification, Springer;The Classification Society, vol. 33(2), pages 210-242, July.
    6. J. Fernando Vera & Rodrigo Macías, 2021. "On the Behaviour of K-Means Clustering of a Dissimilarity Matrix by Means of Full Multidimensional Scaling," Psychometrika, Springer;The Psychometric Society, vol. 86(2), pages 489-513, June.
    7. Bairong Wang & Jun Zhuang, 2017. "Crisis information distribution on Twitter: a content analysis of tweets during Hurricane Sandy," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 89(1), pages 161-181, October.
    8. Andrea Cerasa, 2016. "Combining homogeneous groups of preclassified observations with application to international trade," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 70(3), pages 229-259, August.
    9. Dong, Aqi & Melnykov, Volodymyr, 2024. "Contaminated Kent mixture model for clustering non-spherical directional data with heavy tails or scatter," Statistics & Probability Letters, Elsevier, vol. 208(C).
    10. Wayne DeSarbo & Richard Oliver & Arvind Rangaswamy, 1989. "A simulated annealing methodology for clusterwise linear regression," Psychometrika, Springer;The Psychometric Society, vol. 54(4), pages 707-736, September.
    11. Ana Oliveira-Brochado & Francisco Vitorino Martins, 2008. "Aspectos Metodológicos da Segmentação de Mercado: Base de Segmentação e Métodos de Classificação," FEP Working Papers 261, Universidade do Porto, Faculdade de Economia do Porto.
    12. Ahmad Ali Abin & Mohammad Ali Bashiri & Hamid Beigy, 2020. "Learning a metric when clustering data points in the presence of constraints," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 14(1), pages 29-56, March.
    13. repec:dgr:rugsom:96b34 is not listed on IDEAS
    14. Antonello Maruotti & Antonio Punzo, 2021. "Initialization of Hidden Markov and Semi‐Markov Models: A Critical Evaluation of Several Strategies," International Statistical Review, International Statistical Institute, vol. 89(3), pages 447-480, December.
    15. Lin, Tsung-I & McLachlan, Geoffrey J. & Lee, Sharon X., 2016. "Extending mixtures of factor models using the restricted multivariate skew-normal distribution," Journal of Multivariate Analysis, Elsevier, vol. 143(C), pages 398-413.
    16. Marco Riani & Andrea Cerioli & Domenico Perrotta & Francesca Torti, 2015. "Simulating mixtures of multivariate data with fixed cluster overlap in FSDA library," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 9(4), pages 461-481, December.
    17. Melnykov, Volodymyr, 2013. "On the distribution of posterior probabilities in finite mixture models with application in clustering," Journal of Multivariate Analysis, Elsevier, vol. 122(C), pages 175-189.
    18. Emilio Carrizosa & Vanesa Guerrero & Dolores Romero Morales, 2023. "On mathematical optimization for clustering categories in contingency tables," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 17(2), pages 407-429, June.
    19. Melnykov, Volodymyr, 2016. "ClickClust: An R Package for Model-Based Clustering of Categorical Sequences," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 74(i09).
    20. Qi Chen & Wen Luo & Gregory J. Palardy & Ryan Glaman & Amber McEnturff, 2017. "The Efficacy of Common Fit Indices for Enumerating Classes in Growth Mixture Models When Nested Data Structure Is Ignored," SAGE Open, , vol. 7(1), pages 21582440177, March.
    21. Motegi, Ryosuke & Seki, Yoichi, 2023. "SMLSOM: The shrinking maximum likelihood self-organizing map," Computational Statistics & Data Analysis, Elsevier, vol. 182(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jclass:v:37:y:2020:i:3:d:10.1007_s00357-019-09349-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.