K-means

2024-03-21 20:14:40

K-means

  • K-means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也可以，K-means算法有大量的变体，还有一次额优化的k-means++和距离优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。

K-means原理

  • k-means算法的思想很简单，对于给定的样本集，按照样本之间的距离，将样本划分为k个簇。让簇内的点尽量紧密的链接在一起，而让簇间的距离尽可能大。
  • 如果用数据表达式表示，假设簇划分为（C1，C2，… Ck），则我们的目标是最小化平方误差E:
    E = ∑ i = 1 k ∑ x ∈ C i ∣ ∣ x − μ i ∣ ∣ 2 2 E=\sum_{i=1}^k\sum_{x\in{C_{i}}}||x-\mu_{i}||_{2}^2 E=i=1∑k​x∈Ci​∑​∣∣x−μi​∣∣22​,其中μi ,其中μi是簇Ci的均值向量，有时也称为质心，表达式为：
    μ i = 1 ∣ C i ∣ ∑ x ∈ C i x \mu_{i}=\frac{1}{|C_{i}|}\sum_{x\in{C_{i}}}x μi​=∣Ci​∣1​x∈Ci​∑​x如果我们想直接求上诉的最小值并不容易，这是一个NP的难题，因此只能采用启发式的迭代方法。
    K-means
    a表示初始数据集，假设k=2，在b中我们选择了两个k类所对应的类别质心即途中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记（用不同的颜色标记）每个样本的类别所属的类别（同一个样本距离质心越近就属于离它最近的类别）如c图**，接下来需要再次确定质心**，再次计算样本到红色和蓝色的距离，再分类，新的质心已经发生了变化，如图e，（所有点的类别标记为距离最近的质心的类别并求新的质心）

对传统的k-means算法的基本流程总结

  • 对于k-means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的经验选择一个合适的k值，如果没有什么经验则可以通过交叉验证选择一个合适的k值，
  • 再确定好k值后，我们需要选择空格初始化的质心，就像上图中b的随机的质心，由于我们是启发式方法，k个初始化的质心的位置选择对最后的聚合结果和运行时间会产生重要影响，因此需要选择合适的k和质心，最好这些质心不能靠的太近。
  • 步骤：
  • 输入样本集D={x1,x2,…xm},聚类的簇树k，最大迭代次数N。
  • 输出是簇划分C={C1,C2,…Ck}
  • 1 从数据集D中随机选择k个样本作为初始的k个质心向量:{μ1,μ2,…,μk}
  • 2 对于n=1，2，…，N
    • a 将簇划分为C初始化为Ct=∅t=1,2…k
    • 对于i=1，2，，…m,计算样本xi 和各个质心向量μj(j=1,2,…k)的距离:
      d i j = ∣ ∣ x i − μ j ∣ ∣ 2 2 d_{ij}=||x_{i}-\mu_{j}||_2^2 dij​=∣∣xi​−μj​∣∣22​，将Xi标记为最小的dij所对应的类别 λi，此时更新Cλi=Cλi∪{xi}
    • 对于j=1，2，…，k对Cj 中所有的样本点重新计算新的质心
    • 如果所有的k个质心向量都没有发生变化，则转到步骤3，
  • 输出簇划分C={C1,C2,…Ck}

K-Means初始化优化K-Means++

  • 在上节我们提到，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢。K-Means++算法就是对K-Means随机初始化质心的方法的优化。
  • 从输入的数据点集合中随机选择一个点作为第一个聚类中心μ1
  • 对于数据集中的每一个点xi，计算它与已经选择的聚类中心的距离
    D ( x i ) = a r g m i n ∣ ∣ x i − μ r ∣ ∣ 2 2 r = 1 , 2 , . . . k s e l e c t e d D(xi)=argmin||xi−μr||_2^2r=1,2,...kselected D(xi)=argmin∣∣xi−μr∣∣22​r=1,2,...kselected
  • 选择一个新的数据点作为新的聚类中心，选择的原则是:D(x) 较大的点，被选取作为聚类中心的概率较大
  • 重复b和c直到选择出K个聚类质心
  • 利用这k个质心来作为初始质心去运行标准的K-Means算法

