过程挖掘

Process Mining学习笔记（一）

课程名称是 《Process Mining： Data Science in Action》，以下是课后笔记整理。

Date Science and Big Data

当今的时代，海量数据不断地产生，在过去的10分钟产生的数据量，都超过了2003年之前人类历史上产生的所有数据。人类的各种活动，都会不断地产生一系列的event data（事件数据）。人类的事件数据形成了一个网，即Internet of Events。它的数据主要有4种来源：

  1. Internet of content 如web 页面数据
  2. Internet of People 社交网络上人们通过各种关系产生
  3. Internet of Things 物联网
  4. Internet of Places 地理位置信息

由数据的指数级增长，又谈到了摩尔定律（Moore’s Law）,每两年芯片中晶体管的数量将翻一翻，在过去的40年间，数量增长了2^20=1048576。这种增长是非常惊人的。40年前从 Amsterdam 到 Newyork 要坐7小时的飞机，如果飞机的飞行速度发展也能遵照摩尔定律，那么40年后只需0.024秒（可惜并没有如此高速发展）……

如今，我们关注的不是如何生成数据，而是如何从海量数据中发现有价值的内容。

4Vs

大数据领域，我们经常会关注的4个V：
大数据的4V

  1. Volume（容量）：海量数据
  2. Velocity（速度）：数据在不断的变化
  3. Variety（多样）：数据的多样性，文本，图象，音视频等
  4. Veracity（真实）：数据的真实性

数据科学领域，我们会提出以下的4个问题：

  1. What happened？ 过去发生了什么？
  2. Why did it happend？为什么会发生？
  3. What will happen？ 将会发生什么？（做预测Prediction）
  4. What is the best that can happend？ 如何更好的发生？

这门课程集中在基于过程process的数据，利用 event data，来改进过程。
课程集中的领域

Different types of process mining

Process Mining集中在关注performance-oriented problems和compliance-oriented problems。

Event data 是 process mining 的入口，什么是 event data 呢？
一系列的日志信息，均可以称为 event data，比如学生的所有成绩单、订单的记录、病人治疗的日志等。

在 Process Mining 中，我们需要关注的是process models 与 event data 之间的关系。如下图所示：
Process Mining 的类型

  1. Play Out：从已知的process模型中生成 event data
  2. Play-In：根据 event data 发现 process模型，是一个discovery的过程。
  3. Replay：已知 model 和 event data，二者互相验证，发现 event data 和 model 的问题

Replay 可以带上 timestamp，即 event data 的数据会带有时间戳，可以知道每个步骤的耗时。Replay 可以用来做performance analysis，发现过程中哪里是瓶颈。

下图是对整个 process mining 的概要描述
Overview

  • World （真实世界），即事件真实发生的存在；
  • Software System（软件系统），负责记录事件发生，并生成 event logs
  • Event logs（日志），可以用来发现process models
  • Model（模型），eventlogs 可以与 model 做一致性的验证，改进 model

从这几部分中，我们可以再次总结一下 process mining 的三种类型：
Play-Out在图中说明 process model在不利用 eventlog 的情况下，在真实世界和软件系统中的应用。
Play-In 负责利用eventlog来发现 process model
Replay 主要体现在 conformance 和 enhancement

Process Mining与Data Mining

Process Mining之前说过，它集中解决 compliance 和 perfermance 相关的问题，在数据领域，它更像是胶水，把很多方面都粘合在一起，如：

  • Data 与 Process
  • Business 与 IT
  • Busienss Intelligence 与Business Process Management
  • Performance 与 Compliance
  • Runtime 与 Design Time

Process Mining 与 BPM 和 data mining 的关系如下：
Process Mining所处位置
特别提到了与 BI 的关系，并举了例子，介绍了 BI 只是将数据以不同的形式展现，而数据背后的深层的涵义，BI 则无法处理了。

Process Discovery（过程模型的发现），与语言的学习类似，在不断的语言环境下学习新的语言在各种情况下的使用，最终学会语言（掌握了过程的模型）。

Data Mining 是 data-centre，而不是 process-centre 的。

课中举了几个数据集的例子，如学生的成绩记录，咖啡店顾客的消费记录等。

  • 数据集由 instances（实例）组成（individuals, entities,cases, objects, or records）,通常指每行数据;
  • Variables（变量）是指数据的各属性，通常以列的形式存在。变量一般有两种类型：
    1. categorical variables：ordinal（序数的）和 nominal（名词性的）特征属性，如 high-med-low，true-false，red-pink-green 等
    2. numerical variables：以数字形式存在的变量值

数据挖掘技术一般有两类，supervised learning（有监督学习）和 unsupervised learning（无监督学习）：

