Reducing the time complexity of the fuzzy c-means algorithm
Reducing the time complexity of the fuzzy c-means algorithm
复制标题
DOI：
10.1109/91.995126
复制
发表时间：
2002-04-01
影响因子：
11.9
通讯作者：
Hutcheson, T
中科院分区：
文献类型：
--
作者：
Kolen, JF;Hutcheson, T
在本文中，我们提出了一个有效的实现模糊c-均值聚类算法。原始算法在估计聚类中心和数据点的模糊隶属度之间交替。隶属矩阵的大小是原始数据集的数量级，如果这种技术被应用于具有许多聚类的非常大的数据集，则大小是禁止的。我们的实现消除了这种数据结构的存储，将两个更新合并为一个单一的更新的集群中心。这一变化显着影响渐近运行时的新算法是线性的集群的数量，而原来的是二次。消除成员关系矩阵还可以减少与重复访问大型数据结构相关的开销。经验证据量化这种新方法所实现的节省。
In this paper, we present an efficient implementation of the fuzzy c-means clustering algorithm. The original algorithm alternates between estimating centers of the clusters and the fuzzy membership of the data points. The size of the membership matrix is on the order of the original data set, a prohibitive size if this technique is to be applied to very large data sets with many clusters. Our implementation eliminates the storage of this data structure by combining the two updates into a single update of the cluster centers. This change significantly affects the asymptotic runtime as the new algorithm is linear with respect to the number of clusters, while the original is quadratic. Elimination of the membership matrix also reduces the overhead associated with repeatedly accessing a large data structure. Empirical evidence is presented to quantify the savings achieved by this new method.