29

本篇推文引自：基于网络的标签空间划分方法预测 CYP450 酶-底物选择性 # 1. 分子描述符计算

本文计算了四种类型的底物分子描述符并把他们当成 4 类特征表示用于机器学习建模，这 4 类特征包括：物化（Physiochemical, PC）特征描述符，mol2vec （M2V）描述符，扩展连接指纹（ECFP）和 Molecular ACCess System（MACCS） 密匙指纹。

在计算物化性质描述符时，通过使用一个经 Python 开源的化学信息包 RDKit（http://www.rdkit.org/）生成了 200 个描述底物性质的物化特征；通过使用药物研发可视化仿真软件（Molecular Operating Environment, MOE）生成了313个描述底物性质的物化特征。通过对两种不同方式获得的物化特征进行去重，最终得到了 478 个物化性质描述符。

Mol2vec 是一种受自然语言处理（Natural Language Processing, NLP）启发的技术，它将源自 Morgan 算法的复合子结构视为“单词”，将该复合结构视为“句子”。Word2vec 是一种基于神经网络的方法，在传统的文本挖掘分析中非常方便，其有助于更好地表示数据：彼此相似的单词有相似的向量，而彼此不相似的单词有不同的向量，这可以很好地将相似的单词描绘成计算机语言。在Word2vec模型中，紧密相关单词的向量在向量空间中非常接近，Mol2vec方法通过在化合物集合上训练一种无监督的机器学习方法，可以获得分子子结构矢量表示，它首先对未标记的数据集进行训练，得到子结构的特征向量，然后对特征向量求和，得到复合向量。本研究以该复合向量作为 mol2vec 描述符，共使用 300 个 mol2vec 描述符进行建模。

MACCS 密匙指纹是一种快速筛选分子数据库中子结构的方法，常被用来计算 化学相似性。据了解，官方研究版的 MACCS 密匙总共包含 166 位，其中的每一位都对应着一个特定的分子标记，比如其对应编号为 NO.154 的键代表羰基，即在 MACCS 密匙指纹第 154 维的特征上，“1”表示有这个分子标记，“0” 表示不存在这一分子标记。

无论是在从诱饵中分离活性物的虚拟筛选方面，还是在根据相似度对不同结构进行搜索排序方面，ECFP 分子指纹都有很好的表现。有研究表明，为了获得更好的表现，超过 1024 维的 ECFP 分子指纹是值得被生成并用于建模的。所以， 在本研究中，选择了 2048 维的 ECFP分子指纹进行建模。

总的来说，选择了 478 个物化性质描述符、300 个 mol2vec 描述符、2048 维 ECFP 分子指纹和 166 位 MACCS 密匙指纹进行模型训练。对这些特征进行了预处理，包括去掉全为 0 或全为 1 的列以及标准化。采取的标准化方法为最大最小值标准化方法，即每一个特征的数值都通过减去该特征数值范围内的最小值并除以数值范围，从而被标准化为 0 到 1 之间。然后，对这 4 类特征进行了基于基准模型 ML-kNN 的 15 种不同特征组合验证，通过计算得到了表现性能最佳的特征组合用于建模。

2. 建模技术

在本研究中，使用了几种不同的多标签分类算法来构建“CYP450 酶-底物 选择性”研究的分类模型。在模型验证阶段，首先选择了一种与“WhichP450” 5一文一样的验证方法——在全数据集（未划分训练集与测试集）上进行 5 折交 叉验证（CV）。其次，第二种验证方法在全数据集上进行了训练集与测试集的划分——留出法验证（HO）。考虑到数据集样本数有限，所以按照 85%:15% 的比例划分了训练集与验证集，然后在训练集上进行了建模训练。为了减少数据集划分带来的偏差，随机打乱了数据集（每次设置一个随机种子），然后在 CV 方法和 HO 方法两种验证方法的基础上，所有模型均重复了 10 次建模过程，在 5 折 CV 的验证下，50 次实验结果的平均值被当作衡量每一个模型表现的最终指标。

