精华内容
下载资源
问答
  • 主要介绍了MySQL数据库事务隔离级别(Transaction Isolation Level) ,需要的朋友可以参考下
  • isolation-threadpool 从Hystrix核心代码中提取出来的线程池隔离的代码,可以非常方便的在Web应用中实现线程池隔离 使用场景 我们的应用在使用Jetty服务时,多个HTTP服务会共享同一个线程池,当其中一个服务依赖的...
  • 库隔离林 描述 该项目包含隔离林算法... from isolationforest import IsolationForest forest = IsolationForest . Forest ( num_trees , sub_sampling_size ) sample = IsolationForest . Sample ( "Training Sample
  • iforest算法是用于检测异常点的。对于电商、金融领域的欺诈检测应用广泛
  • 主要介绍了浅谈spring中isolation 和propagation的用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • transaction_isolation 以与数据库无关的方式在ActiveRecord中设置事务隔离级别。 只要您使用的是新适配器mysql2,pg或sqlite3,就可以与MySQL,PostgreSQL和SQLite一起使用。 支持所有ANSI SQL隔离级别::...
  • ANSI SQL通过脏读、不可重复读和幻想(如幻读)现象定义了隔离级别。这篇论文介绍了这些现象和ANSI SQL定义未能正确描述的几个比较流行的隔离...最后,定了一个重要的多版本隔离类型,快照隔离(Snapshot Isolation)。
  • 为了解决该难题 ,油 田引进了最新一代的固井质量评价仪 Isolation Scanner ,该仪器通过脉冲回波测量和挠曲波衰减测量 ,可 对套管结构进行检测 ,同时对套管磨损、腐蚀及套管居中情况进行定量评价。详细介绍了 ...
  • isolationForest1.0.2.zip

    2019-07-18 16:18:51
    孤立森林算法 java实现 iforest算法是用于检测异常点的。对于电商、金融领域的欺诈检测应用广泛
  • 隔离林 隔离林异常检测算法的Scala实现
  • isolated_forest_example 在Python中实现隔离林的示例
  • oracle lock and isolation at

    2019-07-03 02:52:41
    NULL 博文链接:https://mlaaalm.iteye.com/blog/682540
  • Isolation.READ_COMMITTED):读取已提交数据(会出现不可重复读和幻读) @Transactional(isolation = Isolation.REPEATABLE_READ):可重复读(会出现幻读) @Transactional(isolation = Isolation.SERIALIZABLE):串行化...

    1、Transactional

    @Transactional是spring中声明式事务管理的注解配置方式,相信这个注解的作用大家都很清楚。@Transactional注解可以帮助我们把事务开启、提交或者回滚的操作,通过aop的方式进行管理。通过@Transactional注解就能让spring为我们管理事务,免去了重复的事务管理逻辑,减少对业务代码的侵入,使我们开发人员能够专注于业务层面开发。
    在这里插入图片描述

    在这里插入图片描述

    2、Transactional注解里面的字段

    在这里插入图片描述
    事物传播行为介绍:
      @Transactional(propagation=Propagation.REQUIRED) :如果有事务, 那么加入事务, 没有的话新建一个(默认情况下) spring默认传播行为
      @Transactional(propagation=Propagation.NOT_SUPPORTED) :容器不为这个方法开启事务
      @Transactional(propagation=Propagation.REQUIRES_NEW) :不管是否存在事务,都创建一个新的事务,原来的挂起,新的执行完毕,继续执行老的事务
      @Transactional(propagation=Propagation.MANDATORY) :必须在一个已有的事务中执行,否则抛出异常
      @Transactional(propagation=Propagation.NEVER) :必须在一个没有的事务中执行,否则抛出异常(与Propagation.MANDATORY相反)
      @Transactional(propagation=Propagation.SUPPORTS) :如果其他bean调用这个方法,在其他bean中声明事务,那就用事务.如果其他bean没有声明事务,那就不用事务.

    事物超时设置:
      @Transactional(timeout=30) //默认是30秒

    事务隔离级别:
      @Transactional(isolation = Isolation.READ_UNCOMMITTED):读取未提交数据(会出现脏读, 不可重复读) 基本不使用
      @Transactional(isolation = Isolation.READ_COMMITTED):读取已提交数据(会出现不可重复读和幻读)
      @Transactional(isolation = Isolation.REPEATABLE_READ):可重复读(会出现幻读)
      @Transactional(isolation = Isolation.SERIALIZABLE):串行化
      
      MYSQL: 默认为REPEATABLE_READ级别
      SQLSERVER: 默认为READ_COMMITTED
      Oracle 默认隔离级别 READ_COMMITTED

    3、isolation详解

    isolation的参数有以下五种:

    1_1、Isolation.DEFAULT:为数据源的默认隔离级别

    1_2、isolation=Isolation.READ_UNCOMMITTED:未授权读取级别

    以操作同一行数据为前提,读事务允许其他读事务和写事务,未提交的写事务禁止其他写事务(但允许其他读事务)。此隔离级别可以防止更新丢失,但不能防止脏读、不可重复读、幻读。此隔离级别可以通过“排他写锁”实现。

    1_3、iIsolation.READ_COMMITTED:授权读取级别

    以操作同一行数据为前提,读事务允许其他读事务和写事务,未提交的写事务禁止其他读事务和写事务。此隔离级别可以防止更新丢失、脏读,但不能防止不可重复读、幻读。此隔离级别可以通过“瞬间共享读锁”和“排他写锁”实现。

    1_4、iIsolation.REPEATABLE_READ:可重复读取级别

    以操作同一行数据为前提,读事务禁止其他写事务(但允许其他读事务),未提交的写事务禁止其他读事务和写事务。此隔离级别可以防止更新丢失、脏读、不可重复读,但不能防止幻读。此隔离级别可以通过“共享读锁”和“排他写锁”实现。

    1_5、iIsolation.SERIALIZABLE:序列化级别

    提供严格的事务隔离。它要求事务序列化执行,事务只能一个接着一个地执行,不能并发执行。此隔离级别可以防止更新丢失、脏读、不可重复读、幻读。如果仅仅通过“行级锁”是无法实现事务序列化的,必须通过其他机制保证新插入的数据不会被刚执行查询操作的事务访问到。

    隔离级别越高,越能保证数据的完整性和一致性,但是对并发性能的影响也越大。对于多数应用程序,可以优先考虑把数据库系统的隔离级别设为Read Committed。它能够避免更新丢失、脏读,而且具有较好的并发性能。尽管它会导致不可重复读、幻读这些并发问题,在可能出现这类问题的个别场合,可以由应用程序采用悲观锁或乐观锁来控制。

    有关事务的关键字说明如下,说明如下:

    原子性(Atomicity):

    事务是数据库的逻辑工作单位,它对数据库的修改要么全部执行,要么全部不执行。

    一致性(Consistemcy):

    事务前后,数据库的状态都满足所有的完整性约束。

    隔离性(Isolation):

    并发执行的事务是隔离的,一个不影响一个。如果有两个事务,运行在相同的时间内,执行相同的功能,事务的隔离性将确保每一事务在系统中认为只有该事务在使用系统。这种属性有时称为串行化,为了防止事务操作间的混淆,必须串行化或序列化请求,使得在同一时间仅有一个请求用于同一数据。通过设置数据库的隔离级别,可以达到不同的隔离效果。

    持久性(Durability):

    在事务完成以后,该事务所对数据库所作的更改便持久的保存在数据库之中,并不会被回滚。

    更新丢失:

    两个事务都同时更新一行数据,但是第二个事务却中途失败退出,导致对数据的两个修改都失效了。这是因为系统没有执行任何的锁操作,因此并发事务并没有被隔离开来。

    脏读:

    脏读又称无效数据读出。一个事务读取另外一个事务还没有提交的数据叫脏读。

    例如:事务T1修改了一行数据,但是还没有提交,这时候事务T2读取了被事务T1修改后的数据,之后事务T1因为某种原因Rollback了,那么事务T2读取的数据就是脏的。

    不可重复读:

    不可重复读是指在同一个事务内,两个相同的查询返回了不同的结果。

    例如:事务T1读取某一数据,事务T2读取并修改了该数据,T1为了对读取值进行检验而再次读取该数据,便得到了不同的结果。

    幻读:

    事务在操作过程中进行两次查询,第二次查询的结果包含了第一次查询中未出现的数据或者缺少了第一次查询中出现的数据

    例如:系统管理员A将数据库中所有学生的成绩从具体分数改为ABCDE等级,但是系统管理员B就在这个时候插入了一条具体分数的记录,当系统管理员A改结束后发现还有一条记录没有改过来,就好像发生了幻觉一样。这就叫幻读。

    以上的4种问题(更新丢失、脏读、不可重复读、幻读)都和事务的隔离级别有关。通过设置事务的隔离级别,可以避免上述问题的发生。

    展开全文
  • 隔离级别
  • 牛心线粒体ATP合成酶的分离纯化的方法学研究,朱杰,孙润广,科研工作者们在过去的50年前赴后继的工作中深入了ATP合成酶的功能,并努力尝试解析该酶的空间结构以其能够从结构基础上对ATP合成酶�
  • noise isolation

    2016-06-06 08:04:16
    how to isolate wafer substrate noise
  • 本文总结了四种机器学习中异常检测的算法:Isolation Forest、Local Outlier Factor、Principal Component Analysis、DAGMM,每一种算法都从其基本概念开始详细的介绍,后给出了该算法应用在实际中需要注意的要点。...

    异常检测(Anomaly detection)问题是机器学习算法的一个常见应用。这种算法的一个有趣之处在于:它虽然主要用于非监督学习问题,但从某些角度看,它又类似于一些监督学习问题。本文总结了四种机器学习中异常检测的算法:Isolation Forest、Local Outlier Factor、Principal Component Analysis、DAGMM,每一种算法都从其基本概念开始详细的介绍,后给出了该算法应用在实际中需要注意的要点。

    异常检测算法(一):Isolation Forest

    "An outlier is an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism."

    — D. M. Hawkins, Identification of Outliers, Chapman and Hall, 1980.

    异常检测 (anomaly detection),或者又被称为“离群点检测” (outlier detection),是机器学习研究领域中跟现实紧密联系、有广泛应用需求的一类问题。但是,什么是异常,并没有标准答案,通常因具体应用场景而异。如果要给一个比较通用的定义,很多文献通常会引用 Hawkins 在文章开头那段话。很多后来者的说法,跟这个定义大同小异。这些定义虽然笼统,但其实暗含了认定“异常”的两个标准或者说假设:

    1. 异常数据跟样本中大多数数据不太一样。

    2. 异常数据在整体数据样本中占比比较小。

    为了刻画异常数据的“不一样”,最直接的做法是利用各种统计的、距离的、密度的量化指标去描述数据样本跟其他样本的疏离程度。而 Isolation Forest (Liu et al. 2011) 的想法要巧妙一些,它尝试直接去刻画数据的“疏离”(isolation)程度,而不借助其他量化指标。Isolation Forest 因为简单、高效,在学术界和工业界都有着不错的名声。

     

    算法介绍

    我们先用一个简单的例子来说明 Isolation Forest 的基本想法。假设现在有一组一维数据(如下图所示),我们要对这组数据进行随机切分,希望可以把点 A 和点 B 单独切分出来。具体的,我们先在最大值和最小值之间随机选择一个值 x,然后按照 <x 和 >=x 可以把数据分成左右两组。然后,在这两组数据中分别重复这个步骤,直到数据不可再分。显然,点 B 跟其他数据比较疏离,可能用很少的次数就可以把它切分出来;点 A 跟其他数据点聚在一起,可能需要更多的次数才能把它切分出来。

    我们把数据从一维扩展到两维。同样的,我们沿着两个坐标轴进行随机切分,尝试把下图中的点A'和点B'分别切分出来。我们先随机选择一个特征维度,在这个特征的最大值和最小值之间随机选择一个值,按照跟特征值的大小关系将数据进行左右切分。然后,在左右两组数据中,我们重复上述步骤,再随机的按某个特征维度的取值把数据进行细分,直到无法细分,即:只剩下一个数据点,或者剩下的数据全部相同。跟先前的例子类似,直观上,点B'跟其他数据点比较疏离,可能只需要很少的几次操作就可以将它细分出来;点A'需要的切分次数可能会更多一些。

    按照先前提到的关于“异常”的两个假设,一般情况下,在上面的例子中,点B和点B' 由于跟其他数据隔的比较远,会被认为是异常数据,而点A和点A' 会被认为是正常数据。直观上,异常数据由于跟其他数据点较为疏离,可能需要较少几次切分就可以将它们单独划分出来,而正常数据恰恰相反。这其实正是 Isolation Forest(IF)的核心概念。IF采用二叉树去对数据进行切分,数据点在二叉树中所处的深度反应了该条数据的“疏离”程度。整个算法大致可以分为两步:

    1. 训练:抽取多个样本,构建多棵二叉树(Isolation Tree,即 iTree);

    2. 预测:综合多棵二叉树的结果,计算每个数据点的异常分值。

    训练:构建一棵 iTree 时,先从全量数据中抽取一批样本,然后随机选择一个特征作为起始节点,并在该特征的最大值和最小值之间随机选择一个值,将样本中小于该取值的数据划到左分支,大于等于该取值的划到右分支。然后,在左右两个分支数据中,重复上述步骤,直到满足如下条件:

    1. 数据不可再分,即:只包含一条数据,或者全部数据相同。

    2. 二叉树达到限定的最大深度。

    预测:计算数据 x 的异常分值时,先要估算它在每棵 iTree 中的路径长度(也可以叫深度)。具体的,先沿着一棵 iTree,从根节点开始按不同特征的取值从上往下,直到到达某叶子节点。假设 iTree 的训练样本中同样落在 x 所在叶子节点的样本数为 T.size,则数据 x 在这棵 iTree 上的路径长度 h(x),可以用下面这个公式计算:

    图片

    公式中,e 表示数据 x 从 iTree 的根节点到叶节点过程中经过的边的数目,C(T.size) 可以认为是一个修正值,它表示在一棵用 T.size 条样本数据构建的二叉树的平均路径长度。一般的,C(n) 的计算公式如下:

    图片

    其中,H(n-1) 可用 ln(n-1)+0.5772156649 估算,这里的常数是欧拉常数。数据 x 最终的异常分值 Score(x) 综合了多棵 iTree 的结果:

    图片

    公式中,e 表示数据 x 从 iTree 的根节点到叶节点过程中经过的边的数目,C(T.size) 可以认为是一个修正值,它表示在一棵用 T.size 条样本数据构建的二叉树的平均路径长度。一般的,C(n) 的计算公式如下:

    从异常分值的公式看,如果数据 x 在多棵 iTree 中的平均路径长度越短,得分越接近 1,表明数据 x 越异常;如果数据 x 在多棵 iTree 中的平均路径长度越长,得分越接近 0,表示数据 x 越正常;如果数据 x 在多棵 iTree 中的平均路径长度接近整体均值,则打分会在 0.5 附近。

     

    算法应用

    Isolation Forest 算法主要有两个参数:一个是二叉树的个数;另一个是训练单棵 iTree 时候抽取样本的数目。实验表明,当设定为 100 棵树,抽样样本数为 256 条时候,IF 在大多数情况下就已经可以取得不错的效果。这也体现了算法的简单、高效。

    Isolation Forest 是无监督的异常检测算法,在实际应用时,并不需要黑白标签。需要注意的是:(1)如果训练样本中异常样本的比例比较高,违背了先前提到的异常检测的基本假设,可能最终的效果会受影响;(2)异常检测跟具体的应用场景紧密相关,算法检测出的“异常”不一定是我们实际想要的。比如,在识别虚假交易时,异常的交易未必就是虚假的交易。所以,在特征选择时,可能需要过滤不太相关的特征,以免识别出一些不太相关的“异常”。

     

    异常检测算法(二):Local Outlier Factor

    Local Outlier Factor(LOF)是基于密度的经典算法(Breuning et. al. 2000), 文章发表于 SIGMOD 2000, 到目前已经有 3000+ 的引用。在 LOF 之前的异常检测算法大多是基于统计方法的,或者是借用了一些聚类算法用于异常点的识别(比如 ,DBSCAN,OPTICS)。但是,基于统计的异常检测算法通常需要假设数据服从特定的概率分布,这个假设往往是不成立的。而聚类的方法通常只能给出 0/1 的判断(即:是不是异常点),不能量化每个数据点的异常程度。相比较而言,基于密度的LOF算法要更简单、直观。它不需要对数据的分布做太多要求,还能量化每个数据点的异常程度(outlierness)。

     

    算法介绍

    LOF 是基于密度的算法,其最核心的部分是关于数据点密度的刻画。如果对 distanced-based 或者 density-based 的聚类算法有些印象,你会发现 LOF 中用来定义密度的一些概念似曾相识。了解了这些核心概念,整个算法也就显而易见了。而整个算法,最主要的是下面四个概念:

    K-邻近距离(k-distance):在距离数据点 p 最近的几个点中,第 k 个最近的点跟点 p 之间的距离称为点 p 的 K-邻近距离,记为 k-distance (p) 。

    可达距离(rechability distance):可达距离的定义跟K-邻近距离是相关的,给定参数k时, 数据点 p 到 数据点 o 的可达距离 reach-dist(p, o)为数据点 o 的K-邻近距离 和 数据点p与点o之间的直接距离的最大值。即:


    局部可达密度(local rechability density):局部可达密度的定义是基于可达距离的,对于数据点 p,那些跟点p的距离小于等于 k-distance(p)的数据点称为它的 k-nearest-neighbor,记为 ,数据点 p 的局部可达密度为它与邻近的数据点的平均可达距离的倒数,即:


    局部异常因子(local outlier factor):根据局部可达密度的定义,如果一个数据点跟其他点比较疏远的话,那么显然它的局部可达密度就小。但LOF算法衡量一个数据点的异常程度,并不是看它的绝对局部密度,而是看它跟周围邻近的数据点的相对密度。这样做的好处是可以允许数据分布不均匀、密度不同的情况。局部异常因子即是用局部相对密度来定义的。数据点 p 的局部相对密度(局部异常因子)为点p的邻居们的平均局部可达密度跟数据点p的局部可达密度的比值,即:


    根据局部异常因子的定义,如果数据点 p 的 LOF 得分在1附近,表明数据点p的局部密度跟它的邻居们差不多;如果数据点 p 的 LOF 得分小于1,表明数据点p处在一个相对密集的区域,不像是一个异常点;如果数据点 p 的 LOF 得分远大于1,表明数据点p跟其他点比较疏远,很有可能是一个异常点。下面这个图来自 Wikipedia 的 LOF 词条,展示了一个二维的例子。上面的数字标明了相应点的LOF得分,可以让人对LOF有一个直观的印象。

    了解了 LOF 的定义,整个算法也就显而易见了:

    1. 对于每个数据点,计算它与其它所有点的距离,并按从近到远排序;

    2. 对于每个数据点,找到它的 k-nearest-neighbor,计算 LOF 得分。

    算法应用

    LOF算法中关于局部可达密度的定义其实暗含了一个假设,即:不存在大于等于 k 个重复的点。当这样的重复点存在的时候,这些点的平均可达距离为零,局部可达密度就变为无穷大,会给计算带来一些麻烦。在实际应用时,为了避免这样的情况出现,可以把 k-distance 改为 k-distinct-distance,不考虑重复的情况。或者,还可以考虑给可达距离都加一个很小的值,避免可达距离等于零。

    LOF 算法需要计算数据点两两之间的距离,造成整个算法时间复杂度为  。为了提高算法效率,后续有算法尝试改进。FastLOF (Goldstein,2012)先将整个数据随机的分成多个子集,然后在每个子集里计算 LOF 值。对于那些 LOF 异常得分小于等于 1 的,从数据集里剔除,剩下的在下一轮寻找更合适的 nearest-neighbor,并更新 LOF 值。这种先将数据粗略分成多个部分,然后根据局部计算结果将数据过滤来减少计算量的想法,并不罕见。比如,为了改进 K-means 的计算效率, Canopy Clustering 算法也采用过比较相似的做法。

     

    异常检测算法(三):Principal Component Analysis

    Principal Component Analysis(PCA)是最常见的数据降维的方法。根据 Wikipedia 的介绍,它最早是由 Karl Pearson(同时也是卡方检验的发明者) 在1901年提出,到现在已经一百多年了。作为一种降维的方法,PCA可以将原数据进行线性变换,并找出数据中信息含量最大的主要成分,去除信息含量较低的成分,从而减少冗余,降低噪音。通常在异常检测的语境里,噪音(noise)、离群点(outlier)和 异常值(anomaly)是同一件事情的不同表述。所以,PCA既然可以识别噪音,自然也可以检测异常。

     

    PCA的相关概念

    我们先简单回顾一下 PCA的相关概念。假设原始数据是一个的矩阵,这里m表示数据样本的数量,n表示每一条数据样本的特征数目。一般的,我们先要对原始数据做一些预处理:

    1. 中心化:将原始数据每一列进行零均值化,即将该列上的每一个数值都减去该列的均值。

    2. 归一化:将中心化之后的数据的每一列进行方差归一化,即将该列上的每一个数值都除以该列的标准差。

    上面的两步预处理是通常做法。中心化的主要目的是让后面的公式描述更简洁,并不影响特征值分解。归一化是为了让不同变量的方差变化尺度控制在相同的范围内,消除不同量纲的影响,使得它们更有可比性。我们将预处理之后的矩阵表示为  ,则 PCA 的主要步骤如下:

     

    1. 计算协方差矩阵 

    2. 求解协方差矩阵的特征值  和特征向量 

    3. 按照特征值从大到小的顺序,将特征向量从左至右排列,将前k个特征向量组成的矩阵表示为 

    4. 将  映射到低维的k维空间(  ),则映射之后的数据 

       

    为了更清楚的理解步骤4里的“映射”操作,我们可以拿单个数据样本  和特征向量  来举例。根据步骤4中的公式,样本  在特征向量  方向上的坐标为  。回想一下关于点乘的几何定义,我们有:

    这里  为点乘的两个向量的夹角,这里  是长度为1的单位向量,所以  ,刚好为样本  在特征向量  方向上的投影(坐标)。如果把所有数据点的映射用矩阵的形式表示出来,那就是步骤4的公式了。

    我们将原始数据映射到低维空间之后,也可以根据数据在低维空间里的坐标来重构原始数据。PCA的其中一种推导方式就是基于重构误差得到的。假设数据样本  映射到 k 维空间的坐标为  , 则基于该 k 维坐标重构的数据为:

    上面的重构公式比较直观,即:重构的数据坐标为数据在低维空间每个方向上的坐标乘以该方向上的单位向量之后的求和。如果把所有数据样本的重构用矩阵的形式表示出来,则:

    后面我们在描述PCA用于异常检测的时候还会用到这里的重构公式。

     

     

    PCA用于异常检测

    PCA在异常检测方面的做法,大体有两种思路:一种是将数据映射到低维特征空间,然后在特征空间不同维度上查看每个数据点跟其它数据的偏差;另外一种是将数据映射到低维特征空间,然后由低维特征空间重新映射回原空间,尝试用低维特征重构原始数据,看重构误差的大小。两种思路看似不太一样,其实本质上是差不多的。

    我们先来讲讲第一种思路。PCA在做特征值分解之后得到的特征向量反应了原始数据方差变化程度的不同方向,特征值为数据在对应方向上的方差大小。所以,最大特征值对应的特征向量为数据方差最大的方向,最小特征值对应的特征向量为数据方差最小的方向。原始数据在不同方向上的方差变化反应了其内在特点。如果单个数据样本跟整体数据样本表现出的特点不太一致,比如在某些方向上跟其它数据样本偏离较大,可能就表示该数据样本是一个异常点。

    对于某一个特征向量  ,数据样本  在该方向上的偏离程度  可以用如下的公式计算:

    这里的  主要起归一化的作用,这样可以使得不同方向上的偏离程度具有可比性。在计算了数据样本在所有方向上的偏离程度之后,为了给出一个综合的异常得分,最自然的做法是将样本在所有方向上的偏离程度加起来,即:

    这个公式只是计算异常得分的一种方式。也有一些算法采取了略微不同的做法,比如,有的只考虑数据在前 k 个特征向量方向上的偏差,或者只考虑后 r 个特征向量方向上的偏差,即:

    主要起归一化的作用,这样可以使得不同方向上的偏离程度具有可比性。在计算了数据样本在所有方向上的偏离程度之后,为了给出一个综合的异常得分,最自然的做法是将样本在所有方向上的偏离程度加起来,即:

    这里的  和  是人为设定的两个阈值,如果得分大于阈值则判断为异常。

    一般而言,前几个特征向量往往直接对应原始数据里的某几个特征,在前几个特征向量方向上偏差比较大的数据样本,往往就是在原始数据中那几个特征上的极值点。而后几个特征向量有些不同,它们通常表示某几个原始特征的线性组合,线性组合之后的方差比较小反应了这几个特征之间的某种关系。在后几个特征方向上偏差比较大的数据样本,表示它在原始数据里对应的那几个特征上出现了与预计不太一致的情况。到底是考虑全部特征方向上的偏差,前几个特征向量上的偏差,还是后几个特征向量上的偏差,在具体使用时可以根据具体数据灵活处理。

    前面提到,PCA用于异常检测时候,还有一种思路是基于重构误差的。直观上理解,PCA提取了数据的主要特征,如果一个数据样本不容易被重构出来,表示这个数据样本的特征跟整体数据样本的特征不一致,那么它显然就是一个异常的样本。对于数据样本  , 假设其基于 k 维特征向量重构的样本为  , 则该数据样本的异常得分可以用如下的公式计算:

     

    上面的公式考虑了重构使用的特征向量的个数 k 的影响,将 k 的所有可能做了一个加权求和,得出了一个综合的异常得分。显然,基于重构误差来计算异常得分的公式也不是唯一的,这里只是其中的一种做法。

    根据前面一节提到的重构公式,我们在基于低维特征进行数据样本的重构时,舍弃了较小的特征值对应的特征向量方向上的信息。换一句话说,重构误差其实主要来自较小的特征值对应的特征向量方向上的信息。基于这个直观的理解,PCA在异常检测上的两种不同思路都会特别关注较小的特征值对应的特征向量。所以,我们说PCA在做异常检测时候的两种思路本质上是相似的。

     

    算法延伸

    PCA 是一种线性的数据降维的方法,为了识别一些更为复杂的异常,最自然的做法是应用 kernel PCA。就异常检测的使用方式而言,kernel PCA 并无太大差异,这里就不做赘述。

    在深度学习大行其道的今天,另外一种备受关注的数据降维的方法是深度学习中的 Autoencoder。它跟PCA的差别主要是非线性和线性的差别。相信很多人看到前面基于PCA的重构误差进行异常检测时,也意识到了 Autoencoder 也可以以类似的方式做异常检测。而 Autoencoder 有很多种不同的类型,比如 Denoising Autoencoder,Variational Autoencoder 等等,后面我们可以用单独的篇幅再来具体讲解如何用它们来做异常检测。

     

    机器学习-异常检测算法(四):DAGMM

    自编码器(Autoencoder)在异常检测上有很多应用,之前看到 ICLR-2018 的一篇文章《Deep Autoencoding Gaussian Mixture Model for Unsupervised Anomaly Detection》,觉得有些想法有点意思,跟我之前思考过的问题有点相关, 一直想简单介绍一下。

     

    算法核心思想

    文章介绍的算法简称 DAGMM,主要的想法跟异常检测算法系列的上一篇文章《机器学习-异常检测算法(三):Principal Component Analysis》有很大关联。在上一篇文章里,我们提到 PCA 应用于异常检测,大体上有两种套路:(1)将原始数据映射到低维特征空间,然后在低维空间里查看每一个点跟其他数据点的偏离程度;(2)将原始数据映射到低维特征空间,然后由低维特征空间重新映射回原空间,尝试用低维特征重构原始数据,看重构误差的大小。这两个套路反应出这样一个信息:自编码器中间隐藏层特征和最后的重构误差对于识别异常都是有用的。

    DAGMM 的作者同样注意到了这个信息,为了形象的说明这点,文章还专门给了一个例子,就是下面这张图:

    上图中,横轴是应用自编码器将数据压缩到一维空间的坐标,纵轴是数据点的重构误差。图中蓝色点是正常数据点,红色是异常数据点。显然,从图中我们可以看出,右上角这部分异常数据点可以通过重构误差跟其他点区别开来,而左下角这部分异常点则可以在低维特征空间(这里压缩到了一维)很明显的跟其他点区分开。

    DAGMM 算法试图通过一个基于 Autoencoder+“GMM” 的神经网络模型综合考虑上述两方面信息进行异常检测,这里 GMM 是打引号的,原因在下面会解释。

     

    算法步骤简述

    DAGMM 的网络结构(如上图)分为两个部分:压缩网络 和 估计网络。压缩网络是一个常规的 autoencoder。通过压缩网络我们可以得到前面提到的两部分关键信息:一个是中间隐藏层特征(低维空间特征信息)Z_c,一个是由输入向量 x 和输出向量 x' 计算得到的重构误差 Z_r(重构误差的信息)。关于重构误差,文章中建议了两种方式来计算,欧式距离和余弦相似度。当我们同时使用这两种方式来计算重构误差的时候,Z_r 就是一个长度为 2 的向量。最后,由压缩网络得到的这两个向量(Z_c 和 Z_r)拼接在一起,作为输入接入到后面的估计网络。

    估计网络的部分有点好玩,结构上它只是常规的多层神经网络,但它其实是 GMM(高斯混合模型)的“替代品”,用于模拟 GMM 的结果。具体的,假设 GMM 中 gaussian component 的个数为 k,则估计网络的输出 p 经过 softmax 层可以得到样本分别归属 k 个 component 的概率,即:

    得到 N 个样本分别归属不同 component 的概率之后,我们可以用来估计 GMM 的几个重要参数:均值、方差、协方差矩阵。这步跟常规的高斯混合模型的参数更新过程无异。

    上述几个参数确定之后,sample energy (也就是样本的 negative log-likelihood)也就很容易计算了:

    到这里我们可以看到,估计网络的作用就是模拟 GMM 得到样本归属各个 component 的概率,这部分信息进而用来更新 GMM 的参数,计算得到 sample energy。而 sample energy 是目标函数的一部分,通过优化目标函数,估计网络的参数也会得到更新。

    最后补充介绍一下 DAGMM 的目标函数(如下图),总共包含三个部分,第一项为 autoencoder 部分的重构误差,第二部分为高斯混合模型部分(估计网络部分)的 sample energy ,第三项是一个正则项。

    第三项的具体计算方式为:

    图片

    这项的作用是防止 GMM 中的协方差矩阵的对角线上的值变为 0 并最终导致矩阵不可逆。

    上面是算法的训练过程,当做预测的时候,可以根据 GMM 输出的概率值来判断样本是否异常,只需要确定一个阈值就可以了。

     

    需要注意的问题

    高斯混合模型在实际求解过程中,运行的代码很容易出现奇异矩阵的问题。尽管算法为了防止协方差矩阵不可逆,在目标函数中增加了正则项,但是在代码实际实现过程中还是需要对可能出现奇异矩阵的情况做特别处理,保障算法平稳运行,比如,可以在对角线添加一个极小值之类(光靠这个可能还不够)。这篇文章对这个问题描述的还比较清楚,有兴趣的可以看看:《Regularized Gaussian Covariance Estimation》(https://freemind.pluskid.org/machine-learning/regularized-gaussian-covariance-estimation/)。

    基于深度学习的异常检测算法最近几年层出不穷,后面有机会会继续介绍。还有一些经典的算法,也有好玩的地方。比如,之前一直有一个让我很困惑的问题,为什么 One-Class SVM (不是 SVDD)要找一个可以把坐标原点跟其他数据点分隔开的超平面?并且通过这种方式就可以识别异常。这里的“原点”非常奇怪,原文章也没有给任何直观的解释,只说是受 1963 年的一篇老文章的启发,网上也几乎找不到其他人的解释,大部分人只是把这个当作是作者的一个假设(假设坐标原点是唯一的异常点)。这个问题困扰了我好几年,最近突然看到一篇 2014 年的 Paper,完美答疑, 感觉这个也值得写篇文章。

    参考文献

    1.F. T. Liu, K. M. Ting and Z. H. Zhou,Isolation-based Anomaly Detection,TKDD,2011

    2.M. M. Breunig, H. P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-based Local Outliers. SIGMOD, 2000.

    3.M. Goldstein. FastLOF: An Expectation-Maximization based Local Outlier detection algorithm. ICPR, 2012

    4.Veeramachaneni, K., Arnaldo, I., Korrapati, V., Bassias, C., Li, K.: AI^2 : training a big data machine to defend. In: 2016 IEEE 2nd International Conference on Big Data Security on Cloud (BigDataSecurity), IEEE International Conference on High Performance and Smart Computing (HPSC), and IEEE International Conference on Intelligent Data and Security (IDS), pp. 49–54 (2016)

    5.Shyu M L, Chen S C, Sarinnapakorn K, et al. A novel anomaly detection scheme based on principal component classifier. ICDM, 2003.

    展开全文
  • 而本篇介绍的算法孤立森林Isolation Forest (简称iForest)的想法要巧妙一些,它尝试直接去刻画数据的“疏离”(isolation)程度,而不借助其他量化指标。Isolation Forest 是 无监督 的算法,因为简单、高效,在学术...

    异常检测 (anomaly detection),又被称为“离群点检测” (outlier detection),是机器学习研究领域中跟现实紧密联系、有广泛应用需求的一类问题。但是,什么是异常,并没有标准答案,通常因具体应用场景而异。大多数文献对异常的定义虽然笼统,但其实暗含了认定“异常”的两个标准或者说假设:

    • 异常数据跟样本中大多数数据不太一样。
    • 异常数据在整体数据样本中占比比较小。

    为了刻画异常数据的“不一样”,最直接的做法是利用各种统计的、距离的、密度的量化指标去描述数据样本跟其他样本的疏离程度。这是一类异常检测的方法,有时间我会整理。

    而本篇介绍的算法孤立森林Isolation Forest (简称iForest)的想法要巧妙一些,它尝试直接去刻画数据的“疏离”(isolation)程度,而不借助其他量化指标。Isolation Forest 是无监督的算法,因为简单、高效,在学术界和工业界都有着不错的名声。

    本篇博客先介绍iForest算法的原理,然后基于sklearn应用iForest算法,当然,当下最流行的Python异常检测工具库Python Outlier Detection(PyOD)我们也会提供一个简单的接口例子。

    一、算法介绍

    1.1 iTree

    1.1.1 训练过程

    提到森林,自然少不了树,毕竟森林都是由树构成的,看iForest前,我们先来看看Isolation Tree(简称iTree)是怎么构成的,iTree是一种随机二叉树,每个节点要么有两个孩子,要么就是叶子节点,一个孩子都没有。给定一堆数据集D,这里D的所有属性都是连续型的变量,iTree的构成过程如下:

    • 随机选择一个属性Attr;

    • 随机选择该属性的一个值Value;

    • 根据Attr对每条记录进行分类,把Attr小于Value的记录放在左女儿,把大于等于Value的记录放在右孩子;

    • 然后递归的构造左女儿和右女儿,直到满足以下条件:

      • 传入的数据集只有一条记录或者多条一样的记录;
      • 树的高度达到了限定高度

    下图是iTree的训练过程

    CSDN图标

    1.1.2 预测过程

    iTree构建好了后,就可以对数据进行预测,预测的过程就是把测试记录在iTree上走一下,看测试记录落在哪个叶子节点。iTree能有效检测异常的假设是:异常点一般都是非常稀有的,在iTree中会很快被划分到叶子节点,因此可以用叶子节点到根节点的路径h(x)长度来判断一条记录x是否是异常点


    这里解释下,为什么异常点会很快被划分到叶子节点

    我们先用一个简单的例子来说明iForest的基本想法。假设现在有一组一维数据(如下图所示,可以认为是一个特征),我们要对这组数据进行随机切分,希望可以把点 A A A 和点 B B B 单独切分出来。具体的,我们先在特征的最大值和最小值之间随机选择一个值 x x x,然后按照 &lt; x &lt;x <x &gt; = x &gt;=x >=x 可以把数据分成左右两组。然后,在这两组数据中分别重复这个步骤,直到数据不可再分。显然,点 B B B 跟其他数据比较疏离,可能用很少的次数就可以把它切分出来(这里涉及到停止条件,即叶子节点的样本只有1个了,已经不能再分了);点 A A A 跟其他数据点聚在一起,可能需要更多的次数才能把它切分出来。

    CSDN图标

    我们把数据从一维扩展到两维。同样的,我们沿着两个坐标轴进行随机切分,尝试把下图中的点 A ′ A&#x27; A和点 B ′ B&#x27; B分别切分出来。我们先随机选择一个特征维度,在这个特征的最大值和最小值之间随机选择一个值,按照跟特征值的大小关系将数据进行左右切分。然后,在左右两组数据中,我们重复上述步骤,再随机的按某个特征维度的取值把数据进行细分,直到无法细分,即:只剩下一个数据点,或者剩下的数据全部相同。跟先前的例子类似,直观上,点 B ′ B&#x27; B跟其他数据点比较疏离,可能只需要很少的几次操作就可以将它细分出来;点 A ′ A&#x27; A需要的切分次数可能会更多一些。

    CSDN图标

    以上,就可以知道iForest算法的初衷了。

    我们继续回到iTree的预测过程中:假设,要预测的样本为 x x xiTree 的训练样本中同样落在 x x x 所在叶子节点的样本数为 T . s i z e T.size T.size,则数据 x x x 在这棵 iTree 上的路径长度 h ( x ) h(x) h(x),可以用下面这个公式计算 x x x在 iTree 中的路径长度:
    h ( x ) = e + C ( T . s i z e ) h(x)=e+C(T.size) h(x)=e+C(T.size)

    公式中, e e e 表示数据 x x x 从 iTree 的根节点到叶节点过程中经过的边的数目, C ( T . s i z e ) C(T.size) C(T.size) 可以认为是一个修正值,它表示在一棵用 T . s i z e T.size T.size 条样本数据构建的二叉树的平均路径长度。一般的, C ( n ) C(n) C(n) 的计算公式如下:
    c ( n ) = 2 H ( n − 1 ) − ( 2 ( n − 1 ) n ) c(n) = 2H(n − 1) − (\frac{2(n − 1)}{n}) c(n)=2H(n1)(n2(n1))

    其中 H ( k ) = l n ( k ) + ξ H(k) = ln(k) + \xi H(k)=ln(k)+ξ ξ \xi ξ为欧拉常数。

    假设训练一棵iTree的样本数目为 ψ \psi ψ,则 x x x在这颗树iTree的异常指数为
    s ( x , ψ ) = 2 ( − h ( x ) c ( ψ ) ) s(x,\psi) = 2^{(-\frac{h(x)}{c(\psi)})} s(x,ψ)=2(c(ψ)h(x))

    从异常分值的公式看, s ( x , ψ ) s(x,\psi) s(x,ψ)取值范围为 [ 0 , 1 ] [0,1] [0,1],可以看到,如果 h ( x ) h(x) h(x)越小,则 s ( x , ψ ) s(x,\psi) s(x,ψ)越接近1,如果 h ( x ) h(x) h(x)越大,则 s ( x , ψ ) s(x,\psi) s(x,ψ)越接近0.5.

    如果数据 x x x 在多棵 iTree 中的平均路径长度越短,得分越接近 1,表明数据 x x x 越异常;如果数据 x x x 在多棵 iTree 中的平均路径长度越长,得分越接近 0,表示数据 x x x 越正常;如果数据 x x x 在多棵 iTree 中的平均路径长度接近整体均值,则打分会在 0.5 附近。

    1.2 iForest

    iTree搞明白了,我们现在来看看iForest是怎么构造的,给定一个包含 n n n条记录的数据集D,如何构造一个iForest。iForest和Random Forest的方法有些类似,都是随机采样一部分数据集去构造每一棵树,保证不同树之间的差异性,采样的数据量 ψ \psi ψ不需要等于n,可以远远小于n,论文中提到采样大小超过256效果就提升不大了,明确越大还会造成计算时间的上的浪费。这是论文中的原图:

    左边是原始数据,右边是采样了数据,蓝色是正常样本,红色是异常样本。可以看到,在采样之前,正常样本和异常样本出现重叠,因此很难分开,但我们采样之后,异常样本和正常样本可以明显的分开。

    除了限制采样大小以外,还要给每棵iTree设置最大高度 l = c e i l i n g ( l o g 2 ψ ) l=ceiling(log_2^\psi) l=ceiling(log2ψ),这是因为异常数据记录都比较少,其路径长度也比较低,而我们也只需要把正常记录和异常记录区分开来,因此只需要关心低于平均高度的部分就好,这样算法效率更高先看iForest的伪代码:

    CSDN图标

    当然,iForest是由多颗iTree构成的,自然iForest异常分值的公式也需要改变:
    s ( x , ψ ) = 2 ( − E ( h ( x ) ) c ( ψ ) ) s(x,\psi) = 2^{(-\frac{E(h(x))}{c(\psi)})} s(x,ψ)=2(c(ψ)E(h(x)))

    公式中, E ( h ( x ) ) E(h(x)) E(h(x))表示数据 x x x 在多棵 iTree 的路径长度的均值, ψ \psi ψ 表示单棵 iTree 的训练样本的样本数, c ( ψ ) c(\psi) c(ψ) 表示用 ψ \psi ψ条数据构建的二叉树的平均路径长度,它在这里主要用来做归一化。

    从异常分值的公式看,如果数据 x x x 在多棵 iTree 中的平均路径长度越短,得分越接近 1,表明数据 x x x 越异常;如果数据 x x x 在多棵 iTree 中的平均路径长度越长,得分越接近 0,表示数据 x x x 越正常;如果数据 x x x 在多棵 iTree 中的平均路径长度接近整体均值,则打分会在 0.5 附近。

    1.3 算法应用

    iForest算法主要有两个参数:一个是二叉树的个数;另一个是训练单棵 iTree 时候抽取样本的数目。实验表明,当设定为 100 棵树,抽样样本数为 256 条的时候,iForest在大多数情况下就已经可以取得不错的效果。这也体现了算法的简单、高效。

    Isolation Forest 是无监督的异常检测算法,在实际应用时,并不需要标签。需要注意的是:(1)如果训练样本中异常样本的比例比较高,违背了先前提到的异常检测的基本假设,可能最终的效果会受影响;(2)异常检测跟具体的应用场景紧密相关,算法检测出的“异常”不一定是我们实际想要的。比如,在识别虚假交易时,异常的交易未必就是虚假的交易。所以,在特征选择时,可能需要过滤不太相关的特征,以免识别出一些不太相关的“异常”。

    二、代码应用

    2.1 sklearn:IsolationForest

    sklearn提供了ensemble.IsolationForest模块实现了Isolation Forest算法。

    函数体如下:

    class sklearn.ensemble.IsolationForest(n_estimators=100, max_samples=’auto’, contamination=’legacy’, max_features=1.0, bootstrap=False, n_jobs=None, behaviour=’old’, random_state=None, verbose=0)

    几个主要参数介绍:

    • n_estimators : int, optional (default=100) 森林中树的颗数
    • max_samples : int or float, optional (default=”auto”) 对每棵树,样本个数或比例
    • contamination : float in (0., 0.5), optional (default=0.1) 这是最关键的参数,用户设置样本中异常点的比例
    • max_features : int or float, optional (default=1.0) 对每棵树,特征个数或比例

    几个主要函数介绍:

    • fit(X): Fit estimator.(无监督)
    • predict(X):返回值:+1 表示正常样本, -1表示异常样本。
    • decision_function(X):返回样本的异常评分。 值越小表示越有可能是异常样本。

    下面是一个完整的代码,来自参考文献4。

    #!/usr/bin/python
    # -*- coding:utf-8 -*-
     
    import numpy as np
    import matplotlib.pyplot as plt
    from sklearn.ensemble import IsolationForest
    from scipy import stats
     
    rng = np.random.RandomState(42)
     
    # 构造训练样本
    n_samples = 200  #样本总数
    outliers_fraction = 0.25  #异常样本比例
    n_inliers = int((1. - outliers_fraction) * n_samples)
    n_outliers = int(outliers_fraction * n_samples)
     
    X = 0.3 * rng.randn(n_inliers // 2, 2)
    X_train = np.r_[X + 2, X - 2]   #正常样本
    X_train = np.r_[X_train, np.random.uniform(low=-6, high=6, size=(n_outliers, 2))]  #正常样本加上异常样本
     
    # fit the model
    clf = IsolationForest(max_samples=n_samples, random_state=rng, contamination=outliers_fraction)
    clf.fit(X_train)
    # y_pred_train = clf.predict(X_train)
    scores_pred = clf.decision_function(X_train)
    threshold = stats.scoreatpercentile(scores_pred, 100 * outliers_fraction)  #根据训练样本中异常样本比例,得到阈值,用于绘图
     
    # plot the line, the samples, and the nearest vectors to the plane
    xx, yy = np.meshgrid(np.linspace(-7, 7, 50), np.linspace(-7, 7, 50))
    Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
     
    plt.title("IsolationForest")
    # plt.contourf(xx, yy, Z, cmap=plt.cm.Blues_r)
    plt.contourf(xx, yy, Z, levels=np.linspace(Z.min(), threshold, 7), cmap=plt.cm.Blues_r)  #绘制异常点区域,值从最小的到阈值的那部分
    a = plt.contour(xx, yy, Z, levels=[threshold], linewidths=2, colors='red')  #绘制异常点区域和正常点区域的边界
    plt.contourf(xx, yy, Z, levels=[threshold, Z.max()], colors='palevioletred')  #绘制正常点区域,值从阈值到最大的那部分
     
    b = plt.scatter(X_train[:-n_outliers, 0], X_train[:-n_outliers, 1], c='white',
                        s=20, edgecolor='k')
    c = plt.scatter(X_train[-n_outliers:, 0], X_train[-n_outliers:, 1], c='black',
                        s=20, edgecolor='k')
    plt.axis('tight')
    plt.xlim((-7, 7))
    plt.ylim((-7, 7))
    plt.legend([a.collections[0], b, c],
               ['learned decision function', 'true inliers', 'true outliers'],
               loc="upper left")
    plt.show()
    
    CSDN图标

    2.2 PyOD:IsolationForest

    在PyOD的官方github中有专门的例子,链接如下

    参考文献:

    【1】F. T. Liu, K. M. Ting and Z. H. Zhou,Isolation-based Anomaly Detection,TKDD,2011
    【2】机器学习-异常检测算法(一):Isolation Forest
    【3】异常检测算法–Isolation Forest
    【4】异常检测(二)——IsolationForest

    展开全文
  • SARS检疫隔离控制问题研究I,刘新金,邹云,在缺乏有效药物和疫苗的情况下,检疫隔离控制是阻止疾病传播的有效途径。针对此,本文以SARS疾病为例,分别讨论了检疫隔离控制下SARS SEQ
  • Python实现孤立森林 (Isolation Forest)

    千次阅读 热门讨论 2020-12-31 13:01:22
    """ self.size_data = len(self.data) self.size_attribute = len(self.data[0]) self.tree = self.__get_isolation_forest(np.arange(self.size_data), -1, "") def __get_isolation_forest(self, idx, height, ...

    引入

      代码说明:
      1)输入:给定数据集;
      2)属性:tree,根据孤立森林建立的二叉树;
      3)用法示例:

            # >>> np.random.seed(10)
            # >>> temp_data = np.random.rand(10, 10)
            # >>> temp_model = IsolationForest(temp_data)
            # >>> temp_model.display()
    

      4)树的结构说明:
      4.1)若为叶子节点,则节点.value包含:当前数据在传入数据中的索引,所在层以及标志变量;
      4.2)若为父母节点,则节点.value包含:划分到该节点的数据样本个数,层数,当前划分所选择属性的序号,所选择的阈值以及标志变量。

    代码

    """
    @author: Inki
    @email: inki.yinji@qq.com
    @version: Created in 2020 1230, last modified in 2020 1231.
    @note:
        The paper name --> isolation forest.
    """
    
    import numpy as np
    
    
    class Tree:
        """
        The tree structure.
        """
    
        def __init__(self, value, left, right):
            self.value = value
            self.left = left
            self.right = right
    
    
    class IsolationForest:
        """
        The isolation forest algorithm.
        @param:
            data: The given data.
        @attribute:
            tree: The isolation forest.
        @example:
            # >>> np.random.seed(10)
            # >>> temp_data = np.random.rand(10, 10)
            # >>> temp_model = IsolationForest(temp_data)
            # >>> temp_model.display()
        """
    
        def __init__(self, data):
            self.data = data
            self.size_data = 0
            self.size_attribute = 0
            self.tree = None
            self.__initialize_isolation_forest()
    
        def __initialize_isolation_forest(self):
            """
            The initialize of isolation forest.
            """
            self.size_data = len(self.data)
            self.size_attribute = len(self.data[0])
            self.tree = self.__get_isolation_forest(np.arange(self.size_data), -1, "")
    
        def __get_isolation_forest(self, idx, height, flag):
            """
            Get the isolation forest.
            """
            if len(idx) == 1:
                return Tree((idx[0], height + 1, flag), None, None)
            elif len(idx) == 0:
                return
            else:
                temp_random_attribute_idx = np.random.choice(self.size_attribute)
                temp_attribute = self.data[idx][:, temp_random_attribute_idx]
                temp_threshold = np.random.choice(temp_attribute)
                temp_left_idx, temp_right_idx = self.__filter(idx, temp_attribute, temp_threshold)
                return Tree((len(idx), height + 1, temp_random_attribute_idx, temp_threshold, flag),
                            self.__get_isolation_forest(temp_left_idx, height + 1, "left"),
                            self.__get_isolation_forest(temp_right_idx, height + 1, "right"))
    
        def __filter(self, idx, attribute, threshold):
            """
            Filter the data.
            """
            ret_left, ret_right = [], []
            for i in range(len(idx)):
                if attribute[i] < threshold:
                    ret_left.append(idx[i])
                else:
                    ret_right.append(idx[i])
    
            return ret_left, ret_right
    
        def display(self):
            """
            Display tree
            """
            temp_tree = [self.tree]
            while len(temp_tree) > 0 and temp_tree is not None:
                temp_node = temp_tree.pop(0)
                temp_value = temp_node.value
                if len(temp_value) == 5:
                    if temp_value[-1] == "":
                        print("Len: %d; layer: %d; attribute idx: %d; threshold: %.2f; flag: root" % temp_value[:-1])
                    else:
                        print("Len: %d; layer: %d; attribute idx: %d; threshold: %.2f; flag: %s" % temp_value)
                else:
                    print("Data idx: %d; layer: %d; flag: %s" % temp_value)
                if temp_node.left is not None:
                    temp_tree.append(temp_node.left)
                if temp_node.right is not None:
                    temp_tree.append(temp_node.right)
    
    
    if __name__ == '__main__':
        np.random.seed(10)
        temp_data = np.random.rand(10, 10)
        temp_model = IsolationForest(temp_data)
        temp_model.display()
    
    

    改进代码

    """
    Author: Inki
    Email: inki.yinji@qq.com
    Create: 2021 0224
    Last modify: 2021 0302
    """
    
    import numpy as np
    
    
    class Tree:
        """
        The tree structure.
        """
    
        def __init__(self, value, left, right):
            self.value = value
            self.left = left
            self.right = right
    
    
    class IsolationTree:
        """
        The designed isolation tree.
        :param
            mat:                                The given data matrix.
            feature_idx:                        The index of selected attributes.
            attribute_choose_mechanism:         The feature choose mechanism.
                Including "random", "cycle", and the default setting is "cycle".
            attribute_value_choose_mechanism:   The feature value choose mechanism.
                Including "random", "average", and the default setting is "random".
        """
    
        def __init__(self, mat, feature_idx=None, attribute_choose_mechanism="random",
                     attribute_value_choose_mechanism="random"):
            self.__mat = mat
            self.__feature_idx = feature_idx
            self.__attribute_choose_mechanism = attribute_choose_mechanism
            self.__attribute_value_choose_mechanism = attribute_value_choose_mechanism
            self.__m = 0
            self.__n = 0
            self.__idx_count = 0
            self.tree_ = None
            self.__init_isolation_tree()
    
        def __init_isolation_tree(self):
            """
            The initialize of IsolationTree
            """
            self.__m = len(self.__mat)
            self.__n = len(self.__mat[0])
            if self.__feature_idx is None:
                self.__feature_idx = np.arange(self.__n)
            self.tree_ = self.__get_tree(np.arange(self.__m), -1, "Root")
    
        def __get_tree(self, idx, height, flag):
            """
            Getting tree.
            """
            if len(idx) == 0:
                return
            elif len(idx) == 1:
                return Tree((idx[0], height + 1, flag), None, None)
            else:
                attribute_idx = self.__get_attribute_idx()
                attribute_arr = self.__mat[idx, attribute_idx]
                attribute_value = self.__get_attribute_value(attribute_arr)
                attribute_arr = list(set(attribute_arr))
    
                if len(attribute_arr) == 1:
                    left_idx, right_idx = [idx[0]], idx[1:]
                else:
                    left_idx, right_idx = self.__filter(idx, attribute_arr, attribute_value)
    
                return Tree((len(idx), height + 1, attribute_idx, attribute_value, flag),
                            self.__get_tree(left_idx, height + 1, "Left"),
                            self.__get_tree(right_idx, height + 1, "Right"))
    
        def __get_attribute_idx(self):
            """
            Getting attribute index.
            """
            if self.__attribute_choose_mechanism == "random":
                return np.random.choice(self.__feature_idx)
            elif self.__attribute_choose_mechanism == "cycle":
                if self.__idx_count == len(self.__feature_idx):
                    self.__idx_count = 0
    
                ret_feature_idx = self.__feature_idx[self.__idx_count]
                self.__idx_count += 1
    
                return ret_feature_idx
    
        def __get_attribute_value(self, attribute_arr):
            """
            Taking a value from the specified attribute.
            """
            if self.__attribute_value_choose_mechanism == "random":
                return np.random.choice(attribute_arr)
            elif self.__attribute_value_choose_mechanism == "average":
                return np.average(attribute_arr)
    
        def __filter(self, idx, attribute_arr, attribute_value):
            """
            Filtering data.
            """
            ret_left, ret_right = [], []
            for idx_i, att_i in zip(idx, attribute_arr):
                if att_i < attribute_value:
                    ret_left.append(idx_i)
                else:
                    ret_right.append(idx_i)
    
            return ret_left, ret_right
    
        def show_tree(self):
            """
            Showing tree.
            """
            if self.tree_ is None:
                return
            tree = [self.tree_]
    
            while len(tree) > 0:
                node = tree.pop(0)
                value = node.value
                if len(value) == 5:
                    # The non-leaf node.
                    print("Len: %d; layer: %d; attribute idx: %d; attribute value: %.2f; flag: %s" % value)
                else:
                    print("Data idx: %d; layer: %d; flag: %s" % value)
    
                if node.left is not None:
                    tree.append(node.left)
    
                if node.right is not None:
                    tree.append(node.right)
    
    
    展开全文
  • 转自: ...2, TensorFlow的tf.contrib.learn包已经实现的Random Forest可作参考(Isolation Forest在结构上与Random Forest类似),只需对Isolation Forest定制一个Operation即可(Op的细节看这里: ...
  • Isolation Forest算法实现详解

    万次阅读 多人点赞 2017-06-26 22:32:29
    本文算法完整实现源码已开源至本人的GitHub(如果对你有帮助,请给一个 star ),参看其中的 iforest 包下的 IForest 和 ITree 两个类: ...Isolation Forest异常检测算法原理详解,本文
  • 当主接口采用@Transactional(rollbackFor = Exception.class,isolation = Isolation.SERIALIZABLE)注解事务时,分接口,即主接口调用其他分服务接口时不能采用事务回滚注解,否则将会导致事务嵌套,从而造成死锁...
  • Note of Isolation Forest 论文:https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf 一、介绍 作者认为,异常数据存在两个显著的特性: 数量少,甚至是极少 与正常数据有显著的属性值差异 ...
  • 事务的4种隔离级别(Isolation Level)分别是什么? 当多个线程都开启事务操作数据库中的数据时,数据库系统要能进行隔离操作,以保证各个线程获...
  • postgresql 默认的 isolation level 为 read committed,可以调整隔离级别。 版本 # cat /etc/centos-release CentOS Linux release 7.4.1708 (Core) # # # su - postgres Last login: Wed J...
  • 人体肠道中氯霉素同化菌的分离鉴定与特性研究,赵鑫,田丰伟,采用传统微生物分离方法,以氯霉素为培养基唯一碳源,从健康人粪便样品中分离到五株氯霉素同化微生物。根据菌株形态、生理生化特
  • Isolation Forest算法原理详解

    万次阅读 多人点赞 2017-06-18 18:39:18
    本文只介绍原论文中的 Isolation Forest 孤立点检测算法的原理,实际的代码实现详解请参照我的另一篇博客:Isolation Forest算法实现详解。 或者读者可以到我的GitHub上去下载完整的项目源码以及测试代码(源代码...
  • 语言:English ...============================= Puffin Cloud Isolation目前处于测试阶段。 海鹦云隔离:https://www.puffin.com/cloud-isolation/beta/报告错误和建议:反馈+i@puffinbrowser.com

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 125,778
精华内容 50,311
关键字:

isolation