基于复杂网络模型并行化标签传播算法的药物社团发现方法

摘要

本发明提供一种基于复杂网络模型并行化标签传播算法的药物社团发现方法，包括如下步骤：组网阶段：a)预处理生成中药数据集，格式化为文本数据；b)将初始文本数据部署至Hadoop平台；c)并行化组建中药药物(Traditional Chinese Medicine简称TCM)网络；d)结束。挖掘阶段：a)获取步骤1-c处理生成的TCM网络文本文件；b)将TCM网络文本文件部署至Hadoop平台；c)实施并行化标签传播算法发现药物社团；d)结束。本发明的基于复杂网络模型并行化标签传播算法的药物社团发现方法建立了TCM网络模型，利用并行化技术提高了组网以及标签传播算法的可扩展性和运行速度，并且能有效挖掘复方中药性相似的药物社团，帮助研究中药配伍规律。

说明书

技术领域

本发明涉及一种中药复杂网络建模方法，以及在该中药药物复杂 网络TCM上采用并行标签传播算法挖掘中药药物社团的技术。

背景技术

利用数据挖掘技术可以智能分析中药复方数据，发现潜在中药配 伍规律。常用的中药数据挖掘中有一类应用是药物的聚类算法，其基 于事务项模型(把复方看成由多种药物组成的事务并储存在事务数据 库中)对相似药物进行聚合以发现频繁组方的药物组。传统基于事务 项模型的中药药物聚类算法很难挖掘间接组方配伍的药物，而且往往 忽略对生僻药物的处理，不利于深入研究每种药物的配伍规律知识。 本发明尝试用复杂网络模型建模中药药物网络，在药物网络中应用社 团发现算法挖掘药性相似的药物组。

在复杂网络分析中对网络社团结构的研究已经有很长的历史，其 涉及到计算机科学、社会学、生命科学等各个领域。分析和揭示网络 中的社团结构，对于了解网络结构与分析网络特性都是非常重要的。 在中药复杂网络中进行社团发现与传统基于事务项模型的药物聚类 分析的目的很相近，都是将频繁在一起组方的药物聚合在同一类别中， 并挖掘出药性相似的药物以便研究中药配伍规律。

基于复杂网络模型构建中药药物复杂网络这一思路打破了传统 中药数据挖掘都基于事务项的建模模型的惯例，并且采用复杂网络分 析中的标签传播算法可以深入挖掘中药药物社团，发现药性相似、社 团内部相对频繁组方的药物组，克服了传统基于事务项聚类算法不能 发现间接配伍以及忽略生僻药物的缺陷。

近期以来，随着中药复方数据的激增，非并行的算法已不再适用 于较大规模中药数据的社团发现。

发明内容

本发明所要解决的技术问题是实现中药复杂网络建模，并在该模 型上采用并行标签传播算法，以快速有效地发现药物社团。

为解决上述问题，本发明的基于复杂网络模型并行化标签传播算 法的药物社团发现方法包括如下步骤：

1)组网阶段：

a预处理以生成中药数据集，格式化为初始文本数据；

b将初始文本数据部署至Hadoop平台；

c并行化组建中药药物网络，即TCM网络，该网络以药物为节 点，将SC_AB大于给定阈值的节点连边；

d结束。

2)挖掘阶段：

a获取步骤1)-c处理生成的中药药物网络文本文件；

b将上述TCM网络文本文件部署至Hadoop平台；

c实施并行化标签传播算法，即采用MapReduce框架并行化的标 签传播算法，利用节点邻居信息迭代更新自身标签(即所属社团号)， 以发现药物社团；

d)结束。

步骤1)-a中所说的预处理为抽取中药复方数据中所有复方的药 物组成。

步骤1)-b中所说的部署为将步骤1)-a生成的初始文本数据上传 至Hadoop平台的分布式文件系统(HDFS)。

进一步，步骤1)-c的具体过程如下：

1)为每个中药复方，即一行文本数据，设定一个唯一标识ID

2)建立从药物到复方标识ID之间的倒排索引；

3)为每个药物设定唯一药物标识id，其中包含该药物在复方中出 现的频次；

4)对倒排索引进行还原，即再次实行倒排索引算法，每行复方 读入此次任务的某个Map函数中，还原中药复方文本数据；

5)每个Map函数读取一行文本，解析出药物节点信息；

