Может ли быть перекрытие в кластерах k-средних?

Question

Мне неясно, почему кластеризация k-средних может перекрываться в кластерах. От Чена (2018) я увидел следующее определение:

".. пусть наблюдения будут образцом, который будет разбит на K непересекающихся кластеров"

Однако я вижу наложение в моих графиках, и я не уверен, почему это так.

Для справки, я пытаюсь кластеризовать многомерный набор данных с тремя переменными (Recency, Frequency, Доход). Чтобы визуализировать кластеризацию, я могу проецировать 3D-данные в 2D с использованием PCA и запускать на этом k-means. Ниже приведен код и график, который я получаю:

df1=tx_user[["Recency","Frequency","Revenue"]]
#standardize
names = df1.columns
# Create the Scaler object
scaler = preprocessing.StandardScaler()
# Fit your data on the scaler object
scaled_df1 = scaler.fit_transform(df1)
df1 = pd.DataFrame(scaled_df1, columns=names)
df1.head()
del scaled_df1

sklearn_pca = PCA(n_components = 2)
X1 = sklearn_pca.fit_transform(df1)
X1 = X1[:, ::-1] # flip axes for better plotting
kmeans = KMeans(3, random_state=0)
labels = kmeans.fit(X1).predict(X1)
plt.scatter(X1[:, 0], X1[:, 1], c=labels, s=40, cmap='viridis');

from sklearn.cluster import KMeans
from scipy.spatial.distance import cdist

def plot_kmeans(kmeans, X, n_clusters=4, rseed=0, ax=None):
    labels = kmeans.fit_predict(X)

    # plot the input data
    ax = ax or plt.gca()
    ax.axis('equal')
    #ax.set_ylim(-5000,7000)
    ax.scatter(X[:, 0], X[:, 1], c=labels, s=40, cmap='viridis', zorder=2)

    # plot the representation of the KMeans model
    centers = kmeans.cluster_centers_
    radii = [cdist(X[labels == i], [center]).max()
             for i, center in enumerate(centers)]
    for c, r in zip(centers, radii):
        ax.add_patch(plt.Circle(c, r, fc='#CCCCCC', lw=3, alpha=0.5, zorder=1))

kmeans = KMeans(n_clusters=4, random_state=0)
plot_kmeans(kmeans, X1)

Мой вопрос: 1. Почему происходит наложение? Мое кластеризация неправильная, если есть? 2. Как k-means решает присвоение кластера в случае совпадения?

Спасибо

Ссылка: Chen, L., Xu, Z., Wang, H. & Liu, S. (2018). Упорядоченный алгоритм кластеризации на основе K-средних и метода PROMETHEE. Международный журнал машинного обучения и кибернетики, 9 (6), 917-926.

Answer 1

Алгоритм Kmeans - это итеративный алгоритм, который пытается разбить набор данных на заранее определенные K непересекающиеся подгруппы (кластеры), где каждая точка данных принадлежит только одной группе. Он пытается сделать точки данных между кластерами как можно более похожими, в то же время сохраняя кластеры как можно более разными (далекими). Он назначает точки данных кластеру так, чтобы сумма квадратов расстояния между точками данных и центроидом кластера (среднее арифметическое c всех точек данных, принадлежащих этому кластеру) была минимальной. Чем меньше вариаций у нас в кластерах, тем более однородные (похожие) точки данных находятся в одном кластере.

Возможно, вы сделали что-то не так ... У меня нет ваших данных, поэтому я не могу проверить это. Вы можете добавить границы и проверить их. См. Пример кода ниже.

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Voronoi

def voronoi_finite_polygons_2d(vor, radius=None):
    """
    Reconstruct infinite voronoi regions in a 2D diagram to finite
    regions.

    Parameters
    ----------
    vor : Voronoi
        Input diagram
    radius : float, optional
        Distance to 'points at infinity'.

    Returns
    -------
    regions : list of tuples
        Indices of vertices in each revised Voronoi regions.
    vertices : list of tuples
        Coordinates for revised Voronoi vertices. Same as coordinates
        of input vertices, with 'points at infinity' appended to the
        end.

    """

    if vor.points.shape[1] != 2:
        raise ValueError("Requires 2D input")

    new_regions = []
    new_vertices = vor.vertices.tolist()

    center = vor.points.mean(axis=0)
    if radius is None:
        radius = vor.points.ptp().max()*2

    # Construct a map containing all ridges for a given point
    all_ridges = {}
    for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices):
        all_ridges.setdefault(p1, []).append((p2, v1, v2))
        all_ridges.setdefault(p2, []).append((p1, v1, v2))

    # Reconstruct infinite regions
    for p1, region in enumerate(vor.point_region):
        vertices = vor.regions[region]

        if all([v >= 0 for v in vertices]):
            # finite region
            new_regions.append(vertices)
            continue

        # reconstruct a non-finite region
        ridges = all_ridges[p1]
        new_region = [v for v in vertices if v >= 0]

        for p2, v1, v2 in ridges:
            if v2 < 0:
                v1, v2 = v2, v1
            if v1 >= 0:
                # finite ridge: already in the region
                continue

            # Compute the missing endpoint of an infinite ridge

            t = vor.points[p2] - vor.points[p1] # tangent
            t /= np.linalg.norm(t)
            n = np.array([-t[1], t[0]])  # normal

            midpoint = vor.points[[p1, p2]].mean(axis=0)
            direction = np.sign(np.dot(midpoint - center, n)) * n
            far_point = vor.vertices[v2] + direction * radius

            new_region.append(len(new_vertices))
            new_vertices.append(far_point.tolist())

        # sort region counterclockwise
        vs = np.asarray([new_vertices[v] for v in new_region])
        c = vs.mean(axis=0)
        angles = np.arctan2(vs[:,1] - c[1], vs[:,0] - c[0])
        new_region = np.array(new_region)[np.argsort(angles)]

        # finish
        new_regions.append(new_region.tolist())

    return new_regions, np.asarray(new_vertices)

# make up data points
np.random.seed(1234)
points = np.random.rand(15, 2)

# compute Voronoi tesselation
vor = Voronoi(points)

# plot
regions, vertices = voronoi_finite_polygons_2d(vor)
print("--")
print(regions)
print("--")
print(vertices)

# colorize
for region in regions:
    polygon = vertices[region]
    plt.fill(*zip(*polygon), alpha=0.4)

plt.plot(points[:,0], points[:,1], 'ko')
plt.axis('equal')
plt.xlim(vor.min_bound[0] - 0.1, vor.max_bound[0] + 0.1)
plt.ylim(vor.min_bound[1] - 0.1, vor.max_bound[1] + 0.1)

Большой ресурс здесь.

https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_digits.html

Answer 2

K-средних вычисляет k кластеров по среднему приближению. Каждый кластер определяется своим вычисленным центром и, таким образом, является уникальным по определению.

Выборочное назначение выполняется для кластера с ближайшим расстоянием от центра кластера, также уникальным по определению. Таким образом, в этом смысле NO OVERLAP .

Однако для данного расстояния d>0 выборка может находиться в пределах d от более чем одного центра кластера (это возможно). Это то, что вы видите, когда говорите перекрытие . Однако по-прежнему выборка назначается ближайшему кластеру, а не всем. Таким образом, нет перекрытия.

ПРИМЕЧАНИЕ: В случае, когда выборка имеет точно такое же самое близкое расстояние до более чем одного центра кластера, любое случайное назначение может быть сделано между ближайшими кластерами, и это не меняет ничего важного в алгоритме или результатах, так как кластеры пересчитываются после назначения.