一个就医行为模式挖掘算法

第２８卷第８期

２０１１年８月

计算机应用与软件

ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｈ叮ａｒｅ

Ｖ０１．２８Ｎｏ．８Ａｕｇ．２０１１

ＶＰＭ：一个就医行为模式挖掘算法

周

坤１王爱荣２张敬谊３熊赘１朱扬勇１

１（复旦大学计算机科学技术学院上海２００４３３）２（上海市医疗保险信息中心上海２０００４０）３（万达信息股份有限公司上海２叭１１２）

摘要在医保基金管理中，第三方付费机制和信息不对称等问题造成了基金运作面临严重“道德风险”困境，医药机构和参保

人可能存在过度使用医保基金的倾向。通过对参保人就医行为序列的分析挖掘其就医行为模式，对于发现疾病发病规律、参保人健康状况以及是否存在违规欺诈行为，从而有效防范基金风险具有非常重要的作用。由于就医行为模式的特殊性，传统的序列模式挖掘算法在结果可用性和效率上存在问题，如挖掘结果丢失时间间隔较长的模式，挖掘过程需多次构造投影数据库等，因此难以直接应用。针对就医行为模式特点，提出了基于二叉树增长策略的向量模式挖掘算法ＶＰＭ。实验表明，ＶＰＭ算法在解决就医行为模式挖掘问题上具有良好的性能。关键词

医保基金

风险防控

就医行为模式

序列模式

数据挖掘

中图分类号ＴＰｌ８文献标识码Ａ

ＶＰＭ：ＡＭＥＤＩＣＡＬＴＲＥＡＴＭＥＮＴＢＥＨ渔ＶＩＯＵＲ

ｚｈｏｕＫｕｎｌ

ＰＡＴＴＥＲＮ

ＭＩＮＩＮＧＡＬＧｏＲＩＴＨＭ

ｚｈｕＹａｎｇｙｏｎ９１

ｗａｎｇ

Ａｉｒｏｎ矿

ｚｈａｎｇＪｉｎｇｙｉ３

ｘｉｏｎｇＹｕｎｌ

。（＆＾∞ｆ矿ｃ０唧Ⅱ河ｓｃ切Ⅻ，凡也ｎ￡，ｎ妇Ｈ蚵，舶ｏ，。ｇ舰ｉ

２０Ｄ钉ｊ，蕊ｉＭ）

２（踟，ｔ咖ｉ胁以池ｆ，ｍⅡｍ删倒白删如厅Ｄｎ灯。踟ｎｇｈｉ２０Ｄ∞Ｄ，醌ｉＭ）

３（％，幽３蝴泐ｃｏ．，￡ｍ，踟，咖ｉ

ｆｕｎｄ

２０，Ｊ，２，吼ｉＭ）

ｆ南ｍ

Ａｂｓ仃ａｃｔＷｉｔｈ

ｒｅｇ捌ｔｏｍｅｄｉｃａｌｉｍｕ啪ｃｅ

ａｒｅ

ｍｎａｇｅｍｅｎｔ，ｐｍｂＩｅ啪ｄ甜ｖｉｌｌｇｔｌｌｉｒｄ－ｐａｒＩ）ｒｐａｙｍｅｎｔｍｅｃｌｌａ仉ｉ８ｍ柚ｄｉＩＩｌｌｂａｌ鲫ｃｅｏｆ

Ｂｏｔｈｍｅｄｉｃａｌａｇｅｎｃｉｅ８ａｎｄ

ｉｎｆｏｎ舱ｔｉｏｎａｃｋｎｏｗｌｅｄｇｅｍｅｎｔ

ｐａｔｉｅｎｔｓｔｅｎｄｐｅｏｐｌｅ

ｔｏ

ｔｏ

ｃ甜ｓｉＩｌｇｔｈｅｐｌｉｇｈｔｏｆ”ｉｍｍｏｍｌ时ｒｉｓｋＩ．ａｌｏｎｇ埘ｔｈｔｈｅｏｐｅｒａｔｉｏｎｏｆｔ｝Ｉｅｆｕｎｄ．

ｅｘｅｅｓｓｉｖｅｌｙｅｘｐｌｏｉｔｔ｜ｌｅｍｅｄｉｃａｌ

ｉｌｌｓｕ埘ｌｃｅｆｕｎｄ．ＴｈｍｕｇＩＩ

ｐａｔｔｅｍ，ｉｔｉｓｅ鹊ｉｅｒ

ｔｏ

ａＩｌａｌｙｓｉｓｏｆｍｅｄｉｃａｌ

ｔｒｅａｔＩＩｌｅｎｔｂｅｈａｖｉｏｕｒ

ｓｅｑｌｌｅｎｃｅ“ｔｌｌｅｉ璐ｕｒｅｄ

ｍｉｎｅｔｈｅｉｒｒｎｅｄｉｃａｌ协Ｂａｔｍｅｍｂｅｈａｖｉｏｕｒｄｉｓｃｏｖｅｒｔｌｌｅ

ｒｅｇｕｌａｒｉｔｉｅｓ

ｏｆｄｉｓｅａｓｅｓ，ｔｈｅｈｅａｌ出ｓｔａｍｓｏｆｔｈｅｉｎｓｕｒｅｄ

ｔ０

ｐｅｏｐｋ，锄ｄｗｈｅｔｈｅｒｔＩｌｅｒｅｉｓ蚰ｙ如ｕｄｂｅｈ８ｖｉｏｕｒ，ｔＩｌｅｒｅｆｂｒｅｉｔｐｌａｙｓ粕ｉｍｐｏｎａ眦ｒｏｌｅｉｎ

ｏｆ出ｅｍｅｄｉｃａｌｔｒｅａｔｍｅｎｔｂｅｈａｖｉｏｕｒｐａｔｔｅｍ８ｉｎＩＩｌｉｎｉｎｇ

ｃｏｎｔＩｏＵｉＩｌｇ妇ｆｕｎｄｒｉｓｋ．【）ｕｅ

ｔｈｅｓｐｅｃｉａｌ

ｎａｈ啪

ｐａｔｔｅｍ，ｔｈｅｒ；ｅｉｓｄ娟ｃｉｅｎｃｙ

ｏｎ

ｉ协陀ｓｕｌｔ

ｆ宅鹪ｉｂｉｌｉｔ），粕ｄｅ伍ｃｉｅｎｃｙ，ｓｕｃｈ∞山ｅｍｉｓｓｉＩｌｇｏｆｌｏｎｇｅｒｉｎｔｅｎ，ａｌ

ｒｅｓｕｌｔｓ锄ｄｔｈｅ陀ｑｕｉｒｅｍｅｎｔｆｏｒｒｅｌ）ｅａｔｅｄｌｙｂｕｉｌｄｉｎｇｓｈａｄｏｗｃ鹬ｔｉＩｌｇｄ北Ｉｂ够∞，ｅｔｃ．ｆｏｒ岫ｄｉｔｉｏＩｌａｌｓｅｑｕｅｎｔｉａｌ

ｅｎｃｏｕｎｔｅｒｓ

ｐａ仕哪ＩＩｌｉｎｉｎｇ

ｐａｔｔｅｍ，ｔｌｌｅ

ａｌｇｏｒｉｔＩｌＩ璐．ＴＩｌｅｒｅｆｏｒｅｔｈｅｉｒｉｍ啦ｅｄｉａｔｅａｐｐｌｉｃａｔｉｏｎ明ｔｈｏｒｓｐｒｏｐｏｓｅ

ａ

ｂ删ｅ玛Ａｉｍｉｎｇ

ａｔ

ｔｈｅｓｐｅｃｉａｌｔｉｅｓｏｆｍｅｄｉｃａｌｔｒｅａｔｍｅｎｔｂｅｈａｖｉｏｕｒ

ｎｏｖｅｌ

ａｌｇｏｒｉｔｂ

ｂ鹳ｅｄ

ｏｎ

ｂｉ∞ｒｙ－ｔＩ傥铲州ｈ

ｓｔｒａｔｅｇｙ，ｃａｌｌｅｄＶｅｃｔｏｒＰａｔｔｅｍ

Ｍｉｎｉ｜ｌｇ址ｇｏｒｉｔｌｌＩｎ（ＶＰＭ）．ＴｈｅｏｒｅｔｉｃａＩ删ｙｓｉｓ

ｐａｔｔｅｍ

ａｎｄｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔＶＰＭａｌｇＤｒｉ出ｍｐｅ娟）ｒＩＩｌｗｅＵｉｎｓｏｌｖｉｎｇｔｈｅｐｍｂｌｅｍｏｆｍｅｄｉｃａｌ廿ｅａｔｍｅｎｔｂｅｌｌａｖｉｏｕｒｐａｔｔｅｍｍｉｎｉｎｇ．

Ｋｅ＂ｒ叫凼

Ｍｅｄｉｃａｌ池ｕ砌ｃｅ

ｆｈｎｄＲｉｓｋ

