2d:null 2e:["$","title",null,{"children":"짧은 머신러닝 안내서: Mean shift clustering | Humble Data Miner | Observable"}] 33:T71c,## 문헌으로 살펴보는 Mean shift 동작 과정

${await FileAttachment("MeanShift_DorinComaniciu_2002_Fig2a.png").image({style:"width:100%;"})}	${await FileAttachment("MeanShift_DorinComaniciu_2002_Fig2b.png").image({style:"width:100%;"})}	${await FileAttachment("MeanShift_DorinComaniciu_2002_Fig2c.png").image({style:"width:100%;"})}
110,400개의 2차원 데이터포인트	mean shift로 7개의 mode발견	각mode들의 밀도 및 등반궤적 시각화
Comaniciu, D. & Meer, P. (2002). Mean shift: A robust approach toward feature space analysis

${await FileAttachment("Recited from Pennsylvania State Univ Mean Shift Theory 01.png").image({style:"width:100%;"})}	${await FileAttachment("Recited from Pennsylvania State Univ Mean Shift Theory 02.png").image({style:"width:100%;"})}
추정되는 밀도분포와 실제 데이터	실제데이터에 근거한 밀도분포 시각화
재인용 Collins, R.(2006). Mean-shift Tracking lecture notes

34:T1b04,{ 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 X = data.map(pt=>[pt.x,pt.y]); const band = meanshift_params.bandwidth; 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 arrowPoints = [[0, 0], [0, 6], [6, 3]]; const markerBoxWidth = 6; const markerBoxHeight = 6; const refX = markerBoxWidth / 2; const refY = markerBoxHeight / 2; svg .append('defs') .append('marker') .attr('id', 'arrow') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX*2) .attr('refY', refY) .attr('markerWidth', markerBoxWidth) .attr('markerHeight', markerBoxHeight) .attr('orient', 'auto-start-reverse') .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', 'black'); const gtrails = svg.append("g"); const trails = meanshift_result.map( (res,i)=>gtrails.append("g").attr("fill","none").attr("stroke","black").attr("opacity",0.5).selectAll("line") .data(res.paths) .join("line") .attr('marker-end', 'url(#arrow)') .attr("x1",d=>x(d[0][0])).attr("x2",d=>x(d[1][0])).attr("y1",d=>y(d[0][1])).attr("y2",d=>y(d[1][1])) ); 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",symbols[i].c) .attr("transform",`translate(${x(d.x)},${y(d.y)})`) .attr("d",symbols[i].s) ); const kernel = svg.append("circle"); const gcents = svg.append("g"); const cents = data.map((d,i)=>gcents.append("path") .attr("stroke","none") ); const activetrail = svg.append("g").attr("stroke","black").attr("fill","white").attr('marker-end', 'url(#arrow)'); 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 history = meanshift_result; 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?"초기":Math.round(i+1)}`) .value(-1).width(ph).fill(d3.schemeCategory10[3]).on("onchange", () => update(slider.value())); const giteration = svg.append("g").attr("class","meanshift-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("(오름차순)"); 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? meanshift_result[it-1] : {labels:Array.from({length:n},(_,i)=>i),modes:X,paths:[]}; const curr_item = it>=0? meanshift_result[it] : {labels:Array.from({length:n},(_,i)=>i),modes:X,paths:[]}; // initial if(it<0) { for(let i=0; i < n; i++) { const curr_symbol = symbols[curr_item.labels[i]]; points[i].interrupt().attr("d",curr_symbol.s).attr("fill",curr_symbol.c); cents[i].interrupt() .attr("d",curr_symbol.s).attr("fill",d3.color(curr_symbol.c).brighter()).attr("opacity",0) .attr("transform",`translate(${x(data[i].x)},${y(data[i].y)})`) .transition().duration(dur).attr("opacity",1); trails[i].attr("visibility","hidden"); } kernel.interrupt().attr("opacity",0); activetrail.selectAll("line").interrupt().attr("visibility","hidden"); } else { for(let i=0; i < n; i++) { const prev_symbol = symbols[prev_item.labels[i]]; const curr_symbol = symbols[curr_item.labels[i]]; points[i].interrupt().attr("d",prev_symbol.s).attr("fill",prev_symbol.c); cents[i].interrupt() .attr("d",prev_symbol.s).attr("fill",d3.color(prev_symbol.c).brighter()).attr("opacity",1) .attr("transform",`translate(${x(prev_item.modes[i][0])},${y(prev_item.modes[i][1])})`); trails[i].attr("visibility",ix(pt[0][0])).attr("y1",pt=>y(pt[0][1])) .attr("x2",pt=>x(pt[0][0])).attr("y2",pt=>y(pt[0][1])) .transition().delay((_,i)=>dur*i).duration(dur) .attr("x2",pt=>x(pt[1][0])).attr("y2",pt=>y(pt[1][1])) .attr("opacity",0.8); } } return svg.node(); }35:T701,meanshift_result = { const data = rawdata; const n = data.length; const X = data.map(d=>[d.x,d.y]); const eps = 1e-5; const params = meanshift_params; 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)); } function in_radius(pts,q) { return pts.filter(pt=>edist(pt,q)<=params.bandwidth); } function in_radius_indices(pts,q) { return pts.map((pt,i)=>[pt,i]).filter((pair,i)=>edist(pair[0],q)<=params.bandwidth).map(pair=>pair[1]); } function in_radius_closest_index(pts,q) { const dists = pts.map((pt,i)=>[edist(pt,q),i]).filter(pair=>pair[0]<=params.bandwidth); return dists.length>0 ? dists[d3.minIndex(dists)][1] : -1; } function mean_flat(pts) { const mean_val = [0,0]; for(let i=0; ii); const modes = []; for(let i=0; i eps) { prev_m = curr_m; curr_m = mean_flat(in_radius(X,curr_m)); paths.push([prev_m,curr_m]); } const closest_idx = in_radius_closest_index(modes,curr_m); modes.push(curr_m); const adjs = in_radius_indices(modes,curr_m); const min_label = closest_idx>=0?labels[closest_idx]:i; console.log(adjs, min_label); adjs.forEach(adjidx=>{labels[adjidx]=min_label;}); history.push({labels:labels.map(lbl=>lbl),modes:modes.concat(X.slice(i+1)),paths:paths.slice(0,-1)}); } return history; }36:[{"id":"c6f53258e0e85556ac8272d06b271f674393e091095c3bde10d534fa0638a1c4a3e2ce673f373ee778f8f7fddc66e784977869c6176ddf38e9a4c43140faff6b","href":"https://static.observableusercontent.com/files/c6f53258e0e85556ac8272d06b271f674393e091095c3bde10d534fa0638a1c4a3e2ce673f373ee778f8f7fddc66e784977869c6176ddf38e9a4c43140faff6b","name":"krx_cap50_tsne_2d.csv","type":"text/csv","lastModified":1695747482645.965,"size":2294},{"id":"2e1a3b8ca5464e10879f6dcb29125628952e2c7d4f6441351fb88a1c8e0362b21f0a021eac49d4fd058cc3adda1dfe3f6fcdfdc96cce74f99095537d26114c08","href":"https://static.observableusercontent.com/files/2e1a3b8ca5464e10879f6dcb29125628952e2c7d4f6441351fb88a1c8e0362b21f0a021eac49d4fd058cc3adda1dfe3f6fcdfdc96cce74f99095537d26114c08","name":"MeanShift_DorinComaniciu_2002_Fig2c.png","type":"image/png","lastModified":1695788483824.431,"size":171688},{"id":"baf756c0c64be45012b0ebdc1575fc8224b1b19188bd2664956585c57c2f66a4416d17fa9edb3f6cf1806c92b5cb7d71d12e9900d8955d98232454f1062d595d","href":"https://static.observableusercontent.com/files/baf756c0c64be45012b0ebdc1575fc8224b1b19188bd2664956585c57c2f66a4416d17fa9edb3f6cf1806c92b5cb7d71d12e9900d8955d98232454f1062d595d","name":"Recited from Pennsylvania State Univ Mean Shift Theory 02.png","type":"image/png","lastModified":1695792841447.171,"size":29153},{"id":"646db56a4cfe940832a2fa87f4109502de8ac10fdaae7a0ded6b17ffa6144e3155d3c7a62af9c521ce4ecfa3d4f95d996cdb3ad21e4cf2174f1d8db8f94824e3","href":"https://static.observableusercontent.com/files/646db56a4cfe940832a2fa87f4109502de8ac10fdaae7a0ded6b17ffa6144e3155d3c7a62af9c521ce4ecfa3d4f95d996cdb3ad21e4cf2174f1d8db8f94824e3","name":"MeanShift_DorinComaniciu_2002_Fig2.png","type":"image/png","lastModified":1695772507990.321,"size":541504},{"id":"bacb6619a19b23f3b4822bb04fc1422fa94876cecee0a229f4be773abe53fa51429382d4e4a34c06ce70b69a127f66edb2759fcd680975a025b2aaff1d4ba68a","href":"https://static.observableusercontent.com/files/bacb6619a19b23f3b4822bb04fc1422fa94876cecee0a229f4be773abe53fa51429382d4e4a34c06ce70b69a127f66edb2759fcd680975a025b2aaff1d4ba68a","name":"MeanShift_DorinComaniciu_2002_Fig2a.png","type":"image/png","lastModified":1695788467431.027,"size":175844},{"id":"ff0a3b67862a44babec778c86c379e448ecb4b4703b9ccf36e7171d0db2b8b0f0d8d9e5bcbea7a416105b353e494dbf6f7b56a00590db52c8da7fadd5c6787cf","href":"https://static.observableusercontent.com/files/ff0a3b67862a44babec778c86c379e448ecb4b4703b9ccf36e7171d0db2b8b0f0d8d9e5bcbea7a416105b353e494dbf6f7b56a00590db52c8da7fadd5c6787cf","name":"MeanShift_DorinComaniciu_2002_Fig2b.png","type":"image/png","lastModified":1695788476204.16,"size":179616},{"id":"7153045060fbcb60014cca1684d23000d95c76fc4a8ae67ac282b288373252b000a6026e66c351443491bd320ccb68586defd7b2de601e0be6a6c445326ae984","href":"https://static.observableusercontent.com/files/7153045060fbcb60014cca1684d23000d95c76fc4a8ae67ac282b288373252b000a6026e66c351443491bd320ccb68586defd7b2de601e0be6a6c445326ae984","name":"Recited from Pennsylvania State Univ Mean Shift Theory 01.png","type":"image/png","lastModified":1695792832679.5,"size":92669}] 31:{"id":"0466ea284d8327f5","slug":"short-guide-to-ml-mean-shift","title":"짧은 머신러닝 안내서: Mean shift clustering","thumbnail":"615efdb32f7fdeb2250fd980190745ea9bb21a00c9d28aa509b8d7fbfe2b61cc","access_level":"public","create_time":"$D2023-09-26T09:28:59.304Z","update_time":"$D2023-09-27T11:54:12.342Z","view_time":null,"first_public_time":"$D2023-09-26T09:28:59.304Z","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":358,"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":"짧은 머신러닝 안내서: Mean shift clustering","cells":[{"id":0,"value":"# 짧은 머신러닝 안내서:
Mean shift clustering","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":21,"value":"---\n## Clustering?\n* 데이터포인트들의 특성값으로 유사한 데이터들의 군집(cluster)을 찾는 알고리즘\n* 데이터에 라벨(미리 정해진 군집)이 없는 비지도적 학습방법(unsupervised learning)\n\n## Mean shift clustering?\n* Kernel Density Estimation 과정\n * Kernel: 데이터의 발생점을 기준으로 어느정도 오차범위를 표현\n * Density: 여러 오차범위로 교차 가중된 곳은 밀도가 높다\n * Estimation: 밀도의 분포를 추정하는 과정\n* Mode seeking 혹은 Hill climbing 방법이라고도 한다\n * Mode seeking: 밀도가 높은 꼭대기(Mode)를 찾아 등반하는 과정\n * 같은 꼭대기로 등반하는 데이터포인트들을 하나의 군집으로 분류","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":200,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":40,"value":"---\n## 알고리즘 개요\n1. n개의 데이터포인트가 곧 n개의 후보mode라 가정하고 시작\n2. 각 후보mode마다 다음을 반복\n 1. 후보mode의 현위치를 기준으로 범위(bandwidth)안의 데이터포인트를 찾음\n 2. 찾은 범위내 데이터포인트들의 평균점으로 후보mode를 이동\n 3. 후보mode의 이동이 없을때(혹은 이동이 미약할때) 이를 최종mode로 결정\n3. 결과로 찾은 최종mode들이 서로 범위(bandwidth)안에 인접한 경우 병합\n4. 각 데이터포인트는 mean shift 등반과정에서 도달한 mode에 할당\n\n## 알고리즘 동작 예시\n* 데이터셋: 시총상위49종목(+1하위종목)의 일가격변동 t-SNE 결과\n* 파라메터: 범위(bandwidth)\n* 슬라이더로 n개의 데이터포인트마다 mode찾는 과정 시각화\n * 연한색깔로 표현된 심볼 = mode\n * 화살표 = mean shift로 인한 등반이동선\n * 원형 회색음영지역 = 현재 mean-shift중인 후보mode의 범위(bandwidth)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":70,"value":"viewof meanshift_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 = d3.range(0.5,3.5,0.5);\n const slider_samples = d3_slider.sliderBottom().min(d3.min(samples)).max(d3.max(samples))\n .tickValues(samples).tickFormat(v=>v.toFixed(1))\n .value(1.5).step(0.5).width(dim.w-40).fill(\"grey\").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\",\"60\").attr(\"y\",-30).attr(\"dy\",4).text(\"범위(bandwidth)\");\n \n return Object.defineProperty(\n svg.node(), \n \"value\", \n {get: () => ({bandwidth:slider_samples.value()})}\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":324,"value":"## 알고리즘의 강점과 약점\n\n* 강점\n * 충분한 데이터 밀도하에 범용성\n * 군집의 형태에 대한 가정이 없다\n * 데이터 특성에 영향을 덜 받는다\n * 단일 파라메터(오직 bandwidth)로 동작한다\n * bandwidth는 사용자가 실질적 의미를 두고 설정가능\n * 랜덤초기화가 없어 결과도 항상 동일하다\n* 약점\n * 적절한 bandwidth의 설정이 어렵다\n * 풀려는 문제(데이터)마다 설정값이 다르다\n * 단일 bandwidth만으로 전체의 분포에 맞지 않을수 있다\n * 비수치형(non-numeric) 데이터에 적용이 어렵다\n * 계산량이 데이터포인트수의 제곱으로 증가, O(N²)\n \n## 알고리즘의 일반적인 활용\n * 컴퓨터비전 분야에서 태어나고 발전함\n * 이미지 세그먼테이션, 영역이나 물체의 경로추적\n * 충분히 큰 사이즈의 데이터에 범용적으로 사용가능","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":338,"value":"---\n\n## 참고자료\n* Mean Shift 원저자 논문: [Comaniciu, D. & Meer, P. (2002). Mean shift: A robust approach toward feature space analysis](https://courses.csail.mit.edu/6.869/handouts/PAMIMeanshift.pdf)\n* 위키피디아 Mean shift 설명자료: [Wikipedia - Mean shift](https://en.wikipedia.org/wiki/Mean_shift)\n* Python sklearn mean shift clustering 모듈: [sklearn.cluster.MeanShift](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html)\n * **(주의)** sklearn의 군집할당방식 ≠ 원래 알고리즘의 군집할당방식\n* 파워포인트형식의 강의자료\n * [Lecture 13: k-means and mean-shift clustering, Stanford Vision Lab](http://vision.stanford.edu/teaching/cs131_fall1617/lectures/lecture13_kmeans_mean_shift_cs131_2016)\n * [Mean-shift Tracking, CSE, Pennsylvania State University\nCSE598G](https://www.cse.psu.edu/~rtc12/CSE598G/introMeanShift_6pp.pdf)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":356,"value":"---\n## 부연설명 동영상\n\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":9,"value":"---\n## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":66,"value":"rawdata = await FileAttachment(\"krx_cap50_tsne_2d.csv\").csv({typed: \"auto\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"rawdata","database":"$undefined"},{"id":89,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"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":11,"value":"symbols = {\n const symbols = [\n d3.symbol(d3.symbolTriangle),\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":7,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"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"