在本研究中，使用了多标签 k 近邻算法（ML-kNN）、多标签双支持向量机算法（Multi-label Twin Support Vector Machine, MLTSVM）和 5 种基于网络的标签空间划分（NLSD）算法（NLSD-MLP, NLSD-XGB, NLSD-EXT, NLSD-RF, NLSD-SVM）进行建模。

2.1 多标签 k 近邻算法（ML-kNN）

采用了 ML-kNN 作为本研究的基准模型。它是一种基于传统 k 近邻（kNearest Neighbor, kNN）的惰性学习方法。对于一个给定的新样本，ML-kNN 算法首先在训练集中找到最接近它的前 k 个样本。接着，k 样本中每个标签的数量得以计算。在上述标签数的基础上，ML-kNN 算法利用朴素贝叶斯方法估计标签概率。最后，通过最大后验估计得到标签的预测概率。ML-kNN 算法现在被广泛运用于多标签分类预测的任务并且取得了令人较为满意的结果，所以我们选 择该算法作为本研究的基准模型。

2.2 多标签双支持向量机算法（MLTSVM）

MLTSVM 是最近提出的针对多标签场景而设计的双支持向量机的变型算法。比起双支持向量机（Twin Support Vector Machine, TSVM），MLTSVM 放宽了 SVM 中分离超平面的并行约束，提高了训练速度。但是比起其他多标签分类算法，MLTSVM 模型的计算速度还有较大提升空间。

2.3 基于网络的标签空间划分算法（NLSD-X）

我们主要采取了基于网络的标签空间划分算法（NLSD-X）用于本研究的多标 签分类预测。随机 k 标签集多标签分类算法（RAkEL）将标签空间划分成了 k 个 预定义好的子集，其子集 k 的划分是任意选择的，没有包含标签相关性。与成熟的多标签监督学习 RAkEL 的标签空间划分方法不同，NLSD-X 算法利用社交网 络研究领域的社区检测方法，以数据驱动的方式对标签空间进行划分，该算法已 经很好地应用于多个多标签分类的基准数据集。

接着我们探讨一下如何将复杂的社区检测方法应用到数据驱动的基于标签空间划分的多标签分类算法中。在这个场景中，我们像 RAkEL 一样转换问题，但是我们不执行随机的空间划分，而是从训练数据中构造一个标签共出现图，并在这个图上执行社区检测以获得标签空间划分。NLSD-X 算法对模型进行预测及分类的步骤如下：

(Ⅰ) 构建标签共出现图

我们构造了如下的标签共出现图。我们从一个无向共出现图 G 开始，标签集 L 作为点的集合，所有标签对构成边的集合，这些标签对至少一次被分配到训练集中的一个输入对象x^-上（l_i,j表示标签，是集合L中的元素）。

通过定义一个函数 w：L→N，可以将这个未加权的标签共出现图扩展为一个 加权的标签共出现图。每一个标签对的权重定义为： 标签空间中出现过的每一个标签对以及相应的权重都可以通过上述方式计算得到，他们共同组成了标签共出现图。

公式(3-1)—(3-2)的过程可以进行如图 3-1 所示更为清晰的可视化展示。其中， 样本 A 的标签为(1,1,1,0)，那么其对应位置的标签对则可以表示为“1-2”、“1-3” 及“2-3”。样本 B 的标签为(0,1,1,1)，那么其对应位置的标签对则可以表示为“2- 3”、“2-4”及“3-4”。以 A、B 两个样本为例，其对应的标签共出现图可表示为图 3-1。我们可以从图 3-1 中看到，“2-3”这个标签对在整个空间中结构相对紧密， 在 A、B 两个样本的标签对集合中，该标签对出现过 2 次，其在共出现图中所占的权重即为 2。

(Ⅱ) 通过社区检测划分标签空间

