Complex_Network_Analysis/链路预测_评价指标.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#AUC\" data-toc-modified-id=\"AUC-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>AUC</a></span><ul class=\"toc-item\"><li><span><a href=\"#代码\" data-toc-modified-id=\"代码-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>代码</a></span></li><li><span><a href=\"#测试\" data-toc-modified-id=\"测试-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>测试</a></span></li></ul></li><li><span><a href=\"#精确度\" data-toc-modified-id=\"精确度-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>精确度</a></span></li><li><span><a href=\"#排序分数-Ranking-Score\" data-toc-modified-id=\"排序分数-Ranking-Score-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>排序分数 Ranking Score</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* AUC :最常用， 整体上衡量算法的精确度\n",
    "\n",
    "\n",
    "* Precision ： 只考虑排在前 L 维 的边是否预测准确\n",
    "\n",
    "\n",
    "* Ranking Score ： 考虑预测边的排序\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  AUC\n",
    "\n",
    "> AUC 指的是  ROC 曲线下的面积， 其中ROC 在信号探测中用来评价某种分类器的分类效果\n",
    "\n",
    "AUC 可以理解为 在测试集中随机选择一条边的分数值比随机选择一条不存在的边的分数值高的概率。\n",
    "\n",
    "\n",
    "* 每次随机从测试集中选择一条边，再从不存在边中随机选择一条，如果测试集中边分数值大于不存在的边的分数值， 就 +1 ， 如果两个相等， 就 +0.5， \n",
    "\n",
    "* 重复上述步骤 n 次， 假设 $n_{1}$ 次大于， $n_{2}$ 次分数相等\n",
    "\n",
    "\n",
    "$$AUC = \\frac{n_{1} + 0.5 n_{2}}{n}$$\n",
    "\n",
    "\n",
    "\n",
    "**AUC 对样本类别是否均衡并不敏感**\n",
    "\n",
    "\n",
    "\n",
    "**训练集选择的比例不同， AUC 值会相应的变化，一般来说， 训练集越大， AUC的 值越高**\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:23:01.046117Z",
     "start_time": "2019-10-30T09:22:59.529199Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import pandas as pd\n",
    "import networkx as nx\n",
    "from scipy import sparse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:29:31.587155Z",
     "start_time": "2019-10-30T09:29:31.570165Z"
    }
   },
   "outputs": [],
   "source": [
    "def CalcAUC(MatrixAdjacency_train, MatrixAdjacency_test, Matrix_similarity, n):\n",
    "    \"\"\"\n",
    "    计算 AUC\n",
    "    \n",
    "    n : 抽样比较的次数\n",
    "    \"\"\"\n",
    "\n",
    "    # 只保留测试集和不存在边集合中的边的相似度（ 不保留自环）\n",
    "    Matrix_similarity = np.triu(Matrix_similarity -\n",
    "                                Matrix_similarity * MatrixAdjacency_train)\n",
    "\n",
    "    Matrix_noexist = np.ones_like(\n",
    "        MatrixAdjacency_train\n",
    "    ) - MatrixAdjacency_train - MatrixAdjacency_test - np.eye(\n",
    "        MatrixAdjacency_train.shape[0])\n",
    "\n",
    "    # 取测试集和不存在边集合的上三角矩阵， 取出对应的相似度分值\n",
    "    Test = np.triu(MatrixAdjacency_test)\n",
    "    NoExist = np.triu(Matrix_noexist)\n",
    "\n",
    "    #Test_num = np.count_nonzero(Test)\n",
    "    #Non_num = np.count_nonzero(NoExist)\n",
    "\n",
    "    Test_num = len(np.argwhere(Test == 1))\n",
    "    Non_num = len(np.argwhere(NoExist == 1))\n",
    "\n",
    "    \n",
    "    # !!! 创建的随机是 正态分布， 选取其他的分布\n",
    "    Test_rd = [int(x) for x in np.random.rand(1, n)[0] * Test_num]\n",
    "    Non_rd = [int(x) for x in np.random.rand(1, n)[0] * Non_num]\n",
    "\n",
    "    Test_pre = Matrix_similarity * Test\n",
    "    Non_pre = Matrix_similarity * NoExist\n",
    "\n",
    "    # test 集合存在的边的预测值\n",
    "\n",
    "    Test_index = np.argwhere(Test == 1)\n",
    "    Test_data = np.array([Test_pre[x[0], x[1]] for x in Test_index]).T\n",
    "\n",
    "    # 不存在边的集合的边的预测值\n",
    "    Non_index = np.argwhere(NoExist == 1)\n",
    "    Non_data = np.array([Non_pre[x[0], x[1]] for x in Non_index]).T\n",
    "\n",
    "    Test_rd_2 = np.array([Test_data[i] for index, i in enumerate(Test_rd)])\n",
    "    Non_rd_2 = np.array([Non_data[i] for index, i in enumerate(Non_rd)])\n",
    "\n",
    "    n1, n2 = 0, 0\n",
    "\n",
    "    for cal_times in range(n):\n",
    "        if Test_rd_2[cal_times] > Non_rd_2[cal_times]:\n",
    "            n1 += 1\n",
    "        elif Test_rd_2[cal_times] == Non_rd_2[cal_times]:\n",
    "            n2 += 1\n",
    "\n",
    "    auc = (n1 + 0.5 * n2) / n\n",
    "\n",
    "    return auc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:23:05.661642Z",
     "start_time": "2019-10-30T09:23:05.640442Z"
    },
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "def spones(array):\n",
    "    \"\"\"\n",
    "    将矩阵中的非零元素全部替换为 1 \n",
    "    \"\"\"\n",
    "    sparse_array = sparse.csr_matrix(array)  # 转换为稀疏矩阵\n",
    "    sparse_array.data.fill(1)  # 稀疏矩阵全部替换为 1\n",
    "    array = sparse_array.toarray()  # 返回密集矩阵\n",
    "\n",
    "    return array\n",
    "\n",
    "\n",
    "def DivideNet(MatrixAdajacency, ratioTrain):\n",
    "    \"\"\"\n",
    "    划分训练集和测试集\n",
    "    \n",
    "    保证网络训练集连通\n",
    "    \"\"\"\n",
    "\n",
    "    # 测试集的连边数目\n",
    "    num_testlinks = int(\n",
    "        (1 - ratioTrain) * np.count_nonzero(MatrixAdajacency) / 2)\n",
    "    # 将邻接矩阵中所有的边找出来 存储到 linklist 中\n",
    "    linklist = [list(i) for i in np.argwhere(np.triu(MatrixAdajacency))]\n",
    "    # 为每条边都设置标志位 ， 判断是否能够删除\n",
    "    MatrixAdajacency_test = np.zeros(shape=(np.shape(MatrixAdajacency)[0],\n",
    "                                            np.shape(MatrixAdajacency)[1]))\n",
    "\n",
    "    while (np.count_nonzero(MatrixAdajacency_test) < num_testlinks):\n",
    "\n",
    "        ### 随机选择一条边\n",
    "        link_index = int(np.random.rand(1) * len(linklist))\n",
    "        uid1 = linklist[link_index][0]  # 边两端的节点 1\n",
    "        uid2 = linklist[link_index][1]\n",
    "\n",
    "        ### 判断所选边两端节点 uid1 和 uid2 是否可达， 若可达则放入测试集， 否则重新选边\n",
    "        # 将这条边从网络中挖去，\n",
    "        MatrixAdajacency[uid1, uid2] = 0\n",
    "        MatrixAdajacency[uid2, uid1] = 0\n",
    "\n",
    "        tempvector = MatrixAdajacency[uid1]  # 取出 uid1  一步可达的点 构成一维向量\n",
    "        sign = 0  # 标记此边是否可以被移除，  sign = 0 表示不可， sign = 1 表示可以\n",
    "        uid1TOuid2 = np.dot(tempvector,\n",
    "                            MatrixAdajacency) + tempvector  # 表示 uid1 2步内可达的点\n",
    "\n",
    "        if uid1TOuid2[0, uid2] > 0:\n",
    "            sign = 1  # 两步即可到达\n",
    "        else:\n",
    "\n",
    "            count = 1\n",
    "            while (len((spones(uid1TOuid2) - tempvector).nonzero()[0]) != 0):\n",
    "                # 直到可达的点到达稳定状态， 仍然不能到达 uid2， 此边就不能删除\n",
    "                tempvector = spones(uid1TOuid2)\n",
    "                uid1TOuid2 = np.dot(\n",
    "                    tempvector, MatrixAdajacency) + tempvector  # 表示 K 步 内可达的点\n",
    "                count += 1\n",
    "                if uid1TOuid2[0, uid2] > 0:\n",
    "                    sign = 1  # 某步内可以到达\n",
    "                    break\n",
    "\n",
    "                if count >= MatrixAdajacency.shape[0]:\n",
    "                    print(\"不可达\" + str([uid1, uid2]))\n",
    "                    sign = 0\n",
    "\n",
    "        ### 如果边可以删除， 将其放入测试集中， 并从 link 集中删除\n",
    "        if sign == 1:\n",
    "            linklist.pop(link_index)\n",
    "            MatrixAdajacency_test[uid1, uid2] = 1\n",
    "\n",
    "        ### 如果不可以删除， 恢复原始矩阵， 也从 link 集中删除\n",
    "        else:\n",
    "            linklist.pop(link_index)\n",
    "            MatrixAdajacency[uid1, uid2] = 1\n",
    "            MatrixAdajacency[uid2, uid1] = 1\n",
    "\n",
    "    MatrixAdajacency_Train = MatrixAdajacency\n",
    "    MatrixAdajacency_Test = MatrixAdajacency_test + MatrixAdajacency_test.T\n",
    "\n",
    "    print('    训练集计划边数：' +\n",
    "          str(np.count_nonzero(MatrixAdajacency) - num_testlinks))\n",
    "    print('    训练集实际边数：' + str(np.count_nonzero(MatrixAdajacency_Train)))\n",
    "    print('    测试集计划边数：' + str(num_testlinks))\n",
    "    print('    测试集实际边数：' + str(np.count_nonzero(MatrixAdajacency_Test)))\n",
    "\n",
    "    return MatrixAdajacency_Train, MatrixAdajacency_Test\n",
    "\n",
    "\n",
    "def check_symmetric(a, tol=1e-8):\n",
    "    \"\"\"\n",
    "    检查是否是 对称矩阵\n",
    "    \"\"\"\n",
    "    return np.allclose(a, a.T, atol=tol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:23:06.678495Z",
     "start_time": "2019-10-30T09:23:06.506469Z"
    },
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "edge_lst = []\n",
    "with open(\"lit-bm-13.txt\",\"r\") as file_txt: # 蛋白质相互作用数据集\n",
    "    for i, line in enumerate(file_txt.readlines()):\n",
    "        edge_tpl =  str(line.split()[0]), str(line.split()[1]),{'weight': 1}\n",
    "        edge_lst.append(edge_tpl)\n",
    "\n",
    "F = nx.from_edgelist(edge_lst)\n",
    "df = nx.to_pandas_adjacency(F)\n",
    "data = np.matrix(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:23:45.597826Z",
     "start_time": "2019-10-30T09:23:07.895736Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    训练集计划边数：7964\n",
      "    训练集实际边数：8428\n",
      "    测试集计划边数：464\n",
      "    测试集实际边数：866\n"
     ]
    }
   ],
   "source": [
    "train , test = DivideNet(data.copy(), 0.9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:23:47.512836Z",
     "start_time": "2019-10-30T09:23:47.507585Z"
    },
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "def Cn(MatrixAdjacency_Train):\n",
    "    \"\"\"\n",
    "    共同邻居算法\n",
    "    \"\"\"\n",
    "    Matrix_similarity = np.dot(MatrixAdjacency_Train,MatrixAdjacency_Train)\n",
    "    return Matrix_similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:23:50.001585Z",
     "start_time": "2019-10-30T09:23:49.068348Z"
    }
   },
   "outputs": [],
   "source": [
    "Matrix_similarity = Cn(train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:31:00.864262Z",
     "start_time": "2019-10-30T09:30:54.832766Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "402\n",
      "5743357\n",
      "(402,)\n"
     ]
    }
   ],
   "source": [
    "auc = CalcAUC(train, test, Matrix_similarity,  400000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-30T09:31:02.311613Z",
     "start_time": "2019-10-30T09:31:02.304493Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.2609425"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "auc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 精确度\n",
    "\n",
    "不关注所有的预测结果， 只关注预测的前面的几条边是否预测的较为准确\n",
    "\n",
    "> 在PPI 之中， 前面几个的预测结果较为准确，可以直接进行试验验证\n",
    "\n",
    "\n",
    "**定义： 前 L 个预测的边之中， 预测准确的比例**\n",
    "\n",
    "$$Presicion = \\frac{m}{L}$$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 排序分数 Ranking Score \n",
    "\n",
    "考虑测试集中边在最终排序中的位置\n",
    "\n",
    "\n",
    "$H = U - E^{T}$ 为未知边的集合\n",
    "\n",
    "\n",
    "$r_{e}$ 表示测试边 e 在排序中的排名\n",
    "\n",
    "\n",
    "测试边的排序分 ：\n",
    "\n",
    "\n",
    "$$RS_{e} = \\frac{r_{e}}{|H|}$$\n",
    "\n",
    "\n",
    "遍历所有的边求平均值\n",
    "\n",
    "\n",
    "--------\n",
    "\n",
    "**排序的分值越小，说明预测的效果越好**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "oldHeight": 488,
   "position": {
    "height": "40px",
    "left": "1060px",
    "right": "20px",
    "top": "120px",
    "width": "360px"
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "varInspector_section_display": "none",
   "window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}