IT技术之家

首页 > 人工智能

人工智能

【数据聚类】第三章第三节1:类K-Means算法之K-中心点算法(PAM算法和CLARA算法)_我擦我擦_kmeans++就是k中心点算法吗

发布时间:2022-10-24 17:13:35 人工智能 0次 标签:算法 聚类 kmeans
kkk-中心点算法:在kkk-meansmeansmeans算法中,中心点会被设定为当前簇中所有数据点的平均值,而这个平均值极大可能是不包含在初始数据集中的,也即它是一个虚拟的点。但在kkk-中心点算法中,选取的是到当前簇中所有其他数据点的距离之和最小的点作为这一簇的中心点,这个点一定是在初始数据集中包含的点中选取的。相比于簇均值,真实的数据点受到离群点的影响会更小一些,因此该种算法对数据集中存在的噪声点和离群点有着更强的鲁棒性该算法以绝对误差和作为算法的目标函数E(C)=∑k=1K∑xi∈Ck∣xi?c...

文章目录

一:K-中心点算法总论(最常见实现方式是PAM算法)(1)算法思想(2)算法流程(3)算法缺陷 二:PAM算法(1)PAM算法思想(2)PAM算法流程(3)Python实现(4)效果展示(5)算法缺陷 三:CLARA算法(1)算法思想(2)算法流程(3)Python实现(4)效果展示(5)算法缺陷

一:K-中心点算法总论(最常见实现方式是PAM算法)

(1)算法思想

k k k-中心点算法:在 k k k- m e a n s means means算法中,中心点会被设定为当前簇中所有数据点的平均值,而这个平均值极大可能是不包含在初始数据集中的,也即它是一个虚拟的点。但在 k k k-中心点算法中,选取的是到当前簇中所有其他数据点的距离之和最小的点作为这一簇的中心点,这个点一定是在初始数据集中包含的点中选取的。相比于簇均值,真实的数据点受到离群点的影响会更小一些,因此该种算法对数据集中存在的噪声点和离群点有着更强的鲁棒性

该算法以绝对误差和作为算法的目标函数

E ( C ) = ∑ k = 1 K ∑ x i ∈ C k ∣ x i ? c k ∣ E(C)=\sum_{k=1}^{K}\sum_{x_{i}\in C_{k}}|x_{i}-c_{k}| E(C)=k=1K?xi?Ck?∑?∣xi??ck?

(2)算法流程

k k k-中心点算法流程:该算法首先从每个簇中随机选择一个对象作为代表对象,然后将其余非代表对象按照其与已选择的代表对象之间的距离来将其分配给最近的一个代表对象所属的簇。通过反复尝试使用非代表对象来代替当前代表对象可以改进聚类的整体质量

在替换代表对象时,对于每一个非代表对象 p p p,考虑以下四种情况

情况一: p p p当前从属于代表对象 O f O_{f} Of?的簇,如果 O f O_{f} Of?被 O r O_{r} Or?代替,且 p p p距离 O i O_{i} Oi?最近, i ≠ f i\neq f i?=f,那么 p p p将会被重新分配给 O i O_{i} Oi?

情况二: p p p当前从属于代表对象 O f O_{f} Of?的簇,如果 O f O_{f} Of?被 O r O_{r} Or?代替,且 p p p距离 O r O_{r} Or?最近,那么 p p p将会被重新分配给 O r O_{r} Or?

情况三: p p p当前从属于代表对象 O i O_{i} Oi?的簇, i ≠ f i\neq f i?=f,如果 O f O_{f} Of?被 O r O_{r} Or?代替,且 p p p距离 O i O_{i} Oi?仍最近,那么 p p p的从属不会发生变化

情况四: p p p当前从属于代表对象 O i O_{i} Oi?的簇, i ≠ f i\neq f i?=f,如果 O f O_{f} Of?被 O r O_{r} Or?代替,且 p p p距离 O r O_{r} Or?最近,那么 p p p将会被重新分配给 O r O_{r} Or?

(3)算法缺陷

相比于标准的 K K K- M e a n s Means Means算法, K K K-中心点算法加强了算法的鲁棒性,但没有解决标准 K K K- M e a n s Means Means算法中所包含的其他问题,而且 K K K-中心点的时间复杂度很大,达到

O ( k × ( n ? k ) 2 ) O(k×(n-k)^{2}) O(k×(n?k)2)

