Hiyerarşik Kümeleme (Hierarchical Clustering) Algoritması

1// Hiyerarşik kümeleme algoritması (Aglomeratif - AGNES)
2function hierarchicalClustering(
3  points: Point[],
4  cutoffDistance: number = Infinity
5): { 
6  dendrogram: ClusterNode, 
7  clusterAssignments: number[]
8} {
9  // Her nokta için başlangıçta ayrı küme oluştur
10  let clusters: ClusterNode[] = points.map((point, index) => ({
11    id: index,
12    points: [{ ...point, cluster: index }],
13  }));
14  
15  // Uzaklık eşiği altında en az 2 küme kalana kadar kümeleri birleştir
16  let nextId = points.length;
17  while (clusters.length > 1) {
18    // En yakın iki kümeyi bul
19    let minDistance = Infinity;
20    let closestPair: [number, number] = [-1, -1];
21    
22    for (let i = 0; i < clusters.length; i++) {
23      for (let j = i + 1; j < clusters.length; j++) {
24        // İki küme arasındaki mesafeyi hesapla
25        const distance = calculateClusterDistance(clusters[i], clusters[j]);
26        
27        if (distance < minDistance) {
28          minDistance = distance;
29          closestPair = [i, j];
30        }
31      }
32    }
33    
34    // Mesafe eşik değerini aştıysa, birleştirmeyi durdur
35    if (minDistance > cutoffDistance) {
36      break;
37    }
38    
39    // En yakın kümeleri birleştir
40    const [i, j] = closestPair;
41    const mergedCluster: ClusterNode = {
42      id: nextId++,
43      points: [...clusters[i].points, ...clusters[j].points],
44      children: [clusters[i], clusters[j]],
45      distance: minDistance
46    };
47    
48    // Birleştirilen kümeleri güncelle
49    mergedCluster.points.forEach(p => p.cluster = mergedCluster.id);
50    
51    // Yeni kümeyi ekle, eski kümeleri çıkar
52    const newClusters = clusters.filter((_, index) => index !== i && index !== j);
53    newClusters.push(mergedCluster);
54    clusters = newClusters;
55  }
56  
57  // Son kümeleme durumuna göre nokta atamalarını yap
58  const clusterAssignments = new Array(points.length).fill(-1);
59  
60  for (const cluster of clusters) {
61    for (const point of cluster.points) {
62      // Orijinal nokta dizisindeki indeksi bulmalıyız
63      const originalIndex = points.findIndex(p => p.x === point.x && p.y === point.y);
64      if (originalIndex !== -1) {
65        clusterAssignments[originalIndex] = cluster.id;
66      }
67    }
68  }
69  
70  // Dendrogram kökünü bul (tek kök yoksa yapay bir kök oluştur)
71  let dendrogram: ClusterNode;
72  if (clusters.length === 1) {
73    dendrogram = clusters[0];
74  } else {
75    // Birden fazla kök varsa, yapay bir kök oluştur
76    dendrogram = {
77      id: nextId,
78      points: clusters.flatMap(c => c.points),
79      children: clusters.length >= 2 ? [clusters[0], clusters[1]] : undefined
80    };
81  }
82  
83  return { dendrogram, clusterAssignments };
84}
85
86// İki küme arasındaki mesafeyi hesapla (en yakın komşu/tek bağlantı yöntemi)
87function calculateClusterDistance(clusterA: ClusterNode, clusterB: ClusterNode): number {
88  let minDistance = Infinity;
89  
90  // Her iki kümedeki her nokta çifti için mesafeyi hesapla
91  for (const pointA of clusterA.points) {
92    for (const pointB of clusterB.points) {
93      const distance = euclideanDistance(pointA, pointB);
94      minDistance = Math.min(minDistance, distance);
95    }
96  }
97  
98  return minDistance;
99}
100
101// İki nokta arasındaki Öklid mesafesi
102function euclideanDistance(p1: Point, p2: Point): number {
103  return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
104}