clustering lezione 1

%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%22marimo%22%2C%20%22numpy%22%2C%20%22matplotlib%22%2C%20%22scikit-learn%22%2C%20%22scipy%22%5D%0A%23%20%2F%2F%2F%0A%23%20Pattern%20Recognition%20%E2%80%94%20Clustering.%20Marimo%20slides%2C%20one%20concept%20per%20cell.%0A%23%20Open%20with%3A%20marimo%20edit%20clustering_lezione_1.py%3B%20switch%20to%20presentation%2Fslides%20mode.%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%2CewogICJ0eXBlIjogInNsaWRlcyIsCiAgImRhdGEiOiB7CiAgICAiY2VsbHMiOiBbCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2tpcCIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2tpcCIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2tpcCIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAge30KICAgIF0sCiAgICAiZGVjayI6IHt9CiAgfQp9%22%2C%0A)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20from%20sklearn.datasets%20import%20make_moons%2C%20make_blobs%0A%20%20%20%20from%20scipy.cluster.hierarchy%20import%20linkage%2C%20dendrogram%0A%0A%20%20%20%20return%20make_blobs%2C%20make_moons%2C%20mo%2C%20np%2C%20plt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23Clustering%20I%0A%0A%20%20%20%20-%20Unsupervised%20learning%3A%20basic%20concepts%0A%20%20%20%20-%20Proximity%20measures%0A%20%20%20%20-%20K-means%3A%20objective%2C%20updates%2C%20convergence%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E1%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20From%20dimensionality%20reduction%20to%20clustering%0A%0A%20%20%20%20-%20PCA%20%2F%20KPCA%3A%20coordinates%20preserving%20variance.%0A%20%20%20%20-%20Laplacian%20Eigenmaps%3A%20preserve%20local%20neighborhoods.%0A%20%20%20%20-%20Clustering%3A%20discover%20groups%2C%20without%20known%20labels.%0A%0A%20%20%20%20%24%24%5Cmathbf%7Bx%7D_1%2C%5Cldots%2C%5Cmathbf%7Bx%7D_N%5Cin%5Cmathbb%7BR%7D%5Ed%5Cquad%5Clongrightarrow%5Cquad%20c_i%5Cin%5C%7B1%2C%5Cldots%2Ck%5C%7D%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E2%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20What%20makes%20a%20cluster%3F%0A%0A%20%20%20%20-%20Compact%20cloud%20around%20a%20centroid.%0A%20%20%20%20-%20Chain%20of%20nearby%20points%3A%20another%20idea%20of%20a%20group.%0A%20%20%20%20-%20No%20universal%20notion%20of%20a%20%E2%80%9Ccorrect%E2%80%9D%20partition.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E3%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_4_mode%3Dmo.ui.slider(start%3D0%2Cstop%3D2%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%22Geometry%20(0%3A%20clouds%20%C2%B7%201%3A%20arcs%20%C2%B7%202%3A%20elongated)%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_4_mode%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_4_mode%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_4_mode%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3.6))%0A%20%20%20%20_rng%3Dnp.random.default_rng(12)%0A%20%20%20%20if%20control_4_mode.value%3D%3D0%3A%0A%20%20%20%20%20%20%20%20_A%3D_rng.normal(%5B-2%2C0%5D%2C%5B.35%2C.35%5D%2C(45%2C2))%3B%20_B%3D_rng.normal(%5B2%2C0%5D%2C%5B.35%2C.35%5D%2C(45%2C2))%0A%20%20%20%20elif%20control_4_mode.value%3D%3D1%3A%0A%20%20%20%20%20%20%20%20_t%3Dnp.linspace(.05%2Cnp.pi-.05%2C45)%0A%20%20%20%20%20%20%20%20_A%3Dnp.c_%5B2*np.cos(_t)%2C2*np.sin(_t)%5D%3B%20_B%3Dnp.c_%5B1.15*np.cos(_t)%2C1.15*np.sin(_t)%5D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_A%3D_rng.normal(%5B-2%2C0%5D%2C%5B.32%2C.32%5D%2C(45%2C2))%3B%20_t%3Dnp.linspace(-1.8%2C1.8%2C45)%3B_B%3Dnp.c_%5B_t%2B1.7%2C%20_t*.45%2B.08*_rng.normal(size%3D45)%5D%0A%20%20%20%20_ax.scatter(*_A.T%2Cs%3D27%2Clabel%3D%22Group%20A%22)%3B_ax.scatter(*_B.T%2Cs%3D27%2Clabel%3D%22Group%20B%22)%3B_ax.set_aspect('equal')%3B_ax.legend(loc%3D'upper%20right')%3B_ax.set_xlim(-3.3%2C4)%3B_ax.set_ylim(-2.5%2C3)%3B_ax.grid(alpha%3D.15)%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Three%20geometries%2C%20three%20intuitions%0A%0A%20%20%20%20-%20Compare%20compact%20clouds%2C%20nested%20arcs%20and%20elongated%20groups.%0A%20%20%20%20-%20Which%20shape%20is%20easiest%20to%20describe%20with%20a%20center%3F%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E4%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Partition%2C%20labels%2C%20centroids%0A%0A%20%20%20%20-%20Each%20observation%20belongs%20to%20exactly%20one%20cluster.%0A%20%20%20%20-%20The%20centroid%20is%20the%20mean%3A%20not%20necessarily%20an%20observed%20point.%0A%0A%20%20%20%20%24%24C_r%3D%5C%7Bi%3Ac_i%3Dr%5C%7D%2C%5Cqquad%20n_r%3D%7CC_r%7C%2C%5Cqquad%20%5Cboldsymbol%5Cmu_r%3D%5Cfrac1%7Bn_r%7D%5Csum_%7Bi%5Cin%20C_r%7D%5Cmathbf%20x_i%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E5%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Three%20algorithmic%20families%0A%0A%20%20%20%20-%20K-means%3A%20iteratively%20reassign%20points%20to%20k%20centers.%0A%20%20%20%20-%20Sequential%3A%20decide%20what%20to%20do%20with%20the%20next%20arriving%20point.%0A%20%20%20%20-%20Hierarchical%3A%20merge%20currently%20existing%20groups%2C%20one%20pair%20at%20a%20time.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E6%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Proximity%3A%20what%20does%20%E2%80%9Cnear%E2%80%9D%20mean%3F%0A%0A%20%20%20%20-%20Distances%3A%20smaller%20means%20more%20similar.%0A%20%20%20%20-%20Similarities%3A%20larger%20means%20more%20similar.%0A%20%20%20%20-%20The%20notion%20of%20proximity%20affects%20the%20resulting%20clusters.%0A%0A%20%20%20%20%24%24d_2(%5Cmathbf%20x_i%2C%5Cmathbf%20x_j)%3D%5C%7C%5Cmathbf%20x_i-%5Cmathbf%20x_j%5C%7C_2%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E7%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_8_s%3Dmo.ui.slider(start%3D1%2Cstop%3D6%2Cstep%3D1%2Cvalue%3D4%2Clabel%3D%22Vertical%20separation%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_8_s%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_8_s%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_8_s%0A%20%20%20%20_x%2C_y%3D3%2Ccontrol_8_s.value%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(7.5%2C3.6))%3B_ax.plot(%5B0%2C_x%5D%2C%5B0%2C_y%5D%2Clw%3D2.5%2Clabel%3Df'Euclidean%20%3D%20%7Bnp.hypot(_x%2C_y)%3A.2f%7D')%3B_ax.plot(%5B0%2C_x%2C_x%5D%2C%5B0%2C0%2C_y%5D%2Clw%3D2%2Cls%3D'--'%2Clabel%3Df'Manhattan%20%3D%20%7B_x%2B_y%7D')%3B_ax.scatter(%5B0%2C_x%5D%2C%5B0%2C_y%5D%2Cs%3D70%2Czorder%3D4)%3B_ax.set_xlim(-.7%2C6)%3B_ax.set_ylim(-.7%2C7)%3B_ax.set_aspect('equal')%3B_ax.grid(alpha%3D.2)%3B_ax.legend(loc%3D'upper%20left')%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Euclidean%20vs%20Manhattan%20distance%0A%0A%20%20%20%20-%20Same%20endpoints%3B%20different%20routes%20through%20the%20plane.%0A%20%20%20%20-%20Move%20the%20point%20to%20compare%20%24d_2%24%2C%20%24d_1%24%20and%20%24d_%5Cinfty%24.%0A%0A%20%20%20%20%24%24d_1%3D%5Csum_%7B%5Cell%3D1%7D%5Ed%7Cx_%7Bi%5Cell%7D-x_%7Bj%5Cell%7D%7C%2C%5Cqquad%20d_%5Cinfty%3D%5Cmax_%5Cell%20%7Cx_%7Bi%5Cell%7D-x_%7Bj%5Cell%7D%7C%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E8%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Distances%3A%20properties%20and%20squared%20distance%0A%0A%20%20%20%20-%20A%20metric%20is%20nonnegative%2C%20symmetric%20and%20satisfies%20the%20triangle%20inequality.%0A%20%20%20%20-%20Squared%20Euclidean%20distance%20is%20useful%20for%20k-means%20but%20is%20not%20generally%20a%20metric.%0A%0A%20%20%20%20%24%24%5Coperatorname*%7Barg%5C%2Cmin%7D_r%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_r%5C%7C%3D%5Coperatorname*%7Barg%5C%2Cmin%7D_r%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_r%5C%7C%5E2%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E9%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Cosine%20similarity%0A%0A%20%20%20%20-%20Focuses%20on%20direction%20rather%20than%20vector%20length.%0A%20%20%20%20-%20Common%20for%20document%20and%20high-dimensional%20vector%20comparisons.%0A%20%20%20%20-%20Cosine%20dissimilarity%20is%20not%20automatically%20a%20metric.%0A%0A%20%20%20%20%24%24s_%7B%5Cmathrm%7Bcos%7D%7D(%5Cmathbf%20x%2C%5Cmathbf%20y)%3D%5Cfrac%7B%5Cmathbf%20x%5ET%5Cmathbf%20y%7D%7B%5C%7C%5Cmathbf%20x%5C%7C%5C%2C%5C%7C%5Cmathbf%20y%5C%7C%7D%2C%5Cqquad%5Cdelta_%7B%5Cmathrm%7Bcos%7D%7D%3D1-s_%7B%5Cmathrm%7Bcos%7D%7D%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E10%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_11_ang%3Dmo.ui.slider(start%3D0%2Cstop%3D180%2Cstep%3D10%2Cvalue%3D40%2Clabel%3D%22Angle%20(degrees)%22%2Cshow_value%3DTrue)%0A%20%20%20%20control_11_len%3Dmo.ui.slider(start%3D1%2Cstop%3D4%2Cstep%3D1%2Cvalue%3D2%2Clabel%3D%22Length%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20control_11_ang%2C%20control_11_len%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_11_ang%2C%20control_11_len%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dmo.hstack(%5Bcontrol_11_ang%2Ccontrol_11_len%5D)%0A%20%20%20%20_t%3Dnp.deg2rad(control_11_ang.value)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(7.5%2C3.4))%3B_ax.arrow(0%2C0%2C2.3%2C0%2Chead_width%3D.13%2Clength_includes_head%3DTrue%2Ccolor%3D'tab%3Ablue')%3B_ax.arrow(0%2C0%2Ccontrol_11_len.value*np.cos(_t)%2Ccontrol_11_len.value*np.sin(_t)%2Chead_width%3D.13%2Clength_includes_head%3DTrue%2Ccolor%3D'tab%3Aorange')%3B_ax.set_xlim(-4.6%2C4.6)%3B_ax.set_ylim(-.6%2C4.6)%3B_ax.set_aspect('equal')%3B_ax.grid(alpha%3D.2)%3B_ax.set_title(f'Cosine%20similarity%20%3D%20%7Bnp.cos(_t)%3A.3f%7D')%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Cosine%20similarity%3A%20rotate%20a%20vector%0A%0A%20%20%20%20-%20Changing%20the%20angle%20changes%20the%20similarity.%0A%20%20%20%20-%20Changing%20only%20the%20length%20does%20not.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E11%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Feature%20scales%20matter%0A%0A%20%20%20%20-%20Large-scale%20features%20can%20dominate%20Euclidean%20distances.%0A%20%20%20%20-%20Standardization%20changes%20the%20geometry%20before%20clustering.%0A%20%20%20%20-%20Handle%20constant%20features%20separately.%0A%0A%20%20%20%20%24%24%5Cwidetilde%20x_%7Bi%5Cell%7D%3D%5Cfrac%7Bx_%7Bi%5Cell%7D-%5Cbar%20x_%5Cell%7D%7Bs_%5Cell%7D%5Cqquad(s_%5Cell%3E0)%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E12%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_13_scale%3Dmo.ui.switch(value%3DFalse%2Clabel%3D%22Standardize%20features%22)%0A%20%20%20%20return%20(control_13_scale%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_13_scale%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_13_scale%0A%20%20%20%20_P%3Dnp.array(%5B%5B0.%2C0.%5D%2C%5B2.%2C45.%5D%2C%5B4.%2C4.%5D%5D)%0A%20%20%20%20_Q%3Dnp.array(%5B2.%2C3.%5D)%3B_all%3Dnp.vstack(%5B_P%2C_Q%5D)%3B_sd%3D_all.std(axis%3D0)%3B_avg%3D_all.mean(axis%3D0)%0A%20%20%20%20_Z%3D(_all-_avg)%2F_sd%20if%20control_13_scale.value%20else%20_all%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(7.5%2C3.5))%3B_ax.scatter(_Z%5B%3A3%2C0%5D%2C_Z%5B%3A3%2C1%5D%2Cs%3D90%2Clabel%3D%22Candidates%22)%3B_ax.scatter(_Z%5B3%2C0%5D%2C_Z%5B3%2C1%5D%2Cmarker%3D'*'%2Cs%3D230%2Clabel%3D%22Query%22)%3B_j%3Dnp.argmin(np.linalg.norm(_Z%5B%3A3%5D-_Z%5B3%5D%2Caxis%3D1))%3B_ax.plot(%5B_Z%5B_j%2C0%5D%2C_Z%5B3%2C0%5D%5D%2C%5B_Z%5B_j%2C1%5D%2C_Z%5B3%2C1%5D%5D%2Cls%3D'--')%3B_ax.set_title(f'Nearest%20candidate%3A%20%7B%22ABC%22%5B_j%5D%7D')%3B_ax.legend()%3B_ax.grid(alpha%3D.2)%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Scaling%20can%20change%20the%20nearest%20point%0A%0A%20%20%20%20-%20A%20large%20feature%20range%20dominates%20before%20standardization.%0A%20%20%20%20-%20Toggle%20rescaling%20to%20see%20how%20the%20nearest%20neighbor%20changes.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E13%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Proximity%3A%20quick%20recap%0A%0A%20%20%20%20-%20Physical%20separation%20%E2%86%92%20Euclidean.%0A%20%20%20%20-%20Sum%20of%20coordinate%20deviations%20%E2%86%92%20Manhattan.%0A%20%20%20%20-%20Vector%20orientation%20%E2%86%92%20cosine%20similarity.%0A%20%20%20%20-%20Next%3A%20fix%20squared%20Euclidean%20distance%20and%20optimize%20compactness.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E14%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20K-means%3A%20a%20precise%20optimization%20objective%0A%0A%20%20%20%20-%20Input%3A%20%24k%24%20clusters%20and%20%24N%24%20observations.%0A%20%20%20%20-%20Penalize%20each%20squared%20distance%20to%20its%20assigned%20centroid.%0A%20%20%20%20-%20Optimize%20labels%20and%20centroids%20alternately.%0A%0A%20%20%20%20%24%24%5Cboxed%7BJ(%5Cmathbf%20c%2C%5Cboldsymbol%5Cmu)%3D%5Csum_%7Bi%3D1%7D%5EN%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_%7Bc_i%7D%5C%7C%5E2%7D%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E15%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_16_seed%3Dmo.ui.slider(start%3D0%2Cstop%3D2%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%22Initialization%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_16_seed%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_16_seed%2C%20make_blobs%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_16_seed%0A%20%20%20%20_X%2C_%3Dmake_blobs(n_samples%3D110%2Ccenters%3D%5B%5B-2%2C0%5D%2C%5B2%2C0%5D%5D%2Ccluster_std%3D.65%2Crandom_state%3D11)%0A%20%20%20%20_C%3Dnp.array(%5B%5B%20-3.%2C0.%5D%2C%5B3.%2C0.%5D%5D)%20if%20control_16_seed.value%3D%3D0%20else%20(np.array(%5B%5B-2.%2C2.%5D%2C%5B0.%2C2.%5D%5D)%20if%20control_16_seed.value%3D%3D1%20else%20np.array(%5B%5B0.%2C-2.%5D%2C%5B1.%2C-2.%5D%5D))%0A%20%20%20%20_labels%3Dnp.argmin(((%20_X%5B%3A%2CNone%2C%3A%5D-_C%5BNone%2C%3A%2C%3A%5D)**2).sum(2)%2Caxis%3D1)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(7.7%2C3.8))%3B_ax.scatter(*_X.T%2Cc%3D_labels%2Ccmap%3D'coolwarm'%2Cs%3D21)%3B_ax.scatter(*_C.T%2Cmarker%3D'X'%2Cs%3D160%2Cc%3D'black')%3B_ax.set_xlim(-5%2C5)%3B_ax.set_ylim(-3.2%2C3.2)%3B_ax.set_aspect('equal')%3B_ax.set_title('One%20assignment%20step%3B%20initial%20centroids%20marked%20X')%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20K-means%3A%20initialization%20changes%20the%20story%0A%0A%20%20%20%20-%20Move%20the%20chosen%20seed%20configuration.%0A%20%20%20%20-%20Assignments%20depend%20on%20which%20centroids%20are%20initially%20selected.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E16%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Why%20is%20the%20optimal%20centroid%20the%20mean%3F%0A%0A%20%20%20%20-%20Hold%20assignments%20fixed.%0A%20%20%20%20-%20Minimize%20within-cluster%20squared%20error%20with%20respect%20to%20the%20center.%0A%20%20%20%20-%20Derivation%20on%20the%20board%20%E2%86%92%20stationary%20point%20is%20the%20mean.%0A%0A%20%20%20%20%24%24J_r(%5Cboldsymbol%5Cmu_r)%3D%5Csum_%7Bi%5Cin%20C_r%7D%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_r%5C%7C%5E2%5Cquad%5CLongrightarrow%5Cquad%20%5Cboxed%7B%5Cboldsymbol%5Cmu_r%3D%5Cfrac1%7Bn_r%7D%5Csum_%7Bi%5Cin%20C_r%7D%5Cmathbf%20x_i%7D%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E17%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_18_center%3Dmo.ui.slider(start%3D-1%2Cstop%3D5%2Cstep%3D.25%2Cvalue%3D1%2Clabel%3D%22Candidate%20centroid%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_18_center%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_18_center%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_18_center%0A%20%20%20%20_xx%3Dnp.array(%5B0.%2C2.%2C4.%5D)%3B_t%3Dnp.linspace(-1%2C5%2C140)%3B_loss%3D((_xx%5B%3A%2CNone%5D-_t%5BNone%2C%3A%5D)**2).sum(0)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(7.7%2C3.5))%3B_ax.plot(_t%2C_loss)%3B_ax.axvline(_xx.mean()%2Cls%3D'--'%2Clabel%3D'Mean%20%3D%202')%3B_ax.scatter(%5Bcontrol_18_center.value%5D%2C%5B((_xx-control_18_center.value)**2).sum()%5D%2Cs%3D90%2Czorder%3D3)%3B_ax.set_title(f'J(%7B%20control_18_center.value%3Ag%7D)%20%3D%20%7B((_xx-control_18_center.value)**2).sum()%3A.2f%7D')%3B_ax.set_xlabel('Candidate%20centroid')%3B_ax.set_ylabel('Squared%20error')%3B_ax.legend()%3B_ax.grid(alpha%3D.2)%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20The%20mean%20minimizes%20squared%20error%0A%0A%20%20%20%20-%20Slide%20the%20candidate%20center.%0A%20%20%20%20-%20The%20error%20curve%20is%20minimized%20at%20the%20sample%20mean.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E18%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Why%20assign%20to%20the%20nearest%20centroid%3F%0A%0A%20%20%20%20-%20Now%20hold%20centroid%20positions%20fixed.%0A%20%20%20%20-%20Each%20observation%20affects%20only%20its%20own%20distance%20term.%0A%20%20%20%20-%20Minimize%20independently%2C%20one%20point%20at%20a%20time.%0A%0A%20%20%20%20%24%24%5Cboxed%7Bc_i%5Cleftarrow%5Coperatorname*%7Barg%5C%2Cmin%7D_%7B1%5Cleq%20r%5Cleq%20k%7D%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_r%5C%7C%5E2%7D%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E19%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Lloyd%20algorithm%3A%20alternating%20updates%0A%0A%20%20%20%20-%201.%20Initialize%20%24k%24%20centroids.%0A%20%20%20%20-%202.%20Assignment%3A%20nearest%20centroid.%0A%20%20%20%20-%203.%20Update%3A%20arithmetic%20mean%20of%20each%20nonempty%20group.%0A%20%20%20%20-%204.%20Repeat%20until%20assignments%20stabilize.%0A%0A%20%20%20%20%24%24c_i%5Cleftarrow%5Carg%5Cmin_r%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_r%5C%7C%5E2%2C%5Cqquad%5Cboldsymbol%5Cmu_r%5Cleftarrow%5Cfrac1%7Bn_r%7D%5Csum_%7Bi%5Cin%20C_r%7D%5Cmathbf%20x_i%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E20%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_21_step%3Dmo.ui.slider(start%3D0%2Cstop%3D8%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%22Algorithm%20step%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_21_step%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_21_step%2C%20make_blobs%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_21_step%0A%20%20%20%20_X%2C_%3Dmake_blobs(n_samples%3D105%2Ccenters%3D%5B%5B-2.5%2C-.4%5D%2C%5B2%2C1%5D%5D%2Ccluster_std%3D%5B.8%2C.85%5D%2Crandom_state%3D6)%0A%20%20%20%20_C%3Dnp.array(%5B%5B-3.%2C2.5%5D%2C%5B.5%2C-1.8%5D%5D)%3B_lab%3Dnp.argmin(((_X%5B%3A%2CNone%2C%3A%5D-_C%5BNone%2C%3A%2C%3A%5D)**2).sum(2)%2Caxis%3D1)%0A%20%20%20%20_for%3Drange(control_21_step.value)%0A%20%20%20%20for%20_st%20in%20_for%3A%0A%20%20%20%20%20%20%20%20if%20_st%252%3D%3D0%3A_lab%3Dnp.argmin(((_X%5B%3A%2CNone%2C%3A%5D-_C%5BNone%2C%3A%2C%3A%5D)**2).sum(2)%2Caxis%3D1)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_r%20in%20range(2)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20np.any(_lab%3D%3D_r)%3A_C%5B_r%5D%3D_X%5B_lab%3D%3D_r%5D.mean(axis%3D0)%0A%20%20%20%20_J%3Dnp.sum((_X-_C%5B_lab%5D)**2)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3.7))%3B_ax.scatter(*_X.T%2Cc%3D_lab%2Ccmap%3D'coolwarm'%2Cs%3D25%2Calpha%3D.85)%3B_ax.scatter(*_C.T%2Cmarker%3D'X'%2Cs%3D200%2Cc%3D'black'%2Clabel%3D'Centroids')%3B_ax.legend(loc%3D'upper%20left')%3B_ax.set_xlim(-5%2C5)%3B_ax.set_ylim(-4%2C4)%3B_ax.set_aspect('equal')%3B_ax.set_title(f'Step%20%7Bcontrol_21_step.value%7D%20%C2%B7%20J%20%3D%20%7B_J%3A.1f%7D')%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20K-means%20animation%3A%20assignments%20and%20moving%20centroids%0A%0A%20%20%20%20-%20Advance%20through%20initialization%2C%20assignment%20and%20centroid%20updates.%0A%20%20%20%20-%20Watch%20the%20objective%20decrease%20as%20centers%20move.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E21%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Why%20does%20the%20objective%20never%20increase%3F%0A%0A%20%20%20%20-%20Assignment%20step%20minimizes%20%24J%24%20with%20centers%20fixed.%0A%20%20%20%20-%20Update%20step%20minimizes%20%24J%24%20with%20labels%20fixed.%0A%20%20%20%20-%20A%20decreasing%20cost%20does%20not%20guarantee%20a%20global%20optimum.%0A%0A%20%20%20%20%24%24J(%5Cmathbf%20c%5E%7B(t)%7D%2C%5Cboldsymbol%5Cmu%5E%7B(t)%7D)%5Cgeq%20J(%5Cmathbf%20c%5E%7B(t%2B1)%7D%2C%5Cboldsymbol%5Cmu%5E%7B(t)%7D)%5Cgeq%20J(%5Cmathbf%20c%5E%7B(t%2B1)%7D%2C%5Cboldsymbol%5Cmu%5E%7B(t%2B1)%7D)%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E22%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_23_stage%3Dmo.ui.slider(start%3D0%2Cstop%3D2%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%220%3A%20initialize%20%C2%B7%201%3A%20assign%20%C2%B7%202%3A%20update%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_23_stage%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_23_stage%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_23_stage%0A%20%20%20%20_points%3Dnp.array(%5B0%2C2%2C7%2C9%5D)%3B_means%3Dnp.array(%5B0%2C7%5D)%20if%20control_23_stage.value%3C2%20else%20np.array(%5B1%2C8%5D)%3B_lab%3Dnp.array(%5B0%2C0%2C1%2C1%5D)%3B_J%3Dsum((_points-_means%5B_lab%5D)**2)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3))%3B_ax.scatter(_points%2Cnp.zeros(4)%2Cc%3D_lab%2Ccmap%3D'coolwarm'%2Cs%3D120%2Czorder%3D3)%3B_ax.scatter(_means%2C%5B.2%2C.2%5D%2Cs%3D170%2Cmarker%3D'X'%2Cc%3D'black'%2Clabel%3D'Centroids')%3B_ax.set_yticks(%5B%5D)%3B_ax.set_ylim(-.35%2C.6)%3B_ax.set_xlim(-1%2C10)%3B_ax.set_xticks(range(10))%3B_ax.grid(axis%3D'x'%2Calpha%3D.2)%3B_ax.set_title(f'Step%20%7Bcontrol_23_stage.value%7D%20%C2%B7%20cost%20J%20%3D%20%7B_J%3Ag%7D')%3B_ax.legend()%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Worked%20example%3A%20four%20observations%0A%0A%20%20%20%20-%20Data%3A%20%240%2C2%2C7%2C9%24%3B%20initial%20centers%20%240%2C7%24.%0A%20%20%20%20-%20Assignment%20%E2%86%92%20groups%20%24(0%2C2)%24%20and%20%24(7%2C9)%24%3B%20update%20%E2%86%92%20means%20%241%2C8%24.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E23%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20control_24_k%3Dmo.ui.slider(start%3D1%2Cstop%3D4%2Cstep%3D1%2Cvalue%3D2%2Clabel%3D%22Number%20of%20clusters%20k%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_24_k%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_24_k%2C%20make_moons%2C%20mo%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_24_k%0A%20%20%20%20_X%2C_y%3Dmake_moons(n_samples%3D220%2Cnoise%3D.065%2Crandom_state%3D42)%0A%20%20%20%20from%20sklearn.cluster%20import%20KMeans%0A%20%20%20%20_lab%3DKMeans(n_clusters%3Dcontrol_24_k.value%2Cn_init%3D10%2Crandom_state%3D2).fit_predict(_X)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3.6))%3B_ax.scatter(*_X.T%2Cc%3D_lab%2Ccmap%3D'tab10'%2Cs%3D24)%3B_ax.set_aspect('equal')%3B_ax.set_title('K-means%20partitions%20of%20curved%20data')%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%5Bmo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Geometric%20limitation%3A%20two%20moons%0A%0A%20%20%20%20-%20K-means%20creates%20centroid-based%20regions%2C%20not%20curved%20chains.%0A%20%20%20%20-%20The%20two%20arcs%20are%20not%20necessarily%20recovered%20as%20separate%20groups.%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E24%20%2F%2025%3C%2Fdiv%3E%0A%20%20%20%20%22%22%22)%2C%20_controls%2C%20mo.as_html(_fig)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20K-means%3A%20takeaways%0A%0A%20%20%20%20-%20Fast%2C%20intuitive%3B%20compact%20center-based%20groups.%0A%20%20%20%20-%20Sensitive%20to%20scale%2C%20outliers%20and%20initialization.%0A%20%20%20%20-%20Each%20iteration%20reduces%20(or%20preserves)%20squared%20error.%0A%20%20%20%20-%20No%20guarantee%20of%20global%20optimum%3B%20elongated%20%2F%20curved%20groups%20may%20be%20difficult.%0A%0A%20%20%20%20%24%24%5Cboxed%7BJ%3D%5Csum_i%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_%7Bc_i%7D%5C%7C%5E2%5Cqquad%20J%5E%7B(t%2B1)%7D%5Cleq%20J%5E%7B(t)%7D%7D%24%24%0A%0A%20%20%20%20%3Cdiv%20style%3D%22position%3Afixed%3Bbottom%3A12px%3Bleft%3A16px%3Bfont-size%3A13px%3Bcolor%3A%23888%3Bfont-family%3Asystem-ui%2Csans-serif%3B%22%3E25%20%2F%2025%3C%2Fdiv%3E%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