期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于最小聚类划分的K-means聚类(1+ε)近似算法 被引量：5

The (1+ε) Approximate Algorithm for K-means Based on the Minimum Size of Sub-Cluster
下载PDF
导出
摘要 k-means聚类算法是解决聚类问题的一个常用方法.近年来,国外许多学者对该问题的近似常数算法和(1+ε)近似算法进行了研究.利用Kumar等人随机取样技术对于基于最小聚类划分k-means提出一个(1+ε)随机近似算法.该算法利用随机取样技术从集合中求出部分取样点,再对随机取样点进行组合找出每个聚类的部分点,将该部分点的质心点作为相应子聚类簇的质心点.通过多次运行该算法可以以较高概率求出k-means聚类的1+ε近似值. k-means clustering is one of the most popular approaches used in clustering problem. In recent years, many researches have been conducted to find algorithms with bounded quality, either (1+ε) approximation or constant approximation. In this paper, the (1+ε) randomized approximate algorithm is presented for the k-means clustering based on the minimum size of the smallest optimal sub cluster. The main idea of this algorithm is to use the sampling technique proposed by Kumar et al. First, some points are sampled from the input point set. Then some sampled points are combined to calculate their centroid and the new centroid is used as one of the sub cluster center point. If the algorithm is run several times, the result of the (1+ε) approximation can be obtained with high probability proved.
作者 王守强 朱大铭 史士英
机构地区 山东大学计算机科学与技术学院 山东交通学院信息工程系
出处 《计算机研究与发展》 EI CSCD 北大核心 2008年第z1期26-30,共5页 Journal of Computer Research and Development
基金 国家自然科学基金项目(60573024)
关键词 K-MEANS 聚类 质心点 ε质心点 k-means cluster centroid ε-centroid
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献9

  • 1[1]M Inaba,N Kaoth,H Imai.Application of weighted Voronoi diagrams and randomization to variance-based k-clustering(extended abstract).In:Proc of the 10th Annual Symp on Computational Geometry.New York:ACM Press,1994.332-339
  • 2[2]V Arya,et al.Local search heurictics for k-median and facility location problems.STOC'2001,Hersonissons,Crete,Greece,2001
  • 3潘锐,朱大铭,马绍汉,肖进杰.k-Median近似计算复杂度与局部搜索近似算法分析[J].软件学报,2005,16(3):392-399. 被引量：8
  • 4[4]T Kanungo,D M Mount,N Netanyahu,et al.A local search approximation algorithm for k-means clustering.Computational Geometry,2004,28(2-3):89-112
  • 5[5]J Matousek.On approximate geometric k-clustering.Discrete and Computational Geometry,2000,24(1):61-84
  • 6[6]W F de la Vega,M Karpinski,C Kenyon,et al.Approximation schemes for clustering problems.In:Proc of the 35th Annual ACM Symp on Theory of Computing.New York:ACM Press,2003.50-58
  • 7[7]S Har-Peled,S Mazumdar.Coresets for k-means and k-median clustering and their applications.In:Proc of the 36th Annual ACM Symp on Theory Computer.New York:ACM Press,2004.291-300
  • 8[8]A Kumar,Y Sabharwal,S Sen.A sample linear time (1+ε) algorithm for k-means clustering in any dimensions.In:Proc of the 45th FOCS.Piscataway,NJ:IEEE Press,2004.454-462
  • 9[9]Vaidya.An O(nlogn) algorithm for the all-nearest-neighbors problem.Discrete Computer Geom,1989,4(2):101-115

二级参考文献11

  • 1Arora S, Raghavan P, Rao S. Approximation schemes for euclidean k-Medians and related problems. In: Jeffrey V, ed. Proc. of the 30th Annual ACM Symp. on Theory of Computing. New York: ACM Press, 1998. 106-113.
  • 2Badoiu M, Har-Peled S, Indyk P. Approximate clustering via core-sets. In: John R, ed. Proc. of the 34th Annual ACM Symp. on Theory of Computing. New York: ACM Press, 2002. 250-257.
  • 3Lin JH, Vitter JS. Approximation algorithms for geometric Median problems. Information Processing Letters, 1992,44(5):245-249.
  • 4Charikar M, Guha S, Tardos E, Shmoys D. A constant-factor approximation algorithm for the k-Median problem (Extended Abstract). In: Jeffrey V, ed. Proc. of the 31th Annual ACM Symp. on Theory of Computing. New York: ACM Press, 1999. 1-10.
  • 5Jain K, Vazirani V. Primal-Dual approximation algorithms for metric facility location and k-Median problems. In: Alok A, ed. Proc. of the 40th Annual Symp. on Foundations of Computer Science. Washington: IEEE Computer Society, 1999. 2-13.
  • 6Charikar M, Guha S. Improved combinatorial algorithms for the facility location and k-Median problems. In: Alok A, ed. Proc. of the 40th Annual Symp. on Foundations of Computer Science. Washington: IEEE Computer Society, 1999. 378-388.
  • 7Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V. Local search heuristics for k-Median and facility location problems. In: Jeffrey V, ed. Proc. of the 33rd Annual ACM Symp. on Theory of Computing. New York: ACM Press, 2001. 21-29.
  • 8Lin JH, Vitter JS. ε-Approximations with minimum packing constraint violation. In: Rao K, ed. Proc. of the 24th Annual ACM Symp. on Theory of Computing. New York: ACM Press, 1992. 771-782.
  • 9Guha S, Khuller S. Greedy strikes back: Improved facility location algorithms. In: Howard K, ed. Proc. of the 9th Annual ACM-SIAM Symp. on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 1998. 649-657.
  • 10Feige U. A threshold of lnn for approximating set-cover. Journal of the ACM, 1998,45(4):634-652.

共引文献7

同被引文献63

引证文献5

二级引证文献106

计算机研究与发展
2008年 第z1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部