ｐｒｅｖｅｌｎｉ蚰粕ｄｃｏｎｈｄ

Ｍｅｄｉｃａｌ

ｔｒｅ咖ｅｎｔ

ｂｅｌｌａ“伽ｒ

ＳｅｑｕｅｎｔｉａＩ

ｐａｔｔｅｍ

ＤａｔａｒｎｉＩｌｉｌｌｇ

下一些特点。

Ｏ

引言

首先，表示方式不同。参保人就诊往往是突发性的，比如某些人平时不怎么生病，但最近忽然患有某类疾病，就诊次数将会频繁增长，如表ｌ所示。

表ｌ示例序列集

ＩＤｌ

序列模式挖掘问题是Ａｇｒａｗａｌ和晒ｋａｎｔ在１９９５年研究交

易序列时第一次提出的…。许多应用领域都涉及到序列模式的挖掘。２】。医保基金风险防控领域中参保人就医行为模式就是一种序列模式。通过对就医行为模式的挖掘，可以得出疾病的发病规律；划分易患人群，提前做好防治工作；还可以筛选出就医行为异常的参保人，为审核监督提供重点监督管理对象，提高审核监督力度和效率。因此，如何挖掘就医行为模式对医保基金风险防控具有十分重要的意义。

就医行为是指参保人在一段时间内到医院就诊的次数。例如，参保人在第１、２、４、６天就诊，可以表示成序列模式＜ｄ。，如，也，ｃｆ６＞。就医行为模式不同于一般的事务序列模式，它具有如

序列

ｄｌ，ｄ２，ｄ３，ｄ４，ｄ１００，ｄ３０ｌｄｌｏ。ｄｌ∞，ｄ加１＇ｄ撇，ｄ２０３，ｄ２阱

２

参保人ｌ和参保人２存在一种相同的就医行为模式：连续

收稿日期：２０ｌＯ一０３—３ｌ。上海市科委科研计划基金项目（０８５１ｌ５００２０３）；上海市重点学科建设项目（Ｂｌｌ４）。周坤，硕士生，主研领域：数据挖掘，数据科学。

万方数据

１２４

计算机应用与软件

２０１１年

４天就诊。但如果仅从ｄ，上看，是找不出这种模式的，因为面、ｄ２、ｄ３、ｄ４显然不同于ｄ∞，、ｄ２０２、ｄ抛、ｄ枷。所以如果仅仅像交易型记录那样记录天数．算法难以挖掘出这种模式。因此必须将交易数据转化成向量形式，某天内用ｌ表示就诊，０表示未就诊。这样我们就能挖掘出＜ｌ，ｌ，１，１，０，０，…，Ｏ，ｌ＞与＜ｌ，０，０…０，ｌ，１，ｌ，ｌ，Ｏ，０，ｌ＞之间的共有模式＜ｌ，１，ｌ，ｌ＞。

其次，我们找的往往是精确的模式匹配，如＜１ｌＯｌ＞与＜１０００ｌＯｌ＞显然是不同的就医行为模式。

第三，由于就诊治疗的阶段性，单条序列中可能含有较大时间间隔的重复模式。例如，＜１１１０００…０００ｌｌｌ…＞表示某参保人上个月化疗和本月化疗记录。

第四，就医行为模式以ｌ开头和结尾。在就医行为模式中，ｌ表示就诊，０表示未就诊，故以０开头或结尾的序列是没有实际意义的。例如模式＜１０ｌＯｌ０００＞等价于模式＜１０１０１＞，＜０００１０１０ｌｌ＞等价于模式＜１０１０ｌｌ＞。

随着近年来的研究与发展，很多序列模式挖掘算法被提出。这些算法主要分为两大类，一类基于Ａｐｒｉｏｒｉ性质；另一类基于

频繁模式增长。代表性的算法有ＧＳ川Ｊ、Ｐ硝ｘＳｐ锄嵋１。虽然这

些算法原则上可以处理更广泛的数据结构，但是它们最初都是针对交易序列模式设计的，难以直接应用到诸如生物、就医行为等序列数据上。因此，这些算法存在一些共同的问题。首先，带有约束的Ｐｒｅ６ｘｓｐａｎ等算法在投影数据库中查找序列模式时，引入了模式间隔约束，考虑了序列模式问可能存在间隔的情况。例如，针对就医模式序列＜１１０ｌ＞和＜１０００１０１＞，将会得到＜ｌ１０１＞这样的频繁模式，但在第二条序列中包含的＜１１０ｌ＞模式间间隔了没来就诊的三天＜ｌｏ００１０ｌ＞。从就诊意义上看，它与＜１１０ｌ＞存在较大差异。其次，Ｐｒｅｆｉｘｓｐａｎ算法在创建初始投影数据库时，仅仅对单个符号的第一次出现进行投影，而忽略该符号在该条序列中重复出现的情况。因此，如果单条序列中含有重复的序列模式，并且这些模式超过了引入的时间间隔的约束，则这些模式将会丢失。而生物ＤＮＡ序列、就医行为序列中常常含有这类序列模式。针对生物序列，Ｙｕｎ等提出ＢｉｏＰＭ算法旧Ｊ，很好地解决了生物序列模式挖掘问题。但针对就医模式问题，该算法会产生大量莺叠投影数据库。降低了算法效率。第三，大部分已有算法没有考虑到分布支持度和局部支持度的区别。多投影策略会造成模式误判，可能重复计算单条序列中的重复模式，从而把局部频繁的模式认为是全局频繁的。例如模式＜１１１＞是＜１０００１１１０００１ｌｌ＞中的局部频繁序列，但可能并不是序列数据库中的全局频繁序列。因此需要记录模式对应的分布支持度和局部支持度，用以判断模式是全局频繁还是局

部频繁的。最后，无论是Ｐ蔺ｘｓｐ锄算法还是ＢｉｏＰＭ算法，得到

的模式集中可能会存在冗余，即包含重叠的模式。这类问题并没有得到很好的解决。

本文针对就医行为模式的特点，提出了一个新的序列模式挖掘算法：向量模式挖掘算法ＶＰＭ（Ｖｅｃｔｏｒ

Ｐａｔｔｅｍ

Ｍｉｎｉｎｇ）。该

算法采用二叉树增长的策略，通过建立ＶＰ．ｔｒｅｅ的方式挖掘频繁模式，避免产生不必要的投影数据库，并有效区分分布支持度和局部支持度。分析和实验表明，ＶＰＭ算法具有良好的性能。１

问题定义

就医行为数据库Ｄ是元组＜，Ｄ，｜ｓ＞的集合，如表２所示。

，Ｄ表示参保人卡号，ｓ表示就医行为模式。

万方数据

表２就医行为数据库Ｄ

ＩＤｄｌｄ２ｄ３ｄ４ｄ５ｄ６ｌ１

１０ｌＯ

１

２

ｌＯ

ｌＯ

ｌ】

３

ｌＯＯ１

ｌｌ

４

ｌ

０

Ｏ

Ｏ

ｌ

ｌ

如果ａ是ｓ的子序列，则称元组＜，Ｄ，ｓ＞包含序列ａ。序列“在就医行为数据库中的支持度是数据库中包含ａ的元组个数，记为ｓｕｐｐＤｎ，（口）≥ｍｉｎ－ｓｕｐ。给定一个正整数ｍｉｎ—ｓｕｐ，表示最小支持度阈值。如果ｓｕｐｐＤｎ。（ａ）≥ｍｉＩｌ＿ｓｕｐ，则称序列ａ在数据库Ｄ中是频繁的。

２ⅦＭ：向量序列模式的挖掘算法

２．１基本概念

引理１分区问题。

①设｛口，，口：，…，％｝是Ｄ中所有长度为１的序列模式集合。在Ｄ中的所有序列模式可以分成ｎ个不相交的子集，第ｉ个子集（１≤ｉ≤ｎ）是具有前缀Ｈ１为ｏ；的序列模式集。

②设ａ是长度为Ｚ的序列模式，｛崩，岛，…，卢。｝是所有具有前缀ｄ的长度为Ｚ＋钾的序列模式。包含前缀仅的所有序列模式的集合，ａ本身除外，可以被分为ｍ个不相交的子集。第Ｊ个子集（ｍ≥』≥１）是含有前缀鼠的序列模式。

引理ｌ的证明参见Ｐ—ｉｘＳｐ柚算法。基于引理ｌ，ＶＰＭ算法可通过建立ＶＰ．ｔｒｅｅ树的方式递归地把问题分割成几个小问题解决，并且序列模式的每个子集也可以进一步划分，从而采用模式增长的方式来产生频繁模式。

定义ｌ

ＶＰ一讹ｅ一棵向量模式树定义为一棵有向根树ｒ