K-Means距离计算优化elkan K-Means

  • 在传统的K-means算法中，我们每次迭代时，要计算所有的样本点到所有的质心的距离，这样会比较耗时，那么，对于距离的计算有没有可以进行优化的呢，elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。那么哪些距离不需要计算呢？
  • elkan K-means利用了两边之和大于等于第三边，以及两边之差小于第三边的三角性质，来减少距的计算。
  • 第一种规律是对于一个样本点x和两个质心μj1,μj2。如果我们预先计算出了这两个质心之间的距离D(j1,j2)，则如果计算发现2D(x,j1)≤D(j1,j2),我们立即就可以知道D(x,j1)≤D(x,j2),此时我们不需要再计算D(x,j2),也就是说省了一步距离计算。
  • 第二种规律是对于一个样本点x和两个质心μj1,μj2,D(x,j2)≥max{0,D(x,j1)−D(j1,j2)} 。
  • 利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法。

大样本优化Mini Batch K-Means

  • 在统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。
  • 顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精度也会有一些降低。一般来说这个幅度在可以接受的范围内。
  • 在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的？一般是通过无放回的随机采样得到的。
  • 为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。

K-Means与KNN

  • 初学者很容易把K-Means和KNN搞混，两者其实差别还是很大的。
  • k-means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对于测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试的类别，而K-means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本簇类别。

k-means总结

  • K-Means是个简单实用的聚类算法，这里对K-Means的优缺点做一个总结。
  • K-Means的主要优点有：
  • 1）原理比较简单，实现也是很容易，收敛速度快。
  • 2）聚类效果较优。
  • 3）算法的可解释度比较强。
  • 4）主要需要调参的参数仅仅是簇数k。
  • K-Means的主要缺点有：
  • 1）K值的选取不好把握
  • 2）对于不是凸的数据集比较难收敛
  • 3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
  • 4） 采用迭代方法，得到的结果只是局部最优。
  • 5） 对噪音和异常点比较的敏感。

K-Means案例

  • 网页浏览数据分析
  • 数据来源
  • 1、读取基本的数据并且把数据字符串转换为整数
#读取数据，用'\t'进行分割
raw_data = pd.read_csv("../data/ad_performance.csv", delimiter="\t")
# 2 字符串分类转整数类型
# 定义要转换的数据
conver_cols = ['素材类型', '广告类型', '合作方式', '广告尺寸', '广告卖点']
# 得到转换后的conver_cols的数据项
convert_matrix = data_fillna[conver_cols]
# lines得到总的行数
lines = data_fillna.shape[0]
dict_list = []
unique_list = []
"""
unique_list得到所有的类别
"""
# 获得所有列的唯一值列表
for col_name in conver_cols:
    # 拿到所有的类别
    cols_unique_value = data_fillna[col_name].unique().tolist()
    unique_list.append(cols_unique_value)
# print(unique_list)
# 将每条记录的具体值
# 跟其在唯一值列表中的索引做映射
for line_index in range(lines):
    # each_record映射出所有的需要转换的数据
    each_record = convert_matrix.iloc[line_index]
    # print(each_record)
    for each_index, each_data in enumerate(each_record):
        list_value = unique_list[each_index]
        each_record[each_index] = list_value.index(each_data)
    each_dict = dict(zip(conver_cols, each_record))
    dict_list.append(each_dict)
# 使用DictVectorizer将字符串转换为整数
model_dvtransform = DictVectorizer(sparse=False, dtype=np.int64)
data_dictvec = model_dvtransform.fit_transform(dict_list)
  • 2、数据标准化
scale_matrix = data_fillna.iloc[:, 1:8]  # 获得要转换的矩阵前8列
minmax_scaler = MinMaxScaler()  #
data_scaled = minmax_scaler.fit_transform(scale_matrix)
  • 3、合并所有输入维度