这是因为在得到每个簇的最终代表对象的过程中需要进行多次交换操作

二:PAM算法

(1)PAM算法思想

PAM算法:该算法将聚类结果的质量用一个评估对象及其代表对象之间的平均相异度函数来估算

E = ∑ j = 1 K ∑ p ∈ C j ( ∣ ∣ p ? O i ∣ ∣ 2 ) E=\sum_{j=1}^{K}\sum_{p\in C_{j}}(||p-O_{i}||^{2}) E=j=1K?p∈Cj?∑?(∣∣p?Oi?∣∣2)

该算法在最初选择了 k k k个中心点之后,对所有可能替代原有中心点的更好的数据点进行分析;算法会将两个数据点看做一个点对(一个点为中心点,一个点为从属点),通过进行距离的计算判断这种组合是否是一个更好的组合,最终得到一个满意的聚类结果

(2)PAM算法流程

输入:数据集D,划分簇的个数k
输出:k个簇的集合
从数据集D中任意选择k个对象作为初始簇中心
repeat
    把剩余对象分配到距离最近的簇中心
    对于所有(中心点C,非中心点P)的二元组。尝试将中心点与非中心点交换,并计算聚类误差
    若交换之后聚类误差降低了,则使用该非中心点替换中心点
until k个簇的簇中心不再发生变化

(3)Python实现

from sklearn.datasets import make_blobs
from matplotlib import pyplot
import numpy as np
import random
import pickle
import copy


# 欧式距离
def euclid_distance(x, y):

    return np.sqrt(sum(np.square(x - y)))

# 划分
def assign_points(data_set, centorids):
    cluster_points = [[centorid] for centorid in centorids]  # 第centorid个元素,为第centorid类数据点的集合
    cluster = []

    for each_point in data_set:
        distances = []
        for each_centorid in centorids:
            distances.append(euclid_distance(each_point, each_centorid))
        nearest_centorid_index = np.argmin(distances)  # 最近簇中心
        cluster.append(nearest_centorid_index)  # 划分
        cluster_points[nearest_centorid_index].append(each_point)  # 将该点加入到距离最近的簇中

    return cluster, cluster_points


def pam(data_set, k):
    data_index = list(range(len(data_set)))
    random.shuffle(data_index)  # 洗牌
    init_centorids_index = data_index[:k]
    centorids = data_set[init_centorids_index, :]  # k个质心
    cluster = []   # 每个数据点所属簇的编号
    stop_flag = False  # 停止标签

    while not stop_flag:
        stop_flag = True
        cluster_points = [[]]
        cluster_points = [[centorid] for centorid in centorids]  # 第centorid个元素,为第centorid类数据点的集合

        cluster = []

        # 第一次划分
        for each_point in data_set:
            distances = []
            for each_centorid in centorids:
                distances.append(euclid_distance(each_point, each_centorid))
            nearest_centorid_index = np.argmin(distances)  # 最近簇中心
            cluster.append(nearest_centorid_index)  # 划分
            cluster_points[nearest_centorid_index].append(each_point)  # 将该点加入到距离最近的簇中

        # 计算出当前中心点和其他所有点距离总和
        distances = []
        for i in range(k):
            distances.extend([euclid_distance(point_1, centorids[i]) for point_1 in cluster_points[i]])
        old_distances_sum = sum(distances)

        # 尝试让整个数据集的每个非中心点替换中心点,若聚类误差降低,则改变中心点
        for each_cluster in range(k):
            for each_point in data_set:
                new_centorids = copy.deepcopy(centorids)
                new_centorids[each_cluster] = each_point  # 假设
                cluster, cluster_points = assign_points(data_set, new_centorids)

                # 计算新的聚类误差
                distances = []
                for i in range(k):  # 对于每一个簇
                    distances.extend([euclid_distance(point_1, centorids[i]) for point_1 in cluster_points[i]])
                new_distances_sum = sum(distances)  # 新代价

                # 判断聚类误差是否降低
                if new_distances_sum < old_distances_sum:
                    old_distances_sum = new_distances_sum
                    centorids[each_cluster] = each_point  # 修改簇中心
                    stop_flag = False

    return centorids, cluster

(4)效果展示

import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
import PAM