＝＜ｙ（ｒ），Ｅ（ｒ）＞，其中，ｙ（ｒ）是结点集，每个结点口属于ｙ（Ｔ），代表一个（或埘个）序元的值和它的分布支持度，分别记为仉口口￡ｗ和仉ｓｕｐ。Ｅ（ｒ）ｃｙ（ｒ）×ｙ（ｒ）是（有向）边集。ｒ必须满足约束：Ｖ口Ｅｙ（ｒ），口．８ｕｐ≥ｍｉｎ－ｓｕｐ（最小的支持度阈值）。根据就医行为数据库建立一个ＶＰ．ｔｒｅｅ，其根结点到每个叶子结点的路径序列就是序列模式。

定义２散列

散列是一种以线性表中每个元素的关键字

Ｋ为自变量，通过一种函数＿ＩＩ（Ｋ）计算出函数值，并以这个值作为一块连续存储空间的单元地址，将该元素存储到这个单元中的存储方法。

散列技术可以用来压缩数据库，减少，／Ｄ次数。我们根据序列中ｌ的个数将其散列到不同的桶中。如图１所示。

桶地址

ｌ

２

３

４

｛１００００１１０００ｌＩｌｌ加ｌ１１ｌｌ∞ｌ

ｌｌ｝

｝

Ｉ咖ｌＯ

１１∞ＩＯ

ｆｌｌＯｌＯ

｛１１００儿

檑内容

ｌｌ

ｌｌ

１００ｌ∞

ｆｌｌｏｏＯ

｝ｌ

图ｌ散列表：根据每条序列中Ｉ的个数将其映射到散列表的不同桶中

第８期

周坤等：ＶＰＭ：一个就医行为模式挖掘算法

２．２、甲Ｍ算法的序列模式产生

２．３

ＶＰＭ算法

根据以上定义和基本概念，下面给出基于频繁模式增长的

…ｗ２２。

例ｌ设就医行为数据库Ｄ如表３所示．最小支持度闺值

无候选生成的就医行为模式挖掘算法ＶＰＭ。

表３就Ｅ行为蕞式数据牟Ｄ

算法ＶＰＭ模式。

使用Ｖｎｎ槐，通过模式增长挖掘就医序列

输入Ｄ：就医行为模式散据库；一一ｓｕｐ：最小支持度计数

阈值。

输出就医行为模式集。方法

（１）为降低ⅣＯ次数．将数据库Ｄ中就医序列读人戢列表

就医行为模式挖掘过程如下：

步骤１为降低∥０攻数，首先将就医模式数据库Ｄ中的记录存＾散列表Ｐ中。由于本例所有序列都古有４个１，故映射到同一个桶中。如表４所示。

襄４靛到囊ｖ

Ｖ中。

（２）接以下步骤构造ｖｎⅡ恍：

（ａ）首先创建ＶＰ—盹ｅ的根结点，以１标记它。

（ｂ）分别刨建根结点的左右子结点，分别以０，ｌ标记之。记录该结点到根结点的路径，存人栈中。出栈，形成扶根结点到该结点的序列‰并扫描散列表Ｖ，如果散列表中序列ｑ古有该序列＾，则其支持度ｓ。８”ｐ加ｌ。统计根结点左右子树的支持度，

如果某子树ｓ．．ｅｕｐ㈣ｎ－暑“ｐ，则删除该子树，并记根结点该子

树为Ⅳ““如果根结点左右子树均为№“，则该结点为叶子结

点，人队列Ｑ｜Ｊｅｕｅ，Ｑ—ｅ中用于保存所有叶子结点。

（ｃ）递归执行（ｂ），直到ＶＰ・ｔ眦所有叶子结点的左右子树

步骤２创建根结点．用慎ｌ标记。

步骤３划分搜索空问。就医行为模式表示成二元向量的形式，其序列模式的完全集可根据２个前缀划分成：（１）前缀为（０＞的子集；（２）前缀为＜ｌ＞的子集。创建根结点的左右子树结点，分别用Ｏ．１标记。

步骤４支持度计数。记录从根结点到该序元的路径１０和１】．其中１０含有１个ｌ，故扫描散列表ｖ中大于等于１的桶地址，１１吉有２个１．故扫描散列表ｖ中大于等于２的桶地址。这里都扫描４号桶。如果桶中向量ｃ；包含序列１０，则口．．ｓ“ｐ加ｌ（即使向量ｅ．包古多条１０序列，也仅仅对－．．８“ｐ贡献了１，从而有效区别分布支持度和局部支持度问题）。统计１０序列和１１序列的支持度．１Ｅ为（０：４），＜１：３＞，其中，符号＜序元：计数）表示从根结点到该序元的支持度计数。如果该序元的支持度计数”ｓｕｐ（ｍｌｎ－ｓｕｐ，则删除该序元结点．并记该序元的父结点该子树为空。

径｝

（ｂ）ｂｒ队列中每个叶于结点Ｂ，ＥＯｍ∞ｄｏ

均为空。

（３）通过调用叫‘ｐ．Ｊｔ一呻ｅｎｃ。ｐａｌｌｅｍ（ＶＰ岫，Ｑｕｅｕｅ）生成

ｓ；｝建立韧始栈．月ｆ保存从叶｝结点到根结点∞路

就医序列模式集。

（４）‰ｋ

（ｃ）Ｈｐ叫

（ｄ）（ｅ）

（ｆ）Ⅲ“ｌ

Ｂ埘ｄ（５．）｛将该结点＾栈ｆ

％＝ｓ…ｉ日期到Ｚ结点｝

５…ｕｕ

（ｇ）ｍⅢ

（ｈ）（】）∞ｄｂ‘

（＿）∞ｍ目…Ｐ‘ｙ

（ｋ）Ｒ咖Ｊ１Ｉ＝ｕ８ｔ

ｓＦ…ｐ叩（）｛±成序列模式｝

（４）删除序列模式中可能含有的０结尾，然后判断删踪后的序列是否是序列模式集中其他序列的前缀。如果是，删除该序列，从而去除冗余。最后输出就医行为模式集。

３实验分析

３ｌ数据集和实验环境

本实验的散据集来自某市医疗保险局提供的就医模式序列数据库。该数据库中共收集了１００天内就诊２０状以上的

１９２

７９０名参保人就诊记录。

实验程序在内存为２Ｇ、处理器为Ｉ““嗍酷睿双核２

ｘＰ

２４

ｃｍ的ｐｃ机上运行．操作系统为ｗｌｎｄｏｗ５验程序采用ｈＨ语言编写。

中叶于结点之间的指针链接（图中虚日２对＆３就日模式

Ｐ曲聃ｌｏｎｄ。实

线所示），这样有助于依次回蝴到根结数据库Ｄ建ｉ的ｖ＾№

点，输出序列模式。

步骤７就医行为模式是从根结点到每个叶子结点的路径的汇集。奉例中，行为模式为；＜１００１００１），（１１＞ｆ。

３．２实验结果

实验的目的是对比ＶＰＭ算法和胁ｎｘｓｐ蛆算法在不同阈

值支持度下得出的序刊模式的个数和长度。

（下转第１帅贾ｌ

万方数据

１８０

计算机应用与软件２０１１年

实验过程中，本文算法中的式（５）改为：ｓ溉（邪，粥Ｒ）＝÷［ｓ拥（Ｓ，，彤）＋ｓ拥（如，肋）］

Ｉ

‘

文献［４］算法和本文算法的平均查全率分别为７３％和８４％，平均查准率分别为８ｌ％和７９％，两种算法的平均查准率相近，本文算法的平均查全率较高。分析得知，文献［４］的算法只注重用于服务匹配的领域本体概念间的子类关系，忽略了概念间的其它多元关系，导致概念的语义不能被完整地反映出来，从而影响了算法的查全率。本文算法在对服务进行匹配时利用了本体概念间的多元关系，因而在整体性能上较好。

４结语

服务匹配算法是ｗｅｂ服务发现的核心技术。本文提出的基于语义相似度的ｗｅｂ服务匹配算法，利用本体概念间的多元关系定义了一种语义距离，在此基础上，给出概念间的语义相似度计算方法，进而通过计算与服务功能参数集中参数相应的本体概念间的语义相似度实现了ｗｅｂ服务的匹配。实验的结果表明，与文献［４］中的算法相比，本文提出的算法具有较好的整体性能。本文主要针对服务的功能匹配进行了研究，但没有考虑到服务的ＱｏＳ属性，所以下一步工作是研究服务的Ｑ０ｓ匹配，以使服务匹配算法迸一步完善。

参考文献

［１］廖祝华，刘建勋，刘毅志。等．ｗｅｂ服务发现技术研究综述［Ｊ］．情

报学报，２００８，２７（２）：１８６一１９２．

［２］吕庆聪，周集良，杨帆，等．普适计算机服务匹配技术研究［Ｊ］．计

算机科学，２００９。３６（１１）：１８２—１８５．【３］Ｐ∞ｌｕｏｃｉ

Ｍ。Ｋａｗ出哪Ｔ，Ｐａｙｎｅ

Ｔ

Ｒ，眦ａ１．ｓｅｍ明ｔｉｃＭａｔｃｈｉｎｇ０ｆ

ｗｅｂ

