knn

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.16%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20METADATA%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22id%22%3A%20%22knn%22%2C%0A%20%20%20%20%20%20%20%20%22name%22%3A%20%22K-Nearest%20Neighbors%22%2C%0A%20%20%20%20%20%20%20%20%22types%22%3A%20%5B%22algorithm%22%5D%2C%0A%20%20%20%20%20%20%20%20%22families%22%3A%20%5B%22distance%22%5D%2C%0A%20%20%20%20%20%20%20%20%22tasks%22%3A%20%5B%22classification%22%2C%20%22regression%22%5D%2C%0A%20%20%20%20%20%20%20%20%22data%22%3A%20%5B%22tabular%22%5D%2C%0A%20%20%20%20%20%20%20%20%22learning%22%3A%20%5B%22supervised%22%5D%2C%0A%20%20%20%20%20%20%20%20%22capacity%22%3A%20%22non_parametric%22%2C%0A%20%20%20%20%20%20%20%20%22mechanisms%22%3A%20%5B%22nearest_neighbors%22%2C%20%22distance%22%5D%2C%0A%20%20%20%20%20%20%20%20%22properties%22%3A%20%5B%22local_method%22%2C%20%22nonlinear%22%5D%2C%0A%20%20%20%20%20%20%20%20%22constraints%22%3A%20%5B%22poor_extrapolation%22%2C%20%22requires_scaling%22%2C%20%22sensitive_to_high_dimension%22%2C%20%22slow_inference%22%5D%2C%0A%20%20%20%20%20%20%20%20%22difficulty%22%3A%20%22beginner%22%2C%0A%20%20%20%20%20%20%20%20%22status%22%3A%20%22complete%22%2C%0A%20%20%20%20%20%20%20%20%22explainability%22%3A%20%22medium%22%2C%0A%20%20%20%20%20%20%20%20%22training_cost%22%3A%20%22low%22%2C%0A%20%20%20%20%20%20%20%20%22inference_cost%22%3A%20%22high%22%2C%0A%20%20%20%20%20%20%20%20%22data_appetite%22%3A%20%22medium%22%2C%0A%20%20%20%20%7D%0A%0A%20%20%20%20mo.md(f%22%23%20%7BMETADATA%5B'name'%5D%7D%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%20In%20one%20sentence%0A%0A%20%20%20%20KNN%20predicts%20from%20the%20labels%20of%20the%20most%20similar%20stored%20examples.%0A%0A%20%20%20%20%23%23%20Mental%20model%0A%0A%20%20%20%20To%20estimate%20a%20new%20apartment's%20price%2C%20find%20the%20most%20similar%20apartments%20and%20average%20their%20prices.%20For%20classification%2C%20ask%20the%20nearest%20examples%20to%20vote.%0A%0A%20%20%20%20KNN%20has%20almost%20no%20conventional%20training%20phase.%20The%20work%20is%20delayed%20until%20prediction%2C%20when%20distances%20to%20stored%20examples%20must%20be%20computed.%0A%0A%20%20%20%20%23%23%20Input%20and%20output%0A%0A%20%20%20%20-%20**Input%3A**%20a%20feature%20vector%20and%20a%20distance%20definition.%0A%20%20%20%20-%20**Output%3A**%20a%20class%20vote%20or%20average%20numeric%20target.%0A%20%20%20%20-%20**Stores%3A**%20essentially%20the%20training%20data.%0A%0A%20%20%20%20%23%23%20How%20it%20works%0A%0A%20%20%20%201.%20Scale%20or%20transform%20the%20features.%0A%20%20%20%202.%20Compute%20the%20distance%20from%20a%20new%20point%20to%20training%20points.%0A%20%20%20%203.%20Select%20the%20nearest%20%24k%24.%0A%20%20%20%204.%20Aggregate%20their%20targets%2C%20optionally%20weighting%20closer%20neighbors%20more.%0A%0A%20%20%20%20Small%20%24k%24%20creates%20flexible%2C%20jagged%20behavior%20and%20can%20chase%20noise.%20Large%20%24k%24%20smooths%20predictions%20but%20can%20erase%20local%20structure.%0A%0A%20%20%20%20%23%23%20Why%20distance%20is%20the%20real%20model%0A%0A%20%20%20%20Euclidean%20distance%20assumes%20features%20share%20a%20meaningful%20geometry.%20If%20%22annual%20income%22%20ranges%20in%20tens%20of%20thousands%20and%20%22number%20of%20children%22%20ranges%20from%20zero%20to%20five%2C%20income%20dominates%20unless%20features%20are%20scaled.%0A%0A%20%20%20%20In%20high%20dimensions%2C%20points%20often%20become%20similarly%20far%20apart%20%E2%80%94%20the%20curse%20of%20dimensionality.%20Irrelevant%20features%20dilute%20the%20useful%20neighborhood.%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%20When%20to%20use%20it%0A%0A%20%20%20%20-%20The%20dataset%20is%20small%20or%20medium.%0A%20%20%20%20-%20Similar%20cases%20should%20genuinely%20have%20similar%20outcomes.%0A%20%20%20%20-%20The%20useful%20boundary%20is%20local%20and%20irregular.%0A%20%20%20%20-%20You%20want%20a%20simple%20nonparametric%20reference.%0A%20%20%20%20-%20Prediction%20latency%20is%20not%20extremely%20tight.%0A%0A%20%20%20%20%23%23%20When%20to%20avoid%20it%0A%0A%20%20%20%20-%20Data%20has%20many%20noisy%20or%20high-dimensional%20features.%0A%20%20%20%20-%20The%20dataset%20is%20very%20large%20and%20exact%20neighbor%20search%20is%20too%20slow.%0A%20%20%20%20-%20Serving%20cannot%20retain%20training%20examples.%0A%20%20%20%20-%20Feature%20scales%20or%20similarity%20are%20poorly%20understood.%0A%20%20%20%20-%20Extrapolation%20beyond%20observed%20examples%20is%20required.%0A%0A%20%20%20%20%23%23%20Important%20controls%0A%0A%20%20%20%20%7C%20Control%20%7C%20Role%20%7C%0A%20%20%20%20%7C---------%7C------%7C%0A%20%20%20%20%7C%20Number%20of%20neighbors%20%7C%20Main%20smoothness%20control%20%7C%0A%20%20%20%20%7C%20Distance%20metric%20%7C%20Encodes%20what%20similarity%20means%20%7C%0A%20%20%20%20%7C%20Weights%20%7C%20Uniform%20voting%20or%20distance-weighted%20influence%20%7C%0A%20%20%20%20%7C%20Search%20algorithm%20%7C%20Brute%20force%2C%20tree-based%2C%20or%20approximate%20neighbors%20%7C%0A%0A%20%20%20%20Choose%20these%20inside%20cross-validation%20and%20preprocessing%20pipelines%20so%20scaling%20is%20fitted%20only%20on%20the%20training%20folds.%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20Notebook%20%E2%80%94%20the%20distance%20definition%20is%20the%20model%0A%0A%20%20%20%20**Question%3A**%20how%20do%20scaling%20and%20the%20number%20of%20neighbors%20change%20a%20local%20classifier%3F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20from%20sklearn.datasets%20import%20make_moons%0A%20%20%20%20from%20sklearn.inspection%20import%20DecisionBoundaryDisplay%0A%20%20%20%20from%20sklearn.neighbors%20import%20KNeighborsClassifier%0A%20%20%20%20from%20sklearn.pipeline%20import%20make_pipeline%0A%20%20%20%20from%20sklearn.preprocessing%20import%20StandardScaler%0A%0A%20%20%20%20X%2C%20y%20%3D%20make_moons(n_samples%3D260%2C%20noise%3D0.23%2C%20random_state%3D8)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20DecisionBoundaryDisplay%2C%0A%20%20%20%20%20%20%20%20KNeighborsClassifier%2C%0A%20%20%20%20%20%20%20%20StandardScaler%2C%0A%20%20%20%20%20%20%20%20X%2C%0A%20%20%20%20%20%20%20%20make_pipeline%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20y%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20DecisionBoundaryDisplay%2C%0A%20%20%20%20KNeighborsClassifier%2C%0A%20%20%20%20StandardScaler%2C%0A%20%20%20%20X%2C%0A%20%20%20%20make_pipeline%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20y%2C%0A)%3A%0A%20%20%20%20fig%2C%20axes%20%3D%20plt.subplots(1%2C%203%2C%20figsize%3D(14%2C%204))%0A%20%20%20%20for%20ax%2C%20k%20in%20zip(axes%2C%20%5B1%2C%209%2C%2045%5D)%3A%0A%20%20%20%20%20%20%20%20model%20%3D%20make_pipeline(StandardScaler()%2C%20KNeighborsClassifier(n_neighbors%3Dk)).fit(X%2C%20y)%0A%20%20%20%20%20%20%20%20DecisionBoundaryDisplay.from_estimator(model%2C%20X%2C%20ax%3Dax%2C%20alpha%3D0.3)%0A%20%20%20%20%20%20%20%20ax.scatter(X%5B%3A%2C%200%5D%2C%20X%5B%3A%2C%201%5D%2C%20c%3Dy%2C%20s%3D14%2C%20edgecolor%3D%22k%22%2C%20linewidth%3D0.2)%0A%20%20%20%20%20%20%20%20ax.set_title(f%22k%20%3D%20%7Bk%7D%22)%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(KNeighborsClassifier%2C%20StandardScaler%2C%20X%2C%20make_pipeline%2C%20y)%3A%0A%20%20%20%20%23%20Stretch%20one%20feature%3A%20without%20scaling%2C%20it%20dominates%20Euclidean%20distance.%0A%20%20%20%20X_stretched%20%3D%20X.copy()%0A%20%20%20%20X_stretched%5B%3A%2C%200%5D%20*%3D%20100%0A%20%20%20%20raw%20%3D%20KNeighborsClassifier(n_neighbors%3D9).fit(X_stretched%2C%20y)%0A%20%20%20%20scaled%20%3D%20make_pipeline(StandardScaler()%2C%20KNeighborsClassifier(n_neighbors%3D9)).fit(%0A%20%20%20%20%20%20%20%20X_stretched%2C%20y%0A%20%20%20%20)%0A%20%20%20%20print(%22training%20accuracy%20without%20scaling%3A%22%2C%20round(raw.score(X_stretched%2C%20y)%2C%203))%0A%20%20%20%20print(%22training%20accuracy%20with%20scaling%3A%20%20%20%22%2C%20round(scaled.score(X_stretched%2C%20y)%2C%203))%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---%0A%0A%20%20%20%20%23%23%20Evaluation%20and%20diagnosis%0A%0A%20%20%20%20Compare%20several%20%24k%24%20values%20on%20validation%20data.%20Inspect%20neighbor%20identities%20for%20individual%20errors%3A%20incorrect%20predictions%20often%20reveal%20a%20broken%20distance%20metric%20or%20a%20region%20with%20sparse%20coverage.%0A%0A%20%20%20%20Measure%20inference%20latency%20and%20memory%2C%20not%20just%20accuracy.%20KNN%20moves%20cost%20from%20training%20to%20serving.%0A%0A%20%20%20%20%23%23%20Related%20models%0A%0A%20%20%20%20-%20**Logistic%20Regression**%20learns%20a%20global%20linear%20boundary.%0A%20%20%20%20-%20**Decision%20Tree**%20forms%20local%20regions%20with%20threshold%20rules.%0A%20%20%20%20-%20**K-Means**%20also%20uses%20distance%2C%20but%20discovers%20unlabeled%20groups%20rather%20than%20predicting%20known%20targets.%0A%0A%20%20%20%20%23%23%20Practical%20takeaway%0A%0A%20%20%20%20KNN%20is%20simple%20only%20after%20similarity%20has%20been%20designed%20well.%20Scaling%20and%20representation%20are%20part%20of%20the%20model.%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