Iris_types = ['Iris-setosa', 'Iris-versicolor', 'Iris-virginica']  # 花类型
Iris_data = pd.read_csv('./dataSet/Iris.csv')
x_axis = 'PetalLengthCm'  # 花瓣长度
y_axis = 'PetalWidthCm'   # 花瓣宽度
# x_axis = 'SepalLengthCm'  # 花萼长度
# y_axis = 'SepalWidthCm'  # 花萼宽度

examples_num = Iris_data.shape[0]  # 样本数量
train_data = Iris_data[[x_axis, y_axis]].values.reshape(examples_num, 2)  # 整理数据

# 归一化
min_vals = train_data.min(0)
max_vals = train_data.max(0)
ranges = max_vals - min_vals
normal_data = np.zeros(np.shape(train_data))
nums = train_data.shape[0]
normal_data = train_data - np.tile(min_vals, (nums, 1))
normal_data = normal_data / np.tile(ranges, (nums, 1))

#  训练参数
k = 3  # 簇数
max_iterations = 50

centroids, cluster = PAM.pam(normal_data, k)
centroids = np.array(centroids)
cluster = np.array(cluster)


plt.figure(figsize=(12, 5), dpi=80)

#  第一幅图是已知标签或全部数据
plt.subplot(1, 2, 1)

for Iris_type in Iris_types:
        plt.scatter(Iris_data[x_axis], Iris_data[y_axis], c='black')
plt.title('raw')

# 第二幅图是聚类结果
plt.subplot(1, 2, 2)
for centroid_id, centroid in enumerate(centroids):  # 非聚类中心
    current_examples_index = (cluster == centroid_id).flatten()
    plt.scatter(normal_data[current_examples_index, 0], normal_data[current_examples_index, 1])

for centroid_id, centroid in enumerate(centroids):  # 聚类中心
    plt.scatter(centroid[0], centroid[1], c='red', marker='x')
plt.title('label kemans')
plt.show()

(5)算法缺陷

一般情况下,PAM算法只能处理小数据集,对于大数据集,在数据个数 n n n和聚类类别个数 k k k的值都很大的情况下,PAM算法在处理时将会花费极大的计算代价,算法每次迭代的时间复杂度为

O ( k × ( n ? k ) 2 ) O(k×(n-k)^{2}) O(k×(n?k)2)

三:CLARA算法

(1)算法思想

CLARA算法:PAM算法难以处理大数据集合,所以后续研究中,有人把PAM算法与抽样的方法相结合,提出了CLARA算法。这是一种基于选择的算法,在进行数据处理的过程中并没有考虑整个数据集,而是选择了其中一部分作为样本。具体来说:

首先从原始数据集选取部分数据构成一个新的但是规模较小的数据集作为算法的输入接着使用PAM算法对其进行处理,得到一个类中心点集合的输出在构建这一子数据集的过程中,如果是以随机的方式进行数据的选取,那么所构建的子数据集就可以作为原始的数据集的一个良好的表示

因此,算法在这样的子数据集运行得到的结果很可能与在整个数据集上运行得到的结果非常近似。CLARA算法通过从整体数据集中抽取多个样本集,并对每个样本集使用PAM算法的方式,最终从所有获得结果中选取最好的聚类结果作为算法的输出

(2)算法流程

循环执行以下步骤

    随机从整个数据集中抽取一个 N N N(例如(40+2 k k k))个对象的样本,调用PAM方法从样本中找出样本的 k k k个最优的中心点将这 k k k个中心点应用到整个数据集上,对于每一个非代表对象,判断它与样本中选出的哪个代表对象距离最近计算上一步中得到的聚类总代价,若该值小于当前的最小值,则替换,并保留在这次选样中得到的 k k k个代表对象作为到目前为止得到的最好的代表对象的集合

算法结束后输出一个最好的聚类结果

(3)Python实现

import random
import numpy as np
import PAM
import copy


# 距离
def euclid_distance(x, y):

    return np.sqrt(sum(np.square(x - y)))

# 划分
def assign_points(data_set, centorids):
    cluster_points = [[centorid] for centorid in centorids]  # 第centorid个元素,为第centorid类数据点的集合
    cluster = []

    for each_point in data_set:
        distances = []
        for each_centorid in centorids:
            distances.append(euclid_distance(each_point, each_centorid))
        nearest_centorid_index = np.argmin(distances)  # 最近簇中心
        cluster.append(nearest_centorid_index)  # 划分
        cluster_points[nearest_centorid_index].append(each_point)  # 将该点加入到距离最近的簇中

    return cluster, cluster_points

