K-Ortalamalar Kümeleme#
K-Ortalamalar, noktaları merkezlere atayan denetimsiz bir kümeleme algoritmasıdır. Veri noktalarını hızlıca gruplamak ve aykırı değerleri fark etmek için kullanışlıdır. Dezavantajı, tüm veriyi belleğe alması gerektiği için bellek tüketiminin yüksek olabilmesidir. Buna karşılık uygulaması kolaydır ve pek çok kullanım alanı vardır.
Kitaplıkları içe aktaralım.
import numpy as np
import matplotlib.pyplot as plt
import scienceplots
from IPython.display import Image
from celluloid import Camera
np.random.seed(0)
plt.style.use(["science", "no-latex"])
Örnek Veri Kümesi#
Rastgele noktalardan oluşan bir veri kümesi üretelim.
K = 12
w = 1200
h = 675
nums = 100
colors = np.random.rand(K, 3)
x = np.random.randint(0, w, size=nums)
y = np.random.randint(0, h, size=nums)
pts = np.column_stack((x, y))
# plot the points
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(x, y)
<matplotlib.collections.PathCollection at 0x10c5df500>
Mesafe Fonksiyonları#
Noktaları merkezlere atarken onları en yakın merkeze yerleştiririz. Bunu sayısallaştırmak için uzaklığı nasıl ölçtüğümüzü tanımlamamız gerekir. Aşağıda iki örnek mesafe fonksiyonu yer alıyor.
\(p1\) noktası \((x_1, y_1)\) ve \(p2\) noktası \((x_2, y_2)\) olsun. Bu iki nokta için şu mesafe fonksiyonlarını yazabiliriz:
Öklid Uzaklığı: \(\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}\)
Manhattan Uzaklığı: \(|x_2-x_1| + |y_2-y_1|\)
def euclidean_distance(p1, p2):
return np.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
def manhattan_distance(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
K-Ortalamalar Kurulumu#
Başlangıçta merkezlerin x ve y değerleri rastgele seçilir.
centroids_x = np.random.randint(0, w, size=K)
centroids_y = np.random.randint(0, h, size=K)
centroids = np.column_stack((centroids_x, centroids_y))
Grafik Fonksiyonları#
Solda uzaklıkların kareleri toplamını, sağda ise merkezleri gösteren bir grafik üretmek için yardımcı bir fonksiyon oluşturalım. Ayrıca görselleştirme için, o ana kadarki toplam uzaklık gibi bazı değişkenleri de başlatalım.
def create_plots():
fig, ax = plt.subplots(1, 3, figsize=(16 / 9.0 * 4, 4 * 1), layout="constrained")
fig.suptitle("K-Ortalamalar Kümeleme (Denetimsiz)")
ax[0].set_xlabel("K Kümesi", fontweight="normal")
ax[0].set_ylabel("Öklid Uzaklıklarının Kareleri Toplamı", fontweight="normal")
ax[0].set_title("Dirsek Yöntemi")
ax[1].axis("off")
ax[2].axis("off")
ax[2] = fig.add_subplot(1, 2, 2)
ax[2].set_xlabel("X")
ax[2].set_ylabel("Y")
ax[2].set_title("Merkezler")
camera = Camera(fig)
return ax[0], ax[2], camera
boundary_div = 25
x_boundary_inc = int(w / boundary_div)
y_boundary_inc = int(h / boundary_div)
x_boundary = np.linspace(0, w, x_boundary_inc + 1)
y_boundary = np.linspace(0, h, y_boundary_inc + 1)
x_boundary, y_boundary = np.meshgrid(x_boundary, y_boundary)
colors_idx_boundary = np.random.randint(0, K, size=x_boundary.shape)
x_boundary_flat = x_boundary.flatten()
y_boundary_flat = y_boundary.flatten()
dists = np.zeros(K)
dists_idx = np.arange(1, K + 1)
Modeli Eğitmek#
Şimdi her şeyi bir araya getirelim. Bu görselleştirmede, toplam merkez sayısını ifade eden farklı \(K\) değerleri için merkezleri gösteriyorum. Her \(K\) değeri için algoritmayı belirli sayıda epok boyunca çalıştırıyorum. Başlangıçta merkezler düzlem üzerinde rastgele konumlarda bulunuyor. Her epokta noktalar en yakın merkeze atanıyor. Ardından merkezin yeni konumu, bir önceki adımda o merkeze atanmış noktaların ortalama x ve y değeri olarak hesaplanıyor.
ax0, ax1, camera = create_plots()
epochs = 8
output_filename = "k_means.gif"
for k in range(1, K + 1):
acc_dist_squared = 0
for e in range(epochs):
# Draw the boundaries
for index in np.ndindex(x_boundary.shape):
x = x_boundary[index]
y = y_boundary[index]
colors_idx_boundary[index] = 0
min_group = 0
# set min distance to largest possible distance initially
min_dist = np.sqrt(w**2 + h**2)
curr_pt = [x, y]
curr_c = []
for c in range(k):
curr_c = centroids[c]
dist = euclidean_distance(curr_pt, curr_c)
if dist < min_dist:
min_dist = dist
min_group = c
colors_idx_boundary[index] = min_group
colors_boundary = colors[colors_idx_boundary.flatten()]
ax1.scatter(
x_boundary_flat, y_boundary_flat, c=colors_boundary, s=20, alpha=0.45
)
# Assign each point to a centroid
groups = [[] for _ in range(k)]
acc_dist_squared = 0
for i in range(nums):
min_group = 0
# set min distance to largest possible distance initially
min_dist = np.sqrt(w**2 + h**2)
curr_pt = pts[i]
curr_c = []
for c in range(k):
curr_c = centroids[c]
dist = euclidean_distance(curr_pt, curr_c)
if dist < min_dist:
min_dist = dist
min_group = c
groups[min_group].append(curr_pt)
acc_dist_squared += min_dist**2
# Merkezler
for g in range(k):
# Draw the centroids
curr_centroid = centroids[g]
curr_centroid = np.array([curr_centroid], dtype=np.int32)
ax1.scatter(curr_centroid[:, 0], curr_centroid[:, 1], color=colors[g], s=8)
group_pts = np.array(groups[g])
if group_pts.size != 0:
# Draw lines between points and the centroids
pts_in_group = group_pts.shape[0]
for i in range(pts_in_group):
group_pt = group_pts[i]
ax1.plot(
[group_pt[0], centroids[g][0]],
[group_pt[1], centroids[g][1]],
color=colors[g],
linewidth=2,
alpha=0.55,
)
# Update the location of the centroids
new_centroid = np.mean(group_pts, axis=0)
centroids[g] = new_centroid
new_centroid = np.array([new_centroid], dtype=np.int32)
# Draw the points
ax1.scatter(pts[:, 0], pts[:, 1], c="black", s=15, alpha=0.3)
# Draw the Dirsek Yöntemi graph
if k - 2 > 0:
ax0.plot(dists_idx[: k - 1], dists[: k - 1], color="red")
camera.snap()
# if e % 2 == 0:
# camera.snap()
# else:
# ax0.clear()
# ax1.clear()
acc_dist_squared /= nums
dists[k - 1] = acc_dist_squared
print(k-1, acc_dist_squared)
animation = camera.animate()
animation.save("k_means.gif", writer="pillow")
plt.close()
0 158627.63
1 62379.95
2 47984.72
3 40085.6
4 28638.72
5 24290.07
6 20755.56
7 15453.13
8 12900.14
9 12373.94
10 12023.81
11 11002.26
Image(filename=output_filename)