一个社区由一组紧密连接的节点组成，而这些节点与该社区外部的节点连接 较稀疏，如图 3-2 所示。社区检测（Community Detection）就是在复杂的网络结构中发现这些紧密连接的社区结构。换句话说，社区检测就是发现网络中的节点集群。

①Newman 快速贪婪算法 在 Newman 快速贪婪算法中，我们先定义一个模块度的概念。模块度表述一 个社区划分结果的好坏，一个相对好的划分在社区内的节点相似度较高，而在社 区外的节点相似度较低。我们分别来讨论一下全局模块度及局部模块度的定义。

假设全网络的数据已知，我们可以进行全局模块度的定义。

假设 Mab 为网络中相邻矩阵的一个元素，如果点 a 和点 b 是连接的，那么 Mab = 1；如果点 a 和点 b 没有连接，那么 Mab = 0。

假设 Ca 和 Cb 分别代表了点 a 和点 b 所在的两个社区，n 代表图网络中边的总数，那么该社区内部的边数与网络中边的总数的比值为： 其中函数δ（Ca，Cb）表示：如果点 a 和点 b 在同一个社区，则 Ca = Cb，此时δ（Ca，Cb）=1；如果点 a 和点 b 不在同一个社区，则δ（Ca，Cb）=0。

模块度大小的定义为社区内部的边数与网络中边的总数的比值减掉一个期望 值，该期望值的定义是随机状态下的高斯分布网络中同样的社区分配形成的社区 内部的边数与网络中边的总数的比值大小，将点 a 的度表示为：da=ΣbMab,所以模块度 Q 的定义为： 对上述公式进行整理，假设R_ij表述社区 i 和社区 j 内部的边数与网络中边的总数的比值，C_i 表示社区 i 内部的点相连的所有边数与网络中边的总数的比值。我们可以得到：

对模块度 Q 的计算进行简化，假设网络此时已被划分成 m 个社区，此时就生 成了一个 m 维矩阵，我们将公式(3-5)与公式(3-6)代入公式(3-4)，模块度 Q 的计算可以变成：

假设我们不知道全网络的数据，我们可以进行局部模块度的定义，从而检查社区划分的合理性。

假设有一个已经被检测出的社区 C，该社区点的集合为 V，与这些点相连的邻 接点加入到集合 V 中，共同构成新集合V。我们可以定义V的邻接矩阵为P_ab， 如果点 a 和点 b 有连接且点 a 和点 b 至少有一个属于集合 V 时，P_ab= 1；否则，P_ab= 0。

与上述全局模块度相似的是，可以用节点新集合V*中属于节点集合 V 中的元素的比值大小来评判一个社区划分的好坏：

其中函数δ（Ca，Cb）表示：如果点 a 和点 b 在集合V中，则δ（Ca，Cb）=1；否则δ（Ca，Cb）=0。n*表示邻接矩阵P_ab内部边的总数。

基于模块化的方法，便是最大化上述模块度 Q 值，从而实现最好的标签空间 划分。Newman 快速贪婪算法（fast greedy）是基于 Newman 等人研究的最大化模 块度进行标签空间划分的一种方法。快速贪婪方法基于贪婪的社区检测，从 单例开始迭代合并社区。在每一次迭代中，该算法会合并两个社区，并在此基础上实现对模块化结构的最大贡献。当没有可能增大当前社区的模块度值的合并时， 则定义为收敛，整个网络经迭代合并成一个社团，其计算复杂度为O (Nlog² (N))。

②标签传播算法 标签传播算法（Label Propagation Algorithm, LPA）是基于图的半监督学习算 法，该算法为图中的每个顶点分配一个唯一的标签。基本思路是从已标记的节点标签信息来预测未标记的节点标签信息。在标签传播过程中，每个节点保持已标记的数据的标签不变，将标签按相似度传播给相邻未标记的节点，更新顺序在每次迭代中随机选择，当所有的顶点的标记都与其邻域内的主标记一致记时，算法就停止迭代。