def clara(data_set, k):
    # 保存最好的结果
    ret_centorids = []
    ret_cluster = []

    # 初始代价(设置大一点)
    old = 1000000

    # 迭代
    for i in range(10):
        #  从原始数据集中进行抽样
        random_samples_indexes = random.sample(range(np.shape(data_set)[0]), 40+2*k)  # 无放回采样
        random_samples_indexes = sorted(random_samples_indexes)
        random_samples = data_set[random_samples_indexes, :]  # 抽取样本
        sample_centorids, _, _ = PAM.pam(random_samples, k)  # k个中心点

        cluster = []  # 每个数据点所属簇的编号
        cluster_points = [[]]
        cluster_points = [[centorid] for centorid in sample_centorids]  # 第centorid个元素,为第centorid类数据点的集合

        cluster = []

        # 根据sample_centorids进行划分
        for each_point in data_set:
            distances = []
            for each_centorid in sample_centorids:
                distances.append(euclid_distance(each_point, each_centorid))
            nearest_centorid_index = np.argmin(distances)  # 最近簇中心
            cluster.append(nearest_centorid_index)  # 划分
            cluster_points[nearest_centorid_index].append(each_point)  # 将该点加入到距离最近的簇中

        # 计算当前代价
        distances = []
        for i in range(k):
            distances.extend([euclid_distance(point_1, sample_centorids[i]) for point_1 in cluster_points[i]])
        current_distances_sum = sum(distances)

        # 如果代价变小则更换中心点
        if current_distances_sum < old:
            ret_centorids = sample_centorids
            old = current_distances_sum
            ret_cluster = cluster

    return ret_centorids, ret_cluster

(4)效果展示

import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
import CLARA

Iris_types = ['Iris-setosa', 'Iris-versicolor', 'Iris-virginica']  # 花类型
Iris_data = pd.read_csv('./dataSet/Iris.csv')
# x_axis = 'PetalLengthCm'  # 花瓣长度
# y_axis = 'PetalWidthCm'   # 花瓣宽度
x_axis = 'SepalLengthCm'  # 花萼长度
y_axis = 'SepalWidthCm'  # 花萼宽度

examples_num = Iris_data.shape[0]  # 样本数量
train_data = Iris_data[[x_axis, y_axis]].values.reshape(examples_num, 2)  # 整理数据

# 归一化
min_vals = train_data.min(0)
max_vals = train_data.max(0)
ranges = max_vals - min_vals
normal_data = np.zeros(np.shape(train_data))
nums = train_data.shape[0]
normal_data = train_data - np.tile(min_vals, (nums, 1))
normal_data = normal_data / np.tile(ranges, (nums, 1))

#  训练参数
k = 3  # 簇数
max_iterations = 50

centroids, cluster = CLARA.clara(normal_data, k)
centroids = np.array(centroids)
cluster = np.array(cluster)
print(centroids)
print(cluster)


plt.figure(figsize=(12, 5), dpi=80)

#  第一幅图是已知标签或全部数据
plt.subplot(1, 2, 1)

for Iris_type in Iris_types:
        plt.scatter(Iris_data[x_axis], Iris_data[y_axis], c='black')
plt.title('raw')

# 第二幅图是聚类结果
plt.subplot(1, 2, 2)
for centroid_id, centroid in enumerate(centroids):  # 非聚类中心
    current_examples_index = (cluster == centroid_id).flatten()
    plt.scatter(normal_data[current_examples_index, 0], normal_data[current_examples_index, 1])

for centroid_id, centroid in enumerate(centroids):  # 聚类中心
    plt.scatter(centroid[0], centroid[1], c='red', marker='x')
plt.title('label kemans')
plt.show()

(5)算法缺陷

相比于PAM算法,CLARA算法虽然能够处理更大的数据集合,但也存在以下缺陷

CLARA算法有效性取决于所抽取的样本大小。它是从整体的数据集中抽取一部分作为数据样本,然后再在样本中寻找 k k k个中心点。如果在多次取样计算过程中,每一次取样的结果都不能作为原始数据集的一个好的表示,那么就无法得到最佳中心点当所选取的样本发生偏斜时,样本就无法将初始数据集的特征很好表示出来,那么这种基于样本的聚类结果就不能代表整个数据集的类别特征