2d:null 2e:["$","title",null,{"children":"짧은 머신러닝 안내서: K-means clustering | Humble Data Miner | Observable"}] 33:T5a3,{ const ps = 300; // square plot size const margin = { left:10, right:10, top:10, bottom: 10 }; const svg = d3.create("svg").attr("viewBox", [0, 0, ps, ps]).attr("width",ps).attr("height",ps); const data = d3.shuffle(rawdata.map(d=>({x:d.x,y:d.y}))).slice(0,20); const ex = d3.extent(data,d=>d.x); const ey = d3.extent(data,d=>d.y); const x = d3.scaleLinear().domain(ex).range([margin.left, ps-margin.right]); const y = d3.scaleLinear().domain(ey).range([ps-margin.bottom, margin.top]); const color = "grey"; const r = 4; const xGrid = (g) => g .attr('class', 'x-grid-lines') .selectAll('line') .data(x.ticks()) .join('line') .attr('stroke','gray').attr("stroke-opacity",0.2) .attr('x1', d => x(d)).attr('x2', d => x(d)) .attr('y1', margin.top).attr('y2', ps - margin.bottom); svg.append("g").call(xGrid); const yGrid = (g) => g .attr('class', 'y-grid-lines') .selectAll('line') .data(y.ticks()) .join('line') .attr('stroke','gray').attr("stroke-opacity",0.2) .attr('x1', margin.left) .attr('x2', width - margin.right) .attr('y1', d => y(d)) .attr('y2', d => y(d)) svg.append("g").call(yGrid); svg.append("g").attr("stroke",color).attr("stroke-opacity",0.7).attr("stroke-width",2).attr("fill","none").selectAll("circle") .data(data) .join("circle") .attr("r",r) .attr("cx",d=>x(d.x)) .attr("cy",d=>y(d.y)); return svg.node(); }34:T1bf4,{ const height = 700; const slider_height = 60; const margin = { left: 40, right:40, top:0, bottom: 20+slider_height }; const svg = d3.create("svg").attr("viewBox", [0, 0, width, height]); const data = rawdata; const ex = [d3.min(data,d=>d.x)-1,d3.max(data,d=>d.x)+1]; const ey = [d3.min(data,d=>d.y)-1,d3.max(data,d=>d.y)+1]; const ph = height - margin.bottom; const pw = Math.ceil(ph*(ex[1]-ex[0])/(ey[1]-ey[0])); const x = d3.scaleLinear().domain(ex).range([margin.left, margin.left+pw]); const y = d3.scaleLinear().domain(ey).range([margin.top+ph, margin.top]); const glines = Array.from({length:data.length},_=>svg.append("g")); const gpts = svg.append("g"); const points = data.map((d,i)=>gpts.append("path") .attr("stroke","black").attr("stroke-opacity",0.5).attr("stroke-width",2).attr("fill","white") .attr("transform",`translate(${x(d.x)},${y(d.y)})`) .attr("d",symbols[0].s) ); const gcents = svg.append("g"); const cents = d3.range(kmeans_params.k).map((d,i)=>gcents.append("path") .attr("stroke","none") ); const gvoronoi = svg.append("g"); const labels = svg.append("g") .attr("font-size",10).attr("text-anchor","start").attr("dominant-baseline","middle").selectAll("text") .data(data) .join("text") .attr("x", d=>x(d.x)).attr("y", d=>y(d.y)).attr("dx",6).attr("dy",1) .text(d=>`${d.rank}.${d.name}`); svg.append("path").attr("fill","white").attr("stroke","none").attr("d",`M 0 0 H ${margin.left} V ${height} H 0 V 0`); svg.append("path").attr("fill","white").attr("stroke","none").attr("d",`M 0 ${height-margin.bottom} H ${width} V ${height} H 0`); const legend = svg.append("g"); const rmse = legend.append("text") .attr("text-anchor","start").attr("dominant-baseline","hanging") .attr("x", margin.left+pw-200).attr("y", margin.top+10).text("에러(RSME): "); const history = kmeans_result.history; const its = d3.range(-1,history.length,1); const slider = d3_slider.sliderBottom().min(-1).max(its.length-2).step(1).value(-1) .tickValues(its) .tickFormat(i=>`${i<0?"초기값":i==its.length-3?"정지":i==its.length-2?"결과":(i+1).toFixed(0)}`) .value(-1).width(ph).fill(d3.schemeCategory10[3]).on("onchange", () => update(slider.value())); const giteration = svg.append("g").attr("class","ransac-iteration").attr("transform",`translate(120,${height-margin.bottom/2})`); giteration.call(slider); giteration.selectAll(".slider text").attr("font-size", "12"); giteration.selectAll(".axis text").attr("fill","grey"); giteration.append("text") .attr("text-anchor","middle").attr("dominant-baseline","middle") .attr("x","-70").attr("y",0).attr("dy",4).text("반복회차"); giteration.append("text") .attr("text-anchor","middle").attr("dominant-baseline","middle") .attr("x","-70").attr("y",20).attr("dy",4).text("(#iteration)"); svg.append("g").attr("transform",`translate(0,${height-margin.bottom})`).call(d3.axisBottom(x)); svg.append("g").attr("transform",`translate(${margin.left},0)`).call(d3.axisLeft(y).tickFormat(d=>`${d.toLocaleString()}`)); update(-1); function update(it) { it = Math.round(it); const n = data.length; const dur = anim_step_ms; const line = d3.line().x(d=>d[0]).y(d=>d[1]); const prev_item = it>0? kmeans_result.history[it-1] : it==0? kmeans_result.init : {C:kmeans_result.init.C, L:Array.from({length:n},_=>-1)}; const curr_item = it>=0? kmeans_result.history[it] : kmeans_result.init; const sym_null = {s:d3.symbol(d3.symbolCircle),c:"white"}; rmse.text(`에러(RSME): ${curr_item.hasOwnProperty("err")?curr_item.err.toFixed(2):""}`) // initial if(it<0) { for(let pi=0; pi < n; pi++) { const gline = glines[pi]; const pt = data[pi]; points[pi] .interrupt() .attr("d",sym_null.s).attr("fill",sym_null.c); gline.selectAll("path") .interrupt() .attr("opacity",0) } for(let ci=0; ci < cents.length; ci++) { const curr_cent = curr_item.C[ci]; cents[ci] .interrupt() .attr("d",symbols[ci].s).attr("fill",d3.color(symbols[ci].c).brighter()).attr("opacity",1) .attr("transform",`translate(${x(curr_cent[0])},${y(curr_cent[1])})`); } } // final else if(it==kmeans_result.history.length-1) { for(let pi=0; pi < n; pi++) { const gline = glines[pi]; const pt = data[pi]; const curr_sym = symbols[curr_item.L[pi]]; points[pi] .interrupt() .attr("d",curr_sym.s).attr("fill",curr_sym.c); gline.selectAll("path") .interrupt() .attr("opacity",0); } for(let ci=0; ci < cents.length; ci++) { const curr_cent = curr_item.C[ci]; cents[ci] .interrupt() .attr("d",symbols[ci].s).attr("fill",d3.color(symbols[ci].c).brighter()).attr("opacity",1) .attr("transform",`translate(${x(curr_cent[0])},${y(curr_cent[1])})`); } } // intermediate(active) else { let dur_offset = 0; for(let pi = 0; pi < n; pi++) { const gline = glines[pi]; const pt = data[pi]; const prev_sym = prev_item.L[pi]>=0 ? symbols[prev_item.L[pi]] : sym_null; const curr_sym = curr_item.L[pi]>=0 ? symbols[curr_item.L[pi]] : sym_null; const changed = prev_item.L[pi] != curr_item.L[pi]; points[pi] .interrupt() .attr("d",prev_sym.s).attr("fill",prev_sym.c) .transition().delay(dur_offset+dur*2/3).duration(dur).attr("opacity",1) .attr("d",curr_sym.s).attr("fill",curr_sym.c); gline.selectAll("path") .data(prev_item.C.map(c=>[[x(pt.x),y(pt.y)],[x(c[0]),y(c[1])]])) .join("path") .interrupt() .attr("opacity",0).attr("stroke",(_,i)=>symbols[i].c).attr("fill","none").attr("d",d=>line(d)) .transition().delay(dur_offset).duration(dur/3).attr("opacity",1) .transition().delay(dur/3).duration(dur/3).attr("opacity",(_,i)=>curr_item.L[pi]==i?1:0); dur_offset += dur; } for(let ci=0; ci < cents.length; ci++) { const prev_cent = prev_item.C[ci]; const curr_cent = curr_item.C[ci]; cents[ci] .interrupt() .attr("d",symbols[ci].s).attr("fill",d3.color(symbols[ci].c).brighter()).attr("opacity",1) .attr("transform",`translate(${x(prev_cent[0])},${y(prev_cent[1])})`) .transition().delay(dur_offset).duration(dur).attr("transform",`translate(${x(curr_cent[0])},${y(curr_cent[1])})`).attr("opacity",1);; } } const prev_polygons = Array.from( d3.Delaunay.from(prev_item.C.map(d=>[x(d[0]),y(d[1])])) .voronoi([margin.left, margin.top, margin.left+pw, margin.top+ph]) .cellPolygons()); gvoronoi.attr("opacity",it>=0?1:0); gvoronoi.selectAll("path") .data(prev_polygons) .join("path") .attr("d",d=>line(d)) .attr("fill","none") .attr("stroke","black") .attr("stroke-opacity",0.1); } return svg.node(); }35:T638,kmeans_result = { rerun; const data = rawdata; const n = data.length; const X = data.map(d=>[d.x,d.y]); const history = []; const params = kmeans_params; const initidx = d3.shuffle(d3.range(n)).slice(0,params.k); function sqdiff(lhs,rhs) { return (rhs[0]-lhs[0])**2+(rhs[1]-lhs[1])**2; } function edist(lhs,rhs) { return Math.sqrt(sqdiff(lhs,rhs)); } let C = initidx.map(i=>[X[i][0],X[i][1]]); let L = X.map(_=>-1); const hitem_init = {C:C,L:L}; for(let it = 0; it < params.maxit; it++) { // relabel L = X.map(_=>-1); for(let i = 0; i < X.length; i++) { let min_dist = Infinity; for(let c = 0; c < C.length; c++) { const dist = edist(X[i],C[c]); if(min_dist <= dist) continue; L[i] = c; min_dist = dist; } } // recenter C = C.map((_,i)=>[0,0]); let cnt = C.map(_=>0); for(let i = 0; i < L.length; i++) { const c = L[i]; C[c][0]+=X[i][0]; C[c][1]+=X[i][1]; cnt[c] += 1; } for(let c = 0; c < C.length; c++) { C[c][0] /= cnt[c]; C[c][1] /= cnt[c]; } // calc RMSE let rmse = 0; for(let i = 0; i < L.length; i++) { const c = L[i]; rmse += sqdiff(X[i],C[c]); } rmse = Math.sqrt(rmse/n); const stop = (history.length > 0 && history.slice(-1)[0].err == rmse); const hitem = {it:it,C:C,L:L,err:rmse}; history.push(hitem); if(stop) { history.push(hitem); // duplicate to show the result break; } } return {init:hitem_init, history: history}; }36:[{"id":"ceffeffc07f5b4be81e23aefa5af63681f8e6539d0c8a271b83872f1d03739fe6c56a9a3a6e2c1180e6001718d7db2bcb6312421daed57546228400d527c2d5c","href":"https://static.observableusercontent.com/files/ceffeffc07f5b4be81e23aefa5af63681f8e6539d0c8a271b83872f1d03739fe6c56a9a3a6e2c1180e6001718d7db2bcb6312421daed57546228400d527c2d5c","name":"krx_cap50_tsne_2d@1.csv","type":"text/csv","lastModified":1693932857638.25,"size":2097},{"id":"c6f53258e0e85556ac8272d06b271f674393e091095c3bde10d534fa0638a1c4a3e2ce673f373ee778f8f7fddc66e784977869c6176ddf38e9a4c43140faff6b","href":"https://static.observableusercontent.com/files/c6f53258e0e85556ac8272d06b271f674393e091095c3bde10d534fa0638a1c4a3e2ce673f373ee778f8f7fddc66e784977869c6176ddf38e9a4c43140faff6b","name":"krx_cap50_tsne_2d@2.csv","type":"text/csv","lastModified":1693941108957.514,"size":2294}] 31:{"id":"dd83f1a9a13ba9af","slug":"short-guide-to-ml-kmeans-clustering","title":"짧은 머신러닝 안내서: K-means clustering","thumbnail":"4ece86c66b063e3a529921a58d8d3b3cdf3b4115e124070abe4cae3090a62c9c","access_level":"public","create_time":"$D2023-09-04T18:10:11.599Z","update_time":"$D2023-09-07T13:49:17.498Z","view_time":null,"first_public_time":"$D2023-09-04T18:10:11.599Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"50faa4da52a9ff9b","login":"humble-data-miner","name":"Humble Data Miner","avatar_url":"https://avatars-next.observableusercontent.com/3046b1bea86c5e825baea7c0c403d90ad9690b5396b11b5d02b3a0839fbcb946","tier":"starter_2024"},"version":473,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"4e2fc41e06361cc3","login":"humble-data-miner","name":"Humble Data Miner","avatar_url":"https://avatars-next.observableusercontent.com/3046b1bea86c5e825baea7c0c403d90ad9690b5396b11b5d02b3a0839fbcb946","tier":null}],"members":[{"type":"individual","id":"4e2fc41e06361cc3","login":"humble-data-miner","name":"Humble Data Miner","avatar_url":"https://avatars-next.observableusercontent.com/3046b1bea86c5e825baea7c0c403d90ad9690b5396b11b5d02b3a0839fbcb946","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"b886df04acb387aa","slug":"short-guide-to-machine-learning","title":"Short Guide to Machine Learning","owner":{"id":"50faa4da52a9ff9b","login":"humble-data-miner","name":"Humble Data Miner"}},"type":"notebook","body":{"title":"짧은 머신러닝 안내서: K-means clustering","cells":[{"id":0,"value":"# 짧은 머신러닝 안내서:
K-means clustering","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":22,"value":"---\n## Clustering?\n* 데이터포인트들의 특성으로 유사한 데이터들의 군집(cluster)을 찾는 알고리즘\n* 결과군집 대한 정보가 없는 비지도적 학습방법(unsupervised learning)\n\n## K-means clustering?\n* k개의 군집중심점(means;centroid)을 찾는 가장 기본적인 클러스터링 알고리즘\n* 각 데이터포인트는 가장 가까운 군집중심점에 할당된다\n\n## 사람이 대신해보는 K-means\n* 아래 산포도에서 3개의 군집중심점(k=3)을 찍어보고 각 점을 할당해보자\n 1. 좌표상에 대강(Randomized) 3개의 군집중심점을 찍는다\n 2. 육안으로 별다른 대안이 없을때까지 다음을 반복한다\n 1. 데이터포인트마다 가장 가까운 군집중심점을 할당한다\n 2. 같은 군집내 데이터포인트들을 기준으로 군집중심점을 보정한다\n 3. 최종 군집중심점과 데이터포인트들의 최근접군집할당을 반환한다","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":389,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"---\n## 알고리즘 개요\n1. n개의 데이터포인트 중 k개를 임의지정해 초기 군집중심점(centroid)으로 활용\n2. 군집중심점의 변경이 없을때까지 아래 단계를 반복 수행, 매 반복(iteration)마다 \n 1. 각 데이터포인트마다 모든 군집중심점과의 거리를 계산해 최근접 군집중심점에 할당\n 2. 각 군집에 할당된 데이터포인트들의 평균점을 군집중심점으로 재설정\n\n3. 결과로 k개의 군집중심점과 n개의 데이터포인트당 군집할당값을 반환\n\n## 알고리즘 동작 예시\n* 데이터셋: 시총상위49종목(+1하위종목)의 일가격변동 t-SNE 결과\n* 파라메터: 군집의 수(k)\n* 반복회차를 변경하면 해당 반복내에서 일어나는 알고리즘 동작을 시작화\n * 연한색깔로 표현된 점 = 군집중심점\n * 회색 구분선(Voronoi Diagram) = 군집간의 경계선","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":363,"value":"viewof rerun = Inputs.button(\"다시계산\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"viewof kmeans_params = {\n const dim = {w:340*2,h:65};\n const svg = d3.create(\"svg\")\n .attr(\"viewBox\", [0, 0, dim.w, dim.h])\n .attr(\"width\", dim.w)\n .attr(\"height\", dim.h);\n \n const samples = [1,2,3,4,5,6,7,8,9,10,15,20,25,30,35,40,45,50];\n const slider_samples = d3_slider.sliderBottom().min(d3.min(samples)).max(d3.max(samples))\n .tickValues(samples).tickFormat(v=>v.toFixed(0))\n .value(3).step(1).width(dim.w-40).fill(\"black\").on(\"onchange\", () => svg.dispatch(\"input\"));\n const gsamples = svg.append(\"g\").attr(\"class\",\"kmeans-param-k\").attr(\"transform\",`translate(20,30)`);\n gsamples.call(slider_samples);\n gsamples.append(\"text\")\n .attr(\"text-anchor\",\"middle\").attr(\"dominant-baseline\",\"hanging\")\n .attr(\"x\",\"140\").attr(\"y\",-30).attr(\"dy\",4).text(\"군집의 수(k)\");\n \n return Object.defineProperty(\n svg.node(), \n \"value\", \n {get: () => ({k:slider_samples.value(), maxit:20})}\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"## 알고리즘의 강점과 약점\n\n* 강점\n * 단순하다 (계산량이 다른 클러스터링 알고리즘에 비해 적다)\n * 계산규모가 데이터포인트에 단순비례한다\n* 약점\n * 문제에 맞는 k값을 지정하기 어렵다 (k값을 바꿔가며 반복해봐야...)\n * 초기중심점에 따라 결과가 다르게 나온다 (초기중심점을 바꿔가며 또반복...)\n * 각 특성의 스케일에 민감하게 반응한다 (데이터의 정규화 혹은 변환이 중요)\n * 기존에 없었던 이상치를 구분해낼수 없다\n * 비수치형(non-numeric) 데이터에 적용이 어렵다\n \n## 알고리즘의 일반적인 활용\n * 결국 데이터를 대표성을 가진 소수그룹으로 축약하는 기능\n * 이미지 세그먼테이션, 아날로그 신호의 디지털 부호화 등등\n * 전처리를 통해 데이터가 공간에 고르게 펴발라진 경우에 잘 동작\n * t-SNE같은 준균등화배치 및 차원축소 알고리즘의 결과와 잘 맞음","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":454,"value":"---\n\n## 참고자료\n* 종합적인 k-means 설명자료: [Wikipedia - k-means clustering](https://en.wikipedia.org/wiki/K-means_clustering)\n* Python sklearn k-means 모듈: [sklearn.cluster.KMeans](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html)\n* 소박한데광부의 t-SNE 설명: [짧은 머신러닝 안내서: t-SNE](https://observablehq.com/@humble-data-miner/t-sne)\n* 소박한데광부의 변동연관지도 설명: [개미투자공학4장: 변동연관지도](https://observablehq.com/@humble-data-miner/personal-investment-engineering-ch-4)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":472,"value":"---\n## 부연설명 동영상\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":9,"value":"---\n## Appendix\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"rawdata = await FileAttachment(\"krx_cap50_tsne_2d@2.csv\").csv({typed: \"auto\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"rawdata","database":"$undefined"},{"id":84,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"viewof anim_step_ms = Inputs.range([500,2000], {step:500,value:1000,label:\"anim 최소단위(ms)\"});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"symbols = {\n const symbols = [\n d3.symbol(d3.symbolCircle),\n d3.symbol(d3.symbolCross),\n d3.symbol(d3.symbolDiamond),\n d3.symbol(d3.symbolSquare),\n d3.symbol(d3.symbolStar),\n ];\n const colors = d3.schemeCategory10;\n return d3.merge(symbols.map(sym=>colors.map(color=>({s:sym,c:color}))));\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"mathjs = require('mathjs')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"d3_slider = require(\"d3-simple-slider\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 32:"$31:body"