K-Means.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "class KMeansScratch:\n",
    "    def __init__(self, k=3, max_iters=100, tol=1e-4, random_state=None):\n",
    "        \"\"\"\n",
    "        :param k: 指定聚类数量\n",
    "        :param max_iters: 最大迭代次数\n",
    "        :param tol: 判断质心变化是否收敛的阈值\n",
    "        :param random_state: 随机种子，便于结果重现\n",
    "        \"\"\"\n",
    "        self.k = k\n",
    "        self.max_iters = max_iters\n",
    "        self.tol = tol\n",
    "        self.random_state = random_state\n",
    "        \n",
    "        # 训练后的属性\n",
    "        self.centroids = None  # 质心\n",
    "        self.labels_ = None    # 每个样本所属簇标签\n",
    "\n",
    "    def fit(self, X):\n",
    "        \"\"\"\n",
    "        训练 K-means 模型\n",
    "        :param X: 输入数据，形状 (m, n) - m 条样本, n 个特征\n",
    "        \"\"\"\n",
    "        # 1) 初始化质心\n",
    "        np.random.seed(self.random_state)\n",
    "        self._init_centroids(X)\n",
    "        \n",
    "        for i in range(self.max_iters):\n",
    "            # 2) 将每个样本分配到最近的质心\n",
    "            labels = self._assign_clusters(X)\n",
    "            \n",
    "            # 3) 计算新的质心\n",
    "            new_centroids = self._update_centroids(X, labels)\n",
    "            \n",
    "            # 判断质心是否发生明显变化（小于 tol 则视为收敛）\n",
    "            shift = np.linalg.norm(self.centroids - new_centroids)\n",
    "            if shift < self.tol:\n",
    "                # 收敛\n",
    "                break\n",
    "            \n",
    "            self.centroids = new_centroids\n",
    "        \n",
    "        # 更新最终的 labels（可能最后一次更新后与原先略不同）\n",
    "        self.labels_ = self._assign_clusters(X)\n",
    "\n",
    "    def _init_centroids(self, X):\n",
    "        \"\"\"\n",
    "        随机选择 k 个不同的样本点作为初始质心\n",
    "        \"\"\"\n",
    "        m = X.shape[0]\n",
    "        # 从 m 条样本里随机无放回地选 k 条\n",
    "        indices = np.random.choice(m, self.k, replace=False)\n",
    "        self.centroids = X[indices]  # 形状 (k, n)\n",
    "\n",
    "    def _assign_clusters(self, X):\n",
    "        \"\"\"\n",
    "        计算每个样本到 k 个质心的距离，返回分配的簇标签数组 (m,)\n",
    "        \"\"\"\n",
    "        # 对于每个样本，计算它与所有质心的距离，然后取最小距离对应的索引\n",
    "        distances = self._compute_distances(X, self.centroids)\n",
    "        # distances 形状 (m, k), 行对应样本, 列对应质心\n",
    "        # 每行找最小值对应的列索引 -> 该样本所属的簇\n",
    "        labels = np.argmin(distances, axis=1)\n",
    "        return labels\n",
    "\n",
    "    def _update_centroids(self, X, labels):\n",
    "        \"\"\"\n",
    "        根据当前分配结果重新计算质心\n",
    "        对于每个簇，计算其所有样本在各个维度的平均值\n",
    "        \"\"\"\n",
    "        new_centroids = []\n",
    "        for cluster_id in range(self.k):\n",
    "            # 取出属于 cluster_id 簇的所有样本\n",
    "            cluster_points = X[labels == cluster_id]\n",
    "            if len(cluster_points) == 0:\n",
    "                # 如果有空簇，可随机或使用其它策略重新初始化\n",
    "                # 这里简单地随机重新选一个质心\n",
    "                new_centroid = self.centroids[cluster_id]\n",
    "            else:\n",
    "                # 各维度平均\n",
    "                new_centroid = cluster_points.mean(axis=0)\n",
    "            new_centroids.append(new_centroid)\n",
    "        return np.array(new_centroids)\n",
    "\n",
    "    def _compute_distances(self, X, centroids):\n",
    "        \"\"\"\n",
    "        计算 X 到各个质心的欧几里得距离\n",
    "        :param X: 形状 (m, n)\n",
    "        :param centroids: 形状 (k, n)\n",
    "        :return: 距离矩阵, 形状 (m, k)\n",
    "        \"\"\"\n",
    "        # 做法1: 逐样本、逐质心循环计算\n",
    "        # 做法2: 矩阵计算 (如下):\n",
    "        # dist(x, c) = sqrt( sum( (x_j - c_j)^2 ) ), \n",
    "        # 这里可以用广播技巧、或 for 循环\n",
    "        m = X.shape[0]\n",
    "        k = centroids.shape[0]\n",
    "        \n",
    "        # distances[i, j] = ||X[i] - centroids[j]||\n",
    "        distances = np.zeros((m, k))\n",
    "        for i in range(k):\n",
    "            # centroids[i] 形状 (n,)\n",
    "            # X - centroids[i] 形状 (m, n)\n",
    "            diff = X - centroids[i]\n",
    "            distances[:, i] = np.sqrt(np.sum(diff**2, axis=1))\n",
    "        return distances\n",
    "\n",
    "    def predict(self, X):\n",
    "        \"\"\"\n",
    "        对新数据 X 做聚类预测，返回标签 (与最近质心对应的簇)\n",
    "        \"\"\"\n",
    "        distances = self._compute_distances(X, self.centroids)\n",
    "        labels = np.argmin(distances, axis=1)\n",
    "        return labels\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Final centroids:\n",
      " [[6.83333333 7.33333333]\n",
      " [0.875      1.85      ]]\n",
      "Labels: [1 1 0 0 1 0 0 1 0 0]\n",
      "New points: [[0.5 2. ]\n",
      " [7.  8.5]]\n",
      "Predictions: [1 0]\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    # 假设我们有一些 2D 数据\n",
    "    X = np.array([\n",
    "        [1.0, 2.0],\n",
    "        [1.5, 1.8],\n",
    "        [5.0, 8.0],\n",
    "        [8.0, 8.0],\n",
    "        [1.0, 0.6],\n",
    "        [9.0, 11.0],\n",
    "        [8.0, 9.0],\n",
    "        [0.0, 3.0],\n",
    "        [5.0, 4.0],\n",
    "        [6.0, 4.0]\n",
    "    ])\n",
    "\n",
    "    # 创建并训练 KMeansScratch\n",
    "    kmeans = KMeansScratch(k=2, max_iters=10, tol=1e-4, random_state=42)\n",
    "    kmeans.fit(X)\n",
    "\n",
    "    # 打印结果\n",
    "    print(\"Final centroids:\\n\", kmeans.centroids)\n",
    "    print(\"Labels:\", kmeans.labels_)\n",
    "\n",
    "    # 预测新点的聚类归属\n",
    "    new_points = np.array([\n",
    "        [0.5, 2.0],\n",
    "        [7.0, 8.5]\n",
    "    ])\n",
    "    predictions = kmeans.predict(new_points)\n",
    "    print(\"New points:\", new_points)\n",
    "    print(\"Predictions:\", predictions)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}