上一节中我们定义了权重w(λi,λj)，假设数据集中有 a 个标记数据，b 个未标记数据，我们可以定义传播矩阵 M ∈(a + b)×(a + b)，M_ij表示标签 j 传播到标签 i 的概率： 定义标签矩阵（soft label 矩阵）Y∈(a + b)×C，Y_i,C= 1 表示节点y_i的标签为 C。

基于上述定义，LPA 开始执行传播，每个节点按照传播概率Mi,j将周围节点传 来的标签值按照相应的权重w(λi,λj)相加，并且更新入自身节点的概率分布，Y^t = M×Y^t-1。迭代 Y 中已标记的标签，保持已标记的数据的标签不变，将Y^t重新赋值给初始值，算法不断迭代上述过程，直到 Y 收敛。

标签传播法的时间复杂度接近于线性，假设对顶点进行分配标签的复杂度为O(N)，每次迭代所需时间为 O(M)，那么在网络中找出所有社区的复杂度即为O(N+M)。

(Ⅲ) 对于每一个社区L_i，使用社区L_i中出现的标签列作为原始输入空间去创建一个新的训练数据集D_i。

(Ⅳ) 最后，对每一个社区，我们在训练集D_i上学习，得到分类器h_i。

(Ⅴ) 分类阶段是通过对训练阶段检测到的所有子空间进行分类，并获取分配标签的并集，获得最终的分类器 最终，我们采取了标签传播法进行标签空间划分并使用了 5 种算法作为多分 类器来共同构成 NLSD-X 算法，包括：多层感知器（Multi-Layer Perceptron, MLP）、极端梯度提升（eXtreme Gradient Boosting, XGB）、极限树（EXtra Tree, EXT）、随机森林（Random Forest, RF）和支持向量机（Support Vector Machines, SVM），获得了对应的基于网络的标签空间划分方法 NLSD-MLP、NLSD-XGB、NLSDEXT、NLSD-RF 和 NLSD-SVM。

3. 小结

主要介绍了进行“基于网络的标签空间划分方法预测 CYP450 酶 -底物选择性”研究时涉及到的底物分子描述符计算技术、建模技术。

在计算底物分子描述符部分，我们计算了 4 种类型的底物分子描述符并把他们当成 4 类特征表示用于机器学习建模，这 4 类特征包括：PC 描述符， M2V 描述符，ECFP 分子指纹和 MACCS 密匙指纹。然后，我们对这 4 类特征进行了基于基准模型 ML-kNN 的 15 种不同特征组合验证，通过计算得到了表现性能最佳的特征组合用于建模。

在建模部分，使用了 ML-kNN、 MLTSVM 和 5 种基于网络的标签空间划分算法（NLSD-X）进行建模研究。详细介绍了 NLSD-X 算法对模型进行预测 及分类的步骤：

(Ⅰ)基于训练数据集构造标签共出现图。 (Ⅱ)在标签共出现图上执行选定的社区检测算法，通过社区检测划分标签空间， 我们比较了快速贪婪算法及标签传播法。 (Ⅲ)对于每一个社区 Li，使用社区 Li 中出现的标签列作为原始输入空间去创 建一个新的训练数据集 Di。 (Ⅳ)最后，对每一个社区，在训练集 Di 上学习从而得到分类器 hi。 (Ⅴ)分类阶段是通过对训练阶段检测到的所有子空间进行分类，并获取分配标签的并集，获得最终的分类器 最终，我们采取了标签传播法进行标签空间划分并使用了 5 种算法作为底层多分类器来共同构成 NLSD-X 算法，包括：MLP、XGB、EXT、RF 和 SVM，从 而获得了对应的基于网络的标签空间划分方法 NLSD-MLP、NLSD-XGB、NLSDEXT、NLSD-RF 和 NLSD-SVM。

本篇文章引自：基于网络的标签空间划分方法预测CYP450 酶-底物选择性