设将d维数据集X＝{x_i|x_i∈R^d，i=1，2，……，n}聚集成k个簇w₁，w₂，……，w_k，它们的质心依次为c₁，c₂，……c_k，其中n_i是簇w_i中数据点的个数。采用误差平方和准则函数作为目标函数来显式地判断算法是否结束，如公式(1)。利用误差平方和准则函数能把真正属于同一类的样本聚合成一个类型的子集，而把不同类的样本分开^[5]。
   
    当准则函数Jc收敛后，算法结束。k-means算法步骤描述如下(称为k-means_1)：
    (1)给定大小为n的数据集X，令I=1，选取k个初始聚类中心c_j(I)，j=1，2，3，……，k。
    (2)以c_j(I)为参照点对X进行划分，计算每个样本数据对象与聚类中心的距离。若d(x_i，c_k(I))=min{d(x_i，c_j(I))，i=1，2，……n}，其中j=1，2，……，k，i=1，2，……n，则将x_i划分到簇w_k。
    (3)令I=I+1，计算新的聚类中心和误差平方和准则函数的值
    (4)若|J_c(I+1)c(I)|<ξ成立，则算法结束。否则，令I=I+1，返回(2)执行。
2.2 改进的k-means算法
    在上述k-means算法中，一次迭代内把每一个数据对象分到离它最近的聚类中心所在类，这个过程的时间复杂度为O(nkd)。n指的是总的数据对象的个数，k是指定的聚类数，d是数据对象的维数。新的分类产生以后需要计算新的聚类中心，这个过程的时间复杂度为O(nd)。因此，这个算法一次迭代需要的总时间复杂度为O(nkd)。如果数据量比较大，算法的时间开销也是相当可观的^[6]。
    针对处理大数据量时开支大的不足，本文提出了一种借用三角形三边不等定律的思想，即三角形两边之和大于第三边的定律，减少每次迭代的计算次数的改进k-means算法。
    在k-means算法的第一个循环阶段，每次迭代中要计算每一个样本数据到各个聚类中心的距离，依次比较得到与之距离最小的一个类中心，并被分配到这个类中。如果能找到一个方法，避免一些不必要的比较和距离计算，就能节省运行的时间开支。在k-means算法中采用的是欧几里德距离，因此可以考虑借用几何三角形中三边关系定理：两边之和大于第三边，从而简化计算比较过程。
    令x_i∈X，d(c_k，c_j)为二个聚类中心的距离，d(c_k，c_j)、d(x_i，c_k)与d(x_i，c_j)三边构成了一个如图2所示的三角形。
    则有d(c_k，c_j)≤d(x_i，c_k)+d(x_i，c_j)
    即：d(c_k，c_j)－d(x_i，c_k)≤d(x_i，c_j)
    如果d(c_k，c_j)≥2d(x_i，c_k)，则有：d(x_i，c_k)≤d(x_i，c_j)，即x_i到中心c_j的距离比到c_k的距离大。因此在d(c_k，c_j)≥2d(x_i，c_k)的前提下，就不必计算d(x_i，c_j)了。k-means算法的演变如下所示(称为k-means_2)：
    (1)给定大小为n的数据集X，令I=1，选取k个初始聚类中心c_j(I)，j=1，2，3，……，k。
    (2)计算每两个聚类中心间的距离d(c_i(I),c_j(I))，其中i=1，2，……，k，j=1，2，……，k。
    (3)设x_i当前所在类为w_m，计算x_i与w_m类中心的距离d(x_i，c_m(I))，若d(c_m(I),c_j(I))≥2d((x_i，c_m(I))不成立，则计算d(x_i，c_j(I))；若d(x_i,c_j(I))＜d(x_i，c_m(I))，则暂时将x_i分配到w_j，返回(3)循环运行，最终将x_i划分到簇w_m中。其中j=1，2，……，k，i=1，2，……n，m=1，2，……n。
    (4)令I=I+1，计算新的聚类中心和误差平方和准则函数的值
    (5)若|J_c(I+1)c(I)|<ξ成立，则算法结束。否则，令I=I+1，返回(2)执行。
    这里对算法k-means_1和k-means_2作一个比较。在第二个循环阶段重新计算聚类中心时，这二个算法的时间复杂度是相同的。但是在第一个循环阶段指定聚类簇时，改进的k-means_2算法显然减少了计算量。先考虑一个样本点的情况。在k-means_1算法中，计算样本点到各中心点的距离的次数是k次，而k-means_2算法中，在最好情况下计算样本点到各中心点的距离的次数是1次，最坏情况下计算样本点到各中心点的距离的次数是k次。假设α为第一循环阶段一次迭代时一个样本点的平均计算次数，则有α3  客户细分的实现
    如上所述，本文采用改进的k-means算法对某酒店的现有客户群进行细分，建立了RFM模型。根据酒店用户的要求，分别把R、F、M三个要素划分为3个等级，结合这三个指标，可以把客户分成9个等级，也就是聚类成9个簇。
    实现聚类算法的主要数据结构如下：
    (1)记录一个簇的信息
    Public Structure clusterlist
      Dim Mean As Double′簇均值
      Dim ClusterNum As Integer′簇中记录数
      Dim CluserId As Integer′簇号
      Dim SquareError As Double′簇中平方误差和
    End Structure
    (2)记录一个簇中所有记录的关键字
    Public Structure recordnum
      Dim culsterid As Integer ′簇号
      Dim recordid As ArrayList ′记录关键字
    End Structure
    (3)记录各个聚类中心间的距离
    Dim mean_dist(，)as double ′用二维数组记录中心间的两两距离
    实现聚类算法的主要函数有：
    (1)init_mean( )：设定初始聚类中心。
    (2)calc_mean_eucli( )：计算各中心间的欧几里德距离。
    (3)calc_sam_eucli( )：计算各个样本点到中心欧几里德距离。
    (4)calc_euclidean( )：计算二个点间的欧几里德距离公式。
    (5)find_cluster( )：找到离样本点最近距离的簇,并分配样本点到该簇。
    (6)calc_new_mean( )：一次划分后计算新的聚类中心。
    (7)calc_Jc( )：计算误差平方和准则函数。
    (8)kmeans( )：运行k-means算法，若不满足算法结束条件则递归调用。
    (9)show_cluster( )：展示一个簇内的客户数据。
    聚类算法实现界面如图3所示，用户首先要输入允许的误差准则和聚类要生成的簇数。