基于PC—Simple算法的医院病案首页数据挖掘

易三莉+杨静+姚旭升+谢颖夫+贺建峰

摘 要：使用数据挖掘中的因果关系技术，分析某甲级医院住院首案中记录的高血压及其它协同疾病之间是否存在因果性。PC-Simple算法作为一种国内较少使用的因果分析算法，将其应用在对医学数据的因果关系挖掘中，能高效地得出变量之间的因果性。分析平台采用IBM SPSS Statistics进行数据预处理，以及R Studio进行数据建模分析。实验结果表明，高血压与冠状动脉粥样硬化、脑梗死、颈动脉粥样硬化、不稳定型心绞痛和急性心肌梗死之间存在着因果关系。使用PC-Simple算法得到的结果与实际医学理论相吻合，验证了该算法的有效性。

关键词：数据挖掘；PC-Simple；因果关系

DOIDOI：10.11907/rjdk.172291

中图分类号：TP392

文献标识码：A 文章编号：1672-7800（2018）002-0175-04

0 引言

关联规则挖掘作为数据挖掘的重要研究内容之一，主要研究事务数据库、关系数据库和其它信息存储中大量数据项之间隐藏的有趣规律。1993年，美国著名学者R Agrawal等[1]首次提出了挖掘布尔关联规则，之后提出了著名的基于频繁项集的Apriori算法。关联规则挖掘最初仅限于事务数据库的布尔型关联规则，近年来广泛应用于关系数据库。因此，积极开展关系数据库中挖掘关联规则的相关研究具有重要意义[2]。然而，产生的关联规则有时也是不正确的，某些时候变量之间看似具有相关性，但它有可能是由某些共同原因导致的。所以为了避免这些不确定因素，在相关性分析基础上进一步分析它们的因果关系，以确定变量之间的强关联性。

PC算法是一个学习因果贝叶斯网络结构的算法，它是以开发者Peter Spirts和Clark Glymour的姓命名的[3]。PC算法使用条件独立性检验确认两个变量之间的关联性是否为因果性。给出一个目标变量和预测变量的集合，判断预测变量集合中其中一个变量与目标变量是否有因果关系，都需要对预测变量集合的每个子集进行一次条件独立性判断。在一个最坏的情况下，比如有m个预测变量，则需要进行条件独立性测试的次数为2m-1。因此，PC算法仅适用于预测变量个数较少的数据集。

为了解决PC算法这个缺点，M Kalisch和P Buehlmann等[4]提出了PC-Simple算法。PC-Simple最初是为了在高维线性回归模型中进行有效的变量选择而开发的。在国外，PC-Simple算法也被用来分析变量之间的因果关系[5]。但是在国内，将该方法应用于因果关系分析的研究还很少，人们分析因果关系通常采用贝叶斯网络。本文将PC-Simple应用于分析疾病间的因果关系上，在真实数据中验证了其实用性。

1 贝叶斯网络

1.1 贝叶斯网络概念

贝叶斯网络应用于人工智能的几大细分领域包括因果推理、不确定性知识表示、模式识别和分类等，它结合了人工智能、概率理论以及图形理论，是一种将因果知识和概率知识相结合的信息表示框架[6]。它是基于概率推理的图形化网络，也是表现和推理因果关系的主要方式。给定一组表示域的变量，贝叶斯网络给出一个有向无环图（DAG）的完整联合概率。该有向无环图包含了代表节点和弧的变量，绘制出变量之间的依赖关系[7]。

1.2 贝叶斯网络简介

贝叶斯网络包括一个有向无环图（DAG）和一个条件概率表集合。DAG中每一个节点表示一个随机变量，可直接观测变量或隐藏变量，而有向边表示随机变量间的条件依赖；条件概率表中的每一个元素对应DAG中的唯一节点，存储此节点对于其所有直接前驱节点的联合条件概率。

如图1所示为一个简单的贝叶斯网络模型，A独立于它的非后代D、E和H；B、C变量相互独立并且它们都独立于D、E和H；D和E都没有双亲，此外它们还相互独立，并且都独立于A、B、C、Z和H；G的有条件双亲为D、Z和E，独立于A、B、C和H；F独立于除了其父节点以外的变量；H是一个孤立节点，所以它独立于所有节点；Z独立于A、D、E和H，它的双亲为B和C。V为一个贝叶斯网络的变量集合，联合概率分布为：

