Revue Bibliographique
Deux méthodes d’apprentissage non supervisé : synthèse sur la méthode des centres mobiles et présentation des courbes principales
[Two methods in unsupervised learning : summary on k -means clustering and presentation of principal curves]
Journal de la société française de statistique, Volume 155 (2014) no. 2, pp. 2-35.

This article proposes a review on unsupervised learning. After an introduction to quantization and to the related question of k -means clustering, the notion of principal curve, that may be seen as a generalization of these methods, is presented. We expound different definitions of principal curve and give an overview of its applications.

Cet article propose une synthèse bibliographique sur le thème de l’apprentissage non supervisé. Après une introduction à la quantification et au problème connexe de classification par la méthode des centres mobiles, nous présentons la notion de courbe principale, qui peut être vue comme une généralisation de ces méthodes. Nous exposons différentes définitions de courbe principale et donnons un aperçu des applications de ces objets.

Mot clés : apprentissage non supervisé, quantification, classification par la méthode des centres mobiles, courbes principales, synthèse bibliographique
Keywords: unsupervised learning, quantization, $k$-means clustering, principal curves, survey
@article{JSFS_2014__155_2_2_0,
     author = {Fischer, Aur\'elie},
     title = {Deux m\'ethodes d{\textquoteright}apprentissage non supervis\'e~: synth\`ese sur la m\'ethode des centres mobiles et pr\'esentation des courbes principales},
     journal = {Journal de la soci\'et\'e fran\c{c}aise de statistique},
     pages = {2--35},
     publisher = {Soci\'et\'e fran\c{c}aise de statistique},
     volume = {155},
     number = {2},
     year = {2014},
     zbl = {1316.62086},
     language = {fr},
     url = {http://www.numdam.org/item/JSFS_2014__155_2_2_0/}
}
TY  - JOUR
AU  - Fischer, Aurélie
TI  - Deux méthodes d’apprentissage non supervisé : synthèse sur la méthode des centres mobiles et présentation des courbes principales
JO  - Journal de la société française de statistique
PY  - 2014
SP  - 2
EP  - 35
VL  - 155
IS  - 2
PB  - Société française de statistique
UR  - http://www.numdam.org/item/JSFS_2014__155_2_2_0/
LA  - fr
ID  - JSFS_2014__155_2_2_0
ER  - 
%0 Journal Article
%A Fischer, Aurélie
%T Deux méthodes d’apprentissage non supervisé : synthèse sur la méthode des centres mobiles et présentation des courbes principales
%J Journal de la société française de statistique
%D 2014
%P 2-35
%V 155
%N 2
%I Société française de statistique
%U http://www.numdam.org/item/JSFS_2014__155_2_2_0/
%G fr
%F JSFS_2014__155_2_2_0
Fischer, Aurélie. Deux méthodes d’apprentissage non supervisé : synthèse sur la méthode des centres mobiles et présentation des courbes principales. Journal de la société française de statistique, Volume 155 (2014) no. 2, pp. 2-35. http://www.numdam.org/item/JSFS_2014__155_2_2_0/

[1] Antos, A.; Györfi, L.; György, A. Individual convergence rates in empirical vector quantizer design, IEEE Transactions on Information Theory, Volume 51 (2005), pp. 4013-4022 | Zbl

[2] Alexandrov, A. D.; Reshetnyak, Y. G. General Theory of Irregular Curves, Mathematics and its Applications, Kluwer Academic Publishers, Dordrecht, 1989 | Zbl

[3] Abaya, E. A.; Wise, G. L. Convergence of vector quantizers with applications to optimal quantization, SIAM Journal on Applied Mathematics, Volume 44 (1984), pp. 183-189 | Zbl

[4] Blanchard, G.; Bousquet, O.; Massart, P. Statistical performance of support vector machines, The Annals of Statistics, Volume 36 (2008), pp. 489-531 | Zbl

[5] Biau, G.; Devroye, L.; Lugosi, G. On the performance of clustering in Hilbert spaces, IEEE Transactions on Information Theory, Volume 54 (2008), pp. 781-790 | Zbl

[6] Ben-David, S.; Pál, D.; Simon, H. U. Stability of k -means clustering, Proceedings of the 20th Annual Conference on Learning Theory (COLT 2007) (Bshouty, N.; Gentile, C., eds.), Springer (2007), pp. 20-34 | Zbl

[7] Ben-David, S.; von Luxburg, U. Relating clustering stability to properties of cluster boundaries, Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008) (Servedio, R. A.; Zhang, T., eds.), Omnipress, Madison (2008), pp. 379-390

[8] Ben-David, S.; von Luxburg, U.; Pál, D. A sober look on clustering stability, Proceedings of the 19th Annual Conference on Learning Theory (COLT 2006) (Lugosi, G.; Simon, H. U., eds.), Springer, Berlin (2006), pp. 5-19 | Zbl

[9] Biau, G.; Fischer, A. Parameter selection for principal curves, IEEE Transactions on Information Theory, Volume 58 (2012), pp. 1924-1939 | Zbl

[10] Ben-Hur, A.; Elisseeff, A.; Guyon, I. A stability based method for discovering structure in clustered data, Proceedings of the 7th Pacific Symposium on Biocomputing, Volume 7 (2002), pp. 6-17

[11] Bartlett, P. L.; Linder, T.; Lugosi, G. The minimax distortion redundancy in empirical quantizer design, IEEE Transactions on Information Theory, Volume 44 (1998), pp. 1802-1813 | Zbl

[12] Birgé, L.; Massart, P. From model selection to adaptive estimation, Festschrift for Lucien Le Cam : Research Papers in Probability and Statistics (Pollard, D.; Torgersen, E.; Yang, G., eds.), Springer, New York, 1997, pp. 55-87 | Zbl

[13] Banerjee, A.; Merugu, S.; Dhillon, I. S.; Ghosh, J. Clustering with Bregman divergences, Journal of Machine Learning Research, Volume 6 (2005), pp. 1705-1749 | Zbl

[14] Banfield, J. D.; Raftery, A. E. Ice floe identification in satellite images using mathematical morphology and clustering about principal curves, Journal of the American Statistical Association, Volume 87 (1992), pp. 7-16

[15] Bregman, L. M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, Volume 7 (1967), pp. 200-217 | Zbl

[16] Brunsdon, C. Path estimation from GPS tracks, Proceedings of the 9th International Conference on GeoComputation, National Centre for Geocomputation, National University of Ireland, Maynooth, Eire (2007)

[17] Corkeron, P. J.; Anthony, P.; Martin, R. Ranging and diving behaviour of two ‘offshore’ bottlenose dolphins, Tursiops sp., off eastern Australia, Journal of the Marine Biological Association of the United Kingdom, Volume 84 (2004), pp. 465-468

[18] Caffo, B. S.; Crainiceanu, C. M.; Deng, L.; Hendrix, C. W. A case study in pharmacologic colon imaging using principal curves in single photon emission computed tomography, Journal of the American Statistical Association, Volume 103 (2008), pp. 1470-1480 | Zbl

[19] Chang, K.; Ghosh, J. Principal curves for nonlinear feature extraction and classification, SPIE Applications of Artificial Neural Networks in Image Processing III, Volume 3307 (1998), pp. 120-129

[20] Calinski, R. B.; Harabasz, J. A dendrite method for cluster analysis, Communications in Statistics, Volume 3 (1974), pp. 1-27 | Zbl

[21] Chou, P. A. The distortion of vector quantizers trained on n vectors decreases to the optimum as O p ( 1 / n ) , Proceedings of the IEEE International Symposium on Information Theory, Trondheim, Norway (1994)

[22] Cleveland, W. S. Robust locally weighted regression and smoothing scatterplots, Journal of the American Statistical Association, Volume 74 (1979), pp. 829-836 | Zbl

[23] Cadre, B.; Paris, Q. On Hölder fields clustering, TEST, Volume 21 (2012), pp. 301-316 | Zbl

[24] De’ath, G. Principal curves : a new technique for indirect and direct gradient analysis, Ecology, Volume 80 (1999), pp. 2237-2253

[25] Delicado, P. Another look at principal curves and surfaces, Journal of Multivariate Analysis, Volume 77 (2001), pp. 84-116 | Zbl

[26] Delicado, P.; Huerta, M. Principal curves of oriented points : theoretical and computational improvements, Computational Statistics, Volume 18 (2003), pp. 293-315 | Zbl

[27] Duda, R. O.; Hart, P. E.; Stork, D. G. Pattern Classification, Wiley-Interscience, New York, 2000 | Zbl

[28] Dempster, A. P.; Laird, N. M.; Rubin, D. B. Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society (1977), pp. 1-38 | Zbl

[29] Dong, D.; McAvoy, T. J. Nonlinear principal component analysis-based principal curves and neural networks, Computers and Chemical Engineering, Volume 20 (1995), pp. 65-78

[30] Duchamp, T.; Stuetzle, W. Geometric properties of principal curves in the plane, Robust Statistics, Data Analysis, and Computer Intensive Methods : in Honor of Peter Huber’s 60th Birthday (Rieder, H., ed.) (Lecture Notes in Statistics), Volume 109, Springer-Verlag, New York, 1996, pp. 135-152 | Zbl

[31] Dereich, S.; Vormoor, C. The high resolution vector quantization problem with Orlicz norm distortion, Journal of Theoretical Probability, Volume 24 (2011), pp. 517-544 | Zbl

[32] Einbeck, J.; Dwyer, J. Using principal curves to analyse traffic patterns on freeways, Transportmetrica (2010)

[33] Einbeck, J.; Tutz, G.; Evers, L. Exploring multivariate data structures with local principal curves, Classification – The Ubiquitous Challenge, Proceedings of the 28th Annual Conference of the Gesellschaft für Klassifikation, University of Dortmund (Weihs, C.; Gaul, W., eds.) (Studies in Classification, Data Analysis, and Knowledge Organization), Springer, Berlin, Heidelberg, 2005, pp. 256-263

[34] Einbeck, J.; Tutz, G.; Evers, L. Local principal curves, Statistics and Computing, Volume 15 (2005), pp. 301-313

[35] Fischer, A. Quantization and clustering with Bregman divergences, Journal of Multivariate Analysis, Volume 101 (2010), pp. 2207-2221 | Zbl

[36] Fischer, A. On the number of groups in clustering, Statistics & Probability Letters, Volume 81 (2011), pp. 1771-1781 | Zbl

[37] Fischer, A. Selecting the length of a principal curve within a Gaussian model, Electronic Journal of Statistics, Volume 7 (2013), pp. 342-363 | Zbl

[38] Friedsam, H.; Oren, W. A. The application of the principal curve analysis technique to smooth beamlines, Proceedings of the 1st International Workshop on Accelerator Alignment (1989)

[39] Gersho, A.; Gray, R. M. Vector Quantization and Signal Compression, Kluwer Academic Publishers, Norwell, 1992 | Zbl

[40] Graf, S.; Luschgy, H. Foundations of Quantization for Probability Distributions, Lecture Notes in Mathematics, Springer-Verlag, Berlin, Heidelberg, 2000 | Zbl

[41] Graf, S.; Luschgy, H. Consistent estimation in the quantization problem for random vectors, Transactions of the Twelfth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes (1994), pp. 84-87

[42] Gordon, A. D. Classification, Monographs on Statistics and Applied Probability, 82, Chapman Hall/CRC, Boca Raton, 1999 | Zbl

[43] Genovese, C. R.; Perone-Pacifico, M.; Verdinelli, I.; Wasserman, L. Nonparametric Ridge Estimation (2012) | arXiv | Zbl

[44] Genovese, C. R.; Perone-Pacifico, M.; Verdinelli, I.; Wasserman, L. The geometry of nonparametric filament estimation, Journal of the American Statistical Association, Volume 107 (2012), pp. 788-799 | Zbl

[45] Gerber, S.; Whitaker, R. Regularization-Free Principal Curve Estimation, Journal of Machine Learning Research, Volume 14 (2013), pp. 1285-1302 | Zbl

[46] Hartigan, J. A. Clustering Algorithms, Wiley Series in Probability and Mathematical Statistics, John Wiley and Sons, New York, 1975 | Zbl

[47] Hardy, A. On the number of clusters, Computational Statistics and Data Analysis, Volume 23 (1996), pp. 83-96 | Zbl

[48] Hastie, T. Principal curves and surfaces (1984) (Technical report)

[49] Hermann, T.; Meinicke, P.; Ritter, H. Principle curve sonification, Proceedings of the 6th International Conference on Auditory Display Curve Sonification (ICAD2000), Atlanta, USA (2000), pp. 81-86

[50] Hotelling, H. Analysis of a complex of statistical variables into principal components, Journal of Educational Psychology, Volume 24 (1933), p. 417-441, 498–520 | JFM

[51] Hastie, T.; Stuetzle, W. Principal curves, Journal of the American Statistical Association, Volume 84 (1989), pp. 502-516 | Zbl

[52] Hastie, T.; Tibshirani, R.; Friedman, J. The Elements of Statistical Learning, Springer, New York, 2001 | Zbl

[53] Kégl, B.; Krzyżak, A. Piecewise linear skeletonization using principal curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 24 (2002), pp. 59-74

[54] Kégl, B.; Krzyżak, A.; Linder, T.; Zeger, K. Learning and design of principal curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 22 (2000), pp. 281-297

[55] Krzanowski, W. J.; Lai, Y. T. A criterion for determining the number of clusters in a data set, Biometrics, Volume 44 (1985), pp. 23-34 | Zbl

[56] Koltchinskii, V. Local Rademacher complexities and oracle inequalities in risk minimization, The Annals of Statistics, Volume 34 (2006), pp. 2593-2656 | Zbl

[57] Kim, D. J.; Park, Y. W.; Park, D. J. A novel validity index for determination of the optimal number of clusters, IEICE Transactions on Information and System, Volume E84D (2001), pp. 281-285

[58] Kaufman, L.; Rousseeuw, P. Finding Groups in Data : An Introduction to Cluster Analysis, Wiley Series in Probability and Mathematical Statistics, Wiley-Interscience, Hoboken, 1990

[59] Kégl, B. Principal Curves : Learning, Design, and Applications, Concordia University, Montréal, Québec, Canada (1999) (Ph. D. Thesis)

[60] Laloë, T. L1-quantization and clustering in Banach spaces, Mathematical Methods of Statistics, Volume 19 (2010), pp. 136-150 | Zbl

[61] Linde, Y; Buzo, A; Gray, R M An algorithm for vector quantizer design, IEEE Transactions on Communication, Volume 28 (1980), pp. 801-804

[62] Lehmann, E. L.; Casella, G. Theory of Point Estimation, Springer-Verlag, New York, 1998 | Zbl

[63] Levine, E.; Domany, E. Resampling method for unsupervised estimation of cluster validity, Journal of Neural Computation, Volume 13 (2002), pp. 2573-2593 | Zbl

[64] Levrard, C. Fast rates for empirical vector quantization, Electronic Journal of Statistics, Volume 7 (2013), pp. 1716-1746 | Zbl

[65] Linder, T. On the training distortion of vector quantizers, IEEE Transactions on Information Theory, Volume 46 (2000), pp. 1617-1623 | Zbl

[66] Linder, T. Learning-theoretic methods in vector quantization, Principles of Nonparametric Learning (Györfi, L., ed.), Springer-Verlag, Wien, 2002

[67] Lloyd, S. P. Least squares quantization in PCM, IEEE Transactions on Information Theory, Volume 28 (1982), pp. 129-137 | Zbl

[68] Linder, T.; Lugosi, G.; Zeger, K Rates of convergence in the source coding theorem, in empirical quantizer design, and in universal lossy source coding, IEEE Transactions on Information Theory, Volume 40 (1994), pp. 1728-1740 | Zbl

[69] Luschgy, H.; Pagès, P. Functional quantization of Gaussian processes, Journal of Functional Analysis, Volume 196 (2002), pp. 486-531 | Zbl

[70] Luschgy, H.; Pagès, P. Functional quantization of a class of Brownian diffusions : a constructive approach, Stochastic Processes and their Applications, Volume 116 (2006), pp. 310-336 | Zbl

[71] MacQueen, J. Some methods for classification and analysis of multivariate observations, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability (1967), pp. 281-297 | Zbl

[72] Milligan, G. W.; Cooper, M. C. An examination of procedures for determining the number of clusters in a data set, Psychometrika, Volume 50 (1985), p. 159-79

[73] Mardia, K. V.; Kent, J. T.; Bibby, J. M. Multivariate Analysis, Academic Press, London, 1979 | Zbl

[74] Ozertem, U.; Erdogmus, D. Signal denoising using principal curves : application to timewarping, Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2008) (2008), pp. 3709-3712

[75] Ozertem, U.; Erdogmus, D. Locally Defined Principal Curves and Surfaces, Journal of Machine Learning Research, Volume 12 (2011), pp. 1249-1286 | Zbl

[76] Pearson, K. On lines and planes of closest fit to systems of points in space, Philosophical Magazine, Volume 2 (1901), pp. 559-572 | JFM

[77] Pollard, D. Strong consistency of k -means clustering, Annals of Statistics, Volume 9 (1981), pp. 135-140 | Zbl

[78] Pollard, D. A central limit theorem for k -means clustering, Annals of Probability, Volume 10 (1982), pp. 919-926 | Zbl

[79] Pollard, D. Quantization and the method of k -means, IEEE Transactions on Information Theory, Volume 28 (1982) | Zbl

[80] Reinhard, K.; Niranjan, M. Parametric subspace modeling of speech transitions, Speech Communication, Volume 27 (1999), pp. 19-42

[81] Silverman, B. W. Some aspects of spline smoothing approaches to non-parametric regression curve fitting., Journal of the Royal Statistical Society, Volume 47 (1985), pp. 1-52 | Zbl

[82] Sugar, C. A.; James, G. M. Finding the number of clusters in a data set : an information theoretic approach, Journal of the American Statistical Association, Volume 98 (2003), pp. 750-763 | Zbl

[83] Sandilya, S.; Kulkarni, S. R. Principal curves with bounded turn, IEEE Transactions on Information Theory, Volume 48 (2002), pp. 2789-2793 | Zbl

[84] Spearman, C. General intelligence, objectively determined and measured, American Journal of Psychology, Volume 15 (1904), pp. 201-293

[85] Stanford, D. C.; Raftery, A. E. Finding curvilinear features in spatial point patterns : principal curve clustering with noise, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 22 (2000), pp. 2237-2253

[86] Shamir, O.; Tishby, N. Cluster stability for finite samples, Advances in Neural Information Processing Systems 20 (Platt, J. C.; Koller, D.; Singer, Y.; Rowseis, S., eds.), MIT Press, Cambridge (2008), pp. 1297-1304

[87] Shamir, O.; Tishby, N. Model selection and stability in k -means clustering, Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008) (Servedio, R. A.; Zhang, T., eds.), Omnipress, Madison (2008), pp. 367-378

[88] Steinhaus, H. Sur la division des corps matériels en parties, Bulletin de l’Académie Polonaise des Sciences, Classe III, Volume IV (1956), pp. 801-804 | Zbl

[89] Tarpey, T.; Flury, B. Self-consistency : a fundamental concept in statistics, Statistical Science, Volume 11 (1996), pp. 229-243 | Zbl

[90] Tibshirani, R. Principal curves revisited, Statistics and Computing, Volume 2 (1992), pp. 183-190

[91] Tibshirani, R.; Walther, G.; Hastie, T. Estimating the number of clusters in a dataset via the gap statistic, Journal of the Royal Statistical Society, Volume 63 (2001), pp. 411-423 | Zbl

[92] Verbeek, J. J.; Vlassis, N.; Kröse, B. A soft k -segments algorithm for principal curves, Proceedings of International Conference on Artificial Neural Networks 2001 (2001), pp. 450-456 | Zbl

[93] Wong, W. C. K.; Chung, A. C. S. Principal curves to extract vessels in 3D angiograms, Proceedings of the 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW’08) (2008), pp. 1-8

[94] Wilson, D. J. H.; Irwin, G. W.; Lightbody, G. RBF principal manifolds for process monitoring, IEEE Transactions of Neural Networks, Volume 10 (1999), pp. 1424-1434

[95] Wong, W. C. K.; So, R. W. K.; Chung, A. C. S. Principal curves : a technique for preliminary carotid lumen segmentation and stenosis grading, MIDAS Journal (2009)

[96] Xu, L.; Jordan, M. I. On convergence properties of the EM algorithm for Gaussian mixtures, Neural Computation, Volume 8 (1996), pp. 129-151

[97] Zayed, M.; Einbeck, J. Constructing economic summary indexes via principal curves, Proceedings of the 19th International Conference on Computational Statistics, COMPSTAT 2010 (Lechevallier, Y.; Saporta, G., eds.), Springer (2010), pp. 1709-1716

[98] Zhang, F.; Wu, B.; Zhang, L.; Huang, H.; Tian, Y. Illicit vessel identification in Inland waters using SAR image, Proceedings of the IEEE International Conference on Geoscience and Remote Sensing Symposium (IGARSS 2006) (2006), pp. 3144-3147