| 81 | } |
| 82 | |
| 83 | function kMeans(data: number[][], k: number): number[] { |
| 84 | const n = data.length; |
| 85 | const dim = data[0].length; |
| 86 | const centroids: number[][] = []; |
| 87 | const used = new Set<number>(); |
| 88 | |
| 89 | centroids.push([...data[0]]); |
| 90 | used.add(0); |
| 91 | for (let c = 1; c < k; c++) { |
| 92 | let bestIdx = 0; |
| 93 | let bestDist = -1; |
| 94 | for (let i = 0; i < n; i++) { |
| 95 | if (used.has(i)) continue; |
| 96 | let minDist = Infinity; |
| 97 | for (const cen of centroids) { |
| 98 | let d = 0; |
| 99 | for (let d2 = 0; d2 < dim; d2++) d += (data[i][d2] - cen[d2]) ** 2; |
| 100 | minDist = Math.min(minDist, d); |
| 101 | } |
| 102 | if (minDist > bestDist) { bestDist = minDist; bestIdx = i; } |
| 103 | } |
| 104 | centroids.push([...data[bestIdx]]); |
| 105 | used.add(bestIdx); |
| 106 | } |
| 107 | |
| 108 | const assignments = new Array(n).fill(0); |
| 109 | |
| 110 | for (let iter = 0; iter < 50; iter++) { |
| 111 | let changed = false; |
| 112 | for (let i = 0; i < n; i++) { |
| 113 | let bestDist = Infinity; |
| 114 | let bestC = 0; |
| 115 | for (let c = 0; c < k; c++) { |
| 116 | let dist = 0; |
| 117 | for (let d = 0; d < dim; d++) dist += (data[i][d] - centroids[c][d]) ** 2; |
| 118 | if (dist < bestDist) { bestDist = dist; bestC = c; } |
| 119 | } |
| 120 | if (assignments[i] !== bestC) { assignments[i] = bestC; changed = true; } |
| 121 | } |
| 122 | if (!changed) break; |
| 123 | for (let c = 0; c < k; c++) { |
| 124 | const members: number[] = []; |
| 125 | for (let i = 0; i < n; i++) if (assignments[i] === c) members.push(i); |
| 126 | if (members.length === 0) continue; |
| 127 | for (let d = 0; d < dim; d++) { |
| 128 | let sum = 0; |
| 129 | for (const m of members) sum += data[m][d]; |
| 130 | centroids[c][d] = sum / members.length; |
| 131 | } |
| 132 | } |
| 133 | } |
| 134 | return assignments; |
| 135 | } |
| 136 | |
| 137 | export function spectralCluster(vectors: number[][], maxClusters: number = 20): ClusterResult[] { |
| 138 | const n = vectors.length; |