import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%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%20%24k%24-means%20Clustering%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%20warnings%0A%20%20%20%20from%20pathlib%20import%20Path%0A%0A%20%20%20%20warnings.filterwarnings(%22ignore%22)%0A%0A%20%20%20%20import%20cvxpy%20as%20cp%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20sklearn.datasets%20import%20make_blobs%0A%0A%20%20%20%20from%20dbcp%20import%20BiconvexProblem%0A%0A%20%20%20%20plt.style.use(Path(__file__).resolve().parent%20%2F%20%22zhlatex.mplstyle%22)%0A%20%20%20%20figure_directory%20%3D%20Path(__file__).resolve().parent%20%2F%20%22figures%22%0A%20%20%20%20figure_directory.mkdir(parents%3DTrue%2C%20exist_ok%3DTrue)%0A%0A%20%20%20%20np.random.seed(10015)%0A%20%20%20%20return%20BiconvexProblem%2C%20cp%2C%20figure_directory%2C%20make_blobs%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%23%20Introduction%0A%0A%20%20%20%20Suppose%20we%20are%20given%20a%20set%20of%20data%20points%20%24x_i%20%5Cin%20%5Cmathbf%7BR%7D%5En%24%2C%20%24i%20%3D%201%2C%20%5Cldots%2C%20m%24%2C%20and%20we%20would%20like%20to%0A%20%20%20%20cluster%20them%20into%20%24k%24%20groups%2C%20using%20the%20%24k%24-means%20clustering%20method.%0A%20%20%20%20This%20corresponds%20to%20the%20following%20biconvex%20optimization%20problem%3A%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Ctext%7Bminimize%7D%20%26%20%5Csum_%7Bi%20%3D%201%7D%5E%7Bm%7D%20z_i%5ET%20(%7B%5C%7C%5Cbar%7Bx%7D_1%20-%20x_i%5C%7C%7D_2%5E2%2C%20%5Cldots%2C%20%7B%5C%7C%5Cbar%7Bx%7D_k%20-%20x_i%5C%7C%7D_2%5E2)%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Ctext%7Bsubject%20to%7D%20%26%200%20%5Cpreceq%20z_i%20%5Cpreceq%20%5Cmathbf%7B1%7D%2C%5Cquad%20%5Cmathbf%7B1%7D%5ET%20z_i%20%3D%201%2C%5Cquad%20i%20%3D%201%2C%20%5Cldots%2C%20m%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20with%20variables%20%24%5Cbar%7Bx%7D_i%20%5Cin%20%5Cmathbf%7BR%7D%5En%24%2C%20%24i%20%3D%201%2C%20%5Cldots%2C%20k%24%2C%20and%20%24z_i%20%5Cin%20%5Cmathbf%7BR%7D%5Ek%24%2C%20%24i%20%3D%201%2C%20%5Cldots%2C%20m%24.%0A%0A%20%20%20%20We%20can%20interpret%20the%20problem%20formulation%20as%20follows%3A%0A%20%20%20%20The%20variables%20%24%5Cbar%7Bx%7D_1%2C%20%5Cldots%2C%20%5Cbar%7Bx%7D_k%24%20represent%20the%20cluster%20centroids%2C%20and%20each%20variable%20%24z_i%24%20is%20a%20soft%0A%20%20%20%20assignment%20vector%20for%20data%20point%20%24x_i%24%2C%20where%20the%20%24j%24th%20entry%20of%20%24z_i%24%20indicates%20the%20probability%20of%20the%20sample%0A%20%20%20%20%24x_i%24%20belonging%20to%20cluster%20%24j%24.%0A%20%20%20%20Then%2C%20the%20objective%20function%20represents%20the%20total%20within-cluster%20variance%2C%20which%20we%20would%20like%20to%20minimize.%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%20Generate%20problem%20data%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(make_blobs)%3A%0A%20%20%20%20n%20%3D%202%0A%20%20%20%20m%20%3D%201000%0A%20%20%20%20k%20%3D%204%0A%20%20%20%20centers%20%3D%20%5B%5B0%2C%202%5D%2C%20%5B0%2C%20-2%5D%2C%20%5B2%2C%200%5D%2C%20%5B-2%2C%200%5D%5D%0A%20%20%20%20xs%2C%20labels%20%3D%20make_blobs(n_samples%3Dm%2C%20centers%3Dcenters%2C%20cluster_std%3D0.5)%0A%20%20%20%20return%20k%2C%20m%2C%20n%2C%20xs%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%20Specify%20and%20solve%20the%20problem%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(BiconvexProblem%2C%20cp%2C%20k%2C%20m%2C%20n%2C%20xs)%3A%0A%20%20%20%20xbars%20%3D%20cp.Variable((k%2C%20n))%0A%20%20%20%20zs%20%3D%20cp.Variable((m%2C%20k)%2C%20nonneg%3DTrue)%0A%20%20%20%20d%20%3D%20cp.sum_squares(xs%5B%3A%2C%20None%2C%20%3A%5D%20-%20xbars%5BNone%2C%20%3A%2C%20%3A%5D%2C%20axis%3D2)%0A%20%20%20%20obj%20%3D%20cp.Minimize(cp.sum(cp.multiply(zs%2C%20d)))%0A%20%20%20%20constr%20%3D%20%5Bzs%20%3C%3D%201%2C%20cp.sum(zs%2C%20axis%3D1)%20%3D%3D%201%5D%0A%20%20%20%20prob%20%3D%20BiconvexProblem(obj%2C%20%5Bxbars%5D%2C%20%5Bzs%5D%2C%20constr)%0A%20%20%20%20prob.solve()%0A%20%20%20%20return%20xbars%2C%20zs%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%20Plot%20the%20results%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(figure_directory%2C%20np%2C%20plt%2C%20xbars%2C%20xs%2C%20zs)%3A%0A%20%20%20%20fig%2C%20axs%20%3D%20plt.subplots(1%2C%201%2C%20figsize%3D(4%2C%204))%0A%20%20%20%20_labels%20%3D%20np.argmax(zs.value%2C%20axis%3D-1)%0A%20%20%20%20cmap%20%3D%20plt.get_cmap(%22tab10%22%2C%20np.unique(_labels).size)%0A%20%20%20%20axs.scatter(xs%5B%3A%2C%200%5D%2C%20xs%5B%3A%2C%201%5D%2C%20s%3D10%2C%20c%3D_labels%2C%20cmap%3Dcmap)%0A%20%20%20%20axs.scatter(xbars.value%5B%3A%2C%200%5D%2C%20xbars.value%5B%3A%2C%201%5D%2C%20s%3D100%2C%20color%3D%22k%22%2C%20marker%3D%22x%22)%0A%20%20%20%20axs.set_xlabel(%22%24x_1%24%22)%0A%20%20%20%20axs.set_ylabel(%22%24x_2%24%22)%0A%0A%20%20%20%20fig.tight_layout()%0A%20%20%20%20fig.savefig(figure_directory%20%2F%20%22kmeans.pdf%22%2C%20bbox_inches%3D%22tight%22)%0A%20%20%20%20plt.show()%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
a0bbabc6466388a49c6ee4bf20e05d8e