有监督学习下，存在着labeled data，即 instance 中有专门的response variable用来标注整个 instance，它的目标是按照predictor variables（dependent variable）来解析response variable（independent variables）。

对于有监督学习，一般采用classification（如决策树） 和regression 的技术：

  • Classification 主要针对categorical response variable，目标是根据predictor variables 把 instance 进行分类；
  • Regression 针对的则是 numerical response variable，目标是找出一个符合数据的函数，并使误差减到最小。

而无监督学习，则是没是 labeled data 的，即 instance 中并没有 response variable和 predictor variables 的区分。针对无监督学习的典型技术有：

  • clustering（聚类），如 k-mean clusters
  • pattern discovery，如association rules （关联规则）

Decision Tree

在决策树方法中，有多个 predictor variables，并且有一个 response variable，我们会根据多个 predictor variables 来预测一个 response variable 的值。比如下面的例子，以死亡人是否饮酒、抽烟、体重作为 predictor 变量，年龄做为 response 变量，来进行的分析：
Decision Tree 的例子

注意叶子结点上的数字，左边的数字表明符合该路径的instance 数量，右边表示不符合决策树的 instance 数。

决策树的基础原理，就是把 instance 的数据集拆分成更小的子集，从一个很大的不确定性的状态（high entropy），划分成确定性逐渐增大的子集，这样的过程就是构建决策树的过程。
Decision Tree 的 构建过程

熵

所以，理解决策树，就要充分了解entropy（熵）。熵是一种degree of uncertainty，一种对不确定性的度量。计算决策树叶子结点的熵值，并不断的降低熵值，就是一个不断改进预测的过程。
熵的计算

举个例子，有六个病人的数据，在没有进行决策树划分的时候，作为一个整体，计算它的熵值：
E=-（3/6log2(3/6)+3/6log2(3/6)） = 1
在划分为是否抽烟的两个子结点后，每个子结点的计算：
会得出 E1=0，E2=0.811

对于一棵树的多个子结点，我们采用加权平均的方式，把每个子结点的熵值与它的比重相乘，求和计算出整个决策树的熵值。
Information gain

在决策树的改进过程中，我们可以发现整个树的熵值是在不断变小，每次改进都获得更多的信息（information gain）值。即熵值越小，信息的获取就越多。

决策树生成算法

下面是生成决策树的一个简单算法描述：

  1. 首先从根结点开始，包括所有的数据；
  2. 迭代的遍历所有的结点，查看是否在 information gain；
  3. 对于每个结点以及它的每一个属性，都计算如果按照该属性分拆结点后的信息获取情况；
  4. 选择那个获取信息最多的属性作为开端；
  5. 继续之前的操作，直到信息获取不在再明显的改善；

  6. 返回一个决策树；

    在决策树的算法中，有许多参数（变量）可以调定，比如：

    1. minimal size of a node：定义结点在分拆前后的最小数量，以避免 overfitting
    2. threshold setting the minimal gain：信息增量的最小值，比小于该值，则不再拆分结点
    3. Maximal depth of the tree：树的最大深度
    4. Allowing the same label to appear multiple times or not: 是否可重复使用同一 label
    5. Alternatives to entropy：采用不同的熵值计算
    6. Splitting the domain of a numerical variable: 将数值型的变量拆分归类
    7. Post pruning：剪枝，剪去不重要的树分支

决策树的质量

如果判定决策树的质量如何？使用 Confusion Matrix

防止决策树 overfitting 和 underfitting，我们需要寻找到一种介于两者间的平衡状态。

Association Rule

assocaition rule 是一种无监督的算法，不存在所谓的 labeled data。经典的啤酒与尿布的故事，就是关联规则算法的一个应用。
例如：{beer}->{diapers}

所以关联规则的形式就是 X->Y (x implies y),x与 y 都是数据集中的项

三个度量的指标：

  1. Support（支持度）:
    Support指标
    support 的值范围在0到1之间，0最差，1最佳。

  2. Confidence（置信度）：
    Confidence 指标
    support 的值范围在0到1之间，0最差，1最佳。

  3. Lift（提升度）：
    Lift 指标

如果lift>1,则 x 与 y 是正相关
如果 lift=1，则x 与 y是独立的
如果 lift<1,则 x 与 y 是负相关

对于关联规则，一个好的关联规则表现在：

  1. support 尽可能高
  2. confidence接近1
  3. lift 大于1

Bruce force approach

其它类型的 pattern mining
sequence mining
episode mining

Cluster Analysis

cluster analysis 也是一种 unsupervised learning techniques

Evaluating Mining Results