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    // Noktayı en yakın kümeye ata
66    point.cluster = closestCluster;
67  }
68}
69
70// Merkez noktalarını güncelle
71function updateCentroids(points: Point[], centroids: Point[], k: number): boolean {
72  let hasUpdated = false;
73  
74  // Her küme için yeni merkez hesapla
75  for (let i = 0; i < k; i++) {
76    const clusterPoints = points.filter(p => p.cluster === i);
77    
78    // Küme boşsa güncelleme yapma
79    if (clusterPoints.length === 0) continue;
80    
81    // Yeni merkezi hesapla (ortalama)
82    const sumX = clusterPoints.reduce((sum, p) => sum + p.x, 0);
83    const sumY = clusterPoints.reduce((sum, p) => sum + p.y, 0);
84    const newX = sumX / clusterPoints.length;
85    const newY = sumY / clusterPoints.length;
86    
87    // Merkez değiştiyse güncelle
88    if (centroids[i].x !== newX || centroids[i].y !== newY) {
89      centroids[i].x = newX;
90      centroids[i].y = newY;
91      hasUpdated = true;
92    }
93  }
94  
95  return hasUpdated;
96}
97
98// İki nokta arasındaki Öklid mesafesi
99function euclideanDistance(p1: Point, p2: Point): number {
100  return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
101}