6)判断该Map函数中的复方所含药物还能否两两组建联合键值 <Key，Value>，是则执行7)，否则执行8)；

7)组建联合键值<Key，Value>；

8)<Key，Value>经过shuffle&&sort发送到Reduce中，Reduce接收 相同Key下组成的[Value]数组，按照下式计算两两药物间度量，将大 于设定阈值的药对写入文件并保存至HDFS中

${\mathrm{SC}}_{\mathrm{AB}}=\frac{|F_A\cap F_B|}{\min \left\{\right|F_A|,|F_B\left|\right\}}$

其中|F_A∩F_B|表示药物A、B一起组方的次数，min{|F_A|，|F_B|}表示 药物A、B中组方次数较少的药物的出现次数，而SC_AB表示药物A、B 共现次数与最少出现药物次数的比率；

9)读取6)中生成的药对文件，即药物复杂网络的边集，格式化为 邻接表形式保存中药网络拓扑结构；

10)结束。

进一步，步骤2)-c中利用邻居节点所属标签更新自身标签(一般 为频次最大的标签，如果最大频次标签有多个则采取一定的随机选 择)。并行化标签传播算法总过程是基于迭代式的，迭代终止条件是 各节点标签基本稳定，例如大于90％的节点标签不发生变化等。在此 给出迭代步骤中的某次迭代算法流程，即其中并行化标签传播算法的 一次迭代过程具体如下：：

1)为每个药物节点设置唯一的初始标签id；

2)每个Map函数从HDFS读取一行文本，存入Value变量中；

3)解析Value变量中的数据，用临时数组Tmp[0]保存节点id， Tmp[1]保存邻接表AdjList及Label；

4)发送节点数据结构；

5)判断Label中是否只含有一个标签，即首次迭代，执行6)，否 则执行7)；

6)令变量V＝标签1；

7)令变量V＝标签1&&标签2，其中标签1表示t-1次迭代的标签 和标签2表示t-2次迭代的标签；

8)令变量i＝0；

9)判断i是否小于AdjList.length，是则执行步骤10，否则执行 步骤12

10)发送<AdjList.get(i)，V>

11)i自增1，执行8)；

12)Map过程结束，Hadoop执行shuffle&&sort；

13)Reduce解析[Value]数组，分别用数据结构AdjLabelPA保存节点 结构，临时链表ls₁，ls₂分别保存每个传递过来的l₁、l₂的值(如果有两 个标签，否则ls₂为空)

14)根据下式找出新的节点标签；

$C_x\left(t\right)=f(C_{x_1}(t-1),...,C_{x_k}(t-1),w*C_{x_1}(t-2),...,w*C_{x_k}(t-2))$

15)其中表示t-1次迭代x_k节点的标签，f函数返回的是 邻居节点传递过来频次最多的标记；

16)更新AdjLabel中的t-1标签和t标签分别为C_x(t-1)与 C_x(t)；

17)保存此次迭代的结果至分布式文件系统HDFS中；

18)结束。

本发明的基于复杂网络模型并行化标签传播算法的药物社团发 现方法建立了中药药物复杂网络模型，利用并行化技术提高了组网以 及标签传播算法的可扩展性和运行速度，并且能有效挖掘复方中药性 相似的药物社团，帮助研究中药配伍规律。

附图说明

图1为药物社团发现操作流程图。

图2为本发明的基于复杂网络模型并行化标签传播算法的药物 社团发现方法的流程图。

图3为生成中药药物(TCM)网络的流程图。

图4为在中药药物(TCM)网络上利用标签传播算法(某一次迭代) 挖掘药物社团的流程图。

具体实施方式

为了更了解本发明的技术内容，特举具体实施例并配合所附图式 说明如下。

如图1所示，核心药物挖掘通过方剂数据库查询、不规则文本数 据提取等获取中药复方数据，经数据规范化、格式化等预处理生成文 本数据，然后在Hadoop平台上并行化组建中药药物复杂网络，最后 在该网络上运行并行化标签传播算法以挖掘药物社团。

中药复方数据组网与行化标签传播算法挖掘药物社团是该发明 的主要步骤，本发明的思路就是通过复杂网络建模和并行化标签传播 算法有效挖掘药物社团，同时提高算法可扩展性和运行速度。

本发明的基于复杂网络模型并行化标签传播算法的药物社团发 现方法的流程图如图2所示。

