k-means聚类问题的改进近似算法  

Improved approximation algorithm for the k-means clustering problem

作　　者：王守强[1] 朱大铭[2] 史士英[1] 

机构地区：[1]山东交通学院信息工程系,山东济南250023 [2]山东大学计算机科学与技术学院,山东济南250101

出　　处：《山东大学学报（工学版）》2011年第4期125-132,共8页Journal of Shandong University（Engineering Science）

基　　金：山东省高校科技计划资助项目(J08LI69);山东交通学院自然科学基金资助项目(Z201024);山东交通学院博士启动基金项目

摘　　要：研究了Ostrovsky给出k-means问题的(1+ε)-近似算法,针对算法中取样参数小的以及枚举数量大的不足,证明了可以选择一个更大的取样参数减小取样点集,基于随机算法,提出新的枚举策略减少枚举数量。本文分析了算法的成功概率。改进算法的期望时间复杂度为O(2O(kα2/ε)dn),其中d、n分别为问题实例的空间维数和输入点个数,α是小于1的分隔系数。算法的成功概率为121-e-21εk(1-O(α))。与Ostrovsky给出的算法相比,算法的运算效率得到很大的提高。The（1＋ε）-randomized approximation algorithm proposed by Ostrovsky was investigated in depth,and an improved algorithm was proposed.The sample parameter was enlarged to reduce the size of sample set.Based on the randomized algorithm,a new method was proposed to decrease the enumerating number.Also,the successful probability of the improved algorithm was analyzed.The running time of the improved algorithm was O2Okα2εnd,where d,n denote the dimension and the number of the input points respectively,and α represents the separated coefficient that is lower than 1.The probability was 121-e-12εk（1-O（α））.Compared to the original algorithm,the improved algorithm runs more efficiency.

关 键 词：算法 聚类 概率 质心点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]