<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport"…
- User
<div class="controls"> <label>Number of dots:</label> <input type="number" id="numDots" value="100" min="4" max="500"> <label>Number of apples:</label> <input type="number" id="numApples" value="4" min="1" max="10"> </div> <div class="controls"> <label>Learning rate:</label> <input type="number" id="learningRate" value="0.01" step="0.001" min="0.001" max="0.1"> <label>Iterations:</label> <input type="number" id="iterations" value="100" min="10" max="1000"> </div> <button onclick="initialize()">Initialize</button> <button onclick="runOptimization()">Run Optimization</button> <button onclick="stopOptimization()">Stop</button> <canvas id="canvas" width="600" height="600"></canvas> <div id="info"> <div>Current Loss: <span id="currentLoss">-</span></div> <div>Iteration: <span id="currentIteration">-</span></div> <div>Reassignments: <span id="reassignments">-</span></div> </div> <script> const canvas = document.getElementById('canvas'); const ctx = canvas.getContext('2d'); const canvasSize = 600; let dots = []; let apples = []; let assignments = []; let isRunning = false; let animationId = null; function initialize() { const numDots = parseInt(document.getElementById('numDots').value); const numApples = parseInt(document.getElementById('numApples').value); if (numDots % numApples !== 0) { alert('Number of dots must be divisible by number of apples!'); return; } // Generate random dots dots = []; for (let i = 0; i < numDots; i++) { dots.push({ x: Math.random(), y: Math.random() }); } // Generate random apple positions apples = []; for (let i = 0; i < numApples; i++) { apples.push({ x: Math.random(), y: Math.random(), vx: 0, vy: 0 }); } // Random initial assignments ensuring equal distribution assignments = []; const dotsPerApple = numDots / numApples; for (let i = 0; i < numApples; i++) { for (let j = 0; j < dotsPerApple; j++) { assignments.push(i); } } // Shuffle assignments for (let i = assignments.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [assignments[i], assignments[j]] = [assignments[j], assignments[i]]; } draw(); updateInfo(); } function distance(p1, p2) { const dx = p1.x - p2.x; const dy = p1.y - p2.y; return Math.sqrt(dx * dx + dy * dy); } function calculateLoss() { let totalLoss = 0; for (let i = 0; i < dots.length; i++) { const appleIdx = assignments[i]; totalLoss += distance(dots[i], apples[appleIdx]); } return totalLoss / dots.length; } function calculateGradients() { const numApples = apples.length; const gradients = new Array(numApples).fill(null).map(() => ({ x: 0, y: 0 })); const counts = new Array(numApples).fill(0); for (let i = 0; i < dots.length; i++) { const appleIdx = assignments[i]; const dot = dots[i]; const apple = apples[appleIdx]; const dist = distance(dot, apple); if (dist > 0) { gradients[appleIdx].x += (apple.x - dot.x) / dist; gradients[appleIdx].y += (apple.y - dot.y) / dist; } counts[appleIdx]++; } // Normalize gradients for (let i = 0; i < numApples; i++) { if (counts[i] > 0) { gradients[i].x /= counts[i]; gradients[i].y /= counts[i]; } } return gradients; } function reassignDots() { const numDots = dots.length; const numApples = apples.length; const dotsPerApple = numDots / numApples; // Calculate distance matrix const distances = []; for (let i = 0; i < numDots; i++) { distances[i] = []; for (let j = 0; j < numApples; j++) { distances[i][j] = distance(dots[i], apples[j]); } } // Create preference lists for each dot (sorted by distance) const preferences = []; for (let i = 0; i < numDots; i++) { preferences[i] = []; for (let j = 0; j < numApples; j++) { preferences[i].push({ apple: j, distance: distances[i][j] }); } preferences[i].sort((a, b) => a.distance - b.distance); } // Hungarian algorithm-inspired assignment const newAssignments = new Array(numDots).fill(-1); const appleCounts = new Array(numApples).fill(0); // First pass: assign dots to their closest available apple const dotIndices = Array.from({length: numDots}, (_, i) => i); // Sort dots by their minimum distance to any apple dotIndices.sort((a, b) => preferences[a][0].distance - preferences[b][0].distance); for (const dotIdx of dotIndices) { for (const pref of preferences[dotIdx]) { if (appleCounts[pref.apple] < dotsPerApple) { newAssignments[dotIdx] = pref.apple; appleCounts[pref.apple]++; break; } } } // Second pass: optimize by swapping let improved = true; while (improved) { improved = false; for (let i = 0; i < numDots; i++) { for (let j = i + 1; j < numDots; j++) { if (newAssignments[i] === newAssignments[j]) continue; const currentCost = distances[i][newAssignments[i]] + distances[j][newAssignments[j]]; const swapCost = distances[i][newAssignments[j]] + distances[j][newAssignments[i]]; if (swapCost < currentCost) { [newAssignments[i], newAssignments[j]] = [newAssignments[j], newAssignments[i]]; improved = true; } } } } // Count reassignments let reassignmentCount = 0; for (let i = 0; i < numDots; i++) { if (assignments[i] !== newAssignments[i]) { reassignmentCount++; } } assignments = newAssignments; return reassignmentCount; } async function runOptimization() { if (isRunning) return; isRunning = true; const learningRate = parseFloat(document.getElementById('learningRate').value); const iterations = parseInt(document.getElementById('iterations').value); for (let iter = 0; iter < iterations && isRunning; iter++) { // Calculate gradients const gradients = calculateGradients(); // Update apple positions with momentum const momentum = 0.9; for (let i = 0; i < apples.length; i++) { apples[i].vx = momentum * apples[i].vx - learningRate * gradients[i].x; apples[i].vy = momentum * apples[i].vy - learningRate * gradients[i].y; apples[i].x += apples[i].vx; apples[i].y += apples[i].vy; // Keep apples within bounds apples[i].x = Math.max(0, Math.min(1, apples[i].x)); apples[i].y = Math.max(0, Math.min(1, apples[i].y)); } // Reassign all dots optimally const reassignmentCount = reassignDots(); // Update visualization draw(); document.getElementById('currentIteration').textContent = iter + 1; document.getElementById('reassignments').textContent = reassignmentCount; updateInfo(); // Allow UI to update await new Promise(resolve => setTimeout(resolve, 10)); } isRunning = false; } function stopOptimization() { isRunning = false; } function draw() { ctx.clearRect(0, 0, canvasSize, canvasSize); // Create color palette for apples const colors = ['#FF6B6B', '#4ECDC4', '#45B7D1', '#96CEB4', '#FECA57', '#FF9FF3']; // Draw connections ctx.globalAlpha = 0.2; for (let i = 0; i < dots.length; i++) { const dot = dots[i]; const appleIdx = assignments[i]; const apple = apples[appleIdx]; ctx.beginPath(); ctx.moveTo(dot.x * canvasSize, dot.y * canvasSize); ctx.lineTo(apple.x * canvasSize, apple.y * canvasSize); ctx.strokeStyle = colors[appleIdx % colors.length]; ctx.stroke(); } ctx.globalAlpha = 1; // Draw dots for (let i = 0; i < dots.length; i++) { const dot = dots[i]; const appleIdx = assignments[i]; ctx.beginPath(); ctx.arc(dot.x * canvasSize, dot.y * canvasSize, 3, 0, 2 * Math.PI); ctx.fillStyle = colors[appleIdx % colors.length]; ctx.fill(); } // Draw apples ctx.font = '30px Arial'; for (let i = 0; i < apples.length; i++) { const apple = apples[i]; ctx.fillText('🍎', apple.x * canvasSize - 15, apple.y * canvasSize + 10); } } function updateInfo() { const loss = calculateLoss(); document.getElementById('currentLoss').textContent = loss.toFixed(4); } // Initialize on load window.onload = initialize; </script>Pls explain
Assistant
This web application demonstrates a clustering algorithm that combines gradient descent optimization with combinatorial reassignment to organize data points ("dots") around cluster centers ("apples"). Here's a breakdown of its components and functionality:
Key Concepts
- Clustering Goal: Group dots into clusters centered around apples, minimizing the average distance between dots and their assigned apples.
- Gradient Descent: Adjusts apple positions to pull them closer to their assigned dots.
- Optimal Reassignment: Uses a Hungarian algorithm-inspired approach to balance clusters and improve assignments.
Components
UI Controls
- Number of dots/apples: Configures dataset size and cluster count.
- Learning rate/Iterations: Controls gradient descent behavior.
- Buttons: Initialize, run, or stop the optimization.
Canvas Visualization
- Dots: Colored circles representing data points.
- Apples: Emoji 🍎 markers representing cluster centers.
- Connections: Faint lines show which dots are assigned to which apples.
Metrics
- Loss: Average distance between dots and their assigned apples (lower = better).
- Reassignments: Number of dots that changed clusters during optimization.
Algorithm Workflow
-
Initialization:
- Randomly place
numDotsandnumApples. - Assign dots to apples evenly (e.g., 100 dots ÷ 4 apples = 25 dots/apple).
- Randomly place
-
Gradient Descent Step:
- For each apple, compute the gradient (direction to move) based on its assigned dots.
- Update apple positions using:
apple.x += momentum * velocity - learningRate * gradient.x - Gradient = average of normalized vectors pointing from dots to their apple.
-
Reassignment Step:
- Greedy Assignment: Assign dots to the nearest apple, respecting cluster size limits.
- Swapping Optimization: Improve assignments by swapping dots between clusters if it reduces total distance.
-
Repeat: Iterate gradient descent and reassignment until stopped.
Why It Works
- Gradient Descent: Smoothly moves apples toward optimal positions.
- Momentum: Helps escape local minima (e.g., bounces past suboptimal positions).
- Balanced Clusters: Ensures even distribution of dots per apple.
- Swapping: Refines assignments beyond simple nearest-neighbor logic.
Example Use Case
- Click Initialize to generate random data.
- Click Run Optimization to see apples move and clusters form.
- Observe the loss decreasing and connections tightening.
Technical Notes
- No TensorFlow.js Usage: Despite the import, gradients are manually calculated.
- Performance: Swapping optimization has O(n²) complexity; may lag with large datasets.
- Determinism: Results vary due to random initialization.
Potential Extensions
- Add automatic differentiation via TensorFlow.js.
- Implement mini-batch processing for large datasets.
- Allow user-drawn dots or custom data input.
This interactive demo illustrates how combining calculus (gradient descent) and combinatorial optimization can solve clustering problems creatively! 🍎📈
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.