seq 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%20%20%20%20%22numpy%22%2C%0A%23%20%20%20%20%20%22matplotlib%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%23%0A%23%20Marimo%20version%20of%20the%20Sequential%20clustering%20lecture.%0A%23%20Same%20content%20as%20notebooks%2F10%2Fseq_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%2F10%2Fseq_clustering.py%60%0A%23%20or%20export%20to%20WASM%20for%20GitHub%20Pages%20(see%20.github%2Fworkflows%2Fpublish-slides.yml).%0A%23%0A%23%20NOTE%20on%20scoping%3A%20in%20Jupyter%20the%20same%20name%20(e.g.%20%60X%60)%20can%20be%20redefined%0A%23%20in%20any%20number%20of%20cells%2C%20but%20Marimo%20requires%20each%20name%20to%20be%20owned%20by%0A%23%20exactly%20one%20cell.%20Below%2C%20every%20cell-local%20dataset%20and%20figure%20is%20given%0A%23%20a%20unique%20suffix%20(%60_three%60%2C%20%60_bridge%60%2C%20%60_norms%60)%20so%20the%20slides%20stay%0A%23%20independent%20and%20the%20data%20each%20figure%20displays%20is%20reproducible.%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_()%3A%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%0A%20%20%20%20return%20np%2C%20plt%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%201%20-%20Sequential%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-%20Often%20important%20to%20find%20groups%20in%20data.%0A%20%20%20%20-%20Vastly%20important%20in%20data%20processing.%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%20Example%0A%0A%20%20%20%20-%20Clustering%20in%20modern%20computer%20vision%0A%20%20%20%20-%20%5B**DINOv2%3A%20Learning%20Robust%20Visual%20Features%20without%20Supervision**%5D(https%3A%2F%2Farxiv.org%2Fpdf%2F2304.07193)%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%20DINOv2%20cluster%20figure%3A%20motivates%20why%20clustering%20matters%20in%0A%20%20%20%20%23%20modern%20computer-vision%20pipelines%20(self-supervised%20features%0A%20%20%20%20%23%20cluster%20semantically%20meaningful%20regions).%0A%20%20%20%20mo.image(src%3D%22media%2Fdino_cluster.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%20Clustering%3A%20Science%20or%20Art%3F%0A%0A%20%20%20%20-%20%5B**Is%20there%20such%20a%20thing%20as%20a%20%22correct%22%20clustering%3F**%5D(https%3A%2F%2Fproceedings.mlr.press%2Fv27%2Fluxburg12a%2Fluxburg12a.pdf)%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%20Three%20images%20from%20Luxburg's%20%22Is%20there%20a%20correct%20clustering%3F%22%0A%20%20%20%20%23%20paper%20that%20frame%20the%20discussion%3A%20thesis%20statement%2C%20what%0A%20%20%20%20%23%20different%20algorithms%20produce%2C%20and%20how%20to%20read%20them.%0A%20%20%20%20mo.hstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.image(src%3D%22media%2Fthesis.png%22%2C%20width%3D%22200px%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.image(src%3D%22media%2Fcluster_results.png%22%2C%20width%3D%22400px%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.image(src%3D%22media%2Fexplanation.png%22%2C%20width%3D%22400px%22)%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20justify%3D%22start%22%2C%0A%20%20%20%20%20%20%20%20gap%3D2%2C%0A%20%20%20%20)%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%20Key%20points%0A%0A%20%20%20%20-%20Often%20no%20prior%20knowledge%20about%20data%20-%3E%20unsupervised%0A%20%20%20%20-%20Different%20ways%20of%20specifying%20groups%20%2F%20clusters%20-%3E%20different%20answers.%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%20Loose%20idea%20of%20clustering%0A%0A%20%20%20%20-%20Find%20natural%20groups%20such%20that%3A%0A%20%20%20%20%20%20%20%20-%20Points%20in%20the%20same%20cluster%20%22similar%22.%0A%20%20%20%20%20%20%20%20-%20Points%20in%20different%20clusters%20are%20%22dissimilar%22.%0A%20%20%20%20-%20Draw%20example%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%20Different%20types%20of%20clustering%0A%0A%20%20%20%20-%20Will%20look%20at%3A%0A%20%20%20%20%20%20%20%20-%20Sequential%0A%20%20%20%20%20%20%20%20-%20Hierarchical%0A%20%20%20%20%20%20%20%20-%20Function%20optimization%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20K-means%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Spectral%0A%20%20%20%20%20%20%20%20-%20Clustering%20evaluation%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%20Membership%20functions%0A%0A%20%20%20%20-%20Let%20%24X%20%3D%20%5C%7B%5Cmathbf%7Bx_1%7D%2C%20%5Ccdots%2C%20%5Cmathbf%7Bx_N%7D%5C%7D%24%0A%20%20%20%20-%20Task%3A%20Assign%20cluster%20memberships%20to%20%24%5Cmathbf%7Bx%7D_i%24%20for%20%24i%3D1%2C%5Ccdots%2CN%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20%23%20Toy%20three-cluster%20dataset%20(4%20points%20each)%20used%20to%20motivate%0A%20%20%20%20%23%20hard%20membership%20functions%3B%20the%20same%20setup%20is%20reused%20in%20later%0A%20%20%20%20%23%20slides%20with%20bridge%20points%20added.%0A%20%20%20%20rng_three%20%3D%20np.random.default_rng(42)%0A%20%20%20%20centers_three%20%3D%20np.array(%5B%5B0.0%2C%200.0%5D%2C%20%5B5.0%2C%200.0%5D%2C%20%5B2.5%2C%204.0%5D%5D)%0A%20%20%20%20points_per_cluster_three%20%3D%204%0A%0A%20%20%20%20X_three%20%3D%20%5B%5D%0A%20%20%20%20labels_three%20%3D%20%5B%5D%0A%20%20%20%20for%20k_three%2C%20c_three%20in%20enumerate(centers_three)%3A%0A%20%20%20%20%20%20%20%20pts_three%20%3D%20c_three%20%2B%200.3%20*%20rng_three.normal(size%3D(points_per_cluster_three%2C%202))%0A%20%20%20%20%20%20%20%20X_three.append(pts_three)%0A%20%20%20%20%20%20%20%20labels_three%20%2B%3D%20%5Bk_three%5D%20*%20points_per_cluster_three%0A%20%20%20%20X_three%20%3D%20np.vstack(X_three)%0A%20%20%20%20labels_three%20%3D%20np.array(labels_three)%0A%0A%20%20%20%20fig_three%2C%20ax_three%20%3D%20plt.subplots(figsize%3D(6%2C%205))%0A%20%20%20%20for%20k_three%20in%20range(3)%3A%0A%20%20%20%20%20%20%20%20ix_three%20%3D%20labels_three%20%3D%3D%20k_three%0A%20%20%20%20%20%20%20%20ax_three.scatter(X_three%5Bix_three%2C%200%5D%2C%20X_three%5Bix_three%2C%201%5D%2C%20s%3D100%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22cluster%20%7Bk_three%2B1%7D%22%2C%20edgecolor%3D%22k%22)%0A%20%20%20%20ax_three.set_title(%22Three%20distinct%20clusters%20(4%20points%20each)%22)%0A%20%20%20%20ax_three.legend()%0A%20%20%20%20ax_three.set_aspect(%22equal%22)%0A%20%20%20%20ax_three.grid(alpha%3D0.3)%0A%0A%20%20%20%20mo.as_html(fig_three)%0A%20%20%20%20plt.close(fig_three)%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%20Membership%20functions%0A%0A%20%20%20%20-%20Assume%20%24m%24%20clusters.%0A%20%20%20%20-%20Let%20%24u_j%3A%20%5Cmathbf%7Bx%7D%20%5Crightarrow%20%5C%7B0%2C%201%5C%7D%24.%0A%20%20%20%20-%20Subject%20to%3A%20%24%5Csum_%7Bj%3D1%7D%5E%7B%5Em%7D%20u_j%20(%5Cmathbf%7Bx%7D_i)%3D1%24%20for%20%24i%3D1%2C%5Ccdots%2CN%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20%23%20Same%20toy%20three-cluster%20dataset%20but%20with%20two%20%22bridge%22%20points%0A%20%20%20%20%23%20added%20between%20the%20clusters%20%E2%80%94%20used%20to%20motivate%20the%20need%20for%0A%20%20%20%20%23%20fuzzy%20%2F%20continuous%20memberships.%0A%20%20%20%20rng_bridge%20%3D%20np.random.default_rng(42)%0A%20%20%20%20centers_bridge%20%3D%20np.array(%5B%5B0.0%2C%200.0%5D%2C%20%5B5.0%2C%200.0%5D%2C%20%5B2.5%2C%204.0%5D%5D)%0A%20%20%20%20points_per_cluster_bridge%20%3D%204%0A%0A%20%20%20%20X_bridge%20%3D%20%5B%5D%0A%20%20%20%20labels_bridge%20%3D%20%5B%5D%0A%20%20%20%20for%20k_bridge%2C%20c_bridge%20in%20enumerate(centers_bridge)%3A%0A%20%20%20%20%20%20%20%20pts_bridge%20%3D%20c_bridge%20%2B%200.3%20*%20rng_bridge.normal(size%3D(points_per_cluster_bridge%2C%202))%0A%20%20%20%20%20%20%20%20X_bridge.append(pts_bridge)%0A%20%20%20%20%20%20%20%20labels_bridge%20%2B%3D%20%5Bk_bridge%5D%20*%20points_per_cluster_bridge%0A%0A%20%20%20%20bridge_pts%20%3D%20np.array(%5B%5B2.5%2C%200.0%5D%2C%20%5B2.5%2C%202.0%5D%5D)%0A%20%20%20%20X_bridge.append(bridge_pts)%0A%20%20%20%20labels_bridge%20%2B%3D%20%5B3%2C%203%5D%0A%0A%20%20%20%20X_bridge%20%3D%20np.vstack(X_bridge)%0A%20%20%20%20labels_bridge%20%3D%20np.array(labels_bridge)%0A%0A%20%20%20%20fig_bridge%2C%20ax_bridge%20%3D%20plt.subplots(figsize%3D(6%2C%205))%0A%20%20%20%20for%20k_bridge%20in%20np.unique(labels_bridge)%3A%0A%20%20%20%20%20%20%20%20ix_bridge%20%3D%20labels_bridge%20%3D%3D%20k_bridge%0A%20%20%20%20%20%20%20%20lbl%20%3D%20f%22cluster%20%7Bk_bridge%2B1%7D%22%20if%20k_bridge%20%3C%203%20else%20%22bridge%22%0A%20%20%20%20%20%20%20%20ax_bridge.scatter(X_bridge%5Bix_bridge%2C%200%5D%2C%20X_bridge%5Bix_bridge%2C%201%5D%2C%20s%3D100%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Dlbl%2C%20edgecolor%3D%22k%22)%0A%20%20%20%20ax_bridge.set_title(%22Three%20distinct%20clusters%20(4%20points%20each)%20%2B%202%20bridge%20points%22)%0A%20%20%20%20ax_bridge.legend()%0A%20%20%20%20ax_bridge.set_aspect(%22equal%22)%0A%20%20%20%20ax_bridge.grid(alpha%3D0.3)%0A%0A%20%20%20%20mo.as_html(fig_bridge)%0A%20%20%20%20plt.close(fig_bridge)%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%20Fuzzy%20membership%0A%0A%20%20%20%20-%20Let%20%24u_j%3A%20%5Cmathbf%7Bx%7D%20%5Crightarrow%20%5B0%2C%201%5D%24.%0A%20%20%20%20-%20Subject%20to%3A%20%24%5Csum_%7Bj%3D1%7D%5E%7B%5Em%7D%20u_j%20(%5Cmathbf%7Bx%7D_i)%3D1%24%20for%20%24i%3D1%2C%5Ccdots%2CN%24%0A%20%20%20%20-%20Going%20from%20discrete%20to%20continuous%20assignments%0A%20%20%20%20%20%20%20%20-%20Opens%20the%20door%20for%20derivative-based%20optimization.%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%20Proximity%20measures%0A%0A%20%20%20%20-%20Both%20dissimilarity%20and%20similarity%0A%20%20%20%20%20%20%20%20-%20Between%20pairs%20of%20vectors%0A%20%20%20%20%20%20%20%20-%20Between%20vector%20and%20set%0A%20%20%20%20%20%20%20%20-%20Between%20pairs%20of%20sets%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%20Proximity%20measures%20between%20pairs%20of%20vectors%0A%0A%20%20%20%20-%20Let%20d%20%3A%20X%20%C3%97%20X%20%E2%86%92%20%E2%84%9D%20be%20a%20dissimilarity%20(distance)%20between%20vectors.%0A%0A%20%20%20%20-%20Non%E2%80%91negativity%3A%20d(x%2C%20y)%20%E2%89%A5%20d_0%20for%20all%20x%2C%20y.%0A%0A%20%20%20%20-%20Identity%3A%20d(x%2C%20x)%20%3D%20d_0%20for%20all%20x.%0A%0A%20%20%20%20-%20Symmetry%3A%20d(x%2C%20y)%20%3D%20d(y%2C%20x)%20for%20all%20x%2C%20y.%0A%0A%20%20%20%20-%20Triangle%20inequality%3A%20d(x%2C%20z)%20%E2%89%A4%20d(x%2C%20y)%20%2B%20d(y%2C%20z)%20for%20all%20x%2C%20y%2C%20z.%0A%0A%20%20%20%20-%20A%20function%20satisfying%201%E2%80%934%20is%20a%20metric.%0A%0A%20%20%20%20-%20Note%3A%20some%20useful%20proximity%20measures%20(similarities%2C%20asymmetric%20scores%2C%20etc.)%20violate%20one%20or%20more%20of%20these%20properties.%0A%20%20%20%20%20%20%20%20-%20Divergence%20measures%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%20Examples%20for%20dissimilarity%20measure%0A%0A%20%20%20%20-%20Weighted%20%24l_p%24%20metric%20dissimilarity%20measure%3A%20%24d(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D)%20%3D%20%5Cbig(%20%5Csum_%7Bi%3D1%7D%5E%7Bl%7D%20w_i%7Cx_i-y_i%7C%5Ep%5Cbig)%5E%7B1%2Fp%7D%24%20for%20%24%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D%20%5Cin%20%5Cmathbb%7BR%7D%24.%0A%20%20%20%20-%20Euclidean%20distance%3A%0A%20%20%20%20%20%20%20%20-%20%24d_2(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D)%20%3D%20%5Csqrt%7B%7B%5Csum_%7Bi%3D1%7D%5E%7Bl%7D%20(x_i-y_i)%5E2%7D%7D%24%0A%20%20%20%20-%20Manhattan%3A%0A%20%20%20%20%20%20%20%20-%20%24d_1(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D)%20%3D%20%7B%5Csum_%7Bi%3D1%7D%5E%7Bl%7D%20%7Cx_i-y_i%7C%7D%24%0A%20%20%20%20-%20l-infinity%3A%0A%20%20%20%20%20%20%20%20%24d_%5Cinfty(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D)%20%3D%20%5Ctext%7Bmax%7D%20%7Cx_i-y_i%7C%24%20for%20%241%5Cleq%20i%20%5Cleq%20l%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20%23%20Unit-ball%20visualisation%20for%20the%20L2%2C%20L1%20and%20L-infinity%20norms%20so%0A%20%20%20%20%23%20students%20can%20see%20the%20geometric%20differences%20between%20common%0A%20%20%20%20%23%20dissimilarity%20measures.%0A%20%20%20%20xs%20%3D%20np.linspace(-1.5%2C%201.5%2C%20401)%0A%20%20%20%20ys%20%3D%20np.linspace(-1.5%2C%201.5%2C%20401)%0A%20%20%20%20X_norms%2C%20Y_norms%20%3D%20np.meshgrid(xs%2C%20ys)%0A%0A%20%20%20%20L2%20%3D%20np.sqrt(X_norms%20**%202%20%2B%20Y_norms%20**%202)%0A%20%20%20%20L1%20%3D%20np.abs(X_norms)%20%2B%20np.abs(Y_norms)%0A%20%20%20%20Linf%20%3D%20np.maximum(np.abs(X_norms)%2C%20np.abs(Y_norms))%0A%0A%20%20%20%20fig_norms%2C%20ax_norms%20%3D%20plt.subplots(figsize%3D(6%2C%204))%0A%20%20%20%20ax_norms.contour(X_norms%2C%20Y_norms%2C%20L2%2C%20levels%3D%5B1.0%5D%2C%20colors%3D%22C0%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D2%2C%20linestyles%3D%22-%22)%0A%20%20%20%20ax_norms.contour(X_norms%2C%20Y_norms%2C%20L1%2C%20levels%3D%5B1.0%5D%2C%20colors%3D%22C1%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D2%2C%20linestyles%3D%22--%22)%0A%20%20%20%20ax_norms.contour(X_norms%2C%20Y_norms%2C%20Linf%2C%20levels%3D%5B1.0%5D%2C%20colors%3D%22C2%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D2%2C%20linestyles%3D%22%3A%22)%0A%20%20%20%20ax_norms.scatter(0%2C%200%2C%20color%3D%22k%22%2C%20zorder%3D5)%0A%20%20%20%20ax_norms.set_aspect(%22equal%22)%0A%20%20%20%20ax_norms.set_xlim(-1.5%2C%201.5)%0A%20%20%20%20ax_norms.set_ylim(-1.5%2C%201.5)%0A%20%20%20%20ax_norms.set_xlabel(%22x%22)%0A%20%20%20%20ax_norms.set_ylabel(%22y%22)%0A%20%20%20%20ax_norms.set_title(%22Unit%20balls%3A%20L2%20(Euclidean)%2C%20L1%20(Manhattan)%2C%20L%E2%88%9E%20(Chebyshev)%22)%0A%20%20%20%20ax_norms.grid(alpha%3D0.3)%0A%0A%20%20%20%20mo.as_html(fig_norms)%0A%20%20%20%20plt.close(fig_norms)%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%20Examples%20of%20similarity%20measures%0A%0A%20%20%20%20-%20Inner-product%3A%20%24%20s_i(%5Cmathbf%7Bx%7D%2C%5Cmathbf%7By%7D)%20%3D%20%5Cmathbf%7Bx%7D%5ET%20%5Cmathbf%7By%7D%24%0A%20%20%20%20-%20Cosine%3A%20%24%20s_i(%5Cmathbf%7Bx%7D%2C%5Cmathbf%7By%7D)%20%3D%20%5Cfrac%7B%5Cmathbf%7Bx%7D%5ET%20%5Cmathbf%7By%7D%7D%7B%5C%7C%20%5Cmathbf%7Bx%7D%20%5C%7C%20%5C%2C%20%5C%7C%20%5Cmathbf%7By%7D%20%5C%7C%7D%24%0A%20%20%20%20-%20From%20dissimilarity%20measure%3A%20%24s%20%3D%20%5Cfrac%7Ba%7D%7Bd%7D%24%20or%20%24s%20%3D%20d_%7B%5Ctext%7Bmax%7D%7D-d%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%20Between%20vector%20and%20set%20C%0A%0A%20%20%20%20-%20Max%20proximity%3A%20%24%5Crho_%7B%5Ctext%7Bmax%7D%7D(%5Cmathbf%7Bx%7D%2C%20C)%20%3D%20%5Cunderset%7B%20%5Cmathbf%7By%7D%20%5Cin%20C%7D%7B%5Cmax%7D%5C%3B%20%5Crho(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D)%24%0A%20%20%20%20-%20Min%20proximity%3A%20%24%5Crho_%7B%5Ctext%7Bmin%7D%7D(%5Cmathbf%7Bx%7D%2C%20C)%20%3D%20%5Cunderset%7B%20%5Cmathbf%7By%7D%20%5Cin%20C%7D%7B%5Cmin%7D%5C%3B%20%5Crho(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D)%24%0A%20%20%20%20-%20Average%20proximity%3A%20%24%5Crho_%7B%5Ctext%7Bavg%7D%7D(%5Cmathbf%7Bx%7D%2C%20C)%20%3D%20%5Cfrac%7B1%7D%7Bn_c%7D%5Csum_%7B%5Cmathbf%7By%7D%20%5Cin%20C%7D%20%5Crho(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7By%7D)%24%0A%0A%20%20%20%20-%20And%20similarly%20for%20proximity%20between%20set%20%24C_i%24%20and%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%20Basic%20sequential%20algorithmic%20scheme%20(BSAS)%0A%0A%20%20%20%20-%20Examine%20all%20samples%20in%20%24X%20%3D%20%5C%7B%5Cmathbf%7Bx_1%7D%2C%20%5Ccdots%2C%20%5Cmathbf%7Bx_N%7D%5C%7D%24%20sequentially.%0A%20%20%20%20-%20Pseudo-code%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%20to%20BSAS%0A%0A%20%20%20%20-%20Order%20important!%0A%20%20%20%20-%20Threshold%20important!%0A%20%20%20%20-%20Vectors%20are%20assigned%20to%20clusters%20before%20the%20number%20of%20clusters%20are%20determined.%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%20Modified%20Basic%20sequential%20algorithmic%20scheme%20(MBSAS)%0A%0A%20%20%20%20-%20First%3B%20determine%20clusters.%0A%20%20%20%20-%20Second%3A%20pattern%20classification.%0A%20%20%20%20-%20Requires%20two%20passes%20through%20the%20data.%0A%20%20%20%20-%20Pseudo-code%3A%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