ｓｅⅣｉｃ∞ｃ印ｌａｂｉｌｉｔｉ∞［ｃ］／／ＰＴ∞ｅｅｄｉｎｇｓ

０ｆｔｈｅ

Ｆｉｒｓｔ

Ｉｎｔｅｍａｔｉｏｎａｌ

ｓｅｍ如ｔｉｃＷｅｂ

Ｃｏｎｆｅ地ｎｃｅ（ＩＳｗＣ）．Ｓａｒｄｉｍａ，ｌｔａｌｉ８，２００２：３３３

—３４７．

［４］彭晖，史忠植。邱莉榕，等．基于本体概念相似度的语义ｗｅｂ服务

匹配算法［Ｊ］．计算机工程，２００８，３４（１５）：５ｌ一５３．

［５］黄志成，李华．改进的语义ｗｅｂ服务匹配算法设计与实现［Ｊ］．计

算机工程，２００９，３５（２０）：８８—９０．

［６］Ｍ８而ｎＤ，ＢｕｒｓｔｅｉｎＭ。ＨｏｂｂｓＪ。ｅ【ａ１．ＯｗＬ・ｓ：ｓｅ眦ｎｔｉｃＭａｒＩｃ印ｈ

ｗｅｂ

ｓｅｆｖｉ啷［ＥＢ／ＯＬ］．［２００４一ｌｌ一２２］．ｈｔｔｐ／／ｗ’哪．’ｄ．叫

ＳＩｌｂｎｌｉｓ８ｉｏｎ／ＯＷＬ．ｓ／．

［７］顾金謇，王芳．关于本体论的研究综述［Ｊ］．情报科学，２００７，２５

（６）：９４９—９５６．

［８］刘汉兴。林旭东，田绪红．基于本体的自动答疑系统的研究与实现

［Ｊ］．计算机应用，２０ｌＯ，３０（２）：４１５—４１８．

［９】姜华．一种基于本体的概念语义相似度计算研究［Ｊ］．计算机应用

与软件，２００９，２６（７）：１４３一１４５．［１０】Ｋｈ丑ｌｉｋ

Ｍ

Ａ，蹦∞Ｂ．ＯｗＬｓ［ＥＢ／ＯＬ］．［２００６一１２—０１］．ｈｕｐ：∥

ｐ玎Ｄｊｅｃ协．ｓｅｎｎ州出∞ｎｔ商．ｏ口ｇ／矗∥ｄｏｗｎｌｏＢｄ．ｐｈｐ／２５５／ｏ岬１５一ｔｃ２．面ｐ．

【上接第１２５页）

实验结果表明，ＶＰＭ算法得出的序列模式结果集中序列的个数和长度明显比ＰｒｅｆｉｘＳｐ柚算法的多，尤其在阈值较小的情况下。此时满足条件的模式大大增加。并且进一步的实验对比表明。ＶＰＭ算法的序列模式结果集中包含了Ｐｒ；ｅｆｉ】【ｓｐ锄算法得出的所有序列模式，表明了Ｐｒｅ６）【ｓｐ如算法并不能获得所有的就医行为模式，遗漏了参保人阶段性就诊治疗所产生的含有时

万方数据

间间隔较长的重复序列模式。而ＶＰＭ算法能很好地挖掘出这类行为模式。如图３、图４、表５所示。

８００

’’

ｔ、’

ｇ

６００

．ｏ

旨枷

＼＼

－、～，．

Ｚ２００

‘＼

、

～～～●

Ｔ

＋＾

Ｏ

ｌＯ％

２０％３０％

臣三运巫三三固

图３不同支持度下序列模式个数比较

２５２０

～～１

雹１５

●ｈ一

姜ｌｏ

＼－

５—、●

｛

０

ｌｏ％

２０９６

３０９６

巨三匦五匠翔

Ｓｕｐｐｏｒｔ

ｔｈｒｅｓｈｏｌｄ（％）

图４不同支持度下序列模式长度比较表５在不同的支持度下Ｐ代ｆｉｘＳ呻ｎ和Ⅵ礓Ｉ

结果集中序列模式个数和长度的比较支持度

ＶＰＭ

Ｐｒ蛳ｘＳｐａｎｌＯ％

ｋｎｇｔｈ：２２

ｋｎｇｔ｝Ｉ：１６

Ｎｕｍｂｅ硌：７３６

Ｎｕｍｂｅ瑁：３５３

２０％

ｋｎｇｔｈ：２２

ｋｎｇｔｈ：１１

ＮｕｌＩｌｂｅ糟：３８２

Ｈｕｍｂｅ玛：１３１

３０％

ｋ“Ｓｔｈ：１８

ｋｎｇｔｈ：７

Ｎｕｍｌ）ｅｒｓ：２５３

Ｎｕｍｂｅｒｓ：９０

实验结果表明。针对就医行为模式的特点，ＶＰＭ算法优于

Ｐｒｅ脑ｐａＩｌ算法。

本文针对就医行为模式的特点，提出了一个新的就医行为目前，ＶＰＭ算法已被成功应用在某市医保基金风险防控数据仓库项目的数据挖掘过程中，为后续的医保风险防控、决策支持提供帮助。进一步工作我们还将考虑内存建树、数据压缩等问参考文献

［１］Ａｇ瑚同Ｒ，蹦ｋ∞ｔＲ．Ｍｉｎｉｎｇ∞ｑｌＩ∞ｔ试ｐＢｔｔｅｍｓ：Ｇｅｍｒａｌｉｚ“ｏ邶蜘ｄ

ｐｅ而ｍｍｃｅｉｍｐｎ玳ｍｅｎｔ８［ｃ］／／ＥＤＢＴ。１９９６．

［２］Ｊｉ蛐Ｐｅｉ，ｅＩａ１．Ｐｒ曲ｘｓｐ曲：ＭｉｎｉｌｌｇｓｅｑｕｅｎｔｉａＩＰａｔｔｅｍ８Ｅ币ｃｉｅｎｄｙｂｙ

Ｐｔ幽ｘ・Ｐ叫佻ｌ耐Ｐ砒ｔ哪Ｇ彤ｗｔＩＩ［ｃ］／／Ｄａｌａ

Ｅｎｇｉｎｅｅｒｉｎｇ，２００１．

［３］）（ｉｏｒＩｇＹ，动ｕ

ＹＹ．ＢｉｏＰＭ：Ａｎ

Ｅｍｃｉ棚ｔＡｌｇｏ削【ｌｍ缸ＰｒｏｔｅｉｎＭ０ｔｉｆ

ＭｉｎｉＩＩｇ［ｃ】／／ｌｃＢＢＥ，２００ｒ７．

【４］Ａ印哪ａｌＲ，ｓｒｉｋ蛐ｔ

Ｒ．ｆ．聃ｔ

ａｌ窜丽ｔｌｌｍｆｏｒｍｉｎｉｎｇａｓｓ∞ｉ砒ｉｏｎｍｌｅｓ

［Ｃ］／／ＶＬＤＢ．１９９４．

［５］）【ｉ∞ｇＹ。办ｕＹＹ．ＡＭｕｍ・Ｓｕｐｐｏｒｔｓ—Ｂａ∞ｄＳｅｑｕｅｎｔｉａｌ

Ｐａｎ哪Ｍｉｎｉ哩

‰ｈ∞１０９ｙ№ｅｅｄｉ咿，舢．

Ａ蛳ｔｌ瑚【ｃ］／／ｈｎｅｌＴＩａｔｉｏｌｌａｌ酬毫嗍ｃｅ硼ｃ伽ｐｕｔｅｒ如ｄｌｎｆｂｎ眦ｔｉ∞

４结语

模式挖掘算法ＶＰＭ。实验表明，该算法优于Ｐｒｅｆｉ）【Ｓｐａｎ算法。题。

VPM:一个就医行为模式挖掘算法

作者：作者单位：

周坤， 王爱荣， 张敬谊， 熊赟， 朱扬勇， Zhou Kun， Wang Airong， Zhang Jingyi， Xiong Yun， Zhu Yangyong

周坤,熊赟,朱扬勇,Zhou Kun,Xiong Yun,Zhu Yangyong(复旦大学计算机科学技术学院,上海,200433) ， 王爱荣,Wang Airong(上海市医疗保险信息中心,上海,200040)， 张敬谊,ZhangJingyi(万达信息股份有限公司,上海,201112)计算机应用与软件

COMPUTER APPLICATIONS AND SOFTWARE2011,28(8)

刊名：英文刊名：年，卷(期)：

参考文献(5条)

1. Agrawal R;Srikant R Mining sequential patterns:Generalizations and performance improvements 19962. Jian Pei PrefixSpan:Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth 20013. Xiong Y;Zhu Y Y BioPM:An Efficient Algorithm lor Protein Motif Mining 20074. Agrawal R;Srikant R Fast algorithms for mining association rules 1994

5. Xiong Y;Zhu Y Y A Multi-Supports-Based Sequential Pattern Mining Algorithm 2005

本文链接：http://d.wanfangdata.com.cn/Periodical_jsjyyyrj201108036.aspx

