import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20time%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20import%20plotly.graph_objects%20as%20go%0A%20%20%20%20from%20plotly.subplots%20import%20make_subplots%0A%20%20%20%20from%20scipy.cluster.hierarchy%20import%20cophenet%2C%20dendrogram%2C%20linkage%0A%20%20%20%20from%20scipy.spatial.distance%20import%20pdist%0A%20%20%20%20from%20sklearn.cluster%20import%20AgglomerativeClustering%0A%20%20%20%20from%20sklearn.datasets%20import%20make_blobs%2C%20make_moons%0A%20%20%20%20from%20sklearn.metrics%20import%20calinski_harabasz_score%2C%20silhouette_score%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20AgglomerativeClustering%2C%0A%20%20%20%20%20%20%20%20calinski_harabasz_score%2C%0A%20%20%20%20%20%20%20%20cophenet%2C%0A%20%20%20%20%20%20%20%20go%2C%0A%20%20%20%20%20%20%20%20linkage%2C%0A%20%20%20%20%20%20%20%20make_blobs%2C%0A%20%20%20%20%20%20%20%20make_moons%2C%0A%20%20%20%20%20%20%20%20make_subplots%2C%0A%20%20%20%20%20%20%20%20mo%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20pd%2C%0A%20%20%20%20%20%20%20%20pdist%2C%0A%20%20%20%20%20%20%20%20silhouette_score%2C%0A%20%20%20%20%20%20%20%20time%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%5B%E2%86%90%2035%20Gini%20Impurity%20vs%20Entropy%5D(35_gini_impurity_vs_entropy.py)%20%7C%20%5BIndex%5D(..%2Findex.html)%20%7C%20%5B37%20Natural%20Breaks%20%E2%86%92%5D(37_natural_breaks.py)%0A%0A%20%20%20%20%23%20Agglomerative%20Hierarchical%20Clustering%3A%20Linkage%20Criteria%2C%20Lance-Williams%20Recurrence%2C%20and%20Dendrogram%20Geometry%0A%0A%20%20%20%20%23%23%20%5Ba%5D%20Why%20do%20you%20need%20to%20know%20these%20concepts%3F%0A%0A%20%20%20%20Clustering%20algorithms%20partition%20unlabeled%20data%20into%20cohesive%20subgroups.%20While%20flat%20partitioning%20methods%20(such%20as%20%24k%24-means%20and%20Gaussian%20Mixture%20Models)%20require%20pre-specifying%20the%20number%20of%20clusters%20%24k%24%20and%20assume%20convex%2C%20isotropic%20cluster%20geometries%2C%20hierarchical%20agglomerative%20clustering%20constructs%20an%20entire%20hierarchy%20of%20nested%20groupings%20from%20the%20bottom%20up.%0A%0A%20%20%20%20%23%23%23%23%20The%20Role%20of%20Linkage%20in%20Determining%20Cluster%20Geometry%0A%20%20%20%20Agglomerative%20clustering%20starts%20with%20every%20observation%20as%20an%20individual%20singleton%20cluster%20and%20sequentially%20merges%20the%20closest%20pair%20of%20clusters.%20The%20core%20distinguishing%20factor%20between%20hierarchical%20clustering%20variants%20is%20the%20**linkage%20criterion**%2C%20which%20defines%20what%20distance%20between%20two%20sets%20of%20points%20means%3A%0A%20%20%20%20-%20**Single%20Linkage%20(Minimum%20Distance)**%3A%20Merges%20clusters%20based%20on%20their%20closest%20pair%20of%20points.%20It%20can%20uncover%20non-convex%20manifolds%20and%20concentric%20geometries%2C%20but%20is%20vulnerable%20to%20the%20**chaining%20effect**%2C%20where%20a%20single%20string%20of%20noise%20points%20merges%20two%20distinct%20clusters.%0A%20%20%20%20-%20**Complete%20Linkage%20(Maximum%20Distance)**%3A%20Merges%20clusters%20based%20on%20their%20most%20distant%20pair%20of%20points.%20It%20aggressively%20resists%20chaining%20and%20produces%20compact%2C%20equal-diameter%20clusters%2C%20but%20is%20sensitive%20to%20isolated%20outliers.%0A%20%20%20%20-%20**Average%20Linkage%20(UPGMA)**%3A%20Evaluates%20the%20average%20pairwise%20distance%20between%20all%20member%20points.%20It%20provides%20a%20balanced%2C%20robust%20trade-off%20and%20is%20widely%20used%20in%20computational%20biology%20and%20phylogenetics.%0A%20%20%20%20-%20**Ward's%20Linkage%20(Minimum%20Variance)**%3A%20Merges%20the%20pair%20of%20clusters%20that%20minimizes%20the%20increase%20in%20total%20within-cluster%20sum%20of%20squared%20errors.%20Like%20%24k%24-means%2C%20Ward's%20method%20seeks%20compact%2C%20spherical%20clusters%20with%20approximately%20equal%20sizes.%0A%0A%20%20%20%20%23%23%23%23%20The%20Lance-Williams%20Recurrence%3A%20%24O(1)%24%20Distance%20Updates%0A%20%20%20%20Naively%20recomputing%20all%20pairwise%20inter-cluster%20distances%20after%20every%20merge%20requires%20%24O(N%5E3)%24%20operations.%20The%20**Lance-Williams%20recurrence%20formula**%20enables%20updating%20the%20distance%20from%20a%20newly%20merged%20cluster%20to%20all%20other%20clusters%20in%20%24O(1)%24%20time%20using%20an%20exact%20parametric%20linear%20formula.%20This%20reduction%20makes%20hierarchical%20clustering%20computationally%20tractable%20for%20practical%20dataset%20sizes.%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%20%5Bb%5D%20Mathematical%20Foundations%20and%20Algorithmic%20Mechanics%0A%0A%20%20%20%20%23%23%23%201.%20The%20General%20Agglomerative%20Framework%0A%0A%20%20%20%20Let%20%24%5Cmathcal%7BD%7D%20%3D%20%5C%7Bx_1%2C%20x_2%2C%20%5Cdots%2C%20x_N%5C%7D%20%5Csubset%20%5Cmathbb%7BR%7D%5Ep%24%20be%20a%20collection%20of%20%24N%24%20observations.%0A%20%20%20%201.%20**Initialization**%3A%20Form%20%24N%24%20singleton%20clusters%20%24%5Cmathcal%7BC%7D_1%20%3D%20%5C%7Bx_1%5C%7D%2C%20%5Cdots%2C%20%5Cmathcal%7BC%7D_N%20%3D%20%5C%7Bx_N%5C%7D%24.%0A%20%20%20%202.%20**Iterative%20Merging**%3A%20At%20step%20%24t%24%2C%20identify%20the%20pair%20of%20clusters%20%24(A%2C%20B)%24%20satisfying%3A%0A%0A%20%20%20%20%24%24(A%2C%20B)%20%3D%20%5Carg%5Cmin_%7Bi%20%5Cneq%20j%7D%20D(%5Cmathcal%7BC%7D_i%2C%20%5Cmathcal%7BC%7D_j)%24%24%0A%0A%20%20%20%203.%20**Union**%3A%20Form%20the%20merged%20cluster%20%24%5Cmathcal%7BC%7D_%7B%5Ctext%7Bnew%7D%7D%20%3D%20A%20%5Ccup%20B%24%20and%20remove%20%24A%24%20and%20%24B%24%20from%20the%20active%20cluster%20list.%0A%20%20%20%204.%20**Distance%20Update**%3A%20Compute%20the%20distance%20%24D(%5Cmathcal%7BC%7D_%7B%5Ctext%7Bnew%7D%7D%2C%20K)%24%20for%20every%20remaining%20active%20cluster%20%24K%24.%0A%20%20%20%205.%20**Termination**%3A%20Repeat%20until%20all%20observations%20are%20merged%20into%20a%20single%20root%20cluster%20%24%5Cmathcal%7BC%7D_%7B%5Ctext%7Broot%7D%7D%20%3D%20%5Cmathcal%7BD%7D%24.%0A%0A%20%20%20%20%23%23%23%202.%20Formulations%20of%20Linkage%20Criteria%0A%0A%20%20%20%20Let%20%24A%24%20and%20%24B%24%20be%20two%20disjoint%20non-empty%20clusters%20with%20cardinalities%20%24%7CA%7C%24%20and%20%24%7CB%7C%24.%0A%0A%20%20%20%20%23%23%23%23%20Single%20Linkage%20(Nearest%20Neighbor)%0A%20%20%20%20%24%24D_%7B%5Ctext%7Bsingle%7D%7D(A%2C%20B)%20%3D%20%5Cmin_%7Bu%20%5Cin%20A%2C%20v%20%5Cin%20B%7D%20%5C%7Cu%20-%20v%5C%7C_2%24%24%0A%0A%20%20%20%20%23%23%23%23%20Complete%20Linkage%20(Furthest%20Neighbor)%0A%20%20%20%20%24%24D_%7B%5Ctext%7Bcomplete%7D%7D(A%2C%20B)%20%3D%20%5Cmax_%7Bu%20%5Cin%20A%2C%20v%20%5Cin%20B%7D%20%5C%7Cu%20-%20v%5C%7C_2%24%24%0A%0A%20%20%20%20%23%23%23%23%20Average%20Linkage%20(UPGMA)%0A%20%20%20%20%24%24D_%7B%5Ctext%7Baverage%7D%7D(A%2C%20B)%20%3D%20%5Cfrac%7B1%7D%7B%7CA%7C%20%7CB%7C%7D%20%5Csum_%7Bu%20%5Cin%20A%7D%20%5Csum_%7Bv%20%5Cin%20B%7D%20%5C%7Cu%20-%20v%5C%7C_2%24%24%0A%0A%20%20%20%20%23%23%23%23%20Ward's%20Minimum%20Variance%20Linkage%0A%20%20%20%20Let%20%24%5Cmu_A%20%3D%20%5Cfrac%7B1%7D%7B%7CA%7C%7D%5Csum_%7Bu%20%5Cin%20A%7D%20u%24%20denote%20the%20centroid%20of%20cluster%20%24A%24.%20The%20sum%20of%20squared%20errors%20within%20cluster%20%24A%24%20is%3A%0A%0A%20%20%20%20%24%24%5Ctext%7BSSE%7D(A)%20%3D%20%5Csum_%7Bu%20%5Cin%20A%7D%20%5C%7Cu%20-%20%5Cmu_A%5C%7C_2%5E2%24%24%0A%0A%20%20%20%20Ward's%20criterion%20selects%20the%20pair%20of%20clusters%20that%20minimizes%20the%20increase%20in%20total%20variance%20%24%5CDelta%20%5Ctext%7BSSE%7D(A%2C%20B)%20%3D%20%5Ctext%7BSSE%7D(A%20%5Ccup%20B)%20-%20%5Ctext%7BSSE%7D(A)%20-%20%5Ctext%7BSSE%7D(B)%24.%20Applying%20Huygens'%20parallel%20axis%20theorem%20yields%3A%0A%0A%20%20%20%20%24%24%5CDelta%20%5Ctext%7BSSE%7D(A%2C%20B)%20%3D%20%5Cfrac%7B%7CA%7C%20%7CB%7C%7D%7B%7CA%7C%20%2B%20%7CB%7C%7D%20%5C%7C%5Cmu_A%20-%20%5Cmu_B%5C%7C_2%5E2%24%24%0A%0A%20%20%20%20Ward's%20distance%20metric%20is%20defined%20as%20%24D_%7B%5Ctext%7BWard%7D%7D(A%2C%20B)%20%3D%20%5Csqrt%7B2%20%5CDelta%20%5Ctext%7BSSE%7D(A%2C%20B)%7D%24.%0A%0A%20%20%20%20%23%23%23%203.%20The%20Lance-Williams%20Recurrence%20Formula%0A%0A%20%20%20%20When%20clusters%20%24A%24%20and%20%24B%24%20are%20merged%20into%20%24A%20%5Ccup%20B%24%2C%20the%20distance%20between%20%24A%20%5Ccup%20B%24%20and%20any%20external%20cluster%20%24K%24%20can%20be%20computed%20from%20known%20pairwise%20distances%20%24D(A%2C%20K)%24%2C%20%24D(B%2C%20K)%24%2C%20and%20%24D(A%2C%20B)%24%20using%3A%0A%0A%20%20%20%20%24%24D(A%20%5Ccup%20B%2C%20K)%20%3D%20%5Calpha_A%20D(A%2C%20K)%20%2B%20%5Calpha_B%20D(B%2C%20K)%20%2B%20%5Cbeta%20D(A%2C%20B)%20%2B%20%5Cgamma%20%7CD(A%2C%20K)%20-%20D(B%2C%20K)%7C%24%24%0A%0A%20%20%20%20The%20parameters%20%24%5Calpha_A%2C%20%5Calpha_B%2C%20%5Cbeta%2C%20%5Cgamma%24%20for%20the%20four%20primary%20linkages%20are%3A%0A%0A%20%20%20%20-%20**Single**%3A%20%24%5Calpha_A%20%3D%20%5Cfrac%7B1%7D%7B2%7D%2C%20%5Calpha_B%20%3D%20%5Cfrac%7B1%7D%7B2%7D%2C%20%5Cbeta%20%3D%200%2C%20%5Cgamma%20%3D%20-%5Cfrac%7B1%7D%7B2%7D%24%0A%20%20%20%20-%20**Complete**%3A%20%24%5Calpha_A%20%3D%20%5Cfrac%7B1%7D%7B2%7D%2C%20%5Calpha_B%20%3D%20%5Cfrac%7B1%7D%7B2%7D%2C%20%5Cbeta%20%3D%200%2C%20%5Cgamma%20%3D%20%5Cfrac%7B1%7D%7B2%7D%24%0A%20%20%20%20-%20**Average**%3A%20%24%5Calpha_A%20%3D%20%5Cfrac%7B%7CA%7C%7D%7B%7CA%7C%20%2B%20%7CB%7C%7D%2C%20%5Calpha_B%20%3D%20%5Cfrac%7B%7CB%7C%7D%7B%7CA%7C%20%2B%20%7CB%7C%7D%2C%20%5Cbeta%20%3D%200%2C%20%5Cgamma%20%3D%200%24%0A%20%20%20%20-%20**Ward**%3A%20%24%5Calpha_A%20%3D%20%5Cfrac%7B%7CA%7C%20%2B%20%7CK%7C%7D%7B%7CA%7C%20%2B%20%7CB%7C%20%2B%20%7CK%7C%7D%2C%20%5Calpha_B%20%3D%20%5Cfrac%7B%7CB%7C%20%2B%20%7CK%7C%7D%7B%7CA%7C%20%2B%20%7CB%7C%20%2B%20%7CK%7C%7D%2C%20%5Cbeta%20%3D%20-%5Cfrac%7B%7CK%7C%7D%7B%7CA%7C%20%2B%20%7CB%7C%20%2B%20%7CK%7C%7D%2C%20%5Cgamma%20%3D%200%24%0A%0A%20%20%20%20%23%23%23%204.%20Cophenetic%20Correlation%20Coefficient%0A%0A%20%20%20%20The%20dendrogram%20represents%20hierarchical%20tree%20distances.%20The%20**cophenetic%20distance**%20%24t_%7Bij%7D%24%20between%20observations%20%24x_i%24%20and%20%24x_j%24%20is%20defined%20as%20the%20height%20in%20the%20dendrogram%20where%20clusters%20containing%20%24x_i%24%20and%20%24x_j%24%20first%20merge.%20The%20cophenetic%20correlation%20coefficient%20%24c%24%20measures%20the%20Pearson%20correlation%20between%20true%20Euclidean%20distances%20%24d_%7Bij%7D%20%3D%20%5C%7Cx_i%20-%20x_j%5C%7C_2%24%20and%20dendrogram%20cophenetic%20distances%20%24t_%7Bij%7D%24%3A%0A%0A%20%20%20%20%24%24c%20%3D%20%5Cfrac%7B%5Csum_%7Bi%20%3C%20j%7D%20(d_%7Bij%7D%20-%20%5Cbar%7Bd%7D)(t_%7Bij%7D%20-%20%5Cbar%7Bt%7D)%7D%7B%5Csqrt%7B%5Csum_%7Bi%20%3C%20j%7D%20(d_%7Bij%7D%20-%20%5Cbar%7Bd%7D)%5E2%20%5Csum_%7Bi%20%3C%20j%7D%20(t_%7Bij%7D%20-%20%5Cbar%7Bt%7D)%5E2%7D%7D%24%24%0A%0A%20%20%20%20A%20cophenetic%20correlation%20closer%20to%20%241.0%24%20indicates%20that%20the%20dendrogram%20faithfully%20preserves%20original%20metric%20distances.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(make_blobs%2C%20make_moons%2C%20np)%3A%0A%20%20%20%20np.random.seed(42)%0A%0A%20%20%20%20%23%201.%20Dataset%20with%20bridging%20noise%20to%20illustrate%20Single%20Linkage%20chaining%20vs%20Ward%2FComplete%0A%20%20%20%20blob_pts%2C%20_%20%3D%20make_blobs(%0A%20%20%20%20%20%20%20%20n_samples%3D%5B80%2C%2080%5D%2C%0A%20%20%20%20%20%20%20%20centers%3D%5B%5B-3.0%2C%200.0%5D%2C%20%5B3.0%2C%200.0%5D%5D%2C%0A%20%20%20%20%20%20%20%20cluster_std%3D0.7%2C%0A%20%20%20%20%20%20%20%20random_state%3D42%2C%0A%20%20%20%20)%0A%20%20%20%20%23%20Bridge%20of%206%20noise%20points%20connecting%20the%20two%20blobs%0A%20%20%20%20bridge_x%20%3D%20np.linspace(-1.5%2C%201.5%2C%206)%0A%20%20%20%20bridge_y%20%3D%20np.random.normal(0.0%2C%200.1%2C%206)%0A%20%20%20%20bridge_pts%20%3D%20np.column_stack(%5Bbridge_x%2C%20bridge_y%5D)%0A%20%20%20%20chaining_data%20%3D%20np.vstack(%5Bblob_pts%2C%20bridge_pts%5D)%0A%0A%20%20%20%20%23%202.%20Non-convex%20Two%20Moons%20dataset%0A%20%20%20%20moons_data%2C%20_%20%3D%20make_moons(n_samples%3D160%2C%20noise%3D0.08%2C%20random_state%3D42)%0A%20%20%20%20return%20chaining_data%2C%20moons_data%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20AgglomerativeClustering%2C%0A%20%20%20%20chaining_data%2C%0A%20%20%20%20go%2C%0A%20%20%20%20make_subplots%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20moons_data%2C%0A)%3A%0A%20%20%20%20%23%20Fit%20Single%2C%20Complete%2C%20Average%2C%20and%20Ward%20on%20Chaining%20Data%0A%20%20%20%20cluster_ward%20%3D%20AgglomerativeClustering(n_clusters%3D2%2C%20linkage%3D%22ward%22).fit_predict(%0A%20%20%20%20%20%20%20%20chaining_data%0A%20%20%20%20)%0A%20%20%20%20cluster_single%20%3D%20AgglomerativeClustering(n_clusters%3D2%2C%20linkage%3D%22single%22).fit_predict(%0A%20%20%20%20%20%20%20%20chaining_data%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Fit%20Single%20and%20Ward%20on%20Two%20Moons%20Data%0A%20%20%20%20moon_single%20%3D%20AgglomerativeClustering(n_clusters%3D2%2C%20linkage%3D%22single%22).fit_predict(moons_data)%0A%20%20%20%20moon_ward%20%3D%20AgglomerativeClustering(n_clusters%3D2%2C%20linkage%3D%22ward%22).fit_predict(moons_data)%0A%0A%20%20%20%20fig%20%3D%20make_subplots(%0A%20%20%20%20%20%20%20%20rows%3D2%2C%0A%20%20%20%20%20%20%20%20cols%3D2%2C%0A%20%20%20%20%20%20%20%20subplot_titles%3D%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%3Cb%3EWard%20Linkage%20on%20Chaining%20Data%20(Compact%20Partitions)%3C%2Fb%3E%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%3Cb%3ESingle%20Linkage%20on%20Chaining%20Data%20(Chaining%20Vulnerability)%3C%2Fb%3E%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%3Cb%3EWard%20Linkage%20on%20Two%20Moons%20(Fails%20Non-Convex%20Shape)%3C%2Fb%3E%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%3Cb%3ESingle%20Linkage%20on%20Two%20Moons%20(Recovers%20Non-Convex%20Shape)%3C%2Fb%3E%22%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20horizontal_spacing%3D0.10%2C%0A%20%20%20%20%20%20%20%20vertical_spacing%3D0.14%2C%0A%20%20%20%20)%0A%0A%20%20%20%20color_map%20%3D%20%7B0%3A%20%22%232563EB%22%2C%201%3A%20%22%23DC2626%22%7D%0A%0A%20%20%20%20%23%20Top-Left%3A%20Ward%20on%20Chaining%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dchaining_data%5B%3A%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dchaining_data%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22markers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%5Bcolor_map%5Bc%5D%20for%20c%20in%20cluster_ward%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20size%3D7%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20opacity%3D0.85%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DFalse%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Top-Right%3A%20Single%20on%20Chaining%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dchaining_data%5B%3A%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dchaining_data%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22markers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%5Bcolor_map%5Bc%5D%20for%20c%20in%20cluster_single%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20size%3D7%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20opacity%3D0.85%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DFalse%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D2%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Bottom-Left%3A%20Ward%20on%20Moons%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dmoons_data%5B%3A%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dmoons_data%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22markers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%5Bcolor_map%5Bc%5D%20for%20c%20in%20moon_ward%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20size%3D7%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20opacity%3D0.85%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DFalse%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D2%2C%0A%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Bottom-Right%3A%20Single%20on%20Moons%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dmoons_data%5B%3A%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dmoons_data%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22markers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%5Bcolor_map%5Bc%5D%20for%20c%20in%20moon_single%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20size%3D7%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20opacity%3D0.85%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DFalse%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D2%2C%0A%20%20%20%20%20%20%20%20col%3D2%2C%0A%20%20%20%20)%0A%0A%20%20%20%20fig.update_layout(%0A%20%20%20%20%20%20%20%20template%3D%22plotly_white%22%2C%0A%20%20%20%20%20%20%20%20height%3D620%2C%0A%20%20%20%20%20%20%20%20margin%3Ddict(l%3D40%2C%20r%3D40%2C%20t%3D60%2C%20b%3D40)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20viz%20%3D%20mo.ui.plotly(fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20AgglomerativeClustering%2C%0A%20%20%20%20calinski_harabasz_score%2C%0A%20%20%20%20chaining_data%2C%0A%20%20%20%20cophenet%2C%0A%20%20%20%20linkage%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20pd%2C%0A%20%20%20%20pdist%2C%0A%20%20%20%20silhouette_score%2C%0A%20%20%20%20time%2C%0A)%3A%0A%20%20%20%20%23%20Example%201%3A%20Verification%20of%20Lance-Williams%20Recurrence%20against%20Exact%20Pairwise%20Computation%0A%20%20%20%20pts_A%20%3D%20np.array(%5B%5B0.0%2C%200.0%5D%2C%20%5B0.0%2C%201.0%5D%5D)%0A%20%20%20%20pts_B%20%3D%20np.array(%5B%5B1.0%2C%200.0%5D%2C%20%5B1.0%2C%201.0%5D%5D)%0A%20%20%20%20pts_K%20%3D%20np.array(%5B%5B3.0%2C%200.0%5D%2C%20%5B3.0%2C%202.0%5D%2C%20%5B4.0%2C%201.0%5D%5D)%0A%0A%20%20%20%20pts_AB%20%3D%20np.vstack(%5Bpts_A%2C%20pts_B%5D)%0A%0A%20%20%20%20%23%20Direct%20average%20distance%0A%20%20%20%20direct_avg_dist%20%3D%20np.mean(%0A%20%20%20%20%20%20%20%20%5Bnp.linalg.norm(u%20-%20v)%20for%20u%20in%20pts_AB%20for%20v%20in%20pts_K%5D%0A%20%20%20%20)%0A%20%20%20%20dist_AK%20%3D%20np.mean(%5Bnp.linalg.norm(u%20-%20v)%20for%20u%20in%20pts_A%20for%20v%20in%20pts_K%5D)%0A%20%20%20%20dist_BK%20%3D%20np.mean(%5Bnp.linalg.norm(u%20-%20v)%20for%20u%20in%20pts_B%20for%20v%20in%20pts_K%5D)%0A%0A%20%20%20%20%23%20Lance-Williams%20for%20Average%20Linkage%3A%20(%7CA%7C%20*%20d(A%2CK)%20%2B%20%7CB%7C%20*%20d(B%2CK))%20%2F%20(%7CA%7C%20%2B%20%7CB%7C)%0A%20%20%20%20lw_avg_dist%20%3D%20(len(pts_A)%20*%20dist_AK%20%2B%20len(pts_B)%20*%20dist_BK)%20%2F%20(len(pts_A)%20%2B%20len(pts_B))%0A%0A%20%20%20%20df_lw_verif%20%3D%20pd.DataFrame(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Linkage_Criterion%22%3A%20%22Average%20(UPGMA)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Direct_Pairwise_Calculation%22%3A%20round(direct_avg_dist%2C%206)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Lance_Williams_Recurrence%22%3A%20round(lw_avg_dist%2C%206)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Difference%22%3A%20round(abs(direct_avg_dist%20-%20lw_avg_dist)%2C%2010)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Update_Speedup%22%3A%20%22O(1)%20vs%20O(%7CA%7C%7CB%7C%7CK%7C)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Example%202%3A%20Cophenetic%20Correlation%20Analysis%20across%20Linkages%0A%20%20%20%20pairwise_distances%20%3D%20pdist(chaining_data)%0A%20%20%20%20linkage_types%20%3D%20%5B%22ward%22%2C%20%22complete%22%2C%20%22average%22%2C%20%22single%22%5D%0A%20%20%20%20cophenet_records%20%3D%20%5B%5D%0A%0A%20%20%20%20for%20l_type%20in%20linkage_types%3A%0A%20%20%20%20%20%20%20%20z_matrix%20%3D%20linkage(chaining_data%2C%20method%3Dl_type)%0A%20%20%20%20%20%20%20%20c_score%2C%20_%20%3D%20cophenet(z_matrix%2C%20pairwise_distances)%0A%20%20%20%20%20%20%20%20cophenet_records.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Linkage%22%3A%20l_type.capitalize()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Cophenetic_Correlation%22%3A%20round(c_score%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Preservation_Quality%22%3A%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22High%20(Faithfully%20retains%20pairwise%20metric%20distances)%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20c_score%20%3E%200.8%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20%22Moderate%20(Imposes%20strong%20geometric%20deformation)%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20df_cophenet%20%3D%20pd.DataFrame(cophenet_records)%0A%0A%20%20%20%20%23%20Example%203%3A%20Comparative%20Performance%20Benchmark%20across%20Linkages%0A%20%20%20%20benchmark_records%20%3D%20%5B%5D%0A%20%20%20%20n_benchmark_runs%20%3D%2050%0A%0A%20%20%20%20for%20l_type%20in%20linkage_types%3A%0A%20%20%20%20%20%20%20%20t0%20%3D%20time.perf_counter()%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(n_benchmark_runs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20model%20%3D%20AgglomerativeClustering(n_clusters%3D2%2C%20linkage%3Dl_type)%0A%20%20%20%20%20%20%20%20%20%20%20%20labels%20%3D%20model.fit_predict(chaining_data)%0A%20%20%20%20%20%20%20%20elapsed_ms%20%3D%20(time.perf_counter()%20-%20t0)%20*%201000%20%2F%20n_benchmark_runs%0A%0A%20%20%20%20%20%20%20%20%23%20Evaluate%20quality%20metrics%0A%20%20%20%20%20%20%20%20if%20len(np.unique(labels))%20%3E%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20sil%20%3D%20silhouette_score(chaining_data%2C%20labels)%0A%20%20%20%20%20%20%20%20%20%20%20%20ch%20%3D%20calinski_harabasz_score(chaining_data%2C%20labels)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20sil%2C%20ch%20%3D%200.0%2C%200.0%0A%0A%20%20%20%20%20%20%20%20benchmark_records.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Linkage%22%3A%20l_type.capitalize()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Execution_Time_ms%22%3A%20round(elapsed_ms%2C%203)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Silhouette_Score%22%3A%20round(sil%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Calinski_Harabasz_Index%22%3A%20round(ch%2C%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Cluster_Sizes%22%3A%20str(list(np.bincount(labels)))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20df_benchmark%20%3D%20pd.DataFrame(benchmark_records)%0A%0A%20%20%20%20table_lw%20%3D%20mo.ui.table(df_lw_verif)%0A%20%20%20%20table_coph%20%3D%20mo.ui.table(df_cophenet)%0A%20%20%20%20table_bench%20%3D%20mo.ui.table(df_benchmark)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%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
07128562de1af6d306bde9223933729e