在一个数据集中可以通过因果贝叶斯网络结构发现变量之间的因果关系，但这不能说明因果关系的方向问题，谁是因谁是果不能仅从贝叶斯网络的边缘方向来判断，因为依靠数据集不能完全确定边缘方向。因此从数据集中学习贝叶斯网络，只能得出两个变量之间有因果关系，但是谁是原因、谁是结果还无法确定，此时则需要用到PC-Simple算法。

2 PC-Simple算法

2.1 PC-Simple算法定义

PC算法是一种学习因果贝叶斯网络结构的常用方法[8]。在数据集中，对于一对变量或节点（X， Y），PC算法用于检测目标变量是否条件独立于给定的其它变量。如果没有绘制X和Y的边缘，则X和Y之间不存在因果关系，换言之，为了确定X和Y之间是否存在持久性关联，PC算法对除X和Y外的所有变量都要进行关联条件测试。只有给定条件集存在关联时，这种关联才被认为是因果关系。

PC-Simple使用与PC算法相同的思想来检测变量之间的持久性关联，此外它还对一对节点的条件集进行分级搜索。然而，与因果DAG不同的是，PC-Simple不仅能找出所有给定变量之间的因果关系，还能发现给定的响应或目标变量周围的局部关系。比如，给定D为变量（X1，X2，…，Xm，Z）的集合，Z是目標变量，PC-Simple能识别出与Z相关的原因和结果。在DAG术语中，这些原因和结果表示为Z的双亲和孩子。

2.2 条件独立性

定义1 2个随机变量（事件）X和Y 相互独立，即变量X不影响变量Y，变量Y也不影响变量X，则有式（1）成立：

可以理解为：对变量Y的了解不会影响变量X的信度；同样，对变量X的了解也不会影响变量Y的信度。endprint

定义2 设有3个随机变量X、Y、Z，其中P（Z = z）>0，则X、Y在给定Z的条件下相互独立，有式（2）成立：

条件独立性可以用贝叶斯网结构方便地表示出来。用贝叶斯网表示的条件独立在知识表示、推理、学习方面起到了简化作用，使贝叶斯网的计算复杂性得到降低，可用性和实用性大大增强。

在贝叶斯网中，2个变量X和Y如果直接相连，则表示它们之间有直接依赖关系，对X的了解会影响对Y的信度；如果2个变量X和Y不直接相连，信息则需要通过它们之间的其它变量才能在两者间传递；如果X和Y之间的所有信息通路都被阻塞，信息则无法在他们之间传递。这时，对其中一个变量的了解不会影响对另一个变量的信度，因而X和Y相互条件独立。

2.3 部分相关性

对于有限的数据集，需要找出目标变量与预测变量的部分相关性，定义如下：

2.4 PC-Simple算法实现步骤

PC-Simple算法步骤如下：

D为输入数据集，预测变量X1，X2，…，Xm和目标变量Z通过PC-Simple算法，生成Z的双亲和孩子集合PC。α参数是用于条件独立性测试的显著性水平。

最初PC集合包括所有预测变量，然后通过条件独立性测试，PC-Simple算法将不是Z的双亲和孩子集合的变量从PC中移除。从一个空的条件集合开始，根据条件集合设置的基数逐级测试。While循环的每次迭代都将PCk-1赋值给PCk，从PCk-1中移除与Z独立的变量。

具体而言，在第一次循环迭代中，k=1，PC-Simple首先让PC1=PC0（第5行），然后判斷PC0是否符合条件（第6～11行），如果在PC0中有一个独立于Z的变量则给出一个空集（第7行，当k=1时，|S|=0），PC1通过独立性测试移除与Z独立的变量。在第一次迭代之后，PC1中则只包含与Z有关的变量。在第二次迭代中，PC-Simple首先让PC2=PC1，在PC1中给出任意其它单变量，通过独立性测试移除与Z独立的变量来更新PC2。之后的迭代与之类似，直到PCk中的变量不超过k个则迭代结束，并且PCk作为最后的一个PC集合输出。

3 PC-Simple算法在医学数据挖掘中的应用

3.1 医学数据挖掘

随着电子病历和病案的大量应用，以及医疗设备和仪器的数字化，使医院数据库的信息容量不断膨胀。这些宝贵的医学信息资源对于疾病的诊断、治疗和医学研究都非常有价值。如何利用这些海量的信息资源，为疾病的诊断和治疗提供科学、准确的决策，以更好地促进远程医疗和社区医疗发展[9]，需要运用医学数据挖掘技术。在数据挖掘之前，必须对这些信息进行清理和过滤，以确保数据的一致性和确定性，将其变成适合挖掘的形式。医学数据挖掘的主要目的是为医疗活动和管理提供科学的决策，因此必须保证挖掘算法提供的知识具有较高的准确性和可靠性。