第２８卷第８期

２０１１年８月

计算机应用与软件

ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｈ叮ａｒｅ

Ｖ０１．２８Ｎｏ．８Ａｕｇ．２０１１

ＶＰＭ：一个就医行为模式挖掘算法

周

坤１王爱荣２张敬谊３熊赘１朱扬勇１

１（复旦大学计算机科学技术学院上海２００４３３）２（上海市医疗保险信息中心上海２０００４０）３（万达信息股份有限公司上海２叭１１２）

摘要在医保基金管理中，第三方付费机制和信息不对称等问题造成了基金运作面临严重“道德风险”困境，医药机构和参保

人可能存在过度使用医保基金的倾向。通过对参保人就医行为序列的分析挖掘其就医行为模式，对于发现疾病发病规律、参保人健康状况以及是否存在违规欺诈行为，从而有效防范基金风险具有非常重要的作用。由于就医行为模式的特殊性，传统的序列模式挖掘算法在结果可用性和效率上存在问题，如挖掘结果丢失时间间隔较长的模式，挖掘过程需多次构造投影数据库等，因此难以直接应用。针对就医行为模式特点，提出了基于二叉树增长策略的向量模式挖掘算法ＶＰＭ。实验表明，ＶＰＭ算法在解决就医行为模式挖掘问题上具有良好的性能。关键词

医保基金

风险防控

就医行为模式

序列模式

数据挖掘

中图分类号ＴＰｌ８文献标识码Ａ

ＶＰＭ：ＡＭＥＤＩＣＡＬＴＲＥＡＴＭＥＮＴＢＥＨ渔ＶＩＯＵＲ

ｚｈｏｕＫｕｎｌ

ＰＡＴＴＥＲＮ

ＭＩＮＩＮＧＡＬＧｏＲＩＴＨＭ

ｚｈｕＹａｎｇｙｏｎ９１

ｗａｎｇ

Ａｉｒｏｎ矿

ｚｈａｎｇＪｉｎｇｙｉ３

ｘｉｏｎｇＹｕｎｌ

。（＆＾∞ｆ矿ｃ０唧Ⅱ河ｓｃ切Ⅻ，凡也ｎ￡，ｎ妇Ｈ蚵，舶ｏ，。ｇ舰ｉ

２０Ｄ钉ｊ，蕊ｉＭ）

２（踟，ｔ咖ｉ胁以池ｆ，ｍⅡｍ删倒白删如厅Ｄｎ灯。踟ｎｇｈｉ２０Ｄ∞Ｄ，醌ｉＭ）

３（％，幽３蝴泐ｃｏ．，￡ｍ，踟，咖ｉ

ｆｕｎｄ

２０，Ｊ，２，吼ｉＭ）

ｆ南ｍ

Ａｂｓ仃ａｃｔＷｉｔｈ

ｒｅｇ捌ｔｏｍｅｄｉｃａｌｉｍｕ啪ｃｅ

ａｒｅ

ｍｎａｇｅｍｅｎｔ，ｐｍｂＩｅ啪ｄ甜ｖｉｌｌｇｔｌｌｉｒｄ－ｐａｒＩ）ｒｐａｙｍｅｎｔｍｅｃｌｌａ仉ｉ８ｍ柚ｄｉＩＩｌｌｂａｌ鲫ｃｅｏｆ

Ｂｏｔｈｍｅｄｉｃａｌａｇｅｎｃｉｅ８ａｎｄ

ｉｎｆｏｎ舱ｔｉｏｎａｃｋｎｏｗｌｅｄｇｅｍｅｎｔ

ｐａｔｉｅｎｔｓｔｅｎｄｐｅｏｐｌｅ

ｔｏ

ｔｏ

ｃ甜ｓｉＩｌｇｔｈｅｐｌｉｇｈｔｏｆ”ｉｍｍｏｍｌ时ｒｉｓｋＩ．ａｌｏｎｇ埘ｔｈｔｈｅｏｐｅｒａｔｉｏｎｏｆｔ｝Ｉｅｆｕｎｄ．

ｅｘｅｅｓｓｉｖｅｌｙｅｘｐｌｏｉｔｔ｜ｌｅｍｅｄｉｃａｌ

ｉｌｌｓｕ埘ｌｃｅｆｕｎｄ．ＴｈｍｕｇＩＩ

ｐａｔｔｅｍ，ｉｔｉｓｅ鹊ｉｅｒ

ｔｏ

ａＩｌａｌｙｓｉｓｏｆｍｅｄｉｃａｌ

ｔｒｅａｔＩＩｌｅｎｔｂｅｈａｖｉｏｕｒ

ｓｅｑｌｌｅｎｃｅ“ｔｌｌｅｉ璐ｕｒｅｄ

ｍｉｎｅｔｈｅｉｒｒｎｅｄｉｃａｌ协Ｂａｔｍｅｍｂｅｈａｖｉｏｕｒｄｉｓｃｏｖｅｒｔｌｌｅ

ｒｅｇｕｌａｒｉｔｉｅｓ

ｏｆｄｉｓｅａｓｅｓ，ｔｈｅｈｅａｌ出ｓｔａｍｓｏｆｔｈｅｉｎｓｕｒｅｄ

ｔ０

ｐｅｏｐｋ，锄ｄｗｈｅｔｈｅｒｔＩｌｅｒｅｉｓ蚰ｙ如ｕｄｂｅｈ８ｖｉｏｕｒ，ｔＩｌｅｒｅｆｂｒｅｉｔｐｌａｙｓ粕ｉｍｐｏｎａ眦ｒｏｌｅｉｎ

ｏｆ出ｅｍｅｄｉｃａｌｔｒｅａｔｍｅｎｔｂｅｈａｖｉｏｕｒｐａｔｔｅｍ８ｉｎＩＩｌｉｎｉｎｇ

ｃｏｎｔＩｏＵｉＩｌｇ妇ｆｕｎｄｒｉｓｋ．【）ｕｅ

ｔｈｅｓｐｅｃｉａｌ

ｎａｈ啪

ｐａｔｔｅｍ，ｔｈｅｒ；ｅｉｓｄ娟ｃｉｅｎｃｙ

ｏｎ

ｉ协陀ｓｕｌｔ

ｆ宅鹪ｉｂｉｌｉｔ），粕ｄｅ伍ｃｉｅｎｃｙ，ｓｕｃｈ∞山ｅｍｉｓｓｉＩｌｇｏｆｌｏｎｇｅｒｉｎｔｅｎ，ａｌ

ｒｅｓｕｌｔｓ锄ｄｔｈｅ陀ｑｕｉｒｅｍｅｎｔｆｏｒｒｅｌ）ｅａｔｅｄｌｙｂｕｉｌｄｉｎｇｓｈａｄｏｗｃ鹬ｔｉＩｌｇｄ北Ｉｂ够∞，ｅｔｃ．ｆｏｒ岫ｄｉｔｉｏＩｌａｌｓｅｑｕｅｎｔｉａｌ

ｅｎｃｏｕｎｔｅｒｓ

ｐａ仕哪ＩＩｌｉｎｉｎｇ

ｐａｔｔｅｍ，ｔｌｌｅ

ａｌｇｏｒｉｔＩｌＩ璐．ＴＩｌｅｒｅｆｏｒｅｔｈｅｉｒｉｍ啦ｅｄｉａｔｅａｐｐｌｉｃａｔｉｏｎ明ｔｈｏｒｓｐｒｏｐｏｓｅ

ａ

ｂ删ｅ玛Ａｉｍｉｎｇ

ａｔ

ｔｈｅｓｐｅｃｉａｌｔｉｅｓｏｆｍｅｄｉｃａｌｔｒｅａｔｍｅｎｔｂｅｈａｖｉｏｕｒ

ｎｏｖｅｌ

ａｌｇｏｒｉｔｂ

ｂ鹳ｅｄ

ｏｎ

ｂｉ∞ｒｙ－ｔＩ傥铲州ｈ

ｓｔｒａｔｅｇｙ，ｃａｌｌｅｄＶｅｃｔｏｒＰａｔｔｅｍ

Ｍｉｎｉ｜ｌｇ址ｇｏｒｉｔｌｌＩｎ（ＶＰＭ）．ＴｈｅｏｒｅｔｉｃａＩ删ｙｓｉｓ

ｐａｔｔｅｍ

ａｎｄｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔＶＰＭａｌｇＤｒｉ出ｍｐｅ娟）ｒＩＩｌｗｅＵｉｎｓｏｌｖｉｎｇｔｈｅｐｍｂｌｅｍｏｆｍｅｄｉｃａｌ廿ｅａｔｍｅｎｔｂｅｌｌａｖｉｏｕｒｐａｔｔｅｍｍｉｎｉｎｇ．

Ｋｅ＂ｒ叫凼

Ｍｅｄｉｃａｌ池ｕ砌ｃｅ

ｆｈｎｄＲｉｓｋ

ｐｒｅｖｅｌｎｉ蚰粕ｄｃｏｎｈｄ

