hier clustering

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.10%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%23%0A%23%20Marimo%20version%20of%20the%20Hierarchical%20clustering%20lecture.%0A%23%20Same%20content%20as%20notebooks%2F11%2Fhier_clustering.ipynb%2C%20but%20authored%20as%20a%0A%23%20reactive%20Marimo%20app%20(one%20slide%20per%20concept%2C%20matching%20the%0A%23%20density_estimation%20notebook's%20structure).%0A%23%20Run%20locally%20with%20%60marimo%20edit%20notebooks%2F11%2Fhier_clustering.py%60%0A%23%20or%20export%20to%20WASM%20for%20GitHub%20Pages%20(see%20.github%2Fworkflows%2Fpublish-slides.yml).%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.23.13%22%0Aapp%20%3D%20marimo.App(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20layout_file%3D%22data%3Aapplication%2Fjson%3Bbase64%2CewogICJ0eXBlIjogInNsaWRlcyIsCiAgImRhdGEiOiB7fQp9Cg%3D%3D%22%2C%0A)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20os%0A%20%20%20%20from%20pathlib%20import%20Path%0A%0A%20%20%20%20%23%20Make%20%60mo.image(src%3D%22media%2Ffoo.png%22)%60%20resolve%20regardless%20of%20which%0A%20%20%20%20%23%20directory%20%60marimo%20edit%60%20is%20launched%20from.%20We%20chdir%20to%20the%20notebook's%0A%20%20%20%20%23%20own%20directory%20so%20the%20relative%20%60media%2F%60%20path%20works%20the%20same%20way%20it%0A%20%20%20%20%23%20does%20for%20the%20deployed%20WASM%20build%20(where%20the%20page%20sits%20next%20to%0A%20%20%20%20%23%20%60media%2F%60).%20In%20WASM%2C%20%60__file__%60%20may%20not%20be%20set%20and%20the%20chdir%20becomes%0A%20%20%20%20%23%20a%20no-op%20%E2%80%94%20the%20browser%20still%20fetches%20the%20images%20via%20the%20page%20URL.%0A%20%20%20%20if%20%22__file__%22%20in%20globals()%20and%20__file__%3A%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20os.chdir(Path(__file__).resolve().parent)%0A%20%20%20%20%20%20%20%20except%20OSError%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Clustering%202%20-%20Hierarchical%20clustering%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Introduction%0A%0A%20%20%20%20-%20Last%20lecture%20we%20looked%20at%20sequential%20clustering.%0A%20%20%20%20%20%20%20%20-%20Start%20from%20on%20data%20point%20and%20sequentially%20determine%20clusterings.%0A%20%20%20%20-%20Today%2C%20we%20take%20alternative%20routes%3A%0A%20%20%20%20%20%20%20%20-%20Divisive%0A%20%20%20%20%20%20%20%20-%20Agglomerative%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Example%0A%0A%20%20%20%20-%20Clustering%20in%20modern%20computer%20vision%0A%20%20%20%20-%20%5B**DINOv3**%5D(https%3A%2F%2Farxiv.org%2Fpdf%2F2304.07193)%0A%20%20%20%20-%20%5B**Automatic%20Data%20Curation%20for%20Self-Supervised%20Learning%3AA%20Clustering-Based%20Approach**%5D(https%3A%2F%2Farxiv.org%2Fpdf%2F2405.15613)%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20%23%20Cluster%20example%20from%20the%20DINOv3%20%2F%20automatic-data-curation%20paper%3A%0A%20%20%20%20%23%20shows%20what%20large-scale%20clustering%20produces%20on%20real%20image%20data.%0A%20%20%20%20mo.image(src%3D%22media%2Fcluster_ex.png%22%2C%20width%3D%22600px%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Divisive%0A%0A%20%20%20%20-%20Core%20idea%3A%20start%20will%20all%20points%20in%20one%20clusters%20and%20split%20based%20on%20proxmity.%0A%20%20%20%20-%20Draw%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Agglomerative%0A%0A%20%20%20%20-%20Core%20idea%3A%20all%20points%20are%20a%20cluster%20and%20merge%20hierarchically.%0A%20%20%20%20-%20Draw%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Remarks%20on%20agglomerative%0A%0A%20%20%20%20-%20Nested%20clusterings!%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Agglomerative%20algorithms%0A%0A%20%20%20%20-%20%24g(c_i%2C%20cj)%20%5Crightarrow%20%24proximity%20between%20clusters%20%24c_i%20%24and%20%24c_j%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Generalized%20agglomerative%20scheme%20(GAS)%0A%0A%20%20%20%20-%20Initialize%3A%20%24R_0%20%3D%20%5C%7B%20c_i%20%3D%20%5C%7B%20%5Cmathbf%7Bx_i%7D%5C%7D%2C%20i%3D1%2C%5Ccdots%2CN%5C%7D%24%0A%20%20%20%20-%20Pseudocode%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Matrix-based%20implementation%0A%0A%20%20%20%20-%20Note%3A%20%24g(c_i%2C%20cj)%24formed%20from%20proximity%20between%20data%20points.%0A%20%20%20%20-%20Will%20focus%20on%20dissimilarity%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Dissimilarity%20matrix%0A%0A%20%20%20%20-%20Define%20%24%5Cmathbf%7BP%7D%20(N%20%5Ctimes%20N)%24such%20that%20%24P_%7Bij%7D%3Dd(%5Cmathbf%7Bx%7D_i%2C%20%5Cmathbf%7Bx%7D_j)%24.%0A%20%20%20%20%20%20%20%20-%20Symmetric%0A%20%20%20%20%20%20%20%20-%20%24P_ii%3Dd_0%24%20(smallest%20value%20along%20diagonal)%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Matrix%20updating%20algorithmic%20scheme%20(MUAS)%0A%0A%20%20%20%20-%20Pseudocode%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Single%20link%20versus%20complete%20link%0A%0A%20%20%20%20-%20Single%20link%20algorithm%3A%0A%20%20%20%20-%20Complete%20link%20algorithm%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Example%20single%20link%0A%0A%20%20%20%20-%20%24%5Cmathbf%7BP%7D_0%20%3D%20%20%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Single%20link%20dendrogram%0A%0A%20%20%20%20-%20Draw%20dendrogram%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Example%20complete%20link%0A%0A%20%20%20%20-%20%24%5Cmathbf%7BP%7D_0%20%3D%20%20%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Complete%20link%20dendrogram%0A%0A%20%20%20%20-%20Draw%20dendrogram%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Computational%20complexity%0A%0A%20%20%20%20-%20For%20large%20datasets%2C%20this%20procedure%20can%20become%20computationally%20demanding.%0A%20%20%20%20-%20Many%20splits%20if%20N%20gets%20large.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A