3.2 数据来源

数据源：2013～2015年某三甲医院住院部的数据，提取出“主要诊断”中患有高血压疾病类型的个案，总共有5 940例。疾病编码是依据国际疾病分类编码的，疾病名称有很多，在本次分析中只选取了疾病数量大于400的疾病种类，高血压协同病种的排名如表1所示。

3.3 分析结果

分析环境：本文数据首先在IBM SPSS Statistics中进行数据预处理，然后将清洗后的数据纳入数据分析软件R Studio建模实现。

分析目的：分析高血压的协同疾病与高血压是否有因果关系。

数据经过PC-Simple算法分析之后，实验结果如表2所示，其中0表示预测变量与目标变量之间没有因果关系，1表示预测变量和目标变量之间有因果关系。部分相关系数越大，代表两个疾病之间的部分相关性越强。

如表2所示，疾病之间通过条件独立性判断是否独立于高血压，独立于高血压的疾病部分相关系数较弱。本文中相关系数大于6的疾病类型被判定为与高血压有因果关系。例如表中第一行表示2型糖尿病与高血压没有因果关系，所以它们之间的部分相关性较弱，为3.508 379 57。

根据分析结果可知，高血压与冠状动脉粥样硬化、脑梗死、颈动脉粥样硬化、不稳定型心绞痛和急性心肌梗死有因果关系。因果关系的相关系数分别为：9.874 980 64、8.080 510 41、6.572 002 53、19.323 492 70和13.176 818 72。

与高血压有因果关系的疾病如图1所示，其中高血压会导致脑梗死、不稳定型心绞痛和颈动脉粥样硬化的发生，高血压合并2型糖尿病会导致冠状动脉粥样硬化，冠状动脉粥样硬化会导致急性心肌梗死。这些与文献[10]～[13]中介绍的一致，说明PC-Simple算法在数据挖掘的研究上与医学实际相符合，验证了该算法的有效性。

4 结语

本文对PC-Simple算法的背景知识、实现步骤和实际运用3方面进行了介绍。在实际运用中，通过PC-Simple算法得出的实验结果表明，高血压会导致多种疾病发生。该方法在数据挖掘的研究上与医学实际相符合，验证了PC-Simple算法的有效性。在之后的学习中，可以运用PC-Simple算法在医院其它科室，比如一些临床科室中，分析某类疾病的影响因素，为临床医生的辅助诊断提供参考。

参考文献：

[1] AGRWAL R， SRIKAN R. Fast algorithms for mining association rules in large databases[C]. Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers，1994： 487-499.endprint

[2] 何军，刘红岩，杜小勇.挖掘多关系关联规则[J]. 软件学报， 2007，18（11）：2752-2765.

[3] P SPIRTES， C GLYMOUR，R SCHEINES. Causation， predication， and search[M]. The MIT Press， 2000.

[4] M KALISCH，P BUEHLMANN，M H MAATHUIS. Variable selection for high-dimensional linear models： partially faithful distributions and the PC-simple algorithm[J]. Biometrika， 2010，97：261-278.

[5] CF ALIFERIS， A STATNIKOV， I TSAMARDINOS， et al. Local causal and Markov blanket induction for causal discovery and feature selection for classification part I： algorithms and empirical evaluation[J]. Journal of Machine Learning Research， 2010，11：171-234.

[6] 李軍，熊飞，钮焱.基于贝叶斯网络的网络风险评估研究[J].软件导刊，2017，16（4）：197-200.

[7] D KOLLER， N FRIEDMAN. Probabilistic graphical models： principles and techniques[M]. The MIT Press， 2009.

[8] J PEARL. Causality： models， reasoning， and inference[M]. Cambridge University Press， 2000.

[9] 朱凌云，吴宝明，曹长修.医学数据挖掘的技术、方法及应用[J].生物医学工程学杂志，2003，20（3）：559-562.

[10] 刘坤申.高血压与脑卒中[J].中国实用内科杂志，2002，22（4）：201-202.

[11] 伍卫.高血压与冠状动脉粥样硬化性心脏病[J].新医学，2003，34（3）：139-139.

[12] 安全宇.老年患者高同型半胱氨酸高血压与不稳定型心绞痛的关系研究[J].首都医药，2014（10）：32-34.

[13] 马尔娃，库拉西汗.冠心病与心肌梗塞的麻醉[J].世界最新医学信息文摘：电子版，2013（7）：93-94.endprint