clustering lezione 2

%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_2.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%2CewogICJ0eXBlIjogInNsaWRlcyIsCiAgImRhdGEiOiB7CiAgICAiY2VsbHMiOiBbCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2tpcCIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNraXAiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2tpcCIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2tpcCIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNraXAiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2tpcCIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNraXAiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJza2lwIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHsKICAgICAgICAidHlwZSI6ICJzbGlkZSIKICAgICAgfSwKICAgICAgewogICAgICAgICJ0eXBlIjogInNsaWRlIgogICAgICB9LAogICAgICB7CiAgICAgICAgInR5cGUiOiAic2xpZGUiCiAgICAgIH0sCiAgICAgIHt9CiAgICBdLAogICAgImRlY2siOiB7fQogIH0KfQ%3D%3D%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%20dendrogram%2C%20linkage%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%23%20Clustering%20II%0A%0A%20%20%20%20-%20Sequential%20clustering%3A%20BSAS%20and%20incremental%20mean.%0A%20%20%20%20-%20Hierarchical%20clustering%3A%20linkage%20and%20dendrogram.%0A%20%20%20%20-%20Ward%3A%20the%20connection%20to%20k-means.%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%2024%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%20batch%20to%20sequential%0A%0A%20%20%20%20-%20K-means%20repeatedly%20reconsiders%20all%20data.%0A%20%20%20%20-%20Sequential%20algorithms%20read%20one%20point%20at%20a%20time.%0A%20%20%20%20-%20Each%20new%20point%20is%20assigned%20immediately%20or%20starts%20a%20new%20group.%0A%20%20%20%20-%20Earlier%20decisions%20can%20influence%20later%20ones.%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%2024%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_3_s%3Dmo.ui.slider(start%3D0%2Cstop%3D4%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%22Advance%20both%20algorithms%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_3_s%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_3_s%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_3_s%0A%20%20%20%20_seq%3D%5B%5B%5B0%5D%5D%2C%5B%5B0%2C1%5D%5D%2C%5B%5B0%2C1%5D%2C%5B2%5D%5D%2C%5B%5B0%2C1%5D%2C%5B2%2C3%5D%5D%2C%5B%5B0%2C1%2C4%5D%2C%5B2%2C3%5D%5D%5D%0A%20%20%20%20_hier%3D%5B%5B%5B0%5D%2C%5B1%5D%2C%5B2%5D%2C%5B3%5D%2C%5B4%5D%5D%2C%5B%5B0%2C1%5D%2C%5B2%5D%2C%5B3%5D%2C%5B4%5D%5D%2C%5B%5B0%2C1%5D%2C%5B2%2C3%5D%2C%5B4%5D%5D%2C%5B%5B0%2C1%5D%2C%5B2%2C3%2C4%5D%5D%2C%5B%5B0%2C1%2C2%2C3%2C4%5D%5D%5D%0A%20%20%20%20_x%3Dnp.array(%5B0.%2C1.%2C6.%2C7.%2C2.%5D)%3B_fig%2C_axs%3Dplt.subplots(1%2C2%2Cfigsize%3D(10%2C3.2)%2Csharex%3DTrue%2Csharey%3DTrue)%0A%20%20%20%20for%20_ax%2C_groups%2C_title%20in%20zip(_axs%2C%5B_seq%5Bcontrol_3_s.value%5D%2C_hier%5Bcontrol_3_s.value%5D%5D%2C%5B'Sequential%20%C2%B7%20points%20arrive'%2C'Hierarchical%20%C2%B7%20clusters%20merge'%5D)%3A%0A%20%20%20%20%20%20%20%20for%20_r%2C_group%20in%20enumerate(_groups)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_idx%20in%20_group%3A_ax.scatter(_x%5B_idx%5D%2C0%2Cc%3Df'C%7B_r%2510%7D'%2Cs%3D140%2Czorder%3D4)%3B_ax.annotate('ABCDE'%5B_idx%5D%2C(_x%5B_idx%5D%2C0)%2Ctextcoords%3D'offset%20points'%2Cxytext%3D(0%2C12)%2Cha%3D'center')%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(_group)%3E1%3A_ax.plot(_x%5B_group%5D%2C%5B0%5D*len(_group)%2Clw%3D5%2Calpha%3D.2%2Ccolor%3Df'C%7B_r%2510%7D')%0A%20%20%20%20%20%20%20%20_ax.set_title(_title)%3B_ax.set_xlim(-1%2C9)%3B_ax.set_ylim(-1%2C1)%3B_ax.set_yticks(%5B%5D)%3B_ax.grid(axis%3D'x'%2Calpha%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%20Animated%20comparison%3A%20sequential%20vs%20agglomerative%0A%0A%20%20%20%20-%20Left%3A%20a%20new%20point%20arrives%20and%20joins%20a%20group%20or%20creates%20one.%0A%20%20%20%20-%20Right%3A%20all%20points%20exist%20from%20the%20start%3B%20groups%20are%20merged.%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%2024%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%20BSAS%3A%20parameters%20and%20state%0A%0A%20%20%20%20-%20Distance%20threshold%20%24%5Ctheta%3E0%24.%0A%20%20%20%20-%20Maximum%20number%20of%20clusters%20%24q_%7B%5Cmax%7D%24.%0A%20%20%20%20-%20Current%20clusters%3A%20%24q%5Cleq%20q_%7B%5Cmax%7D%24%20and%20centroids%20%24%5Cboldsymbol%5Cmu_1%2C%5Cldots%2C%5Cboldsymbol%5Cmu_q%24.%0A%0A%20%20%20%20%24%24%5Ctheta%3E0%2C%5Cqquad%20q%5Cleq%20q_%7B%5Cmax%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%3E4%20%2F%2024%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%20BSAS%3A%20assignment%20rule%0A%0A%20%20%20%20-%20First%20point%20forms%20the%20first%20cluster.%0A%20%20%20%20-%20Find%20nearest%20existing%20center%20and%20its%20distance%20%24%5Cdelta_i%24.%0A%20%20%20%20-%20If%20too%20far%20and%20room%20remains%2C%20create%20a%20new%20group.%0A%20%20%20%20-%20Otherwise%2C%20assign%20to%20nearest%20group%20and%20update%20its%20mean.%0A%0A%20%20%20%20%24%24r%5E*%3D%5Carg%5Cmin_%7B1%5Cleq%20r%5Cleq%20q%7D%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_r%5C%7C%2C%5Cquad%5Cdelta_i%3D%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_%7Br%5E*%7D%5C%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%3E5%20%2F%2024%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_6_s%3Dmo.ui.slider(start%3D1%2Cstop%3D4%2Cstep%3D1%2Cvalue%3D1%2Clabel%3D%22Points%20received%22%2Cshow_value%3DTrue)%0A%20%20%20%20control_6_theta%3Dmo.ui.slider(start%3D.5%2Cstop%3D4.%2Cstep%3D.5%2Cvalue%3D2.5%2Clabel%3D%22Threshold%20%CE%B8%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20control_6_s%2C%20control_6_theta%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_6_s%2C%20control_6_theta%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dmo.hstack(%5Bcontrol_6_s%2Ccontrol_6_theta%5D)%0A%20%20%20%20_points%3D%5B0.%2C2.%2C3.%2C4.%5D%3B_clusters%3D%5B%5D%0A%20%20%20%20for%20_v%20in%20_points%5B%3Acontrol_6_s.value%5D%3A%0A%20%20%20%20%20%20%20%20if%20not%20_clusters%3A_clusters%3D%5B%5B_v%5D%5D%3Bcontinue%0A%20%20%20%20%20%20%20%20_centers%3Dnp.array(%5Bnp.mean(_c)%20for%20_c%20in%20_clusters%5D)%3B_j%3Dint(np.argmin(abs(_centers-_v)))%0A%20%20%20%20%20%20%20%20if%20abs(_centers%5B_j%5D-_v)%3Econtrol_6_theta.value%20and%20len(_clusters)%3C4%3A_clusters.append(%5B_v%5D)%0A%20%20%20%20%20%20%20%20else%3A_clusters%5B_j%5D.append(_v)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3.1))%0A%20%20%20%20for%20_r%2C_group%20in%20enumerate(_clusters)%3A_ax.scatter(_group%2C%5B0%5D*len(_group)%2Cs%3D140%2Ccolor%3Df'C%7B_r%7D'%2Clabel%3Df'Cluster%20%7B_r%2B1%7D%2C%20%CE%BC%3D%7Bnp.mean(_group)%3A.2f%7D')%3B_ax.scatter(np.mean(_group)%2C.27%2Cmarker%3D'X'%2Cs%3D120%2Ccolor%3Df'C%7B_r%7D')%0A%20%20%20%20_ax.set_xlim(-1%2C5)%3B_ax.set_ylim(-.4%2C.75)%3B_ax.set_yticks(%5B%5D)%3B_ax.set_xticks(range(5))%3B_ax.set_title(f'%7Blen(_clusters)%7D%20cluster(s)%20after%20%7Bcontrol_6_s.value%7D%20observations')%3B_ax.grid(axis%3D'x'%2Calpha%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%20BSAS%3A%20one%20point%20at%20a%20time%0A%0A%20%20%20%20-%20Data%20arrive%20in%20the%20order%20%240%2C2%2C3%2C4%24.%0A%20%20%20%20-%20Change%20the%20threshold%20and%20advance%20one%20observation%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%2024%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%20Incremental%20centroid%3A%20no%20need%20to%20reread%20data%0A%0A%20%20%20%20-%20Suppose%20a%20group%20contains%20%24n_r%24%20points%20and%20has%20mean%20%24%5Cboldsymbol%5Cmu_r%24.%0A%20%20%20%20-%20Add%20one%20observation%20%24%5Cmathbf%20x_i%24.%0A%20%20%20%20-%20The%20new%20mean%20uses%20only%20old%20mean%2C%20count%20and%20new%20point.%0A%0A%20%20%20%20%24%24%5Cboxed%7B%5Cboldsymbol%5Cmu_r%5E%7B%5Cmathrm%7Bnew%7D%7D%3D%5Cfrac%7Bn_r%5Cboldsymbol%5Cmu_r%2B%5Cmathbf%20x_i%7D%7Bn_r%2B1%7D%3D%5Cboldsymbol%5Cmu_r%2B%5Cfrac%7B%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_r%7D%7Bn_r%2B1%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%3E7%20%2F%2024%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%3D2%2Clabel%3D%22Observations%20received%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_data%3Dnp.array(%5B0.%2C2.%2C3.%2C4.%2C3.%2C4.%5D)%3B_mean%3Dnp.mean(_data%5B%3Acontrol_8_s.value%5D)%3B_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3))%0A%20%20%20%20_ax.scatter(_data%5B%3Acontrol_8_s.value%5D%2Cnp.zeros(control_8_s.value)%2Cs%3D110%2Czorder%3D3)%3B_ax.scatter(%5B_mean%5D%2C%5B.24%5D%2Cmarker%3D'X'%2Cc%3D'black'%2Cs%3D160%2Clabel%3Df'Mean%20%3D%20%7B_mean%3A.2f%7D')%3B_ax.set_xlim(-1%2C5)%3B_ax.set_ylim(-.45%2C.7)%3B_ax.set_yticks(%5B%5D)%3B_ax.set_xticks(range(5))%3B_ax.grid(axis%3D'x'%2Calpha%3D.2)%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%20Incremental%20mean%3A%20the%20centroid%20moves%0A%0A%20%20%20%20-%20Add%20points%20to%20the%20same%20group.%0A%20%20%20%20-%20The%20influence%20of%20each%20additional%20point%20becomes%20smaller%20as%20%24n%24%20grows.%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%2024%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_9_s%3Dmo.ui.slider(start%3D1%2Cstop%3D4%2Cstep%3D1%2Cvalue%3D1%2Clabel%3D%22Observations%20received%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_9_s%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_9_s%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_9_s%0A%20%20%20%20_orders%3D%5B%5B0.%2C2.%2C3.%2C4.%5D%2C%5B0.%2C4.%2C2.%2C3.%5D%5D%3B_fig%2C_axs%3Dplt.subplots(1%2C2%2Cfigsize%3D(10%2C3)%2Csharex%3DTrue%2Csharey%3DTrue)%0A%20%20%20%20for%20_ax%2C_points%2C_name%20in%20zip(_axs%2C_orders%2C%5B'Order%3A%200%2C%202%2C%203%2C%204'%2C'Order%3A%200%2C%204%2C%202%2C%203'%5D)%3A%0A%20%20%20%20%20%20%20%20_clusters%3D%5B%5D%0A%20%20%20%20%20%20%20%20for%20_v%20in%20_points%5B%3Acontrol_9_s.value%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20_clusters%3A_clusters%3D%5B%5B_v%5D%5D%3Bcontinue%0A%20%20%20%20%20%20%20%20%20%20%20%20_centers%3Dnp.array(%5Bnp.mean(_c)%20for%20_c%20in%20_clusters%5D)%3B_r%3Dint(np.argmin(abs(_centers-_v)))%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20abs(_centers%5B_r%5D-_v)%3E2.5%20and%20len(_clusters)%3C3%3A_clusters.append(%5B_v%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A_clusters%5B_r%5D.append(_v)%0A%20%20%20%20%20%20%20%20for%20_r%2C_group%20in%20enumerate(_clusters)%3A_ax.scatter(_group%2C%5B0%5D*len(_group)%2Ccolor%3Df'C%7B_r%7D'%2Cs%3D120)%3B_ax.scatter(%5Bnp.mean(_group)%5D%2C%5B.3%5D%2Cmarker%3D'X'%2Ccolor%3Df'C%7B_r%7D'%2Cs%3D120)%0A%20%20%20%20%20%20%20%20_ax.set_title(f'%7B_name%7D%20%C2%B7%20%7Blen(_clusters)%7D%20cluster(s)')%3B_ax.set_xlim(-1%2C5)%3B_ax.set_ylim(-.4%2C.8)%3B_ax.set_yticks(%5B%5D)%3B_ax.grid(axis%3D'x'%2Calpha%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%20BSAS%3A%20same%20observations%2C%20different%20order%0A%0A%20%20%20%20-%20Compare%20%240%2C2%2C3%2C4%24%20against%20%240%2C4%2C2%2C3%24.%0A%20%20%20%20-%20With%20%24%5Ctheta%3D2.5%24%2C%20one%20order%20produces%20one%20cluster%2C%20the%20other%20two.%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%2024%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%20Sequential%20variants%3A%20the%20idea%0A%0A%20%20%20%20-%20MBSAS%3A%20separate%20seed-selection%20from%20final%20assignment.%0A%20%20%20%20-%20TTSAS%3A%20two%20thresholds%3B%20defer%20ambiguous%20decisions.%0A%20%20%20%20-%20Order%20dependence%20is%20reduced%20in%20some%20variants%2C%20not%20universally%20eliminated.%0A%0A%20%20%20%20%24%240%3C%5Ctheta_1%3C%5Ctheta_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%3E10%20%2F%2024%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%20Hierarchical%20clustering%3A%20why%20a%20hierarchy%3F%0A%0A%20%20%20%20-%20Rather%20than%20commit%20immediately%20to%20a%20single%20partition%2C%20build%20nested%20partitions.%0A%20%20%20%20-%20Agglomerative%3A%20begin%20with%20%24N%24%20singleton%20clusters.%0A%20%20%20%20-%20At%20each%20step%2C%20merge%20the%20two%20closest%20clusters.%0A%20%20%20%20-%20Merges%20are%20irreversible.%0A%0A%20%20%20%20%24%24N%5Clongrightarrow%20N-1%5Clongrightarrow%5Ccdots%5Clongrightarrow%202%5Clongrightarrow1%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%3E11%20%2F%2024%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_12_s%3Dmo.ui.slider(start%3D0%2Cstop%3D3%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%22Number%20of%20merges%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_12_s%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_12_s%2C%20mo%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_12_s%0A%20%20%20%20_groups%3D%5B%5B%5B0%5D%2C%5B2%5D%2C%5B3%5D%2C%5B10%5D%5D%2C%5B%5B0%5D%2C%5B2%2C3%5D%2C%5B10%5D%5D%2C%5B%5B0%2C2%2C3%5D%2C%5B10%5D%5D%2C%5B%5B0%2C2%2C3%2C10%5D%5D%5D%5Bcontrol_12_s.value%5D%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3))%0A%20%20%20%20for%20_i%2C_group%20in%20enumerate(_groups)%3A_ax.scatter(_group%2C%5B0%5D*len(_group)%2Cs%3D135%2Ccolor%3Df'C%7B_i%7D')%3B_ax.plot(%5Bmin(_group)%2Cmax(_group)%5D%2C%5B.1%2C.1%5D%2Clw%3D5%2Ccolor%3Df'C%7B_i%7D'%2Calpha%3D.6)%0A%20%20%20%20_ax.set_xlim(-1%2C11)%3B_ax.set_ylim(-.5%2C.8)%3B_ax.set_xticks(%5B0%2C2%2C3%2C10%5D)%3B_ax.set_yticks(%5B%5D)%3B_ax.grid(axis%3D'x'%2Calpha%3D.2)%3B_ax.set_title(f'%7Blen(_groups)%7D%20cluster(s)%20%C2%B7%20%7Bcontrol_12_s.value%7D%20merge(s)')%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%20Hierarchical%20merging%3A%20watch%20every%20fusion%0A%0A%20%20%20%20-%20All%20four%20observations%20exist%20from%20the%20beginning.%0A%20%20%20%20-%20Each%20step%20fuses%20two%20clusters%3B%20none%20is%20created%20by%20arriving%20data.%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%2024%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%20What%20is%20linkage%3F%0A%0A%20%20%20%20-%20Distance%20between%20points%20is%20not%20distance%20between%20sets.%0A%20%20%20%20-%20Single%3A%20closest%20cross-cluster%20pair.%0A%20%20%20%20-%20Complete%3A%20farthest%20cross-cluster%20pair.%0A%20%20%20%20-%20Average%3A%20mean%20over%20all%20cross-cluster%20pairs.%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7DD_%7B%5Cmathrm%7Bsingle%7D%7D(A%2CB)%26%3D%5Cmin_%7Bi%5Cin%20A%2Cj%5Cin%20B%7Dd(%5Cmathbf%20x_i%2C%5Cmathbf%20x_j)%5C%5C%20D_%7B%5Cmathrm%7Bcomplete%7D%7D(A%2CB)%26%3D%5Cmax_%7Bi%5Cin%20A%2Cj%5Cin%20B%7Dd(%5Cmathbf%20x_i%2C%5Cmathbf%20x_j)%5Cend%7Baligned%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%3E13%20%2F%2024%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_14_mode%3Dmo.ui.slider(start%3D0%2Cstop%3D2%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%220%3A%20single%20%C2%B7%201%3A%20complete%20%C2%B7%202%3A%20average%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_14_mode%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_14_mode%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_14_mode%0A%20%20%20%20_A%3Dnp.array(%5B0.%2C2.%5D)%3B_B%3Dnp.array(%5B3.%2C10.%5D)%3B_pairs%3D%5B(float(abs(_a-_b))%2C_a%2C_b)%20for%20_a%20in%20_A%20for%20_b%20in%20_B%5D%3B_sel%3Dsorted(_pairs%2Ckey%3Dlambda%20z%3Az%5B0%5D)%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3))%0A%20%20%20%20for%20_v%20in%20_A%3A_ax.scatter(_v%2C0%2Cs%3D110%2Ccolor%3D'tab%3Ablue')%0A%20%20%20%20for%20_v%20in%20_B%3A_ax.scatter(_v%2C.9%2Cs%3D110%2Ccolor%3D'tab%3Aorange')%0A%20%20%20%20for%20_d%2C_a%2C_b%20in%20_pairs%3A%0A%20%20%20%20%20%20%20%20if%20control_14_mode.value%3D%3D2%3A_ax.plot(%5B_a%2C_b%5D%2C%5B0%2C.9%5D%2Ccolor%3D'gray'%2Calpha%3D.5)%0A%20%20%20%20if%20control_14_mode.value%3C2%3A%0A%20%20%20%20%20%20%20%20_d%2C_a%2C_b%3D_sel%5B0%5D%20if%20control_14_mode.value%3D%3D0%20else%20_sel%5B-1%5D%0A%20%20%20%20%20%20%20%20_ax.plot(%5B_a%2C_b%5D%2C%5B0%2C.9%5D%2Clw%3D3%2Ccolor%3D'black')%0A%20%20%20%20else%3A_d%3Dnp.mean(%5B_p%5B0%5D%20for%20_p%20in%20_pairs%5D)%0A%20%20%20%20_ax.set_xlim(-1%2C11)%3B_ax.set_ylim(-.4%2C1.5)%3B_ax.set_yticks(%5B0%2C.9%5D%2C%5B'A'%2C'B'%5D)%3B_ax.set_xticks(%5B0%2C2%2C3%2C10%5D)%3B_ax.grid(axis%3D'x'%2Calpha%3D.2)%3B_ax.set_title(f'%7B%5B%22Single%22%2C%20%22Complete%22%2C%20%22Average%22%5D%5Bcontrol_14_mode.value%5D%7D%20linkage%20distance%20%3D%20%7B_d%3A.2f%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%20Linkage%20animation%3A%20nearest%20%2F%20farthest%20%2F%20average%0A%0A%20%20%20%20-%20Two%20existing%20groups%2C%20four%20cross-group%20distances.%0A%20%20%20%20-%20The%20definition%20of%20inter-cluster%20proximity%20changes%20with%20linkage.%0A%0A%20%20%20%20%24%24D_%7B%5Cmathrm%7Baverage%7D%7D(A%2CB)%3D%5Cfrac1%7B%7CA%7C%7CB%7C%7D%5Csum_%7Bi%5Cin%20A%7D%5Csum_%7Bj%5Cin%20B%7Dd(%5Cmathbf%20x_i%2C%5Cmathbf%20x_j)%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%3E14%20%2F%2024%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%20Agglomerative%20algorithm%0A%0A%20%20%20%20-%20Initialize%20%24%5Cmathcal%20P%5E%7B(0)%7D%24%20with%20%24N%24%20singleton%20sets.%0A%20%20%20%20-%20Compute%20inter-cluster%20linkage%20distances.%0A%20%20%20%20-%20Merge%20the%20pair%20with%20smallest%20linkage%20distance.%0A%20%20%20%20-%20Repeat%20until%20the%20desired%20number%20of%20clusters%20(or%20one).%0A%0A%20%20%20%20%24%24(A%5E*%2CB%5E*)%3D%5Coperatorname*%7Barg%5C%2Cmin%7D_%7BA%5Cneq%20B%7DD_%7B%5Cmathrm%7Blinkage%7D%7D(A%2CB)%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%2024%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_mode%3Dmo.ui.slider(start%3D0%2Cstop%3D2%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%220%3A%20single%20%C2%B7%201%3A%20complete%20%C2%B7%202%3A%20average%22%2Cshow_value%3DTrue)%0A%20%20%20%20control_16_cut%3Dmo.ui.slider(start%3D1%2Cstop%3D10%2Cstep%3D1%2Cvalue%3D5%2Clabel%3D%22Cut%20height%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20control_16_cut%2C%20control_16_mode%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_16_cut%2C%20control_16_mode%2C%20dendrogram%2C%20linkage%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dmo.hstack(%5Bcontrol_16_mode%2Ccontrol_16_cut%5D)%0A%20%20%20%20_X%3Dnp.array(%5B%5B0.%5D%2C%5B2.%5D%2C%5B3.%5D%2C%5B10.%5D%5D)%0A%20%20%20%20_Z%3Dlinkage(_X%2Cmethod%3D%5B'single'%2C'complete'%2C'average'%5D%5Bcontrol_16_mode.value%5D%2Cmetric%3D'euclidean')%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3.8))%3Bdendrogram(_Z%2Clabels%3D%5B'0'%2C'2'%2C'3'%2C'10'%5D%2Cax%3D_ax%2Ccolor_threshold%3D0%2Cabove_threshold_color%3D'tab%3Ablue')%3B_ax.axhline(control_16_cut.value%2Cls%3D'--'%2Ccolor%3D'tab%3Ared'%2Clabel%3D'Cut')%3B_ax.set_title(%5B'Single'%2C'Complete'%2C'Average'%5D%5Bcontrol_16_mode.value%5D%2B'%20linkage%20dendrogram')%3B_ax.set_ylabel('Linkage%20distance')%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%20Dendrogram%3A%20four%20points%2C%20three%20linkage%20choices%0A%0A%20%20%20%20-%20The%20same%20merges%20can%20occur%20at%20different%20heights.%0A%20%20%20%20-%20Cut%20the%20tree%20to%20obtain%20a%20chosen%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%3E16%20%2F%2024%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%20Worked%20example%3A%20dendrogram%20heights%0A%0A%20%20%20%20-%20Observations%20on%20a%20line%3A%20%240%2C2%2C3%2C10%24.%0A%20%20%20%20-%20First%20merge%3A%20%242%24%20and%20%243%24%20at%20distance%20%241%24.%0A%20%20%20%20-%20Second%20merge%3A%20%240%24%20with%20%24%5C%7B2%2C3%5C%7D%24.%0A%20%20%20%20-%20Final%20merge%20with%20%2410%24%3A%20heights%20depend%20on%20linkage.%0A%0A%20%20%20%20%24%24%5Cbegin%7Barray%7D%7Bc%7Cccc%7D%26%5Ctext%7Bsingle%7D%26%5Ctext%7Bcomplete%7D%26%5Ctext%7Baverage%7D%5C%5C%20%5Ctext%7Bsecond%20merge%7D%262%263%262.5%5C%5C%20%5Ctext%7Blast%20merge%7D%267%2610%2625%2F3%5Cend%7Barray%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%2024%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_mode%3Dmo.ui.slider(start%3D0%2Cstop%3D1%2Cstep%3D1%2Cvalue%3D0%2Clabel%3D%220%3A%20single%20%C2%B7%201%3A%20complete%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20(control_18_mode%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_18_mode%2C%20linkage%2C%20make_moons%2C%20mo%2C%20plt)%3A%0A%20%20%20%20_controls%3Dcontrol_18_mode%0A%20%20%20%20_X%2C_y%3Dmake_moons(n_samples%3D120%2Cnoise%3D.045%2Crandom_state%3D7)%0A%20%20%20%20from%20scipy.cluster.hierarchy%20import%20fcluster%0A%20%20%20%20_Z%3Dlinkage(_X%2Cmethod%3D%5B'single'%2C'complete'%5D%5Bcontrol_18_mode.value%5D)%3B_lab%3Dfcluster(_Z%2C2%2Ccriterion%3D'maxclust')%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3.5))%3B_ax.scatter(*_X.T%2Cc%3D_lab%2Ccmap%3D'coolwarm'%2Cs%3D28)%3B_ax.set_aspect('equal')%3B_ax.set_title(%5B'Single%20linkage'%2C'Complete%20linkage'%5D%5Bcontrol_18_mode.value%5D%2B'%20%C2%B7%20two%20clusters')%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%20Two%20moons%3A%20single%20vs%20complete%20linkage%0A%0A%20%20%20%20-%20Single%20linkage%20can%20connect%20a%20curved%20chain.%0A%20%20%20%20-%20Complete%20linkage%20tends%20to%20favor%20tighter%2C%20smaller-diameter%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%3E18%20%2F%2024%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%20Ward%3A%20connect%20hierarchy%20to%20k-means%0A%0A%20%20%20%20-%20Instead%20of%20closest%20%2F%20farthest%20pair%2C%20measure%20the%20increase%20in%20squared%20within-cluster%20error.%0A%20%20%20%20-%20Merge%20the%20pair%20producing%20the%20smallest%20increase.%0A%20%20%20%20-%20Same%20squared-error%20idea%2C%20but%20merges%20are%20irreversible.%0A%0A%20%20%20%20%24%24S(A)%3D%5Csum_%7Bi%5Cin%20A%7D%5C%7C%5Cmathbf%20x_i-%5Cboldsymbol%5Cmu_A%5C%7C%5E2%2C%5Cqquad%20%5CDelta(A%2CB)%3DS(A%5Ccup%20B)-S(A)-S(B)%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%2024%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%20Ward%3A%20final%20formula%20(derive%20on%20the%20board)%0A%0A%20%20%20%20-%20Write%20the%20mean%20of%20the%20union.%0A%20%20%20%20-%20Expand%20squared%20distances%20around%20the%20two%20old%20means.%0A%20%20%20%20-%20Cross-terms%20vanish%20because%20deviations%20sum%20to%20zero.%0A%0A%20%20%20%20%24%24%5Cboxed%7B%5CDelta(A%2CB)%3D%5Cfrac%7Bn_A%20n_B%7D%7Bn_A%2Bn_B%7D%5C%7C%5Cboldsymbol%5Cmu_A-%5Cboldsymbol%5Cmu_B%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%3E20%20%2F%2024%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_n%3Dmo.ui.slider(start%3D1%2Cstop%3D15%2Cstep%3D1%2Cvalue%3D2%2Clabel%3D%22Number%20of%20points%20in%20A%22%2Cshow_value%3DTrue)%0A%20%20%20%20control_21_dist%3Dmo.ui.slider(start%3D1%2Cstop%3D5%2Cstep%3D1%2Cvalue%3D2%2Clabel%3D%22Centroid%20separation%22%2Cshow_value%3DTrue)%0A%20%20%20%20return%20control_21_dist%2C%20control_21_n%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(control_21_dist%2C%20control_21_n%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_controls%3Dmo.hstack(%5Bcontrol_21_n%2Ccontrol_21_dist%5D)%0A%20%20%20%20_nb%3D3%3B_delta%3D(control_21_n.value*_nb%2F(control_21_n.value%2B_nb))*control_21_dist.value**2%0A%20%20%20%20_t%3Dnp.arange(1%2C16)%3B_y%3D_t*_nb%2F(_t%2B_nb)*control_21_dist.value**2%0A%20%20%20%20_fig%2C_ax%3Dplt.subplots(figsize%3D(8%2C3.4))%3B_ax.plot(_t%2C_y)%3B_ax.scatter(%5Bcontrol_21_n.value%5D%2C%5B_delta%5D%2Cs%3D120%2Czorder%3D3)%3B_ax.set_xlabel('Size%20of%20group%20A')%3B_ax.set_ylabel('Ward%20increment%20%CE%94')%3B_ax.set_title(f'nB%20%3D%203%20%C2%B7%20separation%20%3D%20%7Bcontrol_21_dist.value%7D%20%C2%B7%20%CE%94%20%3D%20%7B_delta%3A.2f%7D')%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%20Ward%3A%20distance%20and%20cluster%20sizes%20both%20matter%0A%0A%20%20%20%20-%20Fix%20centroid%20separation%20and%20change%20the%20size%20of%20cluster%20A.%0A%20%20%20%20-%20Ward%20weighs%20squared%20separation%20by%20group%20sizes.%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%2024%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%20Ward%20vs%20k-means%0A%0A%20%20%20%20-%20K-means%3A%20reassign%20observations%20and%20update%20centroids%20repeatedly.%0A%20%20%20%20-%20Ward%3A%20merge%20entire%20groups%3B%20cannot%20undo%20past%20merges.%0A%20%20%20%20-%20Both%20are%20built%20around%20within-cluster%20squared%20errors.%0A%0A%20%20%20%20%24%24J_%7B%5Cmathrm%7Bkmeans%7D%7D%3D%5Csum_r%20S(C_r)%2C%5Cqquad%5Ctext%7BWard%3A%20choose%20%7D%5Carg%5Cmin_%7BA%2CB%7D%5CDelta(A%2CB)%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%2024%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%20Summary%3A%20no%20universal%20clustering%20algorithm%0A%0A%20%20%20%20-%20K-means%3A%20compactness%20around%20centers.%0A%20%20%20%20-%20Sequential%20BSAS%3A%20decisions%20upon%20arrival%3B%20order%20matters.%0A%20%20%20%20-%20Hierarchical%3A%20nested%20structure%20via%20irreversible%20merges.%0A%20%20%20%20-%20Single%20%2F%20complete%20%2F%20average%20%2F%20Ward%20express%20different%20notions%20of%20group.%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%2024%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%20Final%20takeaway%0A%0A%20%20%20%20-%20Start%20with%20the%20meaning%20of%20proximity.%0A%20%20%20%20-%20Then%20choose%20what%20a%20cluster%20should%20represent.%0A%20%20%20%20-%20Only%20then%20choose%20the%20algorithm.%0A%0A%20%20%20%20%24%24%5Ctext%7Bproximity%7D%5C%3B%5Clongrightarrow%5C%3B%5Ctext%7Bcluster%20notion%7D%5C%3B%5Clongrightarrow%5C%3B%5Ctext%7Balgorithm%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%3E24%20%2F%2024%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