28:null 29:["$","title",null,{"children":"Clustering | frynd | Observable"}] 2e:T6b6,{ const svg = d3.select(DOM.svg(mainChartSize.width, mainChartSize.height)); svg.append('g') .attr('transform', `translate(0, ${mainChartSize.height - chartMargin.bottom})`) .call(mainChartAxes.x); svg.append('g') .attr('transform', `translate(${chartMargin.left}, 0)`) .call(mainChartAxes.y); const msPerAnimation = animationMs/kMeansData.length; const centerSize = 10; const pointGroup = svg.append("g") .attr("stroke", "#000") .attr("stroke-opacity", 0.2) const centerGroup = svg.append("g") .attr("stroke", "#000") .attr("stroke-opacity", 0.5) .attr("stroke-width", 2) kMeansData[0].data.forEach((point, idx) => { const circle = pointGroup.append("circle") .attr("cx", mainChartScale.x(point.x)) .attr("cy", mainChartScale.y(point.y)) .attr("fill", point.center.color) .attr("r", 2.5) kMeansData.map(dt => dt.data.find(pt => pt.x == point.x && pt.y == point.y)).reduce((acc, pt) => { return acc.transition().duration(msPerAnimation).ease(d3.easeBounce) .attr("fill", pt.center.color) }, circle) }) kMeansData[0].centers.forEach((center, idx) => { const rect = centerGroup.append("rect") .attr("x", mainChartScale.x(center.x)) .attr("y", mainChartScale.y(center.y)) .attr("fill", center.color) .attr("height", centerSize) .attr("width", centerSize) kMeansData.map(dt => dt.centers[idx]).reduce((acc, point) => { return acc.transition().duration(msPerAnimation) .attr("x", mainChartScale.x(point.x)) .attr("y", mainChartScale.y(point.y)) }, rect) }) return svg.node(); }2f:T8c6,{ const svg = d3.select(DOM.svg(mainChartSize.width, mainChartSize.height)); svg.append('g') .attr('transform', `translate(0, ${mainChartSize.height - chartMargin.bottom})`) .call(mainChartAxes.x); svg.append('g') .attr('transform', `translate(${chartMargin.left}, 0)`) .call(mainChartAxes.y); const pointGroup = svg.append("g") .attr("stroke", "#000") .attr("stroke-opacity", 0.2) const clusterFadeIn = 500 const clusterDelay = animationMs - clusterFadeIn data.forEach((point, idx) => { const circle = pointGroup.append("circle") .attr("cx", mainChartScale.x(point.x)) .attr("cy", mainChartScale.y(point.y)) .attr("r", 2.5) circle.transition().delay(clusterDelay).duration(clusterFadeIn) .attr("fill", meanShiftData.clusteredData[idx].center.color) }) const allCenterGroup = svg.append("g") .attr("stroke", "#000") .attr("stroke-opacity", 0.5) .attr("fill-opacity", .13) const allAnimationTime = clusterDelay/meanShiftData.centers.length; meanShiftData.centers[0].forEach((center, idx) => { const circle = allCenterGroup.append("circle") .attr("cx", mainChartScale.x(center.x)) .attr("cy", mainChartScale.y(center.y)) .attr("r", mainChartScale.r(meanShiftSettings.radius)) meanShiftData.centers.map(arr => arr[idx]).reduce((acc, point) => { return acc.transition().duration(allAnimationTime) .attr("cx", mainChartScale.x(point.x)) .attr("cy", mainChartScale.y(point.y)) }, circle).transition().duration(1000) .attr("fill-opacity", 0.0).attr("stroke-opacity", 0.0) }) meanShiftData.clusters.forEach((center, idx) => { const circle = allCenterGroup.append("circle") .attr("cx", mainChartScale.x(center.x)) .attr("cy", mainChartScale.y(center.y)) .attr("r", mainChartScale.r(meanShiftSettings.radius)) .attr("fill", center.color) .attr("stroke", center.color) .attr("stroke-opacity", 0.0) .attr("fill-opacity", 0.0) circle.transition().delay(clusterDelay).duration(500) .attr("fill-opacity", 0.13).attr("stroke-opacity", 0.5) }) return svg.node(); }30:Ta2d,{ const svg = d3.select(DOM.svg(mainChartSize.width, mainChartSize.height)); const pointGroup = svg.append("g") .attr("stroke", "#000") .attr("stroke-opacity", 0.2) const clusterFade = 500 const clusterDelay = animationMs - clusterFade data.forEach((point, idx) => { const circle = pointGroup.append("circle") .attr("cx", mainChartScale.x(point.x)) .attr("cy", mainChartScale.y(point.y)) .attr("r", 2.5) circle.transition().delay(clusterDelay).duration(clusterFade) .attr("fill-opacity", 0.0) .attr("stroke-opacity", 0.0) }) const allCenterGroup = svg.append("g") .attr("stroke", "#000") .attr("stroke-opacity", 0.5) .attr("fill-opacity", .13) const groupCount = ArrayUtils.flatmap(dbScanData.clusters, cluster => cluster.groups.length).reduce((acc,len) => acc + len, 0) const appearDelay = clusterDelay/groupCount; const groupList = ArrayUtils.flatmap(dbScanData.clusters, cluster => cluster.groups.map(group => ({color: cluster.color, pts: group}))) groupList.forEach((group, groupIdx) => { const subgroupDelta = appearDelay / group.pts.length group.pts.forEach((pt,ptIdx) => { const circle = allCenterGroup.append("circle") .attr("cx", mainChartScale.x(pt.x)) .attr("cy", mainChartScale.y(pt.y)) .attr("r", mainChartScale.r(dbScanSettings.epsilon)) .attr("fill", group.color) .attr("stroke", group.color) .attr("stroke-opacity", 0.0) .attr("fill-opacity", 0.0) circle.transition().delay(appearDelay*groupIdx+subgroupDelta*ptIdx).duration(clusterFade) .attr("fill-opacity", 0.13).attr("stroke-opacity", 0.5) circle.transition().delay(clusterDelay).duration(500) .attr("fill-opacity", 1).attr("stroke-opacity", 0.0) .attr("r", 2.5) }) }) dbScanData.noise.forEach(pt => { const circle = allCenterGroup.append("circle") .attr("cx", mainChartScale.x(pt.x)) .attr("cy", mainChartScale.y(pt.y)) .attr("r", mainChartScale.r(dbScanSettings.epsilon)) .attr("stroke-opacity", 0.0) .attr("fill-opacity", 0.0) circle.transition().delay(clusterDelay).duration(500) .attr("fill-opacity", 0) .attr("stroke-opacity", 1.0) .attr("r", 2.5) }) svg.append('g') .attr('transform', `translate(0, ${mainChartSize.height - chartMargin.bottom})`) .call(mainChartAxes.x); svg.append('g') .attr('transform', `translate(${chartMargin.left}, 0)`) .call(mainChartAxes.y); return svg.node(); }31:Ta21,{ const svg = d3.select(DOM.svg(mainChartSize.width, mainChartSize.height)); const pointGroup = svg.append("g") .attr("stroke", "#000") .attr("stroke-opacity", 0.2) const clusterDelay = animationMs const clusterFadeIn = 500 data.forEach((point, idx) => { const circle = pointGroup.append("circle") .attr("cx", mainChartScale.x(point.x)) .attr("cy", mainChartScale.y(point.y)) .attr("r", 2.5) circle.transition().delay(clusterDelay).duration(clusterFadeIn) .attr("fill-opacity", 0.0) .attr("stroke-opacity", 0.0) }) const treeGroup = svg.append("g") .attr("stroke-width", 0.5) const delayPerLine = clusterDelay / hierarchicalData.length hierarchicalClusterData.connections.forEach((cluster,cluster_idx) => { cluster.forEach((conn) => { const line = treeGroup.append("line") .attr("stroke", "#000") .attr("x1", mainChartScale.x(conn.x)) .attr("x2", mainChartScale.x(conn.x)) .attr("y1", mainChartScale.y(conn.y)) .attr("y2", mainChartScale.y(conn.y)) .attr("stroke-opacity", 1.0) .attr("stroke-width", 2.5) line.transition().duration(clusterDelay) .attr("x1", mainChartScale.x(conn.a.x)) .attr("x2", mainChartScale.x(conn.b.x)) .attr("y1", mainChartScale.y(conn.a.y)) .attr("y2", mainChartScale.y(conn.b.y)) .attr("stroke-opacity", 1.0) .transition().duration(clusterFadeIn) .attr("stroke", index_to_color(cluster_idx, hierarchicalClusterData.clusters.length)) .attr("stroke-width", 0.5) }) }) hierarchicalClusterData.clusters.forEach((cluster,idx) => { cluster.forEach((point) => { const circle = pointGroup.append("circle") .attr("cx", mainChartScale.x(point.x)) .attr("cy", mainChartScale.y(point.y)) .attr("r", 2.5) .attr("fill", index_to_color(idx, hierarchicalClusterData.clusters.length)) .attr("stroke", index_to_color(idx, hierarchicalClusterData.clusters.length)) .attr("fill-opacity", 0.0) .attr("stroke-opacity", 0.0) circle.transition().delay(clusterDelay).duration(clusterFadeIn) .attr("fill-opacity", 1.0) .attr("stroke-opacity", 1.0) }) }) svg.append('g') .attr('transform', `translate(0, ${mainChartSize.height - chartMargin.bottom})`) .call(mainChartAxes.x); svg.append('g') .attr('transform', `translate(${chartMargin.left}, 0)`) .call(mainChartAxes.y); return svg.node() }32:T7af,meanShiftData = { const r = meanShiftSettings.radius const width = r*2 const queryCenters = centers => centers.map(center => ({pt: center, results: CoordMath.rangeQuery(center, r, data)})) const updatedCenters = centerQueries => centerQueries.map(centerQuery => CoordMath.meanPoint(centerQuery.results)) const count = Math.ceil(1/width); const divs = [...Array(count+1)].map((_, idx) => idx*width) var centers = ArrayUtils.flatmap(divs, x => divs.map(y => ({x: x, y: y}))) const offsetCenters = centers.map(center => ({x: center.x+width/2, y: center.y+width/2})) centers = [...centers, ...offsetCenters] centers = ArrayUtils.resevoirSample(data, meanShiftSettings.count, meanShiftSettings.seed) .map((pt, idx) => ({x: pt.x, y: pt.y})) const pointsByCenter = centers.map(center => ({pt: center, results: CoordMath.rangeQuery(center, r, data)})) var centerQuery = pointsByCenter.filter(center => center.results.length > 0) centers = centerQuery.map(c => c.pt) const result = [centers] var converged = false var iteration = 0 while(++iteration < 100 && !converged) { const oldCenters = centers centers = updatedCenters(centerQuery) centerQuery = queryCenters(centers) converged = CoordMath.converged(oldCenters, centers) result.push(centers) } centerQuery.sort((a,b) => a.results.length - b.results.length) const reduced = centerQuery.filter((center,idx) => { return !centerQuery//.sort((a,b) => a.results.length - b.results.length) .slice(idx + 1, centerQuery.length) .some(query => CoordMath.distance(center.pt, query.pt) < (2*r)) }).map(c => c.pt) const clusters = reduced.map((cent,idx) => ({x: cent.x, y: cent.y, color: index_to_color(idx, reduced.length)})) const resultPoints = data.map(pt => ({x: pt.x, y: pt.y, center: CoordMath.closest(pt, clusters)})) return { centers: result, clusters: clusters, clusteredData: resultPoints } }33:T614,dbScanData = { const minPts = dbScanSettings.minPts const radius = dbScanSettings.epsilon const srand = seededRand(dbScanSettings.seed) const clusters = [] const noise = [] const toExplore = data.slice() // copy data const removeIndexedItems = (items, arr) => { items.sort((a,b) => a.index - b.index) items.map(item => item.index).forEach((index, idx) => arr.splice(index-idx, 1)) } while(toExplore.length > 0) { const index = Math.floor(randBetween(0, toExplore.length, srand)()) const startingPoint = toExplore[index] toExplore.splice(index, 1) var neighbors = CoordMath.rangeQuery(startingPoint, radius, toExplore) if ( neighbors.length + 1 >= minPts ) { const cluster = [[startingPoint],neighbors] clusters.push(cluster) removeIndexedItems(neighbors, toExplore) while(neighbors.length > 0 ) { neighbors = ArrayUtils.flatmap(neighbors, neighbor => { const connectedNoise = CoordMath.rangeQuery(neighbor, radius, noise) removeIndexedItems(connectedNoise, noise) const connectedExplore = CoordMath.rangeQuery(neighbor, radius, toExplore) removeIndexedItems(connectedExplore, toExplore) return [...connectedNoise, ...connectedExplore] }) cluster.push(neighbors) } } else { noise.push(startingPoint) } } return { clusters: clusters.map((cluster, idx) => ({color: index_to_color(idx, clusters.length), groups: cluster})), noise: noise } }34:T5fd,hierarchicalData = { var hData = data.slice().map((pt, idx) => ({x: pt.x, y: pt.y, id: idx})) var pairs = hData.map(pt => ({ a: pt, b: CoordMath.closest(pt, hData.filter(b => b.id != pt.id)), })).map(pair => ({ a: pair.a, b: pair.b, dist: CoordMath.distance(pair.a, pair.b) })) const clusters = [] var i; const len = hData.length - 1; for(i = 0; i < len; ++i) { var cluster = pairs.reduce((acc, pt) => acc.dist <= pt.dist ? acc : pt) cluster.id = data.length + i cluster.x = (cluster.a.x + cluster.b.x) / 2 cluster.y = (cluster.a.y + cluster.b.y) / 2 clusters.push(cluster) if(hData.length == 2) break; pairs = pairs.filter(pair => pair.a.id != cluster.a.id && pair.a.id != cluster.b.id) hData = hData.filter(pt => pt.id != cluster.a.id && pt.id != cluster.b.id) const clusterClosest = CoordMath.closest(cluster, hData) const clusterDist = CoordMath.distance(cluster, clusterClosest) pairs.push({a: cluster, b: clusterClosest, dist: clusterDist}) hData.push(cluster) pairs.forEach(pair => { if(pair.b.id == cluster.a.id || pair.b.id == cluster.b.id){ pair.b = CoordMath.closest(pair.a, hData.filter(b => b.id != pair.a.id)) pair.dist = CoordMath.distance(pair.a, pair.b) } else { const clusterDist = CoordMath.distance(pair.a.id, cluster) if (clusterDist < pair.dist) { pair.dist = clusterDist pair.b = cluster } } }) } return clusters }35:T543,hierarchicalClusterData = { const clusterDist = cluster => cluster.hasOwnProperty("dist") ? cluster.dist : 0 const flatten = (root, layers) => { var roots = [root] var i while(roots.length <= layers && roots.length < data.length) { const node = roots.shift() if(node.hasOwnProperty("a") && node.hasOwnProperty("b")) { roots.push(node.a) roots.push(node.b) } else { roots.push(node) } roots.sort((a,b) => clusterDist(b) - clusterDist(a)) } return roots; } const roots = flatten(hierarchicalData[hierarchicalData.length-1],hierarchicalSettings.layers - 1) const getAllLeaves = (node) => { if(!node.hasOwnProperty("a") && !node.hasOwnProperty("b")) return [node] else return [...getAllLeaves(node.a), ...getAllLeaves(node.b)] } const getAllConnections = (node) => { if(!node.hasOwnProperty("a") && !node.hasOwnProperty("b")) return [] else return [{x: node.x, y: node.y, a: { x: node.a.x, y: node.a.y}, b: { x: node.b.x, y: node.b.y} }, ...getAllConnections(node.a), ...getAllConnections(node.b)] } return { clusters: roots.map(getAllLeaves), connections: roots.map(getAllConnections) } }36:T40d,CoordMath = { const sq_distance = (pt1, pt2) => { const dx = pt2.x - pt1.x const dy = pt2.y - pt1.y return dx*dx + dy*dy } const rangeQuery = (a, r, pts) => { const rr = r * r; return pts.map((pt,idx) => ({index:idx, x: pt.x, y: pt.y})).filter(pt => sq_distance(a, pt) <= rr) } const meanPoint = pts => pts.reduce((acc, pt) => { acc.x += pt.x / pts.length acc.y += pt.y / pts.length return acc }, {x:0, y:0}) const pointDiff = function(prev, curr) { return prev.map((v,idx) => sq_distance(v, curr[idx])) } return { distance : (a, b) => Math.sqrt(sq_distance(a,b)), // return the closest point in pts to "a" closest : (a, pts) => pts.map(pt => ({pt: pt, dist: sq_distance(a, pt)})) .reduce((pt1, pt2) => pt1.dist < pt2.dist ? pt1 : pt2).pt, // get all points in radius r from "a" rangeQuery: rangeQuery, meanPoint: meanPoint, converged: (prev, curr) => pointDiff(prev, curr).every(d => d < 0.0001) } }37:T8d1,settingsBuilder = { const buildUniformSettings = function() { return `` } const buildCircleSettings = function() { return `` } const buildGaussianSettings = function() { return `` } const buildPoissonSettings = function() { return `` } const buildUnknownSettings = function() { return `` } return function(dataSetting) { switch(dataSetting){ case dataSettings.uniform: return buildUniformSettings(); case dataSettings.circles: return buildCircleSettings(); case dataSettings.normal: return buildGaussianSettings(); case dataSettings.poisson: return buildPoissonSettings(); default: return buildUnknownSettings(); } } }38:T1035,generatorFor = { const generateUniformPoints = function (params) { const count = (!isFinite(params.count) || params.count < 1) ? 1 : Math.round(params.count) const rand = randBetween(0,1) return [...Array(count)].map(i => ({x: rand(), y: rand()})) } const generateCirclePoints = function (params) { const count = (!isFinite(params.count) || params.count < 1) ? 1 : Math.round(params.count) const ppc = (!isFinite(params.pointsPerCircle) || params.pointsPerCircle < 1) ? 10 : Math.round(params.pointsPerCircle) const w = 1/(count * 2) const bounds = [...Array(count)].map((i, idx) => w+2*idx*w) .map(s => ({start: s, end: s+w})) const bndsToRadii = bounds.map((bnds, idx) => { const randRadius = randBetween(bnds.start, bnds.end) const randTheta = randBetween(0, 2*Math.PI, seededRand(idx + seed.value)) randTheta() // odd, but needed to initialize return [...Array(ppc)].fill(bnds).map(bnd => ({r: randRadius(), theta: randTheta()})) }) const points = ArrayUtils.flatmap(bndsToRadii, i => i) .map(pt => { const r = pt.r const theta = pt.theta return {x: r*Math.sin(theta), y: r*Math.cos(theta)}; }) .map(pt => ({x: (pt.x+1)/2, y: (pt.y+1)/2}));//move to 0,1 domain return points; } const generateNormalPoints = function(params) { const count = (!isFinite(params.count) || params.count < 1) ? 1 : Math.round(params.count) const ppc = (!isFinite(params.pointsPerCenter) || params.pointsPerCenter < 1) ? 10 : Math.round(params.pointsPerCenter) const sigma = (!isFinite(params.sigma) || params.sigma < 0) ? .5 : params.sigma const centerGen = randBetween(0.2, 0.8) const centers = [...Array(count)].map((_) => ({x: centerGen(), y: centerGen()})) return ArrayUtils.flatmap(centers, (center, idx) => { const randDelta = d3.randomNormal.source(seededRand(idx + seed.value))(0, sigma) return [...Array(ppc)].fill(center).map(cent => ({ x: cent.x + randDelta(), y: cent.y + randDelta() })) }) } const generatePoissonPoints = function(params) { const radius = (!isFinite(params.radius) || params.radius <= 0) ? .01 : params.radius const testCount = (!isFinite(params.testCount) || params.testCount < 1) ? 1 : params.testCount const sRand = seededRand(seed.value) const centerGen = randBetween(0.2, 0.8, sRand) const points = [{x: centerGen(), y: centerGen()}] const sourcePoints = [points[0]] const pointInBounds = pt => pt.x >= 0 && pt.x <= 1 && pt.y <= 1 && pt.y >= 0 const minR = radius const maxR = radius * 2 const searchR = radius * 3 const radiusGen = randBetween(minR, maxR) const thetaGen = randBetween(0, 2*Math.PI, sRand) let iters = 2/(radius * radius) while( iters-- > 0 && sourcePoints.length > 0) { let found = false; const srcIndex = Math.floor(randBetween(0, sourcePoints.length, sRand)()) const srcPt = sourcePoints[srcIndex] const neighborPts = CoordMath.rangeQuery(srcPt, searchR, points) for(let i = 0; i < testCount; ++i) { const r = radiusGen() const theta = thetaGen() const testPt = {x: srcPt.x + r*Math.sin(theta), y: srcPt.y+r*Math.cos(theta)} const closeToNeighbor = CoordMath.rangeQuery(testPt, radius, neighborPts).length > 0 if(!closeToNeighbor && pointInBounds(testPt)){ sourcePoints.push(testPt) points.push(testPt) found = true; break; } } if(!found) { sourcePoints.splice(srcIndex, 1) } } return points; } return function(dataSetting) { switch(dataSetting){ case dataSettings.uniform: return generateUniformPoints; case dataSettings.circles: return generateCirclePoints; case dataSettings.normal: return generateNormalPoints; case dataSettings.poisson: return generatePoissonPoints; default: return (_) => [{x: 0.5, y: 0.5}] } } }39:[] 2c:{"id":"036aeb6d55013e4b","slug":"clustering","title":"Clustering","thumbnail":"693bc5c9707405a97a5abfcc7c2714385d20e28d3d2b75d0e50f259d1723b0f0","access_level":"public","create_time":"$D2019-04-19T00:22:53.364Z","update_time":"$D2020-10-03T16:35:48.456Z","view_time":null,"first_public_time":"$D2020-10-03T16:37:19.829Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"7b5359d37efc68ea","login":"frynd","name":"","avatar_url":"https://avatars-next.observableusercontent.com/76212fd619a12c7089558e7ba383e72561706faec73dcab43b67f33506429d09","tier":"starter_2024"},"version":1813,"publish_version":1813,"role":null,"authored":false,"authors":[{"type":"individual","id":"cb80da9044b1e184","login":"frynd","name":"","avatar_url":"https://avatars-next.observableusercontent.com/76212fd619a12c7089558e7ba383e72561706faec73dcab43b67f33506429d09","tier":null}],"members":[{"type":"individual","id":"cb80da9044b1e184","login":"frynd","name":"","avatar_url":"https://avatars-next.observableusercontent.com/76212fd619a12c7089558e7ba383e72561706faec73dcab43b67f33506429d09","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Clustering","cells":[{"id":0,"value":"md`# Clustering\n## What is clustering?\n[Clustering](https://en.wikipedia.org/wiki/Cluster_analysis \"Wikipedia-Cluster analysis\") is generally methods of grouping data points together. Data points in a given group should be more similar to each other than to points in other groups.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":919,"value":"md`## Data Generation\nFirst, generate some data to cluster.\n\nSeveral data generation flavors are available. These can show differences in how clustering algorithms handle differing types of data.\n\n* Gaussian shows simple clusters of data.\n* Circles shows density based clusters.\n* Uniform shows finding patterns in random noise.\n* Poisson shows finding patterns in random noise that has a roughly uniform density.\n\nThe random seed can be modified to generate different data sets with the same settings.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"viewof settingsChoice = {\n const buildoptions = (ds) => Object.entries(ds).map((arr) => ``).join(\"\")\nreturn form(html``)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":229,"value":"viewof seed = form(html``)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"viewof settings = form(html`${settingsBuilder(dataSettings[settingsChoice.generatorStyle])}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":288,"value":"{\n const svg = d3.select(DOM.svg(mainChartSize.width, mainChartSize.height));\n \n svg.append('g')\n \t\t.attr('transform', `translate(0, ${mainChartSize.height - chartMargin.bottom})`)\n \t.call(mainChartAxes.x);\n svg.append('g')\n \t.attr('transform', `translate(${chartMargin.left}, 0)`)\n \t.call(mainChartAxes.y);\n \n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .attr(\"stroke-opacity\", 0.2)\n .selectAll(\"circle\")\n .data(data)\n .enter().append(\"circle\")\n .attr(\"cx\", d => mainChartScale.x(d.x))\n .attr(\"cy\", d => mainChartScale.y(d.y))\n .attr(\"r\", 2.5);\n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1647,"value":"viewof animationSettings = form(html``)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":396,"value":"md`\n## K-Means\n[K-means](https://en.wikipedia.org/wiki/K-means_clustering \"Wikipedia K-Means\") clustering takes ${tex `k`} random points and associates each sample with the closest chosen point.\n\nEach chosen point is then moved to the mean of its associated points. Then each sample is re-assigned. These steps of reassignment and center movement are iterated until the centers do not move (or only move a small amount) between iterations.\n\nThe random seed can be modified to change starting positions of the ${tex `k`} points.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"viewof kMeansSettings = {\n const formData = html``\n formData.button.onclick = event => {\n event.preventDefault(); // Don’t submit the form.\n formData.dispatchEvent(new CustomEvent(\"change\"));\n };\n \n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":665,"value":"md`## Mean shift\n[Mean shift](https://en.wikipedia.org/wiki/Mean_shift \"Wikipedia Mean Shift\") plots a number (${tex `count`}) of circles of radius ${tex `r`} arranged on the domain space, then each circle shifts to the mean of any samples contained inside the circle. \nThis continues until the circles converge to a steady state.\nThen overlapping circles are de-duplicated and clusters are formed.\n\nThe random seed can be modified to change the initial starting points.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":675,"value":"viewof meanShiftSettings = {\n const formData = html``\n formData.button.onclick = event => {\n event.preventDefault(); // Don’t submit the form.\n formData.dispatchEvent(new CustomEvent(\"change\"));\n };\n \n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":669,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":935,"value":"md`## DBSCAN\n[DBSCAN](https://en.wikipedia.org/wiki/DBSCAN \"Wikipedia DBSCAN\") randomly choses a point in the sample, then checks to see if at least ${tex `minPts`} samples are within ${tex `\\epsilon`} of the that point. If so, a cluster starts and all neighbors within ${tex `\\epsilon`} of a sample in the cluster are added to the cluster until no more samples are added. Then a different point is chosen as the starting point, and the process continues.\n\nThe random seed can be modified to change the initial core point selection. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":949,"value":"viewof dbScanSettings = {\n const formData = html``\n formData.button.onclick = event => {\n event.preventDefault(); // Don’t submit the form.\n formData.dispatchEvent(new CustomEvent(\"change\"));\n };\n \n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":963,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1118,"value":"md`## Hierarchical / Agglomerative Clustering\n[Hierarchical / Agglomerative clustering](https://en.wikipedia.org/wiki/Hierarchical_clustering \"Wikipedia Hierarchical Clustering\") finds the closest two points and joins them together as a cluster. Then joins the next closest pair of points or point and cluster, until all points are joined.\n\nThis can produce an arbitrary number of clusters.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1133,"value":"viewof hierarchicalSettings = {\n const formData = html``\n formData.button.onclick = event => {\n event.preventDefault(); // Don’t submit the form.\n formData.dispatchEvent(new CustomEvent(\"change\"));\n };\n \n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1177,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1418,"value":"clusterConnectednessOptions = {\n const safeInverse = (distance) => distance <= 1/Number.MAX_VALUE ? Number.MAX_VALUE : 1/(distance * distance)\n return {\n meanEuclidean : {\n label: \"Mean Euclidean\",\n fn: (pt, cluster) => CoordMath.distance(pt, CoordMath.meanPoint(cluster)) \n },\n closestEuclidean : {\n label: \"Closest Euclidean\",\n fn: (pt, cluster) => CoordMath.distance(pt, CoordMath.closest(pt, cluster))\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1673,"value":"falloffOptions = {\n const safeInverse = (distance) => distance <= 1/Number.MAX_VALUE ? Number.MAX_VALUE : 1/distance\n const safeQuadratic = (distance) => safeInverse(distance * distance)\n const safeCubic = (distance) => safeInverse(distance * distance * distance)\n return {\n linear : {\n label: \"Linear\",\n fn: (distFn) => (pt, cluster) => safeInverse(distFn(pt, cluster))\n },\n quadratic : {\n label: \"Quadratic\",\n fn: (distFn) => (pt, cluster) => safeQuadratic(distFn(pt, cluster))\n },\n cubic : {\n label: \"Cubic\",\n fn: (distFn) => (pt, cluster) => safeCubic(distFn(pt, cluster))\n },\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"data = d3.shuffle(generatorFor(dataSettings[settingsChoice.generatorStyle])(settings))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":403,"value":"kMeansData = {\n const k = kMeansSettings.k\n\n var centers = ArrayUtils.resevoirSample(data, k, kMeansSettings.seed)\n .map((pt, idx) => ({id: idx, x: pt.x, y: pt.y, color: index_to_color(idx,k)}))\n\n var clustered = KMeansClusterMath.updateData(data, centers)\n var kMeansIters = [{ centers: centers, data: clustered }] \n \n var converged = false;\n var i = 0;\n while(!converged && i++ < 100)\n {\n var prevCenters = centers;\n centers = KMeansClusterMath.updateCenters(clustered, k)\n clustered = KMeansClusterMath.updateData(clustered, centers)\n kMeansIters.push({centers: centers, data: clustered})\n // var centerDiffs = KMeansClusterMath.centerDiff(prevCenters, centers)\n // converged = !centerDiffs.some(diff => diff > limit)\n converged = CoordMath.converged(prevCenters, centers) \n }\n\n return kMeansIters\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":683,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":943,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1141,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1273,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"//using styles from https://webdesign.tutsplus.com/tutorials/how-to-build-web-form-layouts-with-css-grid--cms-28776\nhtml``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1658,"value":"animationMs = {\n return animationSettings.seconds*1000\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":644,"value":"KMeansClusterMath = {\n \n const updateData = function(data, centers) {\n return data.map(pt => ({x: pt.x, y: pt.y, center: CoordMath.closest(pt, centers)}))\n } \n const updateCenters = function(clusteredData, k) {\n clusteredData.sort((a,b) => a.center.id - b.center.id)\n const groupedByClusterId = clusteredData.reduce((acc, dat) => {\n (acc[dat.center.id] = (acc[dat.center.id] || [])).push(dat)\n return acc;\n }, Array(k));\n \n return Object.values(groupedByClusterId).map(cluster => CoordMath.meanPoint(cluster))\n .map((cent, idx) => ({id:idx, x: cent.x, y: cent.y, color: index_to_color(idx, k)}));\n }\n \n const centerDiff = function(prevCenters, currCenters) {\n return prevCenters.map((v,idx) => CoordMath.distance(v, currCenters[idx]))\n }\n \n return {\n updateData: updateData,\n updateCenters: updateCenters,\n centerDiff: centerDiff\n }\n \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":617,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":631,"value":"ArrayUtils = {\n const concat = (x, y) => x.concat(y)\n const flatmap = (xs, f) => xs.map(f).reduce(concat, [])\n //TODO: fix typo \"reservoir\"\n const resevoirSample = function(array, numSamples, seed = seed.value) {\n const srand = seededRand(seed)\n // reservoir sample\n return array.reduce((acc, pt, idx) => {\n if(idx >= numSamples){\n const testIdx = Math.floor(randBetween(0, idx, srand)())\n if ( testIdx < numSamples )\n {\n acc[testIdx] = pt;\n }\n }\n else\n {\n acc.push(pt);\n }\n return acc;\n }, [])\n }\n \n return {\n flatmap: flatmap,\n resevoirSample : resevoirSample\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"dataSettings = ({\n normal : {\n description: \"Random Gaussian distributions.\",\n label: \"Gaussian\",\n },\n circles : {\n description: \"Concentric circles.\",\n label: \"Circles\",\n },\n uniform : {\n description: \"Uniform distribution of points.\",\n label: \"Uniform\",\n },\n poisson : {\n description: \"Poisson random field\",\n label: \"Poisson\"\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":177,"value":"randBetween = function(min, max, src){\n if(src === undefined)\n {\n src = seededRand(seed.value)\n }\n const rand = d3.randomUniform.source(src)(min, max)\n return rand;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":210,"value":"seededRand = {\n // from https://stackoverflow.com/questions/521295/seeding-the-random-number-generator-in-javascript\n return seed=>()=>(2**31-1&(seed=Math.imul(48271,seed)))/2**31\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":269,"value":"chartMargin = ({top: 12, right: 10, bottom: 26, left: 26})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"mainChartSize = {\n const side = Math.min(width, 500)\n return {width: side, height: side}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":279,"value":"mainChartScale = {\n return {\n x: d3.scaleLinear().domain([0, 1]).range([chartMargin.left, mainChartSize.width - chartMargin.right]),\n y: d3.scaleLinear().domain([0, 1]).range([mainChartSize.height - chartMargin.bottom, chartMargin.top]),\n r: (r) => (mainChartSize.width - chartMargin.left - chartMargin.right)*r\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":285,"value":"mainChartAxes = ({\n x: d3.axisBottom(mainChartScale.x),\n y: d3.axisLeft(mainChartScale.y)\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":405,"value":"index_to_color = function(index, max) {\n const r = index/max;\n const h = Math.floor(340*r)\n return `hsl(${h}, 100%, 50%)`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"import { form } from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 2d:"$2c:body"