计算机集成制造系统 第２３卷行比较，发现二者在粒度上不一致的部分，从而合理地改进原有的业务流程。进而在分析业务活动间关联规则的基础上合理地分裂或合并业务流程节点，以实 现 业 务 操 作 的 细 化 或 简 化。 在 较 粗 粒度的要求下，对于几个强关联的操作，可以将其对应的多 个 过 于 细 分 的 节 点 合 并 为 一 个 整 合 的 节点，以使业务流程更简洁易懂，提高执行效率并 增强其与人员的交互性；在较细粒度的要求下，可以将一个整 合 的 节 点 继 续 细 分 为 多 个 节 点，分 别 对应几个强关联的操作。节点的分裂可以防止数据或条件丢失，也可以防止逻辑上出现错误的关联，细化的操作能够增强业务流程的精确性。根据粒度合并或 分 裂 节 点 的 实 例 如 图 １ 所 示，在 高 校 课程管理中，课 程 信 息 变 动 包 括 课 程 的 更 新 和 学 生选课的变动，在实际业务操作中，课程表和选课 表是绑定在 一 起 操 作 的，因 此 可 以 在 课 程 变 动 流 程上将二者合并考虑；而在学籍信息变动中，由于对学生选课 信 息 和 学 生 信 息 的 操 作 相 对 独 立，实 际业务产生 了 选 课 变 动 和 查 询／更 新 学 生 信 息 两 种相互独立的节点，对应于原流程，可将学籍信息 变动节点通 过 包 含 网 关 进 一 步 细 分 为 两 类，以 防 产生错误的 关 联。在 节 点 发 生 变 化 时，应 及 时 将 人工评判加 入 网 关 的 选 择 和 节 点 间 的 兼 容 问 题 中，以保证改变后的流程仍能顺利执行，其中：网关分为并行、排他、包含、事件网关４种，应根据业务 需要选择；数 据 兼 容 性 需 要 通 过 拟 定 兼 容 性 评 判 规则来判断。在与本文相关的工作中，文献［１］通过数据库日志产生相对独立的执行路径，作为区分不同特定事务之间的参考；文献［２］提出经典的 Ａｐｒｉｏｒｉ算法挖掘关联规则；文献［３］中的多阶迭代思想反复运用全局的数据，充分考虑了相邻数据对当前数据的影响；文献［４－６］分别对最大子图优先、子图距离、流程测距等方法进行了探究。在此基础上，本文将数据库日志（ＤＢＬｏｇｓ）通过向量化和相似度计算转换为流程日志（ＷＦＬｏｇｓ），并通过对传统 Ａｐｒｉｏｒｉ算法加以调整从当前业务流程中挖掘关联规则，从产生的关联规则中获取用户行为模式（Ｂｅｈａｖｉｏｒ　ｐｒｏｆｉｌｅ），用户的行为模式可以客观反映用户的操作规律，能为优化流程提供指导。其中在关联分析算法中，本文采用多阶迭代的方式提供评价策略来保证合理性。在业务流程优化领域，本文在深入了解已有工作后，从数据库日志入手，根据日志操作中潜在的规律发掘流程中可优化的空间。不论当前业务是否已流程化，本文方法均可通过数据库日志导出流程日志，为后续 流 程 优 化 奠 定 基 础。 日 志 分 析 框 架 如 图 ２所示。本文主要介绍数据库日志的相似性分析方法，首先提出数据库日志多粒度化以及转化为流程日志向量的方法，然后从角度和距离两方面研究向量之间的相似性，并提出迭代计算的概念；在相似度的基础上，利用基于相似度的 Ａｐｒｉｏｒｉ算法对操 作集进行关联分析，获取用户行为模式，并通过迭代计算评估；通过选取实例进行实验对理论进行验证；最后对所做工作进行总结和展望。２　数据库日志相似性分析２．１　数据库日志标签、粒度划分及向量化采用较简单的 ＬＣＲ 日志文件进行研究。ＬＣＲ文件中每条操作涉及的各类标签均抽象自 ＳＱＬ 语句，采用粒度划分的方式将其分成多个层次。最粗粒度级别包含标签?ｓｏｕｒｃｅ＿ｄａｔａｂａｓｅ＿ｎａｍｅ?，该标签代表所有操作的整体数据源，在整个数据库环境下汇总了所有操作；中间粒度级别包含标签?ｃｏｍ－ｍａｎｄ＿ｔｙｐｅ?，?ｏｂｊｅｃｔ＿ｏｗｎｅｒ?，?ｏｂｊｅｃｔ＿ｎａｍｅ? 和?ｓｃｎ?。 这一粒度级别确定了用户在某一时间对某一张表进行操作的类型，相对于整体数据源的操作集缩小了 范 围；最 细 粒 度 级 别 包 含 标 签 ?ｃｏｌｕｍｎ＿ｎａｍｅ?和?ｎｅｗ＿ｖａｌｕｅ?，这一粒度级别确定了用户在某张表中对哪一字段进行了哪一数值的操作。相对于前两重级别，最细粒度级别将操作集锁定到了某一条唯一操作。各标签的含义以及三重粒度级别划分如表１所示。９９４计算机集成制造系统 第２３卷中每条操作对需作比较的向量的影响。对于向量 Ｘ和Ｙ，若计算出的ｋ阶相似度大于一阶相似度，则说明其他操作对一阶相似度有提高作用，即原本的 Ｘ或Ｙ 在所有向量中相对孤立，与其他较多的操作相似性不大；反之，若ｋ 阶相似度小于一阶相似度，则说明其他操作对一阶相似度有降低作用，Ｘ 和Ｙ 之间的相似关系高于其他操作。ｋ阶相似度的这种性质，可用于评估关联分析中算法执行条件的合理性。因为高阶情况下，ｋ 阶相似度计算可能出现不对称的情况，即Ｓｉｍ（ｋ）Ｘ，Ｙ ≠Ｓｉｍ（ｋ）Ｙ，Ｘ，所以一般取ｋ＝２来保证计算的对称性。３　基于相似度的 Ａｐｒｉｏｒｉ算法关联规则挖掘有了数据库日志的相似度概念，借鉴文献［７－８］的操作表示方法，对数据库日志中的操作集进行关联性分析，从而发掘操作规律，得到业务处理实际问题的 粒 度 而 改 进 流 程。 本 文 采 用 基 于 相 似 度 的Ａｐｒｉｏｒｉ算法。相对于传统的 Ａｐｒｉｏｒｉ算法，基于相似度的 Ａｐｒｉｏｒｉ算法的主要区别在于计算项之间的支持度和置信度的方式不同，为此本文增加了参数相似度阈值θｓｉｍ和项基元素的概念，并且项集中“项”的概念不是单个元素而是操作集合。３．１　项基的概念在事务 Ｔ 中，对于 Ｘ，Ｙ∈Ｔ，当Ｓｉｍ（１）Ｘ，Ｙ ≥θｓｉｍ时，将 Ｘ 和Ｙ 归类到项集中的同一个项中，这样每个事务中的操作可以被分为多个项，每个项中含有多条操作。对于每一项，若 Ｓｉｍ（１）Ｘ，Ｙ＝ＭＡＸｉ∈Ｔ｛Ｓｉｍ（１）Ｘ，ｉ｝，则称Ｙ 是Ｘ 的最大相似元素，记作 Ｘ～Ｙ。需要注意的是，最大相似关系不满足交换律，Ｘ～Ｙ 成立不一定有Ｙ～Ｘ 成立。对于项集中的每一项 Ａ＝（Ａ１，Ａ２，…，Ａｎ），统计所 有的最大相似关系，若元素 Ａｉ具有最多数量的最大相似关系Ａｊ～Ａｉ，则称 Ａｉ为Ａ 的项基（若在 Ｔ 范围内无法获得最大相似元素，则将 Ｔ 扩大至整个Ｑ 进行寻找），项基可看作项的核心，在整个项中是最具代表性的操作，甚至在某些运算上用于代替其他操作来提高准确性。最后采用ｋ阶相似度评价项基的选取：一般认为若 Ａｉ为Ａ 的项基，则 Ａｉ与Ａ 中其余操作之间存在较多的最大相似关系，因此存在较多的 Ａｊ∈Ａ，使得Ｓｉｍ（ｋ）Ａｊ，Ａｉ≤Ｓｉｍ（１）Ａｊ，Ａｉ，即非最大相似关系会降低一阶相似度；反之，若出现较多的Ｓｉｍ（ｋ）Ａｊ，Ａｉ＞Ｓｉｍ（１）Ａｊ，Ａｉ，则 Ａｉ作为项基的效果较差。３．２　支持度和置信度计算关联规则 Ａ→Ｂ 可看作（Ａ１，Ａ２，…，Ａｎ）→（Ｂ１，Ｂ２，…，Ｂｍ）的 ｍｎ 重映射。关联规则 Ａｉ→Ｂｊ 的支持度Ｓｕｐｐｏｒｔ（Ａｉ →Ｂｊ）＝σ（Ａｉ ∪ Ｂｊ）Ｎ， ①；ｍａｘＡｐ∈Ａ，Ｂｔ∈Ｂσ（Ａｉ ∪ Ｂｊ）Ｎ，σ（Ａｐ ∪ Ｂｔ）Ｎ·　Ｓｉｍ（１）Ａｐ，Ａｉ·Ｓｉｍ（１）Ｂｊ，Ｂ烅烄烆烍烌烎ｔ， ②烅烄烆。（５）式中：①表示 Ａｉ和Ｂｊ均为项基的情况，②表示 Ａｉ不为项基且Ａｐ为项基（或 Ｂｊ不为项基且Ｂｔ为项基）的情况；σ（Ａｉ∪Ｂｊ）表示对 Ａｉ∪Ｂｊ 的计数，Ｎ 表示所有项的元素总数。式（５）提出了计算支持度的方法，同时描述了用项基替代其他操作的情况。下面基于关联规则支持度的概念，计算关联规则的置信度。置信度可看作通过规则进行推理的可靠性。关联规则 Ａｉ→Ｂｊ 的置信度Ｃｏｎｆｉｄｅｎｃｅ（Ａｉ →Ｂｊ）＝Ｓｕｐｐｏｒｔ（Ａｉ →Ｂｊ）·Ｎσ（Ａｉ）。（６）在得到元素层面关联规则的支持度和置信度的概念后，上升到项的层面计算支持度和相似度，项 Ａ和Ｂ 构成的关联规则Ａ→Ｂ 的支持度和置信度分别为Ｓｕｐｐｏｒｔ（Ａ →Ｂ）＝ ｍａｘＡｉ∈Ａ，Ｂｊ∈Ｂ｛Ｓｕｐｐｏｒｔ（Ａｉ →Ｂｊ）｝；Ｃｏｎｆｉｄｅｎｃｅ（Ａ →Ｂ）＝Ｓｕｐｐｏｒｔ（Ａ →Ｂ）·Ｎ′σ（Ａｉ）烅烄烆。（７）式中：Ｎ′表示项集中项的总个数；σ（Ａｉ）表示 Ａ→Ｂ支持度中涉及的Ａｉ的计数。由式（５）～式（７）知，不同层面上关联规则的支持度和置信度具有不同的指导意义。元素层面上的关联规则表示操作之间的规律，可以通过该规则人工“绑定”若干操作，以预测用户在进行某一步操作之后下一步的意图，在大量分析用户意图之后，便可以改进原有的流程结构；项层面上的关联规则表示操作集之间的共性规律，可对流程图中某一类活动节点的布局进行指导。本文利用基于相似度的 Ａｐｒｉｏｒｉ方法 进 行关联分 析，产生的关联规则用于在流程中分裂节点或优化合并，通过得到频繁同时出现的操作以及存在因果关系的操作来指导流程节点结构和排布的改进。例如频繁同９９６期：２０１６－０９－２８。Ｒｅｃｅｉｖｅｄ　２０Ｊｕｎｅ　２０１６；ａｃｃｅｐｔｅｄ　２８Ｓｅｐ．２０１６．基金项目：国家自然科学基金资助项目（６１３０３０８５，６１５７２２９５，６１３０３００５）；国家创新方法工作专项资助项目（２０１５ＩＭ０１０２００）；山东省自然科学基金资助项目（ＺＲ２０１３ＦＱ０１４，ＺＲ２０１４ＦＭ０３１）；山东省科技发展计划资助项目（２０１４ＧＧＸ１０１０１９，２０１５ＧＧＸ１０１００７）；山东省自主创新重大专项资助项目（２０１５ＺＤＸＸ０２０１Ｂ０３，２０１５ＺＤＸＸ０２０１Ａ０４）；国家留学基金资助项目。Ｆｏｕｎｄａｔｉｏｎ　ｉｔｅｍｓ：Ｐｒｏｊｅｃｔ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａ－ｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．６１３０３０８５，６１５７２２９５，６１３０３００５），ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｉｎｎｏｖａｔｉｏｎ　Ｍｅｔｈｏｄ　Ｆｕｎｄ，Ｃｈｉｎａ（Ｎｏ．２０１５ＩＭ０１０２００），ｔｈｅ　Ｓｈａｎｄｏｎｇ　Ｐｒｏｖｉｎｃｉａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．ＺＲ２０１３ＦＱ０１４，ＺＲ２０１４ＦＭ０３１），ｔｈｅ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏ－ｇｙ　Ｄｅｖｅｌｏｐｍｅｎｔ　Ｐｌａｎ　Ｐｒｏｊｅｃｔ　ｏｆ　Ｓｈａｎｄｏｎｇ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ（Ｎｏ．２０１４ＧＧＸ１０１０１９，２０１５ＧＧＸ１０１００７），ｔｈｅ　Ｓｈａｎｄｏｎｇ　Ｐｒｏｖｉｎｃｉａｌ　ＩｎｄｅｐｅｎｄｅｎｔＩｎｎｏｖａｔｉｏｎ　Ｍａｊｏｒ　Ｓｐｅｃｉａｌ　Ｐｒｏｊｅｃｔ，Ｃｈｉｎａ（Ｎｏ．２０１５ＺＤＸＸ０２０１Ｂ０３，２０１５ＺＤＸＸ０２０１Ａ０４），ａｎｄ　ｔｈｅ　Ｃｈｉｎａ　Ｓｃｈｏｌａｒｓｈｉｐ　Ｃｏｕｎｃｉｌ，Ｃｈｉｎａ．基于数据库日志关联规则挖掘的业务流程优化肖宗水１，２，孟令童１，孔兰菊１＋ ，钱　进１（１．山东大学 软件学院，山东　济南　２５０１０１；２．山大地纬软件股份有限公司，山东　济南　２５０１０１）摘　要：针对需要优化的业务流程，提出基于数据库日志之间关联规则挖掘的解决方法。通过对数据库日志向量化使其变为可几何度量的流程日志，并从角度和距离两方面综合分析数据库日志的相似性。采用基于相似性的关联分析算法获得用户行为模式以指导节点的分裂或合并，实现节点结构重塑从而优化流程。该方法还通过多阶迭代的方式评价关联分析的准确性，使算法可以在合理范围内执行。关键词：相似性分析；关联规则挖掘；流程优化中图分类号：ＴＰ３１１　　　文献标识码：ＡＢｕｓｉｎｅｓｓ　ｐｒｏｃｅｓｓ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｐｐｒｏａｃｈ　ｂａｓｅｄ　ｏｎ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｍｉｎｉｎｇ　ｏｆ　ｄａｔａｂａｓｅ　ｌｏｇｓＸＩＡＯ　Ｚｏｎｇｓｈｕｉ１，２，ＭＥＮＧ　Ｌｉｎｇｔｏｎｇ１，ＫＯＮＧ　Ｌａｎｊｕ１＋，ＱＩＡＮ　Ｊｉｎ１（１．Ｃｏｌｌｅｇｅ　ｏｆ　Ｓｏｆｔｗａｒｅ，Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ　２５０１０１，Ｃｈｉｎａ；２．Ｄａｒｅｗａｙ　Ｓｏｆｔｗａｒｅ　Ｃｏ．，Ｌｔｄ．，Ｊｉｎａｎ　２５０１０１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ　ａｔ　ｔｈｅ　ｂｕｓｉｎｅｓｓ　ｐｒｏｃｅｓｓｅｓ　ｔｏ　ｂｅ　ｏｐｔｉｍｉｚｅｄ，ａ　ｓｏｌｕｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｍｉｎｉｎｇ　ｏｆ　ｄａｔａｂａｓｅｌｏｇｓ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｉｎ　ｔｈｉｓ　ｓｏｌｕｔｉｏｎ，ｔｈｅ　ｄａｔａｂａｓｅ　ｌｏｇｓ　ｗｅｒｅ　ｔｕｒｎｅｄ　ｉｎｔｏ　ｇｅｏｍｅｔｒｉｃ－ｍｅａｓｕｒａｂｌｅ　ｗｏｒｋｆｌｏｗ　ｌｏｇｓ　ｔｈｒｏｕｇｈｖｅｃｔｏｒｉｚａｔｉｏｎ，ａｎｄ　ｔｈｅ　ｓｉｍｉｌａｒｉｔｙ　ｂｅｔｗｅｅｎ　ｄａｔａｂａｓｅ　ｌｏｇｓ　ｗａｓ　ｃｏｍｐｒｅｈｅｎｓｉｖｅｌｙ　ａｎａｌｙｚｅｄ　ｉｎ　ａｎｇｌｅ　ａｎｄ　ｄｉｓｔａｎｃｅ．Ｉｎ　ｔｈｉｓｗａｙ，ｔｈｅ　ｕｓｅｒ　ｂｅｈａｖｉｏｒ　ｐｒｏｆｉｌｅｓ　ｗｅｒｅ　ｏｂｔａｉｎｅｄ　ｗｉｔｈ　ｓｉｍｉｌａｒｉｔｙ－ｂａｓｅｄ　ｃｏｒｒｅｌａｔｉｏｎ　ａｎａｌｙｓｉｓ　ａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈ　ｃｏｕｌｄ　ｇｕｉｄｅｔｈｅ　ｎｏｄｅｓｓｐｌｉｔｔｉｎｇ　ａｎｄ　ｍｅｒｇｉｎｇ　ａｓ　ｗｅｌｌ　ａｓ　ｒｅｓｈａｐｅ　ｔｈｅ　ｎｏｄｅ　ｓｔｒｕｃｔｕｒｅ　ｔｏ　ｏｐｔｉｍｉｚｅ　ｔｈｅ　ｐｒｏｃｅｓｓｅｓ．Ｍｅａｎｗｈｉｌｅ，ｔｈｉｓ　ｓｏ－ｌｕｔｉｏｎ　ａｌｓｏ　ａｓｓｅｓｓｅｄ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｃｏｒｒｅｌａｔｉｏｎ　ａｎａｌｙｓｉｓ　ｂｙ　ｍｕｌｔｉ－ｏｒｄｅｒ　ｉｔｅｒａｔｉｏｎ　ａｎｄ　ｍａｄｅ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｂｅ　ｅｘｅｃｕｔｅｄｉｎ　ａ　ｒｅａｓｏｎａｂｌｅ　ｒａｎｇｅ．Ｋｅｙｗｏｒｄｓ：ｓｉｍｉｌａｒｉｔｙ　ａｎａｌｙｓｉｓ；ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｍｉｎｉｎｇ；ｐｒｏｃｅｓｓ　ｏｐｔｉｍｉｚａｔｉｏｎ１　问题的提出在传统的业务流程构建中，由于领域知识、工作经验、需求变更等因素，建模人员在制定流程时可能无法 精 确 地 把 握 流 程 的 结 构 设 计，已 经 设 计好的流程有时不能精确客观地反映现实世界的活动。实际操作与业务流程中的节 点可能存 在粒度不一致的 问 题，从 而 在 原 有 的 业 务 流 程 中 产 生 了可优化的节点结构。对数据库日志关联 规则进行挖掘，可以发现操作之间存在的潜在规律，根据这些模式和规律能够准确地理解当前业务处 理各种问题的粒 度，通 过 与 已 有 流 程 对 待 问 题 的 粒 度 进计算机集成制造系统 第２３卷由表５知，表４中选择的项基在整体上较为合理，无需进行较大的变动。因此以表４中的项基进行关联规则的挖掘。首先进行操作层面之间的关联分析，然后上升至项的层面。拟定初始的支持度阈值为０．５，产生频繁２－项集和频繁３－项集时的支持度 阈 值 分 别 为 ０．４ 和 ０．２；置 信 度 阈 值 分 别 分０．６７和０．５。根据 基 于 相 似 度 的 Ａｐｒｉｏｒｉ算 法，对于由全部操作构成的候选集产生的频繁 １－项集，使用式（５）对Ｂ１→Ｃ１ 计算其支持度，得Ｓｕｐｐｏｒｔ（Ｂ１→Ｃ１）｛＝ｍａｘσ（Ｂ１∪Ｃ１）５，σ（Ａ２∪Ｃ１）５·Ｓｉｍ（１）Ｂ１，Ａ｝２＝０．４。同理计算得到Ｓｕｐｐｏｒｔ（Ｂ１→Ｅ２）＝０．４，Ｓｕｐ－ｐｏｒｔ（Ｃ１→Ｅ２）＝０．２。根据支持度阈值为０．４，得到频繁２－项集，如表６所示。表６　频繁１－项集和频繁２－项集的基本信息包含的操作 支持度 所在事务 所在项项基Ｂ１ ０．６　 Ｔ２，Ｔ３，Ｔ５ 本身或 Ａ２Ｃ１ ０．６　 Ｔ３，Ｔ４，Ｔ５ 本身Ｅ２ ０．６　 Ｔ１，Ｔ２，Ｔ５ 本身或 Ａ２Ｂ１，Ｃ１０．４　 Ｔ３，Ｔ５ 本身或 Ａ２，Ｃ１Ｂ１，Ｅ２０．４　 Ｔ２，Ｔ５ 本身或 Ａ２，本身或 Ａ２同样采用式（５），得到 Ｓｕｐｐｏｒｔ（Ｂ１Ｃ１→Ｅ２）＝０．２，因此频繁３－项集为｛Ｂ１Ｃ１Ｅ２｝。根据式（６）和时间顺序对所有的频繁项计算置信度，并统计超过阈值的关联关系，如表７所示。表７　置信度超过阈值的关联关系关联关系 置信度 所在频繁项集Ｂ１→Ｃ１ ０．６７ 频繁２－项集Ｂ１→Ｅ２ ０．６７ 频繁２－项集Ｂ１Ｃ１→Ｅ２ ０．５０ 频繁３－项集根据式（７），Ｓｕｐｐｏｒｔ（Ｂ１→Ｃ２）＝０．４还能表示项层面上的关联关系，表示为 Ｓｕｐｐｏｒｔ（Ａ２Ｂ３Ｅ２Ｂ１→Ｃ２）＝０．４。项层面的关联关 系代表了某类操作之间的规律。表７表示 了 频 繁 项 Ｂ１，Ｃ１和 Ｅ２之 间 的 关 联关系，其体现的行 为 模 式 （即 规 律）能 辅 助 合 并 或分裂流程中的节点。例如，Ｂ１和Ｃ１、Ｂ１和Ｅ２总是同时出现，在 拟 定 业 务 流 程 时 应 考 虑 是 否 可 以 将这种“绑定”在 一 起 的 操 作 合 并 至 同 一 活 动 节 点，从而使流 程 图 得 到 最 大 程 度 的 简 化，提 高 可 读 性和易用性。对于 Ｂ１Ｃ１→Ｅ２，Ｅ２可能以较大的概率生成于 Ｂ１Ｃ１ 之后，可见在当前业务处理问题的粒度上可能倾向于将 Ｂ１Ｃ１ 整体考虑，由此通过对比该操作对 应 的 流 程，能 够 发 现 处 理 问 题 上 的 粒 度不一致，从而构造节点的合 并。在实验 数 据中，Ｂ１和Ｃ１分别 表 示 对 课 程 表 和 学 生 选 课 表 增 加 记 录的操作，对这两张表同时添加记录的概率较大，对应于流程 应 考 虑 将 二 者 合 并，每 次 对 课 程 表 的 扩容可能意味着需要对学生选课表进行 扩容。对于Ａ２Ｂ３Ｅ２Ｂ１→Ｃ２，同 理。 对 于 Ｂ１→Ｃ１，Ｂ１→Ｅ２，Ｃ１和 Ｅ２可能 作 为 单 节 点 出 现，可 以 考 虑 将 Ｂ１之 后的关于Ｃ１和 Ｅ２的节点 分 裂 细 化。Ｃ１和 Ｅ２分 别表示学生选课表的增加记录和学生信息表 的查询操作，在逻辑上二者相对独立，学生选课 表的扩容和对学生 信 息 的 查 询 之 间 不 存 在 必 然 的 联 系，若流程中存 在 二 者 整 体 处 理 的 节 点，则 应 考 虑 将 这类节点所 代 表 的 各 个 活 动 依 次 细 化 出 来，从 而 更精确细致 地 描 述 流 程，防 止 数 据 丢 失 或 产 生 错 误的逻辑关联。另外，Ｂ１→Ｃ１ 这 一 类 因 果 关 系 对 时序较敏感，可 以 为 流 程 图 中 的 节 点 执 行 顺 序 构 建提供指 导，使 流 程 中 的 节 点 排 布 和 逻 辑 上 一 致。实验实例的优化结构如图４所示。５　结束语本文从数据库日志入手，对操作序列进行了分析：通过将数据库日志向量化为可度量的流程日志，从角度和距离计算相似度，以此为基础进行关联性分析，从而获得用户行为模式。行为模式可体现流程和业务之间处理问题的粒度是否不一致，从而为流程优化提供条件。相对于传统算法，基于相似度的 Ａｐｒｉｏｒｉ算法通过引入项基改进了支持度和置信度的计算方式。经过评价的项基对其他元素的替代提高了关联分析的准确性和合理性。相对于基于流程图分析的优化方法，本文更注重来自用户操作的意图和规律，根据用户意图进行流程优化，从而使流程更高效精确地服务于业务。后续将着重研究多阶迭代的定量评价方法，以提供更有力的评价方式。９９８肖宗水 等：基于数据库日志关联规则挖掘的业务流程优化表１　数据库日志各标签的含义以及三重粒度级别划分粒度级别 包含标签 标签含义 映射至最粗粒度?ｓｏｕｒｃｅ＿ｄａｔａｂａｓｅ＿ｎａｍｅ?数据源名称 最大操作集中间粒度?ｃｏｍｍａｎｄ ＿ｔｙｐｅ??ｏｂｊｅｃｔ＿ｏｗｎｅｒ? ｏｂ－ｊｅｃｔ＿ｎａｍｅ? ｓｃｎ?操作类型、用户名、表 名、时 间戳（自增 １的时钟）最大操作集的子集最细粒度? ｃｏｌｕｍｎ ＿ ｎａｍｅ ??ｎｅｗ＿ｖａｌｕｅ?表中的列名；更新的数值某一条操作数据库日志向量化是一个反复训练、反复完善的过程。在向量生成初期，选择较小的数据集，根据业务逻辑进行人工赋值并形成参考集。在加入新的日志数据时，系统根据参考集自动赋值并人工修正，由此不断修改完善参考集的赋值规则。在参考集扩充至较大数量后，赋值规则也达到满意的程度，每当加入新的日志数据时，系统便可完成合理的自动赋值。向量化效果的优劣取决于赋值后两个操作向量间的相似度是否与人工评定值一致，向量赋值过程需要丰富的业务经验及大容量的数据训练，经过多次迭代和调整才能得到最合适的赋值规则。赋值规则中每个标签的赋值为某一实数数组中的某个唯一实数，越相似标签的取值在数组中的对应值越相近。若加入新的标签取值，则扩充数组、使每个标签有且仅有唯一对应的实数。完成赋值后，每条操作可看作一个ｎ维向量。进行相似性计算的两个向量应属于同一粒度。２．２　操作向量的一阶相似度设计２．２．１　夹角相似度对于两个操作向量的夹角相似度，借鉴余弦相似度的基本形式。设 Ｘ 和Ｙ 是两个不同的操作向量，则 Ｘ 和Ｙ 的余弦相似度为Ｓｉｍｃｏｓ（Ｘ，Ｙ）＝（Ｘ·Ｙ）／（｜Ｘ｜｜Ｙ｜）。其中：Ｘ·Ｙ 表示向量Ｘ 和Ｙ 的内积，｜Ｘ｜和｜Ｙ｜分别表示向量Ｘ 和Ｙ 的模。由上述公式得知，向量 Ｘ 和Ｙ 的余弦相似度的范围为［－１，１］，余弦相似度的值越大，两个向量的夹角越小，越趋近于相似。然而，两个向量的整体相似度不仅受夹角的影响，还受两个向量长度差的影响。为了使整体相似度的值落在区间（－１，１］，对夹角相似度进行压缩，压缩后夹角相似度的值落在区间［０，１］。向量 Ｘ 和Ｙ 的夹角相似度Ｓｉｍａｎｇ（Ｘ，Ｙ）＝１＋Ｓｉｍｃｏｓ（Ｘ，Ｙ）２。 （１）由式（１）知，两个向量的夹角越小（趋于０），其夹角相似度越高（趋于１）；反之，两个向量的夹角越大（趋于π），其夹角相似度越低（趋于０）。２．２．２　距离相似度若仅采用夹角相似度来度量两个向量的相似性，考虑到存在两个向量夹角为 ０°但长度不同，则这两个向量也存在差异。为了弥补夹角相似度的局限性，引入距离相似度。距离相似度关注两个向量的长度差，长度差越大，距离相似度越低。设ｄ（Ｘ，Ｙ）为向量 Ｘ 和Ｙ 的长度差，则ｄ（Ｘ，Ｙ）＝｜（｜Ｘ｜－｜Ｙ｜）｜。与２．２．１节同理，为了使整体相似度的值落在（－１，１）区间，对ｄ 进行压缩。向量 Ｘ 和Ｙ 的距离相似度Ｓｉｍｄｉｓ（Ｘ，Ｙ）＝－ｄ（Ｘ，Ｙ）１＋ｄ（Ｘ，Ｙ）。 （２）由式（２）知，两个向量的距离相似度介于（－１，０］之间。若两个向量等长，则其距离相似度为０；若两个向量的长度差极大，则其距离相似度趋于－１。２．２．３　一阶相似度的基本形式在给出夹角相似度和距离相似度的计算方法之后，提出向量 Ｘ 和Ｙ 的一阶相似度计算公式，用来表示两个向量的整体相似度：Ｓｉｍ（１）Ｘ，Ｙ ＝ Ｓｉｍａｎｇ（Ｘ，Ｙ）＋Ｓｉｍｄｉｓ（Ｘ，Ｙ）。 （３）由式（３）可知，一阶相似度的值由夹角和长度共同决定且介于（－１，１］之间。若两个向量背向且不等长，则其相似度最低。操作向量的一阶相似度从角度和距离全面描述了两个向量间的相似程度，利用一阶相似度可以更为合理地进行关联规则的挖掘及后续工作。２．３　操作向量的相似度迭代计算利用所有操作对某两个向量的相似度进行迭代、得到高阶相似度，将其用于评价关联分析效果。设Ｑ 为所研究的操作集合（Ｑ 可以表示一个事务中的操作集，也可以表示整个日志的操作集），则向量Ｘ 和Ｙ 的ｋ 阶相似度Ｓｉｍ（ｋ）Ｘ，Ｙ ＝∑ｉ∈Ｑ，ｉ≠Ｘ，Ｙ｜Ｓｉｍ（ｋ－１）Ｘ，ｉ·Ｓｉｍ（１）ｉ，Ｙ ｜｜Ｑ｜１２。 （４）式中：｜Ｑ｜为操作的条数，ｋ 阶相似度的符号位与一阶相似度一致。由式（４）知，在向量 Ｘ 和Ｙ 的ｋ 阶相似度计算过程中，原本的 Ｘ 和Ｙ 扩充至整个操作集Ｑ，扩充过程中加入了 Ｑ 中的每一条相邻操作。相对于一阶相似度，ｋ 阶相似度考虑了整个操作集９９５肖宗水 等：基于数据库日志关联规则挖掘的业务流程优化时出现的操作在对待问题的粒度上倾向于“整合”处理，在流程中可将多操作用单节点表示。对这种倾向的发掘有助于指导对已有流程的改进，本文将在实验环节通过数据模拟这一过程。对于基于相似度的 Ａｐｒｉｏｒｉ算法，主要改进了计算支持度和置信度的方法，而对于支持度和置信度阈值的拟定，因为操作之间存在先后关系，Ａ→Ｂ必有Ａ 在Ｂ 之前发生，所以会自动剔除某些关联，于是每当获得频繁ｋ－项集后，需要重新拟定阈值以适应这种变化。候选集和频繁ｋ－项集的发掘与传统 Ａｐｒｉｏｒｉ算法完全相 同，不 再详细介绍。算 法流程如图３所示。４　仿真性实验与结果分析４．１　数据准备为了使项之间有合理大小的交集，选取中间粒度操作进行研究。根据表１，每条操作可表示为一个５维向 量，其 基 本 格 式 为 （?ｓｏｕｒｃｅ＿ｄａｔａｂａｓｅ＿ｎａｍｅ?，?ｃｏｍｍａｎｄ＿ｔｙｐｅ?，?ｏｂｊｅｃｔ＿ｏｗｎｅｒ?，?ｏｂｊｅｃｔ＿ｎａｍｅ?，?ｓｃｎ?）。选取高校课程管理的实例，ｏｒｃｌ１～ｏｒｃｌ３ 分别表示不同学院隶属的数据源，学生用户ｓ１，ｓ２和教师用户ｔ１有不同的操作权限；Ｓ和Ｃ 分别保存了学生的学籍信息和课程信息，ＳＣ 保存了学生的选课信息。假设已经通过多次训练获得满意的赋值规则，所有标签可能的取值及赋值规则如表２所示。表２　中间粒度的数据库日志实例标签 可能的取值 对应向量分量值?ｓｏｕｒｃｅ＿ｄａｔａｂａｓｅ＿ｎａｍｅ? ｛ｏｒｃｌ１，ｏｒｃｌ２，ｏｒｃｌ３｝ ｛１，２，３｝?ｃｏｍｍａｎｄ＿ｔｙｐｅ?｛ｉｎｓｅｒｔ，ｓｅｌｅｃｔ，ｕｐｄａｔｅ，ｄｅｌｅｔｅ｝｛１，２．５，４，６｝?ｏｂｊｅｃｔ＿ｏｗｎｅｒ? ｛ｓ１，ｓ２，ｔ１｝ ｛１，２，５｝?ｏｂｊｅｃｔ＿ｎａｍｅ? ｛Ｓ，Ｃ，ＳＣ｝ ｛１，３，９｝?ｓｃｎ? 按时间自增 １ 取值 按时间自增 ０．１ 取 值选取一组操作｛Ａ１，Ａ２，Ａ３，Ｂ１，Ｂ２，Ｂ３，Ｃ１，Ｃ２，Ｄ１，Ｄ２，Ｄ３，Ｅ１，Ｅ２，Ｅ３，Ｅ４｝，根据赋值规则向量化后得到如下 ＷＦＬｏｇｓ向量（Ａ１表示用户ｓ１在ｏｒｃｌ３下对表ＳＣ 进行ｕｐｄａｔｅ操作，其他类似）：Ａ１＝（３，４，１，９，０．１），Ａ２＝（２，２．５，５，１，０．２），Ａ３＝（３，６，２，９，０．３），Ｂ１＝（２，１，５，３，０．４），Ｂ２＝（３，１，１，１，０．５），Ｂ３＝（３，１，５，１，０．６），Ｃ１＝（３，１，５，９，０．７），Ｃ２＝（３，４，５，１，０．８），Ｄ１＝（２，２．５，１，３，０．９），Ｄ２＝（２，２．５，２，３，１），Ｄ３＝（３，６，５，１，１．１），Ｅ１＝（２，１，２，９，１．２），Ｅ２＝（１，２．５，５，１，１．３），Ｅ３＝（３，１，１，１，１．４），Ｅ４＝（１，１，１，９，１．５）。４．２　关联规则挖掘所有的操作来自５个事务，每个操作可能存在于多个事务中。ＬＣＲ 文件中每个事务均由唯一的?ｔｒａｎｓａｃｔｉｏｎ＿ｉｄ? 标识 。 每 条 操作在事 务 中 的 分 布如表３所示。表３　每条操作在事务集中的分布事务 包含操作 ?ｔｒａｎｓａｃｔｉｏｎ＿ｉｄ?Ｔ１ Ａ１，Ａ３，Ｄ１，Ｅ１，Ｅ２ ７．３１．３０１　８０Ｔ２ Ａ２，Ｂ１，Ｂ２，Ｂ３，Ｅ２，Ｅ４ ７．３１．３０１　８１Ｔ３ Ａ１，Ｂ１，Ｃ１，Ｃ２，Ｅ１，Ｅ３ ７．３１．３０１　８２Ｔ４ Ｂ２，Ｃ１，Ｄ１，Ｄ２，Ｄ３，Ｅ４ ７．３１．３０１　８３Ｔ５ Ａ２，Ａ３，Ｂ１，Ｃ１，Ｄ２，Ｅ２ ７．３１．３０１　８４拟定相似度阈值θｓｉｍ＝０．５，根据这一阈值进行项的划分，通过计算最大相似关系得到如下结果，以此寻找每个项的项基，并取ｋ＝２进行评价。最后得到如表４和表５所示的结果。Ａ１～Ｃ１， Ａ２～Ｂ３， Ａ３～Ｃ１， Ｂ１～Ｂ３， Ｂ２～Ｅ３，Ｂ３～Ａ２， Ｃ１～Ａ１， Ｃ２～Ａ２， Ｄ１～Ｅ３， Ｄ２～Ｄ１，Ｄ３～Ｃ２， Ｅ１～Ｅ４， Ｅ２～Ａ２， Ｅ３～Ｂ２， Ｅ４～Ｅ１。表４　相似度阈值为０．５时的项划分及项基事务 项划分 项基元素Ｔ１ （Ａ１，Ｅ１）（Ａ３）（Ｄ１）（Ｅ２） （Ａ１，Ａ３，Ｄ１，Ｅ２）Ｔ２ （Ａ２，Ｂ１，Ｂ３，Ｅ２）（Ｂ２）（Ｅ４） （Ａ２，Ｂ２，Ｅ４）Ｔ３ （Ａ１，Ｃ１，Ｅ１）（Ｂ１）（Ｃ２）（Ｅ３） （Ｃ１，Ｂ１，Ｃ２，Ｅ３）Ｔ４ （Ｄ１，Ｄ２）（Ｂ２）（Ｃ１）（Ｄ３）（Ｅ４） （Ｄ１，Ｂ２，Ｃ１，Ｄ３，Ｅ４）Ｔ５ （Ａ２，Ｂ１，Ｅ２）（Ａ３，Ｃ１）（Ｄ２） （Ａ２，Ｃ１，Ｄ２）表５　需评价的项基元素的一阶相似度（二阶相似度）Ａ１ Ａ２ Ｃ１ Ｄ１Ａ１ １．０００（０．２５５）－０．０７１（－０．１７１）０．６３４（０．２３４） ０．１１２（０．１７９）Ａ２ １．０００（０．３６５） ０．００１（０．１３５） ０．２２４（０．２７１）Ｃ１ １．０００（０．２１６） ０．０５４（０．１５５）Ｄ１ １．０００（０．３３２）９９７