IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v56y2012i6p1434-1449.html
   My bibliography  Save this article

A fast and recursive algorithm for clustering large datasets with k-medians

Author

Listed:
  • Cardot, Hervé
  • Cénac, Peggy
  • Monnez, Jean-Marie

Abstract

Clustering with fast algorithms large samples of high dimensional data is an important challenge in computational statistics. A new class of recursive stochastic gradient algorithms designed for the k-medians loss criterion is proposed. By their recursive nature, these algorithms are very fast and are well adapted to deal with large samples of data that are allowed to arrive sequentially. It is proved that the stochastic gradient algorithm converges almost surely to the set of stationary points of the underlying loss criterion. A particular attention is paid to the averaged versions which are known to have better performances. A data-driven procedure that permits a fully automatic selection of the value of the descent step is also proposed. The performance of the averaged sequential estimator is compared on a simulation study, both in terms of computation speed and accuracy of the estimations, with more classical partitioning techniques such as k-means, trimmed k-means and PAM (partitioning around medoids). Finally, this new online clustering technique is illustrated on determining television audience profiles with a sample of more than 5000 individual television audiences measured every minute over a period of 24 hours.

Suggested Citation

  • Cardot, Hervé & Cénac, Peggy & Monnez, Jean-Marie, 2012. "A fast and recursive algorithm for clustering large datasets with k-medians," Computational Statistics & Data Analysis, Elsevier, vol. 56(6), pages 1434-1449.
    • Handle: RePEc:eee:csdana:v:56:y:2012:i:6:p:1434-1449
    DOI: 10.1016/j.csda.2011.11.019
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947311004178
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2011.11.019?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. García-Treviño, E.S. & Barria, J.A., 2012. "Online wavelet-based density estimation for non-stationary streaming data," Computational Statistics & Data Analysis, Elsevier, vol. 56(2), pages 327-344.
    2. Luis García-Escudero & Alfonso Gordaliza & Carlos Matrán & Agustín Mayo-Iscar, 2010. "A review of robust clustering methods," 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. 4(2), pages 89-109, September.
    3. Monnez, Jean-Marie, 2006. "Almost sure convergence of stochastic gradient processes with matrix step sizes," Statistics & Probability Letters, Elsevier, vol. 76(5), pages 531-536, March.
    4. Croux, Christophe & Gallopoulos, Efstratios & Van Aelst, Stefan & Zha, Hongyuan, 2007. "Machine Learning and Robust Data Mining," Computational Statistics & Data Analysis, Elsevier, vol. 52(1), pages 151-154, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Monnez, Jean-Marie & Skiredj, Abderrahman, 2021. "Widening the scope of an eigenvector stochastic approximation process and application to streaming PCA and related methods," Journal of Multivariate Analysis, Elsevier, vol. 182(C).
    2. Godichon-Baggioni, Antoine & Lu, Wei, 2024. "Online stochastic Newton methods for estimating the geometric median and applications," Journal of Multivariate Analysis, Elsevier, vol. 202(C).
    3. Hervé Cardot & Antoine Godichon-Baggioni, 2017. "Fast estimation of the median covariation matrix with application to online robust principal components analysis," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(3), pages 461-480, September.
    4. Gaunand, A. & Hocdé, A. & Lemarié, S. & Matt, M. & Turckheim, E.de, 2015. "How does public agricultural research impact society? A characterization of various patterns," Research Policy, Elsevier, vol. 44(4), pages 849-861.
    5. Godichon-Baggioni, Antoine, 2016. "Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: Lp and almost sure rates of convergence," Journal of Multivariate Analysis, Elsevier, vol. 146(C), pages 209-222.

    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. Pierpaolo D’Urso & Livia De Giovanni & Riccardo Massari & Francesca G. M. Sica, 2019. "Cross Sectional and Longitudinal Fuzzy Clustering of the NUTS and Positioning of the Italian Regions with Respect to the Regional Competitiveness Index (RCI) Indicators with Contiguity Constraints," Social Indicators Research: An International and Interdisciplinary Journal for Quality-of-Life Measurement, Springer, vol. 146(3), pages 609-650, December.
    2. García Treviño, E.S. & Alarcón Aquino, V. & Barria, J.A., 2019. "The radial wavelet frame density estimator," Computational Statistics & Data Analysis, Elsevier, vol. 130(C), pages 111-139.
    3. Rubin Daniel B., 2011. "A Calibrated Multiclass Extension of AdaBoost," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 10(1), pages 1-24, November.
    4. Brunet-Saumard, Camille & Genetay, Edouard & Saumard, Adrien, 2022. "K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means," Computational Statistics & Data Analysis, Elsevier, vol. 167(C).
    5. Yang, Yu-Chen & Lin, Tsung-I & Castro, Luis M. & Wang, Wan-Lun, 2020. "Extending finite mixtures of t linear mixed-effects models with concomitant covariates," Computational Statistics & Data Analysis, Elsevier, vol. 148(C).
    6. Pietro Coretto & Christian Hennig, 2016. "Robust Improper Maximum Likelihood: Tuning, Computation, and a Comparison With Other Methods for Robust Gaussian Clustering," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(516), pages 1648-1659, October.
    7. C. Ruwet & L. García-Escudero & A. Gordaliza & A. Mayo-Iscar, 2012. "The influence function of the TCLUST robust clustering procedure," 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. 6(2), pages 107-130, July.
    8. Šárka Brodinová & Peter Filzmoser & Thomas Ortner & Christian Breiteneder & Maia Rohm, 2019. "Robust and sparse k-means clustering for high-dimensional data," 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. 13(4), pages 905-932, December.
    9. Pierpaolo D’Urso & Livia Giovanni & Riccardo Massari, 2015. "Trimmed fuzzy clustering for interval-valued data," 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(1), pages 21-40, March.
    10. Luis García-Escudero & Alfonso Gordaliza & Carlos Matrán & Agustín Mayo-Iscar, 2010. "A review of robust clustering methods," 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. 4(2), pages 89-109, September.
    11. Sylvia Frühwirth-Schnatter, 2011. "Panel data analysis: a survey on model-based clustering of time series," 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. 5(4), pages 251-280, December.
    12. Slaets, Leen & Claeskens, Gerda & Hubert, Mia, 2012. "Phase and amplitude-based clustering for functional data," Computational Statistics & Data Analysis, Elsevier, vol. 56(7), pages 2360-2374.
    13. Ricardo Fraiman & Badih Ghattas & Marcela Svarc, 2013. "Interpretable clustering using unsupervised binary trees," 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. 7(2), pages 125-145, June.
    14. Alessio Farcomeni & Antonio Punzo, 2020. "Robust model-based clustering with mild and gross outliers," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(4), pages 989-1007, December.
    15. C. Ruwet & L. García-Escudero & A. Gordaliza & A. Mayo-Iscar, 2013. "On the breakdown behavior of the TCLUST clustering procedure," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(3), pages 466-487, September.
    16. Pierpaolo D’Urso & Livia Giovanni & Riccardo Massari & Dario Lallo, 2013. "Noise fuzzy clustering of time series by autoregressive metric," METRON, Springer;Sapienza Università di Roma, vol. 71(3), pages 217-243, November.
    17. Farnè, Matteo & Vouldis, Angelos T., 2018. "A methodology for automised outlier detection in high-dimensional datasets: an application to euro area banks' supervisory data," Working Paper Series 2171, European Central Bank.
    18. Marek A. Dąbrowski & Monika Papież & Sławomir Śmiech, 2020. "Classifying de facto exchange rate regimes of financially open and closed economies: A statistical approach," The Journal of International Trade & Economic Development, Taylor & Francis Journals, vol. 29(7), pages 821-849, October.
    19. 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.
    20. Andrea Cappozzo & Francesca Greselin & Thomas Brendan Murphy, 2020. "A robust approach to model-based classification based on trimming and 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(2), pages 327-354, June.

    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:eee:csdana:v:56:y:2012:i:6:p:1434-1449. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    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.