Clustering with Bregman Divergences
Clustering with Bregman Divergences
复制标题
DOI：
10.1137/1.9781611972740.22
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
A. Banerjee;S. Merugu;I. Dhillon;Joydeep Ghosh
中科院分区：
文献类型：
--
作者：
A. Banerjee;S. Merugu;I. Dhillon;Joydeep Ghosh
各种各样的扭曲函数，如平方欧几里得距离、马氏距离、Itakura-Saito距离和相对熵，已被用于聚类。在本文中，我们提出并分析了基于一大类称为Bregman散度的失真函数的参数硬聚类和软聚类算法。该算法统一了基于质心的参数聚类方法，如经典的kmeans、Linde-Buzo-Gray （LBG）算法和信息论聚类方法，这些方法通过对Bregman散度的特殊选择而产生。该算法保持了经典kmeans算法的简单性和可扩展性，同时将该方法推广到大类聚类损失函数。这是通过首先在最小化布雷格曼信息损失方面提出硬聚类问题来实现的，布雷格曼信息是由率失真理论驱动的数量，然后推导出单调减少这种损失的迭代算法。此外，我们还证明了在正则指数族和一大类布雷格曼散度之间存在一个双射，我们称之为正则布雷格曼散度。这一结果使得开发一种用于学习指数族分布混合的有效EM方案的替代解释成为可能，并导致一种用于规则Bregman散度的简单软聚类算法。最后，我们讨论了速率失真理论和Bregman聚类之间的联系，并从Bregman信息的压缩和损失之间的权衡的角度对Bregman聚类算法进行了信息论分析。
A wide variety of distortion functions, such as squared Euclidean distance, Mahalanobis distance, Itakura-Saito distance and relative entropy, have been used for clustering. In this paper, we propose and analyze parametric hard and soft clustering algorithms based on a large class of distortion functions known as Bregman divergences. The proposed algorithms unify centroid-based parametric clustering approaches, such as classical kmeans , the Linde-Buzo-Gray (LBG) algorithm and information-theoretic clustering, which arise by special choices of the Bregman divergence. The algorithms maintain the simplicity and scalability of the classical kmeans algorithm, while generalizing the method to a large class of clustering loss functions. This is achieved by first posing the hard clustering problem in terms of minimizing the loss in Bregman information, a quantity motivated by rate distortion theory, and then deriving an iterative algorithm that monotonically decreases this loss. In addition, we show that there is a bijection between regular exponential families and a large class of Bregman divergences, that we call regular Bregman divergences. This result enables the development of an alternative interpretation of an efficient EM scheme for learning mixtures of exponential family distributions, and leads to a simple soft clustering algorithm for regular Bregman divergences. Finally, we discuss the connection between rate distortion theory and Bregman clustering and present an information theoretic analysis of Bregman clustering algorithms in terms of a trade-off between compression and loss in Bregman information.