X = np.hstack((data_scaled, data_dictvec))
'''
步骤5 通过平均轮廓系数检验得到最佳KMeans聚类模型
'''
score_list = list()  # 用来存储每个k下模型的平均轮廓系数
silhouette_int = -1  # 初始化的平均轮廓阀值
for n_clusters in range(2, 10):  # 遍历从2-10几个有限组
    model_kmeans = KMeans(n_clusters=n_clusters, random_state=0)  # 建立聚类模型对象
    # print(model_kmeans)
    cluster_labels_tmp = model_kmeans.fit_predict(X)  # 训练聚类模型
    silhouette_tmp = metrics.silhouette_score(X, cluster_labels_tmp)  # 得到每个k下的平均轮廓系数
    # print(silhouette_tmp)
    if silhouette_tmp > silhouette_int:  # 如果平均轮廓系数更高
        best_k = n_clusters  # 将最好的k存储下来
        # print(best_k)
        silhouette_int = silhouette_tmp  # 将最好的平均轮廓得分存储下来
        # print(silhouette_int)
        best_kmeans = model_kmeans  # 将最好的模型存储下来
        cluster_labels_k = cluster_labels_tmp  # 将最好的聚类标签存储下来
        # print(cluster_labels_k)
    score_list.append([n_clusters, silhouette_tmp])
# print(score_list)
print('{:-^60}'.format('K value and silhouette summary:'))
print(np.array(score_list))  # 打印输出k下的详细得分
print('Best K is:{0} with average silhouette of {1}'.format(best_k, silhouette_int.round(4)))
  • 4、针对聚类结果的特征分析
'''
步骤6 针对聚类结果的特征分析
'''
# 6.1 将原始数据与聚类标签整合
cluster_labels = pd.DataFrame(cluster_labels_k, columns=['clusters'])  # 获得训练集下的标签信息
merge_data = pd.concat((data_fillna, cluster_labels), axis=1)  # 将原始处理过的数据跟聚类标签整合
# 6.2 计算每个聚类类别下的样本量和样本占比
clustering_count = pd.DataFrame(merge_data['渠道代号'].groupby(merge_data['clusters']).count()).T.rename({'渠道代号': 'counts'})
clustering_ratio = (clustering_count / len(merge_data)).round(2).rename({'counts': 'percentage'})

# 6.3 计算各个聚类类别内部最显著特征值
cluster_features = []  # 存储最终合并后的所有特征信息
for line in range(best_k):  # 读取每个类索引
    label_data = merge_data[merge_data['clusters'] == line]  # 获得特定类的数据
    part1_data = label_data.iloc[:, 1:8]  # 获得数值型数据特征
    part1_desc = part1_data.describe().round(3)  # 描述性统计信息
    merge_data1 = part1_desc.iloc[2, :]  # 得到数值型特征的均值

    part2_data = label_data.iloc[:, 8:-1]  # 获得字符型数据特征
    part2_desc = part2_data.describe(include='all')  # 获得描述统计信息
    merge_data2 = part2_data.iloc[2, :]  # 获得字符型特征的最频繁值

    merge_line = pd.concat((merge_data1, merge_data2), axis=0)  # 按行合并
    cluster_features.append(merge_line)  # 将每个类别下的数据特征追加到列表

# 6.4 输出完整的类别特征信息
cluster_pd = pd.DataFrame(cluster_features).T  # 将列表转化为矩阵
print('{:-^60}'.format('Detailed features for all clusters:'))
all_cluster_set = pd.concat((clustering_count, clustering_ratio, cluster_pd), axis=0)  # 将每个列别的所有信息合并
print(all_cluster_set)
  • 各类别显著值特征对比