Ｍｅｄｉｃａｌ

ｔｒｅ咖ｅｎｔ

ｂｅｌｌａ“伽ｒ

ＳｅｑｕｅｎｔｉａＩ

ｐａｔｔｅｍ

ＤａｔａｒｎｉＩｌｉｌｌｇ

下一些特点。

Ｏ

引言

首先，表示方式不同。参保人就诊往往是突发性的，比如某些人平时不怎么生病，但最近忽然患有某类疾病，就诊次数将会频繁增长，如表ｌ所示。

表ｌ示例序列集

ＩＤｌ

序列模式挖掘问题是Ａｇｒａｗａｌ和晒ｋａｎｔ在１９９５年研究交

易序列时第一次提出的…。许多应用领域都涉及到序列模式的挖掘。２】。医保基金风险防控领域中参保人就医行为模式就是一种序列模式。通过对就医行为模式的挖掘，可以得出疾病的发病规律；划分易患人群，提前做好防治工作；还可以筛选出就医行为异常的参保人，为审核监督提供重点监督管理对象，提高审核监督力度和效率。因此，如何挖掘就医行为模式对医保基金风险防控具有十分重要的意义。

就医行为是指参保人在一段时间内到医院就诊的次数。例如，参保人在第１、２、４、６天就诊，可以表示成序列模式＜ｄ。，如，也，ｃｆ６＞。就医行为模式不同于一般的事务序列模式，它具有如

序列

ｄｌ，ｄ２，ｄ３，ｄ４，ｄ１００，ｄ３０ｌｄｌｏ。ｄｌ∞，ｄ加１＇ｄ撇，ｄ２０３，ｄ２阱

２

参保人ｌ和参保人２存在一种相同的就医行为模式：连续

收稿日期：２０ｌＯ一０３—３ｌ。上海市科委科研计划基金项目（０８５１ｌ５００２０３）；上海市重点学科建设项目（Ｂｌｌ４）。周坤，硕士生，主研领域：数据挖掘，数据科学。

万方数据

１２４

计算机应用与软件

２０１１年

４天就诊。但如果仅从ｄ，上看，是找不出这种模式的，因为面、ｄ２、ｄ３、ｄ４显然不同于ｄ∞，、ｄ２０２、ｄ抛、ｄ枷。所以如果仅仅像交易型记录那样记录天数．算法难以挖掘出这种模式。因此必须将交易数据转化成向量形式，某天内用ｌ表示就诊，０表示未就诊。这样我们就能挖掘出＜ｌ，ｌ，１，１，０，０，…，Ｏ，ｌ＞与＜ｌ，０，０…０，ｌ，１，ｌ，ｌ，Ｏ，０，ｌ＞之间的共有模式＜ｌ，１，ｌ，ｌ＞。

其次，我们找的往往是精确的模式匹配，如＜１ｌＯｌ＞与＜１０００ｌＯｌ＞显然是不同的就医行为模式。

第三，由于就诊治疗的阶段性，单条序列中可能含有较大时间间隔的重复模式。例如，＜１１１０００…０００ｌｌｌ…＞表示某参保人上个月化疗和本月化疗记录。

第四，就医行为模式以ｌ开头和结尾。在就医行为模式中，ｌ表示就诊，０表示未就诊，故以０开头或结尾的序列是没有实际意义的。例如模式＜１０ｌＯｌ０００＞等价于模式＜１０１０１＞，＜０００１０１０ｌｌ＞等价于模式＜１０１０ｌｌ＞。

随着近年来的研究与发展，很多序列模式挖掘算法被提出。这些算法主要分为两大类，一类基于Ａｐｒｉｏｒｉ性质；另一类基于

频繁模式增长。代表性的算法有ＧＳ川Ｊ、Ｐ硝ｘＳｐ锄嵋１。虽然这

些算法原则上可以处理更广泛的数据结构，但是它们最初都是针对交易序列模式设计的，难以直接应用到诸如生物、就医行为等序列数据上。因此，这些算法存在一些共同的问题。首先，带有约束的Ｐｒｅ６ｘｓｐａｎ等算法在投影数据库中查找序列模式时，引入了模式间隔约束，考虑了序列模式问可能存在间隔的情况。例如，针对就医模式序列＜１１０ｌ＞和＜１０００１０１＞，将会得到＜ｌ１０１＞这样的频繁模式，但在第二条序列中包含的＜１１０ｌ＞模式间间隔了没来就诊的三天＜ｌｏ００１０ｌ＞。从就诊意义上看，它与＜１１０ｌ＞存在较大差异。其次，Ｐｒｅｆｉｘｓｐａｎ算法在创建初始投影数据库时，仅仅对单个符号的第一次出现进行投影，而忽略该符号在该条序列中重复出现的情况。因此，如果单条序列中含有重复的序列模式，并且这些模式超过了引入的时间间隔的约束，则这些模式将会丢失。而生物ＤＮＡ序列、就医行为序列中常常含有这类序列模式。针对生物序列，Ｙｕｎ等提出ＢｉｏＰＭ算法旧Ｊ，很好地解决了生物序列模式挖掘问题。但针对就医模式问题，该算法会产生大量莺叠投影数据库。降低了算法效率。第三，大部分已有算法没有考虑到分布支持度和局部支持度的区别。多投影策略会造成模式误判，可能重复计算单条序列中的重复模式，从而把局部频繁的模式认为是全局频繁的。例如模式＜１１１＞是＜１０００１１１０００１ｌｌ＞中的局部频繁序列，但可能并不是序列数据库中的全局频繁序列。因此需要记录模式对应的分布支持度和局部支持度，用以判断模式是全局频繁还是局

部频繁的。最后，无论是Ｐ蔺ｘｓｐ锄算法还是ＢｉｏＰＭ算法，得到

的模式集中可能会存在冗余，即包含重叠的模式。这类问题并没有得到很好的解决。

本文针对就医行为模式的特点，提出了一个新的序列模式挖掘算法：向量模式挖掘算法ＶＰＭ（Ｖｅｃｔｏｒ

Ｐａｔｔｅｍ

Ｍｉｎｉｎｇ）。该

算法采用二叉树增长的策略，通过建立ＶＰ．ｔｒｅｅ的方式挖掘频繁模式，避免产生不必要的投影数据库，并有效区分分布支持度和局部支持度。分析和实验表明，ＶＰＭ算法具有良好的性能。１

问题定义

就医行为数据库Ｄ是元组＜，Ｄ，｜ｓ＞的集合，如表２所示。

，Ｄ表示参保人卡号，ｓ表示就医行为模式。

万方数据

表２就医行为数据库Ｄ

ＩＤｄｌｄ２ｄ３ｄ４ｄ５ｄ６ｌ１

１０ｌＯ

１

２

ｌＯ

ｌＯ

ｌ】

３

ｌＯＯ１

ｌｌ

４

ｌ

０

Ｏ

Ｏ

ｌ

ｌ

如果ａ是ｓ的子序列，则称元组＜，Ｄ，ｓ＞包含序列ａ。序列“在就医行为数据库中的支持度是数据库中包含ａ的元组个数，记为ｓｕｐｐＤｎ，（口）≥ｍｉｎ－ｓｕｐ。给定一个正整数ｍｉｎ—ｓｕｐ，表示最小支持度阈值。如果ｓｕｐｐＤｎ。（ａ）≥ｍｉＩｌ＿ｓｕｐ，则称序列ａ在数据库Ｄ中是频繁的。

２ⅦＭ：向量序列模式的挖掘算法

２．１基本概念

引理１分区问题。

①设｛口，，口：，…，％｝是Ｄ中所有长度为１的序列模式集合。在Ｄ中的所有序列模式可以分成ｎ个不相交的子集，第ｉ个子集（１≤ｉ≤ｎ）是具有前缀Ｈ１为ｏ；的序列模式集。

②设ａ是长度为Ｚ的序列模式，｛崩，岛，…，卢。｝是所有具有前缀ｄ的长度为Ｚ＋钾的序列模式。包含前缀仅的所有序列模式的集合，ａ本身除外，可以被分为ｍ个不相交的子集。第Ｊ个子集（ｍ≥』≥１）是含有前缀鼠的序列模式。

引理ｌ的证明参见Ｐ—ｉｘＳｐ柚算法。基于引理ｌ，ＶＰＭ算法可通过建立ＶＰ．ｔｒｅｅ树的方式递归地把问题分割成几个小问题解决，并且序列模式的每个子集也可以进一步划分，从而采用模式增长的方式来产生频繁模式。

定义ｌ

ＶＰ一讹ｅ一棵向量模式树定义为一棵有向根树ｒ

