k-means与k-median是聚类分析的典型计算问题模型,它们也是源自同样背景的兄弟问题。将给定点集划分为k个子集,每个子集求一个中心点,若要求点集划分使每个顶点到其中心点的距离平方和最小,则为k-means问题：若要求点集划分使每个顶点到其中心点的距离之和最小,则为k-median问题。本文讨论欧氏平面上的k-means问题与Mmetric空间上k-median问题的随机求解算法。欧氏平面上的k-means问题描述为：给定点集P,要求在欧氏平面寻找k个中心点,将P划分为k个子集P1,…,Pk,优化目标为给定点到其所属子集中心点的距离平方和最小。Metric空间k-median问题描述为：给定设施集合F和客户集合C,F∪C为Metric空间中的点集,d(fi,Cj)∈Z+表示设施fi∈F为客户Cj∈C提供服务的费用,欲在F中选择至多k个设施为C中的客户服务,并使总的服务费用最小Drineas证明了即使k=2,在欧氏空间上,k-means问题为NP-Hard问题；Hamiki则证明了Metric空间k-median问题为NP-Hard问题。给定一个正整数θ(≤n/k),若划分出的k个子集的大小均不小于给定的e,则称这样的点集划分是均衡的,θ称为相应问题的均衡限度。本文讨论欧氏平面k-means与Metric空间k-median问题及其变种问题的随机算法,主要完成如下结果：改进了Ostrovsky所给出的k-means问题的(1+ε)-随机近似算法；利用均衡限度e值,设计出k-median问题的反向贪心随机算法；设计出求解k-means问题的局部搜索随机算法；基于k个初始中心点的选取,改进了Lloyd算法。具体研究工作为：(1)改进Ostrovsky所给出的k-means问题的(1+ε)-随机近似算法。Ostrovsky算法的时间复杂度为O(2O(k(1+α2)/ε)dn),其中d为问题实例的空间维数,n为实例点集的大小,α为小于1的分隔系数。我们提出改进算法,改进算法的时间复杂度期望值为0(2O(kα2/ε)dn)。给定空间点集P,设P1*,…,Pk*代表最优解的k个划分子集,Ostrovsky算法的基本策略为：针对每个最优划分子集Pi*,从P中求出两个子集Bi和Ri,,使它们满足Bi(?)Pi*(?)Ri且|Pi*|≥β|Ri|(0＜β≤1)。从每个Ri中随机选取4／(βε)个点,记取样点集为Si,分别由Si(1≤i≤k);中选择大小为2／ε个点一个的子集,将该子集的质心点作为一个中心点,得到的k个中心点即为一个k-means聚类的可行解。从S1,S2,…,Sk中枚举所有可能的k个中心点,使目标函数最小的k个中心点作为算法的最终解。我们对Ostrovsky算法进行了如下改进。首先,放大了选取样本参数值β。原算法选择β=1/(1+144α2),本文证明可选择一个更大的β值(=1/(1+73.5α2),从而减少了算法选取样本点的个数。其次,利用关系Bi(?)Pi*(?)Ri,将取样点划分为两部分：一部分是能够确定属于最优子集Pi*中的点；另一部分是不能确定属于Pi*中的点。首先从取样点中找出满足第一部分的点,仅枚举属于第二部分的所有可能的点,使这两部分点数之和为2／ε即可。与原算法相比,枚举点数得以减少,改进算法的时间复杂度期望值为O(2O(kα2/ε)dn)。原算法描述中未能给出计算(1+ε)-近似解的成功概率表达式,我们证明改进算法的成功概率为(1/2(1-e(-1/26)))k(1-O((?))。(2)基于均衡限度θ,设计出k-median问题近似性能比为3+O(ln(ln(K)/α)的反向贪心随机算法,其中α=(θk/n)为小于1的均衡限度参数。算法首先从客户点集c中均匀地随机生成一个取样子集S(|S|=O(k/αln(k)),S以较高的概率包含c的每个最优划分子集中至少一个客户点。从设施集合F中找出与S中每个点最近的设施点,由这些最近的设施点组成F的一个子集Fs(|Fs|≤|S|)。最后以Fs和C作为实例点集调用反向贪心算法,从Fs中找出k个设施。我们证明了该随机算法以较高的概率达到近似性能比为(3+O(ln(ln(k)/α))。算法的时间复杂度为O([k/αln(k)]2(n+m)),其中n、m分别代表设施集合F以及客户点集C的大小与Chrobak所给出的贪心算法相比,由于Chrobak算法的近似性能比界于Ω(ln(n)/ln(ln(n))与O(ln(n))之间,算法时间复杂度为O(n3),因此,当均衡限度参数α的值较大时,我们的算法优于Chrobak的反向贪心算法。(3)设计出求解k-means问题的局部搜索随机算法。Minjun Song给出的局部搜索算法的基本思想：将给定空间实例点集P作为中心点的候选点集,从候选中心点集中任取k个点作为初始中心点,通过多次在候选中心点集与k个中心点中交换部分点,找出一个局部最优解。如果选取k个中心点分属于k个不同最优子集中的一个点时,我们证明算法近似性能比的期望值至多为2。基于该结论,我们从两个方面对MingjunSong的算法提出随机策略：第一,选取k个初始中心点时,从P中非均匀地随机选取k个初始中心点,使得这k个点尽可能地分属于k个不同最优子集中的点。第二,给出一个新的候选中心点集的生成方法。该方法基于均衡限度,从给定实例点集中找出一个取样子集S,S以较高的概率包含每个最优划分子集中的一部分点。以S代替整个给定点集P作为候选中心点集,显然能够减小候选中心点集,从而达到降底算法时间复杂度的目的。Minjun Song给出局部搜算法的时间复杂度为O(n2k3log(n)d),本文算法的时间复杂度为O(nk3log2(k))d/α), n为给定实例点集大小,α为小于1的均衡限度参数。实验结果表明：新算法所求的解值以及算法的运算时间均优于Minjun Song给出的局部搜索算法。(4)Lloyd算法是经典的k-means问题求解算法,很多聚类计算任务都选择该算法。该算法的基本思想：首先从P中任选k个点作为初始的中心点,然后将P中的点分配给各个中心点,得到k个划分子集P1,…,Pk,计算每个子集Pi的质心点并对P中的点重新分组。重复以上过程直到中心点不再变化为止。本文对Lloyd算法进行改进。具体改进为：选择k个初始中心点时,利用局部搜索随机算法中选取k个初始中心点的策略从P中非均匀地随机选择k个点；在划分k个子集时,利用Elkan三角不等式点集分配策略避免冗余的距离计算。实验结果表明：无论是算法所求解的精度还是算法的运算时间,改进算法均有很大程度的提高。