# 7.1 各类别数据预处理（标准化）
num_sets = cluster_pd.iloc[:6, :].T.astype(np.float64)  # 获取要展示的数据
num_sets_max_min = minmax_scaler.fit_transform(num_sets)  # 获得标准化后的数据
print(num_sets)
print('-'*60)
print(num_sets_max_min)


fig = plt.figure(figsize=(6,6))  # 建立画布
ax = fig.add_subplot(111, polar=True)
labels = np.array(merge_data1.index)
cor_list = ['#FF0000', '#FF7400', '#009999', '#00CC00']
angles = np.linspace(0, 2 * np.pi, len(labels), endpoint=False)
angles = np.concatenate((angles, [angles[0]]))
for i in range(len(num_sets)):  # 循环每个类别
    data_tmp = num_sets_max_min[i, :]  # 获得对应类数据
    data = np.concatenate((data_tmp, [data_tmp[0]]))  # 建立相同首尾字段以便于闭合
    ax.plot(angles, data, 'o-', c=cor_list[i], label="第%d类渠道"%(i-1))  # 画线
    ax.fill(angles, data,alpha=0.5)
ax.set_thetagrids(angles * 180 / np.pi, labels, fontproperties="SimHei")  # 设置极坐标轴
ax.set_title("各聚类类别显著特征对比", fontproperties="SimHei")  # 设置标题放置
ax.set_rlim(-0.2, 1.2)  # 设置坐标轴尺度范围
plt.legend(loc="upper right" ,bbox_to_anchor=(1.2,1.0))  # 设置图例位置

聚类

  • 什么是聚类
    统计数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性，常见的包括在坐标系中更加短的空间距离等。
  • 聚类的应用
    在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。诸如此类，聚类有着广泛的实际应用。

K-means（k均值）聚类算法

  • 什么是k-means聚类算法
    k-平均算法（英文：k-means clustering）源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是：把 n个点划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。k-平均聚类与k-近邻之间没有任何关系（后者是另一流行的机器学习技术）。
    K-Means是发现给定数据集的K个簇的聚类算法，之所以称之为K-均值是因为它可以发现K个不同的簇，且每个簇的中心采用簇中所含值的均值计算而成。簇个数K是用户指定的，每一个簇通过其质心，即簇中所有点的中心来描述。聚类与分类算法的最大区别在于分类的目标类别已知，而聚类的目标类别是未知的。

  • k-means工作流程
    创建 k 个点作为起始质心（通常是随机选择）
    当任意一个点的簇分配结果发生改变时（不改变时算法结束）
    对数据集中的每个数据点
    对每个质心
    计算质心与数据点之间的距离
    将数据点分配到距其最近的簇
    对每一个簇, 计算簇中所有点的均值并将均值作为质心

  • k-means评价标准
    k-means算法因为手动选取k值和初始化随机质心的缘故，每一次的结果不会完全一样，而且由于手动选取k值，我们需要知道我们选取的k值是否合理，聚类效果好不好，那么如何来评价某一次的聚类效果呢？也许将它们画在图上直接观察是最好的办法，但现实是，我们的数据不会仅仅只有两个特征，一般来说都有十几个特征，而观察十几维的空间对我们来说是一个无法完成的任务。因此，我们需要一个公式来帮助我们判断聚类的性能，这个公式就是SSE (Sum of Squared Error, 误差平方和 ），它其实就是每一个点到其簇内质心的距离的平方值的总和，这个数值对应kmeans函数中clusterAssment矩阵的第一列之和。 SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。 因为对误差取了平方，因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数，但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。

  • k-means优缺点

  • 优点
    属于无监督学习，无须准备训练集
    原理简单，实现起来较为容易
    结果可解释性较好

  • 缺点
    聚类数目k是一个输入参数。选择不恰当的k值可能会导致糟糕的聚类结果。这也是为什么要进行特征检查来决定数据集的聚类数目了。
    可能收敛到局部最小值, 在大规模数据集上收敛较慢
    对于异常点、离群点敏感

上一篇：import * as 是什么？


下一篇：Failing does not mean you're a failure