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%20jenkspy%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%0A%20%20%20%20return%20go%2C%20jenkspy%2C%20make_subplots%2C%20mo%2C%20np%2C%20pd%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%2036%20Agglomerative%20Clustering%5D(36_agglomerative_clustering.py)%20%7C%20%5BIndex%5D(..%2Findex.html)%20%7C%20%5B38%20Oversampling%20%E2%86%92%5D(38_oversampling.py)%0A%0A%20%20%20%20%23%20Jenks%20Natural%20Breaks%3A%20Fisher-Jenks%201D%20Optimal%20Partitioning%20and%20Goodness%20of%20Variance%20Fit%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%20Continuous%20variables%20frequently%20require%20discretization%20into%20discrete%20intervals%20for%20thematic%20choropleth%20mapping%2C%20credit%20risk%20scorecards%2C%20medical%20diagnostic%20tiers%2C%20and%20decision%20rule%20induction.%20In%20practice%2C%20practitioners%20often%20reach%20for%20naive%20heuristics%20such%20as%3A%0A%20%20%20%20-%20**Equal%20Interval%20Discretization**%3A%20Divides%20the%20range%20%24%5Bx_%7B%5Cmin%7D%2C%20x_%7B%5Cmax%7D%5D%24%20into%20bins%20of%20equal%20width.%20When%20data%20is%20skewed%2C%20heavy-tailed%2C%20or%20multimodal%2C%20this%20results%20in%20multiple%20nearly%20empty%20bins%20and%20clumps%20the%20vast%20majority%20of%20observations%20into%20a%20single%20bin.%0A%20%20%20%20-%20**Quantile%20(Equal%20Frequency)%20Discretization**%3A%20Places%20an%20equal%20count%20of%20observations%20into%20every%20bin.%20While%20it%20guarantees%20populated%20classes%2C%20it%20artificially%20fractures%20tight%20natural%20clusters%20across%20arbitrary%20boundaries%20and%20groups%20wildly%20distant%20values%20together%20in%20sparse%20tail%20regions.%0A%0A%20%20%20%20%23%23%23%23%20The%20Fisher-Jenks%20Global%20Optimization%0A%20%20%20%20Formulated%20by%20cartographer%20George%20Jenks%20and%20statistician%20Walter%20D.%20Fisher%2C%20**Jenks%20Natural%20Breaks**%20treats%20discretization%20as%20a%20formal%20one-dimensional%20variance%20minimization%20problem.%20It%20identifies%20class%20boundaries%20that%20simultaneously%20minimize%20variance%20within%20each%20class%20while%20maximizing%20variance%20between%20classes.%0A%0A%20%20%20%20%23%23%23%23%20Global%20Optimality%20via%201D%20Dynamic%20Programming%0A%20%20%20%20In%20multi-dimensional%20spaces%2C%20finding%20variance-minimizing%20partitions%20(%24k%24-means)%20is%20known%20to%20be%20NP-hard.%20Multi-dimensional%20heuristic%20algorithms%20can%20easily%20become%20trapped%20in%20poor%20local%20optima.%20In%20one%20dimension%2C%20however%2C%20sorting%20the%20data%20imposes%20an%20exact%20ordering%20constraint%3A%20optimal%20clusters%20must%20be%20contiguous%20slices%20of%20the%20sorted%20array.%20By%20leveraging%20this%20ordering%20property%2C%20the%20Fisher-Jenks%20algorithm%20employs%20**Dynamic%20Programming**%20to%20find%20the%20provably%20**global%20minimum-variance%20partition**%20in%20polynomial%20time.%0A%0A%20%20%20%20%23%23%23%23%20Measuring%20Partition%20Quality%3A%20Goodness%20of%20Variance%20Fit%20(GVF)%0A%20%20%20%20Just%20as%20%24R%5E2%24%20measures%20explained%20variance%20in%20linear%20regression%2C%20the%20**Goodness%20of%20Variance%20Fit%20(GVF)**%20measures%20the%20fraction%20of%20total%20variance%20explained%20by%20the%20classification.%20Plotting%20GVF%20across%20different%20values%20of%20%24k%24%20provides%20an%20exact%20mathematical%20elbow%20criterion%20to%20choose%20the%20optimal%20number%20of%20bins.%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%20Dynamic%20Programming%20Mechanics%0A%0A%20%20%20%20%23%23%23%201.%20Variance%20Decomposition%3A%20SDAM%20and%20SDCM%0A%0A%20%20%20%20Let%20a%20sorted%20one-dimensional%20dataset%20be%20denoted%20by%3A%0A%0A%20%20%20%20%24%24x_1%20%5Cle%20x_2%20%5Cle%20%5Cdots%20%5Cle%20x_n%24%24%0A%0A%20%20%20%20The%20overall%20sample%20mean%20is%20%24%5Cbar%7Bx%7D%20%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Csum_%7Bi%3D1%7D%5En%20x_i%24.%20The%20**Sum%20of%20Squared%20Deviations%20from%20the%20Array%20Mean%20(SDAM)**%20represents%20the%20total%20baseline%20variance%3A%0A%0A%20%20%20%20%24%24%5Ctext%7BSDAM%7D%20%3D%20%5Csum_%7Bi%3D1%7D%5En%20(x_i%20-%20%5Cbar%7Bx%7D)%5E2%24%24%0A%0A%20%20%20%20Suppose%20the%20array%20is%20partitioned%20into%20%24k%24%20contiguous%20classes%20%24C_1%2C%20C_2%2C%20%5Cdots%2C%20C_k%24%2C%20defined%20by%20partition%20boundary%20indices%20%240%20%3D%20s_0%20%3C%20s_1%20%3C%20s_2%20%3C%20%5Cdots%20%3C%20s_k%20%3D%20n%24%2C%20such%20that%20class%20%24C_j%24%20contains%20elements%20%24%5C%7Bx_%7Bs_%7Bj-1%7D%2B1%7D%2C%20%5Cdots%2C%20x_%7Bs_j%7D%5C%7D%24.%0A%0A%20%20%20%20The%20mean%20of%20class%20%24C_j%24%20is%3A%0A%0A%20%20%20%20%24%24%5Cbar%7Bx%7D_j%20%3D%20%5Cfrac%7B1%7D%7B%7CC_j%7C%7D%20%5Csum_%7Bi%20%5Cin%20C_j%7D%20x_i%24%24%0A%0A%20%20%20%20The%20**Sum%20of%20Squared%20Deviations%20from%20Class%20Means%20(SDCM)**%20(or%20Within-Class%20Sum%20of%20Squares)%20is%3A%0A%0A%20%20%20%20%24%24%5Ctext%7BSDCM%7D%20%3D%20%5Csum_%7Bj%3D1%7D%5Ek%20%5Csum_%7Bi%20%5Cin%20C_j%7D%20(x_i%20-%20%5Cbar%7Bx%7D_j)%5E2%24%24%0A%0A%20%20%20%20By%20the%20Law%20of%20Total%20Variance%2C%20total%20sum%20of%20squares%20decomposes%20into%20within-class%20and%20between-class%20components%3A%0A%0A%20%20%20%20%24%24%5Ctext%7BSDAM%7D%20%3D%20%5Ctext%7BSDCM%7D%20%2B%20%5Ctext%7BSSB%7D%2C%20%5Cquad%20%5Ctext%7Bwhere%20%7D%20%5Ctext%7BSSB%7D%20%3D%20%5Csum_%7Bj%3D1%7D%5Ek%20%7CC_j%7C%20(%5Cbar%7Bx%7D_j%20-%20%5Cbar%7Bx%7D)%5E2%24%24%0A%0A%20%20%20%20Minimizing%20SDCM%20is%20strictly%20equivalent%20to%20maximizing%20between-class%20variance%20SSB.%0A%0A%20%20%20%20%23%23%23%202.%20Goodness%20of%20Variance%20Fit%20(GVF)%0A%0A%20%20%20%20The%20Goodness%20of%20Variance%20Fit%20measures%20the%20proportion%20of%20variance%20explained%20by%20the%20%24k%24%20classes%3A%0A%0A%20%20%20%20%24%24%5Ctext%7BGVF%7D%20%3D%20%5Cfrac%7B%5Ctext%7BSDAM%7D%20-%20%5Ctext%7BSDCM%7D%7D%7B%5Ctext%7BSDAM%7D%7D%20%3D%201%20-%20%5Cfrac%7B%5Ctext%7BSDCM%7D%7D%7B%5Ctext%7BSDAM%7D%7D%24%24%0A%0A%20%20%20%20Properties%20of%20GVF%3A%0A%20%20%20%20-%20%24%5Ctext%7BGVF%7D%20%5Cin%20%5B0%2C%201%5D%24.%0A%20%20%20%20-%20%24%5Ctext%7BGVF%7D%20%3D%200%24%20when%20%24k%20%3D%201%24%20(all%20points%20in%20a%20single%20class%2C%20%24%5Ctext%7BSDCM%7D%20%3D%20%5Ctext%7BSDAM%7D%24).%0A%20%20%20%20-%20%24%5Ctext%7BGVF%7D%20%3D%201%24%20when%20%24k%20%3D%20n%24%20(each%20point%20is%20its%20own%20class%2C%20%24%5Ctext%7BSDCM%7D%20%3D%200%24).%0A%20%20%20%20-%20The%20optimal%20number%20of%20classes%20%24k%5E*%24%20is%20typically%20selected%20at%20the%20elbow%20of%20the%20GVF%20curve%2C%20where%20marginal%20increase%20drops%20below%20a%20desired%20threshold%20(often%20targeting%20%24%5Ctext%7BGVF%7D%20%5Cge%200.85%24%20or%20%240.90%24).%0A%0A%20%20%20%20%23%23%23%203.%20The%20Fisher%20Dynamic%20Programming%20Recurrence%0A%0A%20%20%20%20Let%20%24D(i%2C%20j)%24%20denote%20the%20sum%20of%20squared%20deviations%20of%20the%20subarray%20%24x%5Bi%20%5Cdots%20j%5D%24%20from%20its%20local%20mean%3A%0A%0A%20%20%20%20%24%24D(i%2C%20j)%20%3D%20%5Csum_%7Bm%3Di%7D%5Ej%20%5Cleft(x_m%20-%20%5Cbar%7Bx%7D_%7Bi%3Aj%7D%5Cright)%5E2%20%3D%20%5Csum_%7Bm%3Di%7D%5Ej%20x_m%5E2%20-%20%5Cfrac%7B1%7D%7Bj%20-%20i%20%2B%201%7D%20%5Cleft(%20%5Csum_%7Bm%3Di%7D%5Ej%20x_m%20%5Cright)%5E2%24%24%0A%0A%20%20%20%20Let%20%24V(c%2C%20m)%24%20be%20the%20minimal%20SDCM%20achievable%20by%20partitioning%20the%20prefix%20%24x%5B1%20%5Cdots%20m%5D%24%20into%20%24c%24%20classes.%0A%0A%20%20%20%20**Base%20Case%20(%24c%20%3D%201%24)**%3A%0A%20%20%20%20%24%24V(1%2C%20m)%20%3D%20D(1%2C%20m)%20%5Cquad%20%5Ctext%7Bfor%20%7D%201%20%5Cle%20m%20%5Cle%20n%24%24%0A%0A%20%20%20%20**Recurrence%20Relation%20(%24c%20%5Cge%202%24)**%3A%0A%20%20%20%20%24%24V(c%2C%20m)%20%3D%20%5Cmin_%7Bc-1%20%5Cle%20p%20%3C%20m%7D%20%5Cleft%5C%7B%20V(c%20-%201%2C%20p)%20%2B%20D(p%20%2B%201%2C%20m)%20%5Cright%5C%7D%24%24%0A%0A%20%20%20%20Here%2C%20%24p%24%20represents%20the%20candidate%20boundary%20index%20where%20the%20%24(c-1)%24-th%20class%20ends%2C%20and%20the%20%24c%24-th%20class%20spans%20%24x%5Bp%2B1%20%5Cdots%20m%5D%24.%20By%20recording%20the%20optimal%20split%20index%20%24P%5E*(c%2C%20m)%20%3D%20%5Carg%5Cmin_p%20%5C%7B%5Cdots%5C%7D%24%2C%20the%20globally%20optimal%20class%20boundaries%20are%20reconstructed%20via%20standard%20backward%20backtracking%20from%20%24P%5E*(k%2C%20n)%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(jenkspy%2C%20np)%3A%0A%20%20%20%20np.random.seed(42)%0A%0A%20%20%20%20%23%20Generate%20synthetic%20multimodal%20distribution%20simulating%20real-world%20vulnerability%20%2F%20risk%20scores%0A%20%20%20%20%23%20Three%20distinct%20natural%20clusters%20with%20unequal%20densities%0A%20%20%20%20c1%20%3D%20np.random.normal(loc%3D2.2%2C%20scale%3D0.45%2C%20size%3D150)%0A%20%20%20%20c2%20%3D%20np.random.normal(loc%3D5.8%2C%20scale%3D0.60%2C%20size%3D220)%0A%20%20%20%20c3%20%3D%20np.random.normal(loc%3D9.4%2C%20scale%3D0.50%2C%20size%3D130)%0A%0A%20%20%20%20raw_scores%20%3D%20np.concatenate(%5Bc1%2C%20c2%2C%20c3%5D)%0A%20%20%20%20raw_scores%20%3D%20np.sort(raw_scores%5Braw_scores%20%3E%200%5D)%0A%20%20%20%20n_pts%20%3D%20len(raw_scores)%0A%0A%20%20%20%20%23%20Target%20number%20of%20classes%0A%20%20%20%20k_classes%20%3D%203%0A%0A%20%20%20%20%23%201.%20Jenks%20Natural%20Breaks%0A%20%20%20%20jenks_cutoffs%20%3D%20np.array(jenkspy.jenks_breaks(raw_scores%2C%20n_classes%3Dk_classes))%0A%0A%20%20%20%20%23%202.%20Equal%20Interval%20Breaks%0A%20%20%20%20min_v%2C%20max_v%20%3D%20raw_scores.min()%2C%20raw_scores.max()%0A%20%20%20%20equal_interval_cutoffs%20%3D%20np.linspace(min_v%2C%20max_v%2C%20k_classes%20%2B%201)%0A%0A%20%20%20%20%23%203.%20Quantile%20(Equal%20Count)%20Breaks%0A%20%20%20%20quantile_probs%20%3D%20np.linspace(0.0%2C%201.0%2C%20k_classes%20%2B%201)%0A%20%20%20%20quantile_cutoffs%20%3D%20np.quantile(raw_scores%2C%20quantile_probs)%0A%0A%20%20%20%20%23%20Compute%20GVF%20across%20k%20from%201%20to%207%20for%20the%20elbow%20scree%20plot%0A%20%20%20%20gvf_values%20%3D%20%5B%5D%0A%20%20%20%20sdam%20%3D%20np.sum((raw_scores%20-%20np.mean(raw_scores))%20**%202)%0A%0A%20%20%20%20for%20k%20in%20range(1%2C%208)%3A%0A%20%20%20%20%20%20%20%20if%20k%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20gvf_values.append(0.0)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20b%20%3D%20jenkspy.jenks_breaks(raw_scores%2C%20n_classes%3Dk)%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Compute%20SDCM%0A%20%20%20%20%20%20%20%20%20%20%20%20sdcm_k%20%3D%200.0%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(k)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sub%20%3D%20raw_scores%5B(raw_scores%20%3E%3D%20b%5Bj%5D)%20%26%20(raw_scores%20%3C%3D%20b%5Bj%20%2B%201%5D)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20len(sub)%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sdcm_k%20%2B%3D%20np.sum((sub%20-%20np.mean(sub))%20**%202)%0A%20%20%20%20%20%20%20%20%20%20%20%20gvf_k%20%3D%201.0%20-%20(sdcm_k%20%2F%20sdam)%0A%20%20%20%20%20%20%20%20%20%20%20%20gvf_values.append(max(0.0%2C%20min(1.0%2C%20gvf_k)))%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20equal_interval_cutoffs%2C%0A%20%20%20%20%20%20%20%20gvf_values%2C%0A%20%20%20%20%20%20%20%20jenks_cutoffs%2C%0A%20%20%20%20%20%20%20%20quantile_cutoffs%2C%0A%20%20%20%20%20%20%20%20raw_scores%2C%0A%20%20%20%20%20%20%20%20sdam%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20equal_interval_cutoffs%2C%0A%20%20%20%20go%2C%0A%20%20%20%20gvf_values%2C%0A%20%20%20%20jenks_cutoffs%2C%0A%20%20%20%20make_subplots%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20quantile_cutoffs%2C%0A%20%20%20%20raw_scores%2C%0A)%3A%0A%20%20%20%20fig%20%3D%20make_subplots(%0A%20%20%20%20%20%20%20%20rows%3D1%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%3EPartition%20Boundaries%20on%20Multimodal%20Distribution%3C%2Fb%3E%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%3Cb%3EGoodness%20of%20Variance%20Fit%20(GVF)%20vs%20Number%20of%20Classes%20k%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.12%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Left%3A%20Histogram%20of%20data%20with%20vertical%20cutoffs%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Histogram(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Draw_scores%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20nbinsx%3D45%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker_color%3D%22%2394A3B8%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20opacity%3D0.65%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Observed%20Distribution%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DTrue%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%20Add%20Jenks%20breaks%20(excluding%20min%20and%20max%20endpoints)%0A%20%20%20%20for%20idx%2C%20j_val%20in%20enumerate(jenks_cutoffs%5B1%3A-1%5D)%3A%0A%20%20%20%20%20%20%20%20fig.add_vline(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dj_val%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%2310B981%22%2C%20width%3D2.5%2C%20dash%3D%22solid%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20annotation_text%3Df%22Jenks%20%7Bidx%2B1%7D%3A%20%7Bj_val%3A.2f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20annotation_position%3D%22top%20right%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20Add%20Equal%20Interval%20breaks%0A%20%20%20%20for%20idx%2C%20e_val%20in%20enumerate(equal_interval_cutoffs%5B1%3A-1%5D)%3A%0A%20%20%20%20%20%20%20%20fig.add_vline(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3De_val%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23F59E0B%22%2C%20width%3D2%2C%20dash%3D%22dash%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20annotation_text%3Df%22Equal%20%7Bidx%2B1%7D%3A%20%7Be_val%3A.2f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20annotation_position%3D%22bottom%20right%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20Add%20Quantile%20breaks%0A%20%20%20%20for%20idx%2C%20q_val%20in%20enumerate(quantile_cutoffs%5B1%3A-1%5D)%3A%0A%20%20%20%20%20%20%20%20fig.add_vline(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dq_val%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%233B82F6%22%2C%20width%3D2%2C%20dash%3D%22dot%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20annotation_text%3Df%22Quant%20%7Bidx%2B1%7D%3A%20%7Bq_val%3A.2f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20annotation_position%3D%22top%20left%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20Dummy%20legend%20items%20for%20the%20lines%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%3D%5BNone%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5BNone%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%2310B981%22%2C%20width%3D2.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Jenks%20Natural%20Breaks%20(Valley%20Aligned)%22%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%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%3D%5BNone%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5BNone%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23F59E0B%22%2C%20width%3D2%2C%20dash%3D%22dash%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Equal%20Interval%20(Arbitrary%20Cuts)%22%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%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%3D%5BNone%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5BNone%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%233B82F6%22%2C%20width%3D2%2C%20dash%3D%22dot%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Quantiles%20(Equal%20Frequency%20Cuts)%22%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%20Right%3A%20GVF%20curve%20across%20k%0A%20%20%20%20k_range%20%3D%20list(range(1%2C%208))%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%3Dk_range%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dgvf_values%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Bmarkers%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%238B5CF6%22%2C%20width%3D2.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(size%3D8%2C%20color%3D%22%236D28D9%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22GVF%20Curve%22%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%20Add%20threshold%20reference%20line%20at%20GVF%20%3D%200.90%0A%20%20%20%20fig.add_hline(%0A%20%20%20%20%20%20%20%20y%3D0.90%2C%0A%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23EF4444%22%2C%20width%3D1.5%2C%20dash%3D%22dash%22)%2C%0A%20%20%20%20%20%20%20%20annotation_text%3D%2290%25%20Variance%20Explained%20(Target)%22%2C%0A%20%20%20%20%20%20%20%20annotation_position%3D%22bottom%20right%22%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%20fig.update_xaxes(title_text%3D%22Continuous%20Score%22%2C%20row%3D1%2C%20col%3D1)%0A%20%20%20%20fig.update_yaxes(title_text%3D%22Count%22%2C%20row%3D1%2C%20col%3D1)%0A%20%20%20%20fig.update_xaxes(title_text%3D%22Number%20of%20Classes%20(k)%22%2C%20row%3D1%2C%20col%3D2)%0A%20%20%20%20fig.update_yaxes(title_text%3D%22Goodness%20of%20Variance%20Fit%20(GVF)%22%2C%20range%3D%5B0%2C%201.05%5D%2C%20row%3D1%2C%20col%3D2)%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%3D520%2C%0A%20%20%20%20%20%20%20%20margin%3Ddict(l%3D40%2C%20r%3D40%2C%20t%3D70%2C%20b%3D50)%2C%0A%20%20%20%20%20%20%20%20legend%3Ddict(orientation%3D%22h%22%2C%20yanchor%3D%22bottom%22%2C%20y%3D-0.28%2C%20xanchor%3D%22center%22%2C%20x%3D0.5)%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%20equal_interval_cutoffs%2C%0A%20%20%20%20jenks_cutoffs%2C%0A%20%20%20%20jenkspy%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20pd%2C%0A%20%20%20%20quantile_cutoffs%2C%0A%20%20%20%20raw_scores%2C%0A%20%20%20%20sdam%2C%0A)%3A%0A%20%20%20%20%23%20Example%201%3A%20Fisher%20Dynamic%20Programming%20from%20scratch%20in%20Pure%20Python%0A%20%20%20%20def%20fisher_jenks_dp(arr%2C%20n_classes)%3A%0A%20%20%20%20%20%20%20%20sorted_x%20%3D%20np.sort(arr)%0A%20%20%20%20%20%20%20%20n%20%3D%20len(sorted_x)%0A%0A%20%20%20%20%20%20%20%20%23%20Precompute%20prefix%20sums%20and%20prefix%20sum%20of%20squares%20for%20O(1)%20interval%20variance%0A%20%20%20%20%20%20%20%20prefix_sum%20%3D%20np.zeros(n%20%2B%201)%0A%20%20%20%20%20%20%20%20prefix_sq%20%3D%20np.zeros(n%20%2B%201)%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix_sum%5Bi%20%2B%201%5D%20%3D%20prefix_sum%5Bi%5D%20%2B%20sorted_x%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix_sq%5Bi%20%2B%201%5D%20%3D%20prefix_sq%5Bi%5D%20%2B%20sorted_x%5Bi%5D%20**%202%0A%0A%20%20%20%20%20%20%20%20%23%20Fast%20function%20to%20compute%20D(i%2C%20j)%20%3D%20sum_%7Bm%3Di%7D%5Ej%20(x_m%20-%20mean)%5E2%20using%200-indexed%20indices%20%5Bi%2C%20j%5D%0A%20%20%20%20%20%20%20%20def%20get_d(i%2C%20j)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20count%20%3D%20j%20-%20i%20%2B%201%0A%20%20%20%20%20%20%20%20%20%20%20%20s%20%3D%20prefix_sum%5Bj%20%2B%201%5D%20-%20prefix_sum%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20sq%20%3D%20prefix_sq%5Bj%20%2B%201%5D%20-%20prefix_sq%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20sq%20-%20(s**2)%20%2F%20count%0A%0A%20%20%20%20%20%20%20%20%23%20DP%20tables%3A%20V%5Bc%2C%20m%5D%20stores%20min%20SDCM%20for%20prefix%200..m%20with%20c%20classes%20(1-indexed%20classes)%0A%20%20%20%20%20%20%20%20v%20%3D%20np.zeros((n_classes%20%2B%201%2C%20n))%0A%20%20%20%20%20%20%20%20p_table%20%3D%20np.zeros((n_classes%20%2B%201%2C%20n)%2C%20dtype%3Dint)%0A%0A%20%20%20%20%20%20%20%20%23%20Base%20case%20c%20%3D%201%0A%20%20%20%20%20%20%20%20for%20m%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20v%5B1%2C%20m%5D%20%3D%20get_d(0%2C%20m)%0A%0A%20%20%20%20%20%20%20%20%23%20Fill%20DP%20for%20c%20%3D%202%20..%20n_classes%0A%20%20%20%20%20%20%20%20for%20c%20in%20range(2%2C%20n_classes%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20m%20in%20range(c%20-%201%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min_val%20%3D%20float(%22inf%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_p%20%3D%20-1%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20p%20in%20range(c%20-%202%2C%20m)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cost%20%3D%20v%5Bc%20-%201%2C%20p%5D%20%2B%20get_d(p%20%2B%201%2C%20m)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cost%20%3C%20min_val%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min_val%20%3D%20cost%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_p%20%3D%20p%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20v%5Bc%2C%20m%5D%20%3D%20min_val%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p_table%5Bc%2C%20m%5D%20%3D%20best_p%0A%0A%20%20%20%20%20%20%20%20%23%20Backtrack%20to%20find%20boundaries%0A%20%20%20%20%20%20%20%20breaks%20%3D%20%5Bsorted_x%5B-1%5D%5D%0A%20%20%20%20%20%20%20%20curr_m%20%3D%20n%20-%201%0A%20%20%20%20%20%20%20%20for%20c%20in%20range(n_classes%2C%201%2C%20-1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20split_p%20%3D%20p_table%5Bc%2C%20curr_m%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20breaks.append(sorted_x%5Bsplit_p%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20curr_m%20%3D%20split_p%0A%20%20%20%20%20%20%20%20breaks.append(sorted_x%5B0%5D)%0A%20%20%20%20%20%20%20%20breaks.reverse()%0A%20%20%20%20%20%20%20%20return%20breaks%2C%20v%5Bn_classes%2C%20n%20-%201%5D%0A%0A%20%20%20%20%23%20Run%20on%20a%20representative%20subset%20to%20demonstrate%20exact%20mathematical%20match%0A%20%20%20%20test_data%20%3D%20raw_scores%5B%3A%3A5%5D%0A%20%20%20%20my_breaks%2C%20my_sdcm%20%3D%20fisher_jenks_dp(test_data%2C%203)%0A%20%20%20%20jenkspy_breaks%20%3D%20jenkspy.jenks_breaks(test_data%2C%20n_classes%3D3)%0A%0A%20%20%20%20df_verification%20%3D%20pd.DataFrame(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Class_Boundary%22%3A%20%5B%22Minimum%22%2C%20%22Split%201%22%2C%20%22Split%202%22%2C%20%22Maximum%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22From_Scratch_DP%22%3A%20np.round(my_breaks%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Jenkspy_Library%22%3A%20np.round(jenkspy_breaks%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Absolute_Difference%22%3A%20np.abs(np.array(my_breaks)%20-%20np.array(jenkspy_breaks)).round(8)%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Example%202%3A%20Metric%20comparison%20between%20Equal%20Interval%2C%20Quantile%2C%20and%20Jenks%0A%20%20%20%20def%20compute_metrics(boundaries%2C%20data_arr)%3A%0A%20%20%20%20%20%20%20%20sdcm_val%20%3D%200.0%0A%20%20%20%20%20%20%20%20counts%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(len(boundaries)%20-%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20%3D%3D%20len(boundaries)%20-%202%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20in_bin%20%3D%20data_arr%5B(data_arr%20%3E%3D%20boundaries%5Bj%5D)%20%26%20(data_arr%20%3C%3D%20boundaries%5Bj%20%2B%201%5D)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20in_bin%20%3D%20data_arr%5B(data_arr%20%3E%3D%20boundaries%5Bj%5D)%20%26%20(data_arr%20%3C%20boundaries%5Bj%20%2B%201%5D)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20counts.append(len(in_bin))%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(in_bin)%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sdcm_val%20%2B%3D%20np.sum((in_bin%20-%20np.mean(in_bin))%20**%202)%0A%20%20%20%20%20%20%20%20gvf_val%20%3D%201.0%20-%20(sdcm_val%20%2F%20sdam)%0A%20%20%20%20%20%20%20%20return%20sdcm_val%2C%20gvf_val%2C%20counts%0A%0A%20%20%20%20jenks_sdcm%2C%20jenks_gvf%2C%20jenks_counts%20%3D%20compute_metrics(jenks_cutoffs%2C%20raw_scores)%0A%20%20%20%20eq_sdcm%2C%20eq_gvf%2C%20eq_counts%20%3D%20compute_metrics(equal_interval_cutoffs%2C%20raw_scores)%0A%20%20%20%20quant_sdcm%2C%20quant_gvf%2C%20quant_counts%20%3D%20compute_metrics(quantile_cutoffs%2C%20raw_scores)%0A%0A%20%20%20%20df_comparison%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%22Method%22%3A%20%22Jenks%20Natural%20Breaks%20(Optimal)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22SDCM%20(Within-Class%20Variance)%22%3A%20round(jenks_sdcm%2C%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22GVF%20(Explained%20Variance)%22%3A%20f%22%7Bjenks_gvf%20*%20100%3A.2f%7D%25%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Class_Distribution%22%3A%20str(jenks_counts)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Optimality%22%3A%20%22Provably%20minimal%20SDCM%20in%201D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%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%22Method%22%3A%20%22Quantiles%20(Equal%20Frequency)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22SDCM%20(Within-Class%20Variance)%22%3A%20round(quant_sdcm%2C%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22GVF%20(Explained%20Variance)%22%3A%20f%22%7Bquant_gvf%20*%20100%3A.2f%7D%25%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Class_Distribution%22%3A%20str(quant_counts)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Optimality%22%3A%20%22Forces%20equal%20counts%2C%20ignores%20valleys%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%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%22Method%22%3A%20%22Equal%20Interval%20(Fixed%20Width)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22SDCM%20(Within-Class%20Variance)%22%3A%20round(eq_sdcm%2C%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22GVF%20(Explained%20Variance)%22%3A%20f%22%7Beq_gvf%20*%20100%3A.2f%7D%25%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Class_Distribution%22%3A%20str(eq_counts)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Optimality%22%3A%20%22Heuristic%20interval%2C%20ignores%20density%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%0A%20%20%20%20table_verif%20%3D%20mo.ui.table(df_verification)%0A%20%20%20%20table_comp%20%3D%20mo.ui.table(df_comparison)%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
8629fc24db4f51ecd2ebd5c25689928e