{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:38:41Z","timestamp":1761597521653,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2014,6,17]],"date-time":"2014-06-17T00:00:00Z","timestamp":1402963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Clustering sets of histograms has become popular thanks to the success of the generic method of bag-of-X used in text categorization and in visual categorization applications. In this paper, we investigate the use of a parametric family of distortion measures, called the     \u03b1-divergences, for clustering histograms. Since it usually makes sense to deal with symmetric divergences in information retrieval systems, we symmetrize the \u03b1     -divergences using the concept of mixed divergences. First, we present a novel extension of k-means clustering to mixed divergences. Second, we extend the k-means++ seeding to mixed     \u03b1-divergences and report a guaranteed probabilistic bound. Finally, we describe a soft clustering technique for mixed     \u03b1-divergences.<\/jats:p>","DOI":"10.3390\/e16063273","type":"journal-article","created":{"date-parts":[[2014,6,17]],"date-time":"2014-06-17T10:57:13Z","timestamp":1403002633000},"page":"3273-3301","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["On Clustering Histograms with k-Means by Using Mixed \u03b1-Divergences"],"prefix":"10.3390","volume":"16","author":[{"given":"Frank","family":"Nielsen","sequence":"first","affiliation":[{"name":"Sony Computer Science Laboratories, Inc, Tokyo 141-0022, Japan"},{"name":"Polytechnique, 91128 Palaiseau Cedex, France"}]},{"given":"Richard","family":"Nock","sequence":"additional","affiliation":[{"name":"NICTA and The Australian National University, Locked Bag 9013, Alexandria NSW 1435, Australia"}]},{"given":"Shun-ichi","family":"Amari","sequence":"additional","affiliation":[{"name":"RIKEN Brain Science Institute, 2-1 Hirosawa Wako City, Saitama 351-0198, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2014,6,17]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Baker, L.D., and McCallum, A.K. (1998, January 24\u201328). Distributional clustering of words for text classification, Melbourne, Australia.","key":"ref_1","DOI":"10.1145\/290941.290970"},{"doi-asserted-by":"crossref","unstructured":"Bigi, B. (2003, January 14\u201316). Using Kullback\u2013Leibler distance for text categorization, Pisa, Italy. ECIR\u201903.","key":"ref_2","DOI":"10.1007\/3-540-36618-0_22"},{"unstructured":"Available online: http:\/\/archive.ics.uci.edu\/ml\/datasets\/Bag+of+Words.","key":"ref_3"},{"unstructured":"Csurka, G., Bray, C., Dance, C., and Fan, L. Visual Categorization with Bags of Keypoints.","key":"ref_4"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/s11263-009-0285-2","article-title":"Improving Bag-of-Features for Large Scale Image Search","volume":"87","author":"Douze","year":"2010","journal-title":"Int. J. Comput. Vis"},{"unstructured":"Yu, Z., Li, A., Au, O., and Xu, C. (2012, January 16\u201321). Bag of textons for image segmentation via soft clustering and convex shift, Providence, RI, USA.","key":"ref_6"},{"key":"ref_7","first-page":"801","article-title":"Sur la division des corp mat\u00e9riels en parties","volume":"1","author":"Steinhaus","year":"1956","journal-title":"Bull. Acad. Polon. Sci"},{"unstructured":"Lloyd, S.P. (1957). Least Squares Quantization in PCM, Bell Laboratories.","key":"ref_8"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in PCM","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/s11263-011-0453-z","article-title":"Compressed histogram of gradients: A low-bitrate descriptor","volume":"96","author":"Chandrasekhar","year":"2012","journal-title":"Int. J. Comput. Vis"},{"unstructured":"Nock, R., Nielsen, F., and Briys, E. Non-linear book manifolds: Learning from associations the dynamic geometry of digital libraries, New York, NY, USA.","key":"ref_11"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1415","DOI":"10.1016\/j.media.2012.04.010","article-title":"Endoscopic image analysis in semantic space","volume":"16","author":"Kwitt","year":"2012","journal-title":"Med. Image Anal"},{"unstructured":"Nielsen, F. (2010). A family of statistical symmetric divergences based on Jensen\u2019s inequality, arXiv, 1009.4004.","key":"ref_13"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2882","DOI":"10.1109\/TIT.2009.2018176","article-title":"Sided and symmetrized Bregman centroids","volume":"55","author":"Nielsen","year":"2009","journal-title":"IEEE Trans. Inf. Theory"},{"unstructured":"Nock, R., Luosto, P., and Kivinen, J. (2008, January 15\u201319). Mixed Bregman clustering with approximation guarantees, Antwerp, Belgium.","key":"ref_15"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2780","DOI":"10.1162\/neco.2007.19.10.2780","article-title":"Integration of Stochastic Models by Minimizing \u03b1-Divergence","volume":"19","author":"Amari","year":"2007","journal-title":"Neural Comput"},{"unstructured":"Arthur, D., and Vassilvitskii, S. (2007, January 7\u20139). k-means++: The advantages of careful seeding, New Orleans, LA, USA.","key":"ref_17"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2031","DOI":"10.1016\/j.patcog.2013.11.019","article-title":"Asymmetric clustering using the alpha-beta divergence","volume":"47","author":"Olszewski","year":"2014","journal-title":"Pattern Recognit"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4925","DOI":"10.1109\/TIT.2009.2030485","article-title":"Alpha-divergence is unique, belonging to both f-divergence and Bregman divergence classes","volume":"55","author":"Amari","year":"2009","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","first-page":"1705","article-title":"Clustering with Bregman divergences","volume":"6","author":"Banerjee","year":"2005","journal-title":"J. Mach. Learn. Res"},{"key":"ref_21","first-page":"65","article-title":"A unified continuous optimization framework for center-based clustering methods","volume":"8","author":"Teboulle","year":"2007","journal-title":"J. Mach. Learn. Res"},{"unstructured":"Amari, S., and Nagaoka, H. (2000). Methods of Information Geometry, Oxford University Press.","key":"ref_22"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1143\/JPSJ.18.328","article-title":"Markov Processes and the H-theorem","volume":"18","author":"Morimoto","year":"1963","journal-title":"J. Phys. Soc. Jpn"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1111\/j.2517-6161.1966.tb00626.x","article-title":"A general class of coefficients of divergence of one distribution from another","volume":"28","author":"Ali","year":"1966","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"ref_25","first-page":"229","article-title":"Information-type measures of difference of probability distributions and indirect observation","volume":"2","year":"1967","journal-title":"Studi. Sci. Math. Hung"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"134","DOI":"10.3390\/e13010134","article-title":"Generalized alpha-beta divergences and their application to robust nonnegative matrix factorization","volume":"13","author":"Cichocki","year":"2011","journal-title":"Entropy"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1007\/978-1-4615-6099-9_69","article-title":"Measurements of generalisation based on information geometry","volume":"8","author":"Ellacott","year":"1997","journal-title":"Mathematics of Neural Networks"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations","volume":"23","author":"Chernoff","year":"1952","journal-title":"Ann. Math. Stat"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1109\/LSP.2013.2243726","article-title":"An information-geometric characterization of Chernoff information","volume":"20","author":"Nielsen","year":"2013","journal-title":"IEEE Signal Process. Lett"},{"unstructured":"Wu, J., and Rehg, J. (October, January 29). Beyond the euclidean distance: creating effective visual codebooks using the histogram intersection kernel, Kyoto, Japan.","key":"ref_30"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/978-3-319-06089-7_2","article-title":"A tight lower bound instance for k-means++ in constant dimension","volume":"8402","author":"Gopal","year":"2014","journal-title":"Theory and Applications of Models of Computation"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1109\/LSP.2013.2260538","article-title":"Jeffreys centroids: A closed-form expression for positive histograms and a guaranteed tight approximation for frequency histograms","volume":"20","author":"Nielsen","year":"2013","journal-title":"IEEE Signal Process. Lett"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1016\/0022-247X(89)90128-5","article-title":"Entropic means","volume":"139","author":"Charnes","year":"1989","journal-title":"J. Math. Anal. Appl"},{"doi-asserted-by":"crossref","unstructured":"Nielsen, F., and Nock, R. (2009, January 23\u201326). The dual Voronoi diagrams with respect to representational Bregman divergences, Copenhagen, Denmark.","key":"ref_34","DOI":"10.1109\/ISVD.2009.15"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/BF02054965","article-title":"Beitr\u00e4ge zur St\u00f6rungstheorie der Spektralzerlegung","volume":"123","author":"Heinz","year":"1951","journal-title":"Math. Anna"},{"key":"ref_36","first-page":"973","article-title":"On the invariance equation for Heinz means","volume":"15","author":"Besenyei","year":"2012","journal-title":"Math. Inequal. Appl"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1145\/203082.203084","article-title":"Real values of the W -function","volume":"21","author":"Barry","year":"1995","journal-title":"ACM Trans. Math. Softw"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1109\/97.995827","article-title":"The centroid of the symmetrical Kullback\u2013Leibler distance","volume":"9","author":"Veldhuis","year":"2002","journal-title":"IEEE Signal Process. Lett"},{"unstructured":"Nielsen, F., and Garcia, V. (Statistical exponential families: A digest with flash cards, 2009). Statistical exponential families: A digest with flash cards, arXiv.org: 0911.4863.","key":"ref_39"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"5455","DOI":"10.1109\/TIT.2011.2159046","article-title":"The Burbea-Rao and Bhattacharyya centroids","volume":"57","author":"Nielsen","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"doi-asserted-by":"crossref","unstructured":"Romberg, S., and Lienhart, R. (2013, January 16\u201319). Bundle min-hashing for logo recognition, Dallas, TX, USA.","key":"ref_41","DOI":"10.1145\/2461466.2461486"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1109\/TIT.2002.808105","article-title":"The alpha-EM algorithm: Surrogate likelihood maximization using alpha-logarithmic information measures","volume":"49","author":"Matsuyama","year":"2003","journal-title":"IEEE Trans. Inf. Theory"},{"unstructured":"Amari, S.I. (2013). Mathematical Sciences (suurikagaku), The Science Company. (In Japanese).","key":"ref_43"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/16\/6\/3273\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:12:35Z","timestamp":1760217155000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/16\/6\/3273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,17]]},"references-count":43,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2014,6]]}},"alternative-id":["e16063273"],"URL":"https:\/\/doi.org\/10.3390\/e16063273","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2014,6,17]]}}}