K-Means Kümeleme Algoritması

1// K-means algoritması implementasyonu
2function kMeansAlgorithm(
3  points: Point[],
4  k: number,
5  maxIterations: number = 100
6): { points: Point[], centroids: Point[], iterations: number } {
7  if (points.length < k) {
8    throw new Error("Nokta sayısı küme sayısından az olamaz.");
9  }
10  
11  // Rastgele merkez noktaları seç
12  const centroids: Point[] = [];
13  const usedIndices = new Set();
14  
15  // Rastgele, tekrarlanmayan indekslerde merkezler seç
16  while (centroids.length < k) {
17    const randomIndex = Math.floor(Math.random() * points.length);
18    if (!usedIndices.has(randomIndex)) {
19      usedIndices.add(randomIndex);
20      centroids.push({
21        x: points[randomIndex].x,
22        y: points[randomIndex].y,
23        cluster: centroids.length
24      });
25    }
26  }
27  
28  // Noktaların en yakın merkezlere atanması
29  let iterations = 0;
30  let isConverged = false;
31  
32  while (!isConverged && iterations < maxIterations) {
33    // Noktaları en yakın merkezlere ata
34    assignPointsToClusters(points, centroids);
35    
36    // Önceki merkezleri sakla
37    const oldCentroids = JSON.parse(JSON.stringify(centroids));
38    
39    // Merkez noktalarını güncelle
40    const hasUpdated = updateCentroids(points, centroids, k);
41    
42    // Merkez noktalar değişmediyse yakınsama sağlanmıştır
43    isConverged = !hasUpdated;
44    iterations++;
45  }
46  
47  return { points, centroids, iterations };
48}
49
50// Noktaları en yakın merkezlerine ata
51function assignPointsToClusters(points: Point[], centroids: Point[]): void {
52  for (const point of points) {
53    let minDistance = Infinity;
54    let closestCluster = 0;
55    
56    // Her nokta için en yakın merkezi bul
57    for (let i = 0; i < centroids.length; i++) {
58      const distance = euclideanDistance(point, centroids[i]);
59      if (distance < minDistance) {
60        minDistance = distance;
61        closestCluster = i;
62      }
63    }
64    
65    point.cluster = closestCluster;
66  }
67}
68
69// Merkez noktalarını güncelle
70function updateCentroids(points: Point[], centroids: Point[], k: number): boolean {
71  let hasUpdated = false;
72  
73  for (let i = 0; i < k; i++) {
74    // Kümeye ait noktaları bul
75    const clusterPoints = points.filter(p => p.cluster === i);
76    
77    // Kümede nokta yoksa, merkezi güncelleme
78    if (clusterPoints.length === 0) continue;
79    
80    // Yeni merkez koordinatlarını hesapla (ortalama)
81    const sumX = clusterPoints.reduce((sum, p) => sum + p.x, 0);
82    const sumY = clusterPoints.reduce((sum, p) => sum + p.y, 0);
83    const newX = sumX / clusterPoints.length;
84    const newY = sumY / clusterPoints.length;
85    
86    // Merkez konumu değişti mi?
87    if (centroids[i].x !== newX || centroids[i].y !== newY) {
88      centroids[i].x = newX;
89      centroids[i].y = newY;
90      hasUpdated = true;
91    }
92  }
93  
94  return hasUpdated;
95}
96
97// İki nokta arasındaki Öklid mesafesi
98function euclideanDistance(p1: Point, p2: Point): number {
99  return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
100}