步骤0为本发明的药物社团发现方法的起始状态；

在组网阶段(步骤1-3)，步骤1是从数据库或者其他不规则文本 数据中获取初始的中药复方组网数据，并且格式化为文本数据以便上 传至Hadoop平台的分布式文件系统(HDFS)；

步骤2是在初始数据集中并行组建中药药物(TCM)网络，包括两 次倒排索引以及两两组建药对联合键值对；

步骤3是把生成的TCM网络保存至Hadoop平台的HDFS。

在挖掘阶段(步骤4-5)，步骤4，在步骤3所生成的TCM网络中 运行并行化标签传播算法；

步骤5是将挖掘出的结果保存至HDFS；

步骤6是本发明的基于复杂网络模型并行化标签传播算法的药 物社团发现方法的结束步骤。

图3是对图2中步骤2的详细描述。

步骤20为起始步骤；

步骤21是为每个中药复方设定一个唯一的ID值，从标号1开始；

步骤22是建立药物到复方ID的倒排索引；

步骤23是为每个药物设定id，从标号1％N，其中N表示该药物 在复方中出现的频次，即倒排索引的长度；

步骤24对倒排索引进行还原，即再次实行倒排索引算法，每行 复方读入此次任务的某个Map函数中；

步骤25判断该Map函数中的复方所含药物还能否两两组建联合 键值，可以即执行26，否则执行27(注意此时应该是说该次任务的 Map过程结束)；

步骤26为组建联合键值<Key，Value>(其中Key小于Value)；

步骤27为Reduce函数中利用式1计算SC_AB的值

${\mathrm{SC}}_{\mathrm{AB}}=\frac{|F_A\cap F_B|}{\min \left\{\right|F_A|,|F_B\left|\right\}}---\left(1\right)$

其中|F_A∩F_B|表示药物A、B一起组方的次数，min{|F_A|，|F_B|}表示 药物A、B中组方次数较少的药物的出现次数，而SC_AB表示药物A、B 共现次数与最少出现药物次数的比率；

步骤28为将结果保存至HDFS；

步骤29为图3的结束。

并行化标签传播算法总过程是基于迭代式的，迭代终止条件是各 节点标签基本稳定，图4是对图2中步骤4中标签传播算法一次迭代 的详细描述，具体如下：

步骤40为起始步骤；

步骤41为每个药物节点设定一个唯一的标签；

步骤42表示每个Map函数读取HDFS中药物网络文件的一行文 本，并存入Value变量中；

步骤43表示解析Value变量，用临时数组Tmp[0]保存节点id， Tmp[1]保存邻接表AdjList及Label；

步骤44表示发送节点数据结构；

步骤45判断Label是否只含有一个标签(第一次迭代)，是则执 行步骤46，否则执行步骤47；

步骤46令变量V＝标签1；

步骤47令变量V＝标签1&&标签2，其中标签1表示t-1次迭代 的标签和标签2表示t-2次迭代的标签；

步骤48令变量i＝0；

步骤49判断i是否小于AdjList.length，是则执行步骤50，否则 执行步骤52；

步骤50表示发送<AdjList.get(i)，V>；

步骤51表示i自增1；

步骤52为Hadoop平台的Shuffle和Sort过程；

步骤53为Reduce接收到<Key，[Value]>；

步骤54为Reduce解析[Value]数组，分别用数据结构AdjLabelPA保 存节点结构，临时链表ls₁保存每个邻居节点传递的自身t-1次迭代的 标签，ls₂保存每个邻居节点传递的自身t-2次迭代的标签；

步骤55表示根据f函数返回共同考虑ls₁、ls₂产生的频次最高的 标签L；

步骤56表示更新AdjLabelPA中t-1、t-2次迭代的标签；

步骤57为把结果保存在HDFS上；

步骤58为图4的结束步骤；

注：标签传播算法有多次迭代，迭代的终点为网络中90％以上的 节点的标签稳定不变。

综上所述，本发明利用并行化技术提高了组网以及标签传播算法 的可扩展性和运行速度，以便能在大量复方数据下快速高效运行社团 发现算法，并且能有效挖掘复方中药性相似的药物社团，帮助研究中 药配伍规律。

本发明所属技术领域中具有通常知识者，在不脱离本发明的精神 和范围内，当可作各种的更动与润饰。因此，本发明的保护范围当视 权利要求书所界定者为准。