第5章-文本聚类.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "66e0d34e",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "下面我们实现*k*均值算法，进行文本聚类。这里使用的数据集与第4章的数据集类似，包含3种主题约1万本图书的信息，但文本内容是图书摘要而非标题。首先我们复用第4章的代码进行预处理。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ce835777",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "train size = 8627 , test size = 2157\n",
      "{0: '计算机类', 1: '艺术传媒类', 2: '经管类'}\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 8627/8627 [03:10<00:00, 45.23it/s]\n",
      "100%|██████████| 2157/2157 [00:47<00:00, 45.56it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "unique tokens = 34252, total counts = 806900, max freq = 19197, min freq = 1\n",
      "min_freq = 3, min_len = 2, max_size = None, remaining tokens = 9504,\n",
      " in-vocab rate = 0.8910459784359895\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import sys\n",
    "\n",
    "# 导入前面实现的Books数据集\n",
    "sys.path.append('./code')\n",
    "from utils import BooksDataset\n",
    "\n",
    "dataset = BooksDataset()\n",
    "# 打印出类和标签ID\n",
    "print(dataset.id2label)\n",
    "\n",
    "dataset.tokenize(attr='abstract')\n",
    "dataset.build_vocab(min_freq=3)\n",
    "dataset.convert_tokens_to_ids()\n",
    "\n",
    "train_data, test_data = dataset.train_data, dataset.test_data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96285754",
   "metadata": {},
   "source": [
    "接下来导入实现TF-IDF算法的函数，将处理后的数据集输入到函数中，得到文档特征："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1a16e90b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(8627, 9504)\n"
     ]
    }
   ],
   "source": [
    "# 导入之前实现的TF-IDF算法\n",
    "from utils import TFIDF\n",
    "\n",
    "vocab_size = len(dataset.token2id)\n",
    "train_X = []\n",
    "for data in train_data:\n",
    "    train_X.append(data['token_ids'])\n",
    "# 对TF-IDF的结果进行归一化（norm='l2'）对聚类非常重要，\n",
    "# 不经过归一化会导致数据在某些方向上过于分散从而聚类失败\n",
    "# 初始化TFIDF()函数\n",
    "tfidf = TFIDF(vocab_size, norm='l2', smooth_idf=True, sublinear_tf=True)\n",
    "# 计算词频率和逆文档频率\n",
    "tfidf.fit(train_X)\n",
    "# 转化为TF-IDF向量\n",
    "train_F = tfidf.transform(train_X)\n",
    "print(train_F.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8f04c44",
   "metadata": {},
   "source": [
    "在有了数据之后，运行*k*均值聚类算法为文本进行聚类。我们需要事先确定簇数$K$。为了方便与实际的标签数据进行对比，这里假设$K$为3。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d8493c19",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------初始化-----------\n",
      "-----------初始化完成-----------\n",
      "第1步，中心点平均移动距离：0.059189038070756865\n",
      "...\n",
      "第10步，中心点平均移动距离：0.002389605545132419\n",
      "...\n",
      "第16步，中心点平均移动距离：0.0\n",
      "中心点不再移动，退出程序\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "# 更改簇的标签数量\n",
    "K = 3\n",
    "\n",
    "class KMeans:\n",
    "    def __init__(self, K, dim, stop_val = 1e-4, max_step = 100):\n",
    "        self.K = K\n",
    "        self.dim = dim\n",
    "        self.stop_val = stop_val\n",
    "        self.max_step = max_step\n",
    "\n",
    "    def update_mean_vec(self, X):\n",
    "        mean_vec = np.zeros([self.K, self.dim])\n",
    "        for k in range(self.K):\n",
    "            data = X[self.cluster_num == k]\n",
    "            if len(data) > 0:\n",
    "                mean_vec[k] = data.mean(axis=0)\n",
    "        return mean_vec\n",
    "    \n",
    "    # 运行k均值算法的迭代循环\n",
    "    def fit(self, X):\n",
    "        print('-----------初始化-----------')\n",
    "        N = len(X)\n",
    "        dim = len(X[0])\n",
    "        # 给每个数据点随机分配簇\n",
    "        self.cluster_num = np.random.randint(0, self.K, N)\n",
    "        self.mean_vec = self.update_mean_vec(X)\n",
    "        \n",
    "        print('-----------初始化完成-----------')\n",
    "        global_step = 0\n",
    "        while global_step < self.max_step:\n",
    "            global_step += 1\n",
    "            self.cluster_num = np.zeros(N, int) \n",
    "            for i, data_point in enumerate(X):\n",
    "                # 计算每个数据点和每个簇中心的L2距离\n",
    "                dist = np.linalg.norm(data_point[None, :] - \\\n",
    "                    self.mean_vec, ord=2, axis=-1)\n",
    "                # 找到每个数据点所属新的聚类\n",
    "                self.cluster_num[i] = dist.argmin(-1)\n",
    "\n",
    "            '''\n",
    "            上面的循环过程也可以以下面的代码进行并行处理，但是可能\n",
    "            会使得显存过大，建议在数据点的特征向量维度较小时\n",
    "            或者进行降维后使用\n",
    "            # N x D - K x D -> N x K x D\n",
    "            dist = np.linalg.norm(train_X[:,None,:] - self.mean_vec, \\\n",
    "                ord = 2, axis = -1) \n",
    "            # 找到每个数据点所属新的聚类\n",
    "            self.cluster_num = dist.argmin(-1)\n",
    "            '''\n",
    "\n",
    "            new_mean_vec = self.update_mean_vec(X)\n",
    "\n",
    "            # 计算新的簇中心点和上一步迭代的中心点的距离\n",
    "            moving_dist = np.linalg.norm(new_mean_vec - self.mean_vec,\\\n",
    "                ord = 2, axis = -1).mean()\n",
    "            print(f\"第{global_step}步，中心点平均移动距离：{moving_dist}\")\n",
    "            if moving_dist < self.stop_val:\n",
    "                print(\"中心点不再移动，退出程序\")\n",
    "                break\n",
    "\n",
    "            # 将mean_vec更新\n",
    "            self.mean_vec = new_mean_vec\n",
    "\n",
    "kmeans = KMeans(K, train_F.shape[1])\n",
    "kmeans.fit(train_F)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8f3f765",
   "metadata": {},
   "source": [
    "为了更直观地展示聚类的效果，我们定义show_clusters()这个函数，显示每个真实分类下包含的每个簇的比重。下面对*k*均值算法的聚类结果进行展示，并观察3个标签中不同簇的占比。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1c3158e6",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8627\n",
      "计算机类:\t{ 0: 2583(0.67), 1: 1222(0.32), 2: 37(0.01), }\n",
      "艺术传媒类:\t{ 0: 281(0.12), 1: 72(0.03), 2: 1947(0.85), }\n",
      "经管类:\t{ 0: 2452(0.99), 1: 26(0.01), 2: 7(0.00), }\n"
     ]
    }
   ],
   "source": [
    "# 取出每条数据的标签和标签ID\n",
    "labels = []\n",
    "for data in train_data:\n",
    "    labels.append(data['label'])\n",
    "print(len(labels))\n",
    "\n",
    "# 展示聚类结果\n",
    "def show_clusters(clusters, K):\n",
    "    # 每个标签下的数据可能被聚类到不同的簇，因此对所有标签、所有簇进行初始化\n",
    "    label_clusters = {label_id: {} for label_id in dataset.id2label}\n",
    "    for k, v in label_clusters.items():\n",
    "        label_clusters[k] = {i: 0 for i in range(K)}\n",
    "    # 统计每个标签下，分到每个簇的数据条数\n",
    "    for label_id, cluster_id in zip(labels, clusters):\n",
    "        label_clusters[label_id][cluster_id] += 1\n",
    "        \n",
    "    for label_id in sorted(dataset.id2label.keys()):\n",
    "        _str = dataset.id2label[label_id] + ':\\t{ '\n",
    "        for cluster_id in range(K):\n",
    "            # 计算label_id这个标签ID下，簇为cluster_id的占比\n",
    "            _cnt = label_clusters[label_id][cluster_id]\n",
    "            _total = sum(label_clusters[label_id].values())\n",
    "            _str += f'{str(cluster_id)}: {_cnt}({_cnt / _total:.2f}), '\n",
    "        _str += '}'\n",
    "        print(_str)\n",
    "\n",
    "clusters = kmeans.cluster_num\n",
    "show_clusters(clusters, K)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be29cb62",
   "metadata": {},
   "source": [
    "接下来演示如何使用高斯混合来进行聚类。注意高斯混合会计算每个数据点归属于各簇的概率分布，这里将概率最高的簇作为聚类输出。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9353dbb8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.stats import multivariate_normal as gaussian\n",
    "from tqdm import tqdm\n",
    "\n",
    "# 高斯混合模型\n",
    "class GMM:\n",
    "    def __init__(self, K, dim, max_iter=100):\n",
    "        # K为聚类数目，dim为向量维度，max_iter为最大迭代次数\n",
    "        self.K = K\n",
    "        self.dim = dim\n",
    "        self.max_iter = max_iter\n",
    "        \n",
    "        # 初始化，pi = 1/K为先验概率，miu ~[-1,1]为高斯分布的均值，\n",
    "        # sigma = eye为高斯分布的协方差矩阵\n",
    "        self.pi = np.ones(K) / K\n",
    "        self.miu = np.random.rand(K, dim) * 2 - 1\n",
    "        self.sigma = np.zeros((K, dim, dim))\n",
    "        for i in range(K):\n",
    "            self.sigma[i] = np.eye(dim)\n",
    "        \n",
    "    # GMM的E步骤\n",
    "    def E_step(self, X):\n",
    "        # 计算每个数据点被分到不同簇的密度\n",
    "        for i in range(self.K):\n",
    "            self.Y[:, i] = self.pi[i] * gaussian.pdf(X, \\\n",
    "                mean=self.miu[i], cov=self.sigma[i])\n",
    "        # 对密度进行归一化，得到概率分布\n",
    "        self.Y /= self.Y.sum(axis=1, keepdims=True)\n",
    "    \n",
    "    # GMM的M步骤\n",
    "    def M_step(self, X):\n",
    "        # 更新先验概率分布\n",
    "        Y_sum = self.Y.sum(axis=0)\n",
    "        self.pi = Y_sum / self.N\n",
    "        # 更新每个簇的均值\n",
    "        self.miu = np.matmul(self.Y.T, X) / Y_sum[:, None]\n",
    "        # 更新每个簇的协方差矩阵\n",
    "        for i in range(self.K):\n",
    "            # N * 1 * D\n",
    "            delta = np.expand_dims(X, axis=1) - self.miu[i]\n",
    "            # N * D * D\n",
    "            sigma = np.matmul(delta.transpose(0, 2, 1), delta)\n",
    "            # D * D\n",
    "            self.sigma[i] = np.matmul(sigma.transpose(1, 2, 0),\\\n",
    "                self.Y[:, i]) / Y_sum[i]\n",
    "    \n",
    "    # 计算对数似然，用于判断迭代终止\n",
    "    def log_likelihood(self, X):\n",
    "        ll = 0\n",
    "        for x in X:\n",
    "            p = 0\n",
    "            for i in range(self.K):\n",
    "                p += self.pi[i] * gaussian.pdf(x, mean=self.miu[i],\\\n",
    "                    cov=self.sigma[i])\n",
    "            ll += np.log(p)\n",
    "        return ll / self.N\n",
    "    \n",
    "    # 运行GMM算法的E步骤、M步骤迭代循环\n",
    "    def fit(self, X):\n",
    "        self.N = len(X)\n",
    "        self.Y = np.zeros((self.N, self.K))\n",
    "        ll = self.log_likelihood(X)\n",
    "        print('开始迭代')\n",
    "        for i in range(self.max_iter):\n",
    "            self.E_step(X)\n",
    "            self.M_step(X)\n",
    "            new_ll = self.log_likelihood(X)\n",
    "            print(f'第{i}步, log-likelihood = {new_ll:.4f}')\n",
    "            if new_ll - ll < 1e-4:\n",
    "                print('log-likelihood不再变化，退出程序')\n",
    "                break\n",
    "            else:\n",
    "                ll = new_ll\n",
    "    \n",
    "    # 根据学习到的参数将一个数据点分配到概率最大的簇\n",
    "    def transform(self, X):\n",
    "        assert hasattr(self, 'Y') and len(self.Y) == len(X)\n",
    "        return np.argmax(self.Y, axis=1)\n",
    "    \n",
    "    def fit_transform(self, X):\n",
    "        self.fit(X)\n",
    "        return self.transform(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e5c256e",
   "metadata": {},
   "source": [
    "与*k*均值聚类方法类似，在使用最大期望值法的高斯混合的情况下，观察在Books数据集3个真实类别中不同簇的占比："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "259eb004",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "开始迭代\n",
      "第0步, log-likelihood = 77.2685\n",
      "...\n",
      "第10步, log-likelihood = 95.9564\n",
      "...\n",
      "第20步, log-likelihood = 97.8945\n",
      "...\n",
      "第30步, log-likelihood = 98.2401\n",
      "...\n",
      "第39步, log-likelihood = 98.2509\n",
      "log-likelihood不再变化，退出程序\n",
      "[2 0 2 ... 1 2 1]\n",
      "计算机类:\t{ 0: 114(0.03), 1: 1256(0.33), 2: 2472(0.64), }\n",
      "艺术传媒类:\t{ 0: 2129(0.93), 1: 23(0.01), 2: 148(0.06), }\n",
      "经管类:\t{ 0: 268(0.11), 1: 2152(0.87), 2: 65(0.03), }\n"
     ]
    }
   ],
   "source": [
    "# 直接对TF-IDF特征聚类运行速度过慢，因此使用PCA降维，将TF-IDF向量降到50维\n",
    "from sklearn.decomposition import PCA\n",
    "pca = PCA(n_components=50)\n",
    "train_P = pca.fit_transform(train_F)\n",
    "\n",
    "# 运行GMM算法，展示聚类结果\n",
    "gmm = GMM(K, dim=train_P.shape[1])\n",
    "clusters = gmm.fit_transform(train_P)\n",
    "print(clusters)\n",
    "show_clusters(clusters, K)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b58851b6",
   "metadata": {},
   "source": [
    "下面演示基于朴素贝叶斯模型的聚类算法实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "f215a250",
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.special import logsumexp\n",
    "\n",
    "# 无监督朴素贝叶斯\n",
    "class UnsupervisedNaiveBayes:\n",
    "    def __init__(self, K, dim, max_iter=100):\n",
    "        self.K = K\n",
    "        self.dim = dim\n",
    "        self.max_iter = max_iter\n",
    "        \n",
    "        # 初始化参数，pi为先验概率分布，P用于保存K个朴素贝叶斯模型的参数\n",
    "        self.pi = np.ones(K) / K\n",
    "        self.P = np.random.random((K, dim))\n",
    "        self.P /= self.P.sum(axis=1, keepdims=True)\n",
    "        \n",
    "    # E步骤\n",
    "    def E_step(self, X):\n",
    "        # 根据朴素贝叶斯公式，计算每个数据点分配到每个簇的概率分布\n",
    "        for i, x in enumerate(X):\n",
    "            # 由于朴素贝叶斯使用了许多概率连乘，容易导致精度溢出，\n",
    "            # 因此使用对数概率\n",
    "            self.Y[i, :] = np.log(self.pi) + (np.log(self.P) *\\\n",
    "                x).sum(axis=1)\n",
    "            # 使用对数概率、logsumexp和exp，等价于直接计算概率，\n",
    "            # 好处是数值更加稳定\n",
    "            self.Y[i, :] -= logsumexp(self.Y[i, :])\n",
    "            self.Y[i, :] = np.exp(self.Y[i, :])\n",
    "    \n",
    "    # M步骤\n",
    "    def M_step(self, X):\n",
    "        # 根据估计的簇概率分布更新先验概率分布\n",
    "        self.pi = self.Y.sum(axis=0) / self.N\n",
    "        self.pi /= self.pi.sum()\n",
    "        # 更新每个朴素贝叶斯模型的参数\n",
    "        for i in range(self.K):\n",
    "            self.P[i] = (self.Y[:, i:i+1] * X).sum(axis=0) / \\\n",
    "                (self.Y[:, i] * X.sum(axis=1)).sum()\n",
    "        # 防止除0\n",
    "        self.P += 1e-10\n",
    "        self.P /= self.P.sum(axis=1, keepdims=True)\n",
    "    \n",
    "    # 计算对数似然，用于判断迭代终止\n",
    "    def log_likelihood(self, X):\n",
    "        ll = 0\n",
    "        for x in X:\n",
    "            # 使用对数概率和logsumexp防止精度溢出\n",
    "            logp = []\n",
    "            for i in range(self.K):\n",
    "                logp.append(np.log(self.pi[i]) + (np.log(self.P[i]) *\\\n",
    "                    x).sum())\n",
    "            ll += logsumexp(logp)\n",
    "        return ll / len(X)\n",
    "    \n",
    "    # 无监督朴素贝叶斯的迭代循环\n",
    "    def fit(self, X):\n",
    "        self.N = len(X)\n",
    "        self.Y = np.zeros((self.N, self.K))\n",
    "        ll = self.log_likelihood(X)\n",
    "        print(f'初始化log-likelihood = {ll:.4f}')\n",
    "        print('开始迭代')\n",
    "        for i in range(self.max_iter):\n",
    "            self.E_step(X)\n",
    "            self.M_step(X)\n",
    "            new_ll = self.log_likelihood(X)\n",
    "            print(f'第{i}步, log-likelihood = {new_ll:.4f}')\n",
    "            if new_ll - ll < 1e-4:\n",
    "                print('log-likelihood不再变化，退出程序')\n",
    "                break\n",
    "            else:\n",
    "                ll = new_ll\n",
    "    \n",
    "    def transform(self, X):\n",
    "        assert hasattr(self, 'Y') and len(self.Y) == len(X)\n",
    "        return np.argmax(self.Y, axis=1)\n",
    "    \n",
    "    def fit_transform(self, X):\n",
    "        self.fit(X)\n",
    "        return self.transform(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "57113e8b",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "初始化log-likelihood = -779.0355\n",
      "开始迭代\n",
      "第0步, log-likelihood = -589.0541\n",
      "...\n",
      "第10步, log-likelihood = -571.5391\n",
      "...\n",
      "第20步, log-likelihood = -567.4288\n",
      "...\n",
      "第30步, log-likelihood = -567.3908\n",
      "...\n",
      "第38步, log-likelihood = -567.3578\n",
      "log-likelihood不再变化，退出程序\n",
      "[1 2 1 ... 1 1 1]\n",
      "计算机类:\t{ 0: 307(0.08), 1: 3437(0.89), 2: 98(0.03), }\n",
      "艺术传媒类:\t{ 0: 59(0.03), 1: 156(0.07), 2: 2085(0.91), }\n",
      "经管类:\t{ 0: 2252(0.91), 1: 79(0.03), 2: 154(0.06), }\n"
     ]
    }
   ],
   "source": [
    "# 根据朴素贝叶斯模型，需要统计出每个数据点包含的词表中每个词的数目\n",
    "train_C = np.zeros((len(train_X), vocab_size))\n",
    "for i, data in enumerate(train_X):\n",
    "    for token_id in data:\n",
    "        train_C[i, token_id] += 1\n",
    "\n",
    "unb = UnsupervisedNaiveBayes(K, dim=vocab_size, max_iter=100)\n",
    "clusters = unb.fit_transform(train_C)\n",
    "print(clusters)\n",
    "show_clusters(clusters, K)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}