＝＜ｙ（ｒ），Ｅ（ｒ）＞，其中，ｙ（ｒ）是结点集，每个结点口属于ｙ（Ｔ），代表一个（或埘个）序元的值和它的分布支持度，分别记为仉口口￡ｗ和仉ｓｕｐ。Ｅ（ｒ）ｃｙ（ｒ）×ｙ（ｒ）是（有向）边集。ｒ必须满足约束：Ｖ口Ｅｙ（ｒ），口．８ｕｐ≥ｍｉｎ－ｓｕｐ（最小的支持度阈值）。根据就医行为数据库建立一个ＶＰ．ｔｒｅｅ，其根结点到每个叶子结点的路径序列就是序列模式。

定义２散列

散列是一种以线性表中每个元素的关键字

Ｋ为自变量，通过一种函数＿ＩＩ（Ｋ）计算出函数值，并以这个值作为一块连续存储空间的单元地址，将该元素存储到这个单元中的存储方法。

散列技术可以用来压缩数据库，减少，／Ｄ次数。我们根据序列中ｌ的个数将其散列到不同的桶中。如图１所示。

桶地址

ｌ

２

３

４

｛１００００１１０００ｌＩｌｌ加ｌ１１ｌｌ∞ｌ

ｌｌ｝

｝

Ｉ咖ｌＯ

１１∞ＩＯ

ｆｌｌＯｌＯ

｛１１００儿

檑内容

ｌｌ

ｌｌ

１００ｌ∞

ｆｌｌｏｏＯ

｝ｌ

图ｌ散列表：根据每条序列中Ｉ的个数将其映射到散列表的不同桶中

第８期

周坤等：ＶＰＭ：一个就医行为模式挖掘算法

２．２、甲Ｍ算法的序列模式产生

２．３

ＶＰＭ算法

根据以上定义和基本概念，下面给出基于频繁模式增长的

…ｗ２２。

例ｌ设就医行为数据库Ｄ如表３所示．最小支持度闺值

无候选生成的就医行为模式挖掘算法ＶＰＭ。

表３就Ｅ行为蕞式数据牟Ｄ

算法ＶＰＭ模式。

使用Ｖｎｎ槐，通过模式增长挖掘就医序列

输入Ｄ：就医行为模式散据库；一一ｓｕｐ：最小支持度计数

阈值。

输出就医行为模式集。方法

（１）为降低ⅣＯ次数．将数据库Ｄ中就医序列读人戢列表

就医行为模式挖掘过程如下：

步骤１为降低∥０攻数，首先将就医模式数据库Ｄ中的记录存＾散列表Ｐ中。由于本例所有序列都古有４个１，故映射到同一个桶中。如表４所示。

襄４靛到囊ｖ

Ｖ中。

（２）接以下步骤构造ｖｎⅡ恍：

（ａ）首先创建ＶＰ—盹ｅ的根结点，以１标记它。

（ｂ）分别刨建根结点的左右子结点，分别以０，ｌ标记之。记录该结点到根结点的路径，存人栈中。出栈，形成扶根结点到该结点的序列‰并扫描散列表Ｖ，如果散列表中序列ｑ古有该序列＾，则其支持度ｓ。８”ｐ加ｌ。统计根结点左右子树的支持度，

如果某子树ｓ．．ｅｕｐ㈣ｎ－暑“ｐ，则删除该子树，并记根结点该子

树为Ⅳ““如果根结点左右子树均为№“，则该结点为叶子结

点，人队列Ｑ｜Ｊｅｕｅ，Ｑ—ｅ中用于保存所有叶子结点。

（ｃ）递归执行（ｂ），直到ＶＰ・ｔ眦所有叶子结点的左右子树

步骤２创建根结点．用慎ｌ标记。

步骤３划分搜索空问。就医行为模式表示成二元向量的形式，其序列模式的完全集可根据２个前缀划分成：（１）前缀为（０＞的子集；（２）前缀为＜ｌ＞的子集。创建根结点的左右子树结点，分别用Ｏ．１标记。

步骤４支持度计数。记录从根结点到该序元的路径１０和１】．其中１０含有１个ｌ，故扫描散列表ｖ中大于等于１的桶地址，１１吉有２个１．故扫描散列表ｖ中大于等于２的桶地址。这里都扫描４号桶。如果桶中向量ｃ；包含序列１０，则口．．ｓ“ｐ加ｌ（即使向量ｅ．包古多条１０序列，也仅仅对－．．８“ｐ贡献了１，从而有效区别分布支持度和局部支持度问题）。统计１０序列和１１序列的支持度．１Ｅ为（０：４），＜１：３＞，其中，符号＜序元：计数）表示从根结点到该序元的支持度计数。如果该序元的支持度计数”ｓｕｐ（ｍｌｎ－ｓｕｐ，则删除该序元结点．并记该序元的父结点该子树为空。

径｝

（ｂ）ｂｒ队列中每个叶于结点Ｂ，ＥＯｍ∞ｄｏ

均为空。

（３）通过调用叫‘ｐ．Ｊｔ一呻ｅｎｃ。ｐａｌｌｅｍ（ＶＰ岫，Ｑｕｅｕｅ）生成

ｓ；｝建立韧始栈．月ｆ保存从叶｝结点到根结点∞路

就医序列模式集。

（４）‰ｋ

（ｃ）Ｈｐ叫

（ｄ）（ｅ）

（ｆ）Ⅲ“ｌ

Ｂ埘ｄ（５．）｛将该结点＾栈ｆ

％＝ｓ…ｉ日期到Ｚ结点｝

５…ｕｕ

（ｇ）ｍⅢ

（ｈ）（】）∞ｄｂ‘

（＿）∞ｍ目…Ｐ‘ｙ

（ｋ）Ｒ咖Ｊ１Ｉ＝ｕ８ｔ

ｓＦ…ｐ叩（）｛±成序列模式｝

（４）删除序列模式中可能含有的０结尾，然后判断删踪后的序列是否是序列模式集中其他序列的前缀。如果是，删除该序列，从而去除冗余。最后输出就医行为模式集。

３实验分析

３ｌ数据集和实验环境

本实验的散据集来自某市医疗保险局提供的就医模式序列数据库。该数据库中共收集了１００天内就诊２０状以上的

１９２

７９０名参保人就诊记录。

实验程序在内存为２Ｇ、处理器为Ｉ““嗍酷睿双核２

ｘＰ

２４

ｃｍ的ｐｃ机上运行．操作系统为ｗｌｎｄｏｗ５验程序采用ｈＨ语言编写。

中叶于结点之间的指针链接（图中虚日２对＆３就日模式

Ｐ曲聃ｌｏｎｄ。实

线所示），这样有助于依次回蝴到根结数据库Ｄ建ｉ的ｖ＾№

点，输出序列模式。

步骤７就医行为模式是从根结点到每个叶子结点的路径的汇集。奉例中，行为模式为；＜１００１００１），（１１＞ｆ。

３．２实验结果

实验的目的是对比ＶＰＭ算法和胁ｎｘｓｐ蛆算法在不同阈

值支持度下得出的序刊模式的个数和长度。

（下转第１帅贾ｌ

万方数据

１８０

计算机应用与软件２０１１年

实验过程中，本文算法中的式（５）改为：ｓ溉（邪，粥Ｒ）＝÷［ｓ拥（Ｓ，，彤）＋ｓ拥（如，肋）］

Ｉ

‘

文献［４］算法和本文算法的平均查全率分别为７３％和８４％，平均查准率分别为８ｌ％和７９％，两种算法的平均查准率相近，本文算法的平均查全率较高。分析得知，文献［４］的算法只注重用于服务匹配的领域本体概念间的子类关系，忽略了概念间的其它多元关系，导致概念的语义不能被完整地反映出来，从而影响了算法的查全率。本文算法在对服务进行匹配时利用了本体概念间的多元关系，因而在整体性能上较好。

４结语

服务匹配算法是ｗｅｂ服务发现的核心技术。本文提出的基于语义相似度的ｗｅｂ服务匹配算法，利用本体概念间的多元关系定义了一种语义距离，在此基础上，给出概念间的语义相似度计算方法，进而通过计算与服务功能参数集中参数相应的本体概念间的语义相似度实现了ｗｅｂ服务的匹配。实验的结果表明，与文献［４］中的算法相比，本文提出的算法具有较好的整体性能。本文主要针对服务的功能匹配进行了研究，但没有考虑到服务的ＱｏＳ属性，所以下一步工作是研究服务的Ｑ０ｓ匹配，以使服务匹配算法迸一步完善。

参考文献

［１］廖祝华，刘建勋，刘毅志。等．ｗｅｂ服务发现技术研究综述［Ｊ］．情

报学报，２００８，２７（２）：１８６一１９２．

［２］吕庆聪，周集良，杨帆，等．普适计算机服务匹配技术研究［Ｊ］．计

算机科学，２００９。３６（１１）：１８２—１８５．【３］Ｐ∞ｌｕｏｃｉ

Ｍ。Ｋａｗ出哪Ｔ，Ｐａｙｎｅ

Ｔ

Ｒ，眦ａ１．ｓｅｍ明ｔｉｃＭａｔｃｈｉｎｇ０ｆ

ｗｅｂ

ｓｅⅣｉｃ∞ｃ印ｌａｂｉｌｉｔｉ∞［ｃ］／／ＰＴ∞ｅｅｄｉｎｇｓ

０ｆｔｈｅ

Ｆｉｒｓｔ

Ｉｎｔｅｍａｔｉｏｎａｌ

ｓｅｍ如ｔｉｃＷｅｂ

Ｃｏｎｆｅ地ｎｃｅ（ＩＳｗＣ）．Ｓａｒｄｉｍａ，ｌｔａｌｉ８，２００２：３３３

—３４７．

［４］彭晖，史忠植。邱莉榕，等．基于本体概念相似度的语义ｗｅｂ服务

匹配算法［Ｊ］．计算机工程，２００８，３４（１５）：５ｌ一５３．

［５］黄志成，李华．改进的语义ｗｅｂ服务匹配算法设计与实现［Ｊ］．计

算机工程，２００９，３５（２０）：８８—９０．

［６］Ｍ８而ｎＤ，ＢｕｒｓｔｅｉｎＭ。ＨｏｂｂｓＪ。ｅ【ａ１．ＯｗＬ・ｓ：ｓｅ眦ｎｔｉｃＭａｒＩｃ印ｈ

ｗｅｂ

ｓｅｆｖｉ啷［ＥＢ／ＯＬ］．［２００４一ｌｌ一２２］．ｈｔｔｐ／／ｗ’哪．’ｄ．叫

ＳＩｌｂｎｌｉｓ８ｉｏｎ／ＯＷＬ．ｓ／．

［７］顾金謇，王芳．关于本体论的研究综述［Ｊ］．情报科学，２００７，２５

（６）：９４９—９５６．

［８］刘汉兴。林旭东，田绪红．基于本体的自动答疑系统的研究与实现

［Ｊ］．计算机应用，２０ｌＯ，３０（２）：４１５—４１８．

［９】姜华．一种基于本体的概念语义相似度计算研究［Ｊ］．计算机应用

与软件，２００９，２６（７）：１４３一１４５．［１０】Ｋｈ丑ｌｉｋ

Ｍ

Ａ，蹦∞Ｂ．ＯｗＬｓ［ＥＢ／ＯＬ］．［２００６一１２—０１］．ｈｕｐ：∥

ｐ玎Ｄｊｅｃ协．ｓｅｎｎ州出∞ｎｔ商．ｏ口ｇ／矗∥ｄｏｗｎｌｏＢｄ．ｐｈｐ／２５５／ｏ岬１５一ｔｃ２．面ｐ．

【上接第１２５页）

实验结果表明，ＶＰＭ算法得出的序列模式结果集中序列的个数和长度明显比ＰｒｅｆｉｘＳｐ柚算法的多，尤其在阈值较小的情况下。此时满足条件的模式大大增加。并且进一步的实验对比表明。ＶＰＭ算法的序列模式结果集中包含了Ｐｒ；ｅｆｉ】【ｓｐ锄算法得出的所有序列模式，表明了Ｐｒｅ６）【ｓｐ如算法并不能获得所有的就医行为模式，遗漏了参保人阶段性就诊治疗所产生的含有时

万方数据

间间隔较长的重复序列模式。而ＶＰＭ算法能很好地挖掘出这类行为模式。如图３、图４、表５所示。

８００

’’

ｔ、’

ｇ

６００

．ｏ

旨枷

＼＼

－、～，．

Ｚ２００

‘＼

、

～～～●

Ｔ

＋＾

Ｏ

ｌＯ％

２０％３０％

臣三运巫三三固

图３不同支持度下序列模式个数比较

２５２０

～～１

雹１５

●ｈ一

姜ｌｏ

＼－

５—、●

｛

０

ｌｏ％

２０９６

３０９６

巨三匦五匠翔

Ｓｕｐｐｏｒｔ

ｔｈｒｅｓｈｏｌｄ（％）

图４不同支持度下序列模式长度比较表５在不同的支持度下Ｐ代ｆｉｘＳ呻ｎ和Ⅵ礓Ｉ

结果集中序列模式个数和长度的比较支持度

ＶＰＭ

Ｐｒ蛳ｘＳｐａｎｌＯ％

ｋｎｇｔｈ：２２

ｋｎｇｔ｝Ｉ：１６

Ｎｕｍｂｅ硌：７３６

Ｎｕｍｂｅ瑁：３５３

２０％

ｋｎｇｔｈ：２２

ｋｎｇｔｈ：１１

ＮｕｌＩｌｂｅ糟：３８２

Ｈｕｍｂｅ玛：１３１

３０％

ｋ“Ｓｔｈ：１８

ｋｎｇｔｈ：７

Ｎｕｍｌ）ｅｒｓ：２５３

Ｎｕｍｂｅｒｓ：９０

实验结果表明。针对就医行为模式的特点，ＶＰＭ算法优于

Ｐｒｅ脑ｐａＩｌ算法。

本文针对就医行为模式的特点，提出了一个新的就医行为目前，ＶＰＭ算法已被成功应用在某市医保基金风险防控数据仓库项目的数据挖掘过程中，为后续的医保风险防控、决策支持提供帮助。进一步工作我们还将考虑内存建树、数据压缩等问参考文献

［１］Ａｇ瑚同Ｒ，蹦ｋ∞ｔＲ．Ｍｉｎｉｎｇ∞ｑｌＩ∞ｔ试ｐＢｔｔｅｍｓ：Ｇｅｍｒａｌｉｚ“ｏ邶蜘ｄ

ｐｅ而ｍｍｃｅｉｍｐｎ玳ｍｅｎｔ８［ｃ］／／ＥＤＢＴ。１９９６．

［２］Ｊｉ蛐Ｐｅｉ，ｅＩａ１．Ｐｒ曲ｘｓｐ曲：ＭｉｎｉｌｌｇｓｅｑｕｅｎｔｉａＩＰａｔｔｅｍ８Ｅ币ｃｉｅｎｄｙｂｙ

Ｐｔ幽ｘ・Ｐ叫佻ｌ耐Ｐ砒ｔ哪Ｇ彤ｗｔＩＩ［ｃ］／／Ｄａｌａ

Ｅｎｇｉｎｅｅｒｉｎｇ，２００１．

［３］）（ｉｏｒＩｇＹ，动ｕ

ＹＹ．ＢｉｏＰＭ：Ａｎ

Ｅｍｃｉ棚ｔＡｌｇｏ削【ｌｍ缸ＰｒｏｔｅｉｎＭ０ｔｉｆ

ＭｉｎｉＩＩｇ［ｃ】／／ｌｃＢＢＥ，２００ｒ７．

【４］Ａ印哪ａｌＲ，ｓｒｉｋ蛐ｔ

Ｒ．ｆ．聃ｔ

ａｌ窜丽ｔｌｌｍｆｏｒｍｉｎｉｎｇａｓｓ∞ｉ砒ｉｏｎｍｌｅｓ

［Ｃ］／／ＶＬＤＢ．１９９４．

［５］）【ｉ∞ｇＹ。办ｕＹＹ．ＡＭｕｍ・Ｓｕｐｐｏｒｔｓ—Ｂａ∞ｄＳｅｑｕｅｎｔｉａｌ

Ｐａｎ哪Ｍｉｎｉ哩

‰ｈ∞１０９ｙ№ｅｅｄｉ咿，舢．

Ａ蛳ｔｌ瑚【ｃ］／／ｈｎｅｌＴＩａｔｉｏｌｌａｌ酬毫嗍ｃｅ硼ｃ伽ｐｕｔｅｒ如ｄｌｎｆｂｎ眦ｔｉ∞

４结语

模式挖掘算法ＶＰＭ。实验表明，该算法优于Ｐｒｅｆｉ）【Ｓｐａｎ算法。题。

VPM:一个就医行为模式挖掘算法

作者：作者单位：

周坤， 王爱荣， 张敬谊， 熊赟， 朱扬勇， Zhou Kun， Wang Airong， Zhang Jingyi， Xiong Yun， Zhu Yangyong

周坤,熊赟,朱扬勇,Zhou Kun,Xiong Yun,Zhu Yangyong(复旦大学计算机科学技术学院,上海,200433) ， 王爱荣,Wang Airong(上海市医疗保险信息中心,上海,200040)， 张敬谊,ZhangJingyi(万达信息股份有限公司,上海,201112)计算机应用与软件

COMPUTER APPLICATIONS AND SOFTWARE2011,28(8)

刊名：英文刊名：年，卷(期)：

参考文献(5条)

1. Agrawal R;Srikant R Mining sequential patterns:Generalizations and performance improvements 19962. Jian Pei PrefixSpan:Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth 20013. Xiong Y;Zhu Y Y BioPM:An Efficient Algorithm lor Protein Motif Mining 20074. Agrawal R;Srikant R Fast algorithms for mining association rules 1994

5. Xiong Y;Zhu Y Y A Multi-Supports-Based Sequential Pattern Mining Algorithm 2005

本文链接：http://d.wanfangdata.com.cn/Periodical_jsjyyyrj201108036.aspx