精华内容
下载资源
问答
  • I . 核心距离 概念 II . 核心距离值 III . 核心距离 示例 IV . 可达距离 V . 可达距离 示例 VI . 可达距离 总结



    I . 核心距离 概念



    1 . 核心距离概念引入 : 必须是核心对象 , 才有核心距离 ;


    2 . 已知条件 :


    ① 数据集合 : 给定 数据集 D D D ;

    ② 参数 : 给定两个参数 , ε \varepsilon ε-邻域半径参数 ε \varepsilon ε , MinPts 参数 ( ε \varepsilon ε-邻域中样本个数最小阈值 ) ;

    ③ 数据样对象 : 给定一个数据样本 O O O ;


    3 . 样本 O O O 是核心对象 : 此类情况 核心距离有意义 , 如果是边界对象无意义 ;


    ① 核心距离概念引入 : 如果该样本对象 O O O 是核心对象 , 那么 O O O 对象的 核心距离 , 就是使样本 O O O 能够成为 核心对象 的 最小半径值 ε \varepsilon ε 参数 ;

    ② 核心距离要求 ( 恰好核心的最小距离 ) : 是使得 O O O 能成为 核心对象 的 最小距离 , 不是 之前设定的 ε \varepsilon ε 参数 , 该核心距离小于等于 ε \varepsilon ε 参数 , 样本 O O O ε \varepsilon ε-邻域 内可能有多于 MinPts 个样本 , 但是我们只取其半径范围内 恰好 有 MinPts 样本的 半径值 ε \varepsilon ε 作为其核心距离 ;

    ③ 核心距离种类个数 : 不同的样本 , 核心距离可能不同 , 10 10 10 个样本 , 可能有 10 10 10 个核心距离 ;

    ④ 样本 O O O 是核心对象判定条件 : 以样本 O O O 为中心点 , 再其 ε \varepsilon ε 半径区域范围内 ( ε \varepsilon ε-邻域 ) , 样本个数多于 MinPts 最小阈值 ;


    4 . 样本 O O O 不是核心对象 : 如果该样本对象 O O O 不是核心对象 , 是 边界对象 , 那么 该样本的 核心距离 概念没有意义 ;



    II . 核心距离值



    核心距离确定 :


    ① 样本 O O O 是 边界对象 : 核心距离 无穷大 ; 样本 O O O ε \varepsilon ε-邻域 的样本个数小于 MinPts 个 ;

    ② 样本 O O O 是 核心对象 : 核心距离 是保证 半径范围内恰好有 MinPts 个样本的最小半径 , 一定要注意 , 就是 卡着第 MinPts 个样本点的圆的半径 , O O O 核心对象到第 MinPts 个样本的距离 / 半径 ;



    III . 核心距离 示例



    1 . 已知条件 :


    ε \varepsilon ε-邻域 半径参数 : ε \varepsilon ε ;

    ② MinPts 阈值参数 : MinPts = 5 = 5 =5 , ε \varepsilon ε-邻域中样本个数最小阈值 , 达到该阈值 , 样本才能算作核心对象 ;

    ③ 核心对象 : 红色点是 核心对象 ;

    ε \varepsilon ε-邻域 : 外层的圆 , 以核心对象 ( 红色样本 ) 为中心 , ε \varepsilon ε 参数为半径 , 的区域范围 , 是 ε \varepsilon ε-邻域 ;


    2 . 核心距离分析 :


    ① 核心距离要求 : 样本的 核心距离 是保证 半径范围内恰好有 MinPts 个样本的最小半径 ;

    ε \varepsilon ε 半径说明 : 这里 ε \varepsilon ε 半径内有 11 11 11 个样本 , 这个 ε \varepsilon ε 不是我们要的核心距离 ;

    ③ 本案例的核心距离 : 要恰好保证有 核心距离半径范围内 MinPts = 5 = 5 =5 样本 , 的最小半径值 ;

    ④ 注意两点 : 第一 , 恰好保证区域内有 5 5 5 个样本 ; 第二 , 最小半径 ;

    ⑤ 核心距离确定 : 这两个条件唯一确定了一个半径值 ε ′ \varepsilon' ε ;


    在这里插入图片描述



    IV . 可达距离



    1 . 可达距离概念引入 : 必须是核心对象 , 才有可达距离 ;


    2 . 已知条件 :


    ① 数据集合 : 给定 数据集 D D D ;

    ② 参数 : 给定两个参数 , ε \varepsilon ε-邻域半径参数 ε \varepsilon ε , MinPts 参数 ( ε \varepsilon ε-邻域中样本个数最小阈值 ) ;

    ③ 数据样对象 : 给定一个数据样本 O O O ;


    3 . 样本 O O O 是核心对象 : 此类情况 可达距离有意义 , 如果是边界对象 可达距离 无意义 ;


    4 . 可达距离概念 :


    ① 前提 : 样本 O O O 必须是核心对象 ;

    ② 核心距离 : 样本 O O O 的核心距离 ;

    ③ 欧几里得距离 : O O O p p p 之间的 欧几里得距离 , 这里与 曼哈顿距离 对照 ;

    ④ 可达距离 : 样本 O O O 与样本 p p p 之间的可达距离是 , 核心距离 与 欧几里得距离 的 较大的值 ;



    V . 可达距离 示例



    1 . 已知条件 :


    ε \varepsilon ε-邻域 半径参数 : ε \varepsilon ε ;

    ② MinPts 阈值参数 : MinPts = 5 = 5 =5 , ε \varepsilon ε-邻域中样本个数最小阈值 , 达到该阈值 , 样本才能算作核心对象 ;

    ③ 样本 O O O : 是核心对象 , 中心的红点 ;

    ε \varepsilon ε-邻域 : 外层的圆 , 以核心对象 ( 红色样本 ) 为中心 , ε \varepsilon ε 参数为半径 , 的区域范围 , 是 ε \varepsilon ε-邻域 ;

    ⑤ 样本 p 1 p_1 p1 : 在 样本 O O O 核心距离范围内 ;

    ⑥ 样本 p 2 p_2 p2 : 在样本 O O O 核心距离范围外 , 在 ε \varepsilon ε 半径之内 ;


    2 . 可达距离 :


    ① 样本 O O O 与 样本 p 1 p_1 p1 的可达距离 :核心距离 ε ′ \varepsilon' ε O O O p 1 p_1 p1 欧几里得距离 选较大的那个 , 选择 核心距离 ;

    ② 样本 O O O 与 样本 p 2 p_2 p2 的可达距离 :核心距离 ε ′ \varepsilon' ε O O O p 2 p_2 p2 欧几里得距离 选较大的那个 , 选择 欧几里得距离 ;

    在这里插入图片描述



    VI . 可达距离 总结



    可达距离总结 :


    ① 核心距离内 : 样本 O O O 与其核心距离内的样本的可达距离 都是 核心距离 值 ;

    ② 核心距离外 ( ε \varepsilon ε-邻域内 ) : 样本 O O O 与其核心距离外的样本的可达距离 都是 样本 O O O 与其它样本的 欧几里得距离 ;



    VII . 族序 ( Cluster Ordering ) 概念



    1 . 族序 ( Cluster Ordering ) 概念 :


    ① 多层次同时聚类 : 不同层次的聚类分组 , 可以同时进行构建 ;

    ② 顺序处理样本 : 处理数据集样本对象时 , 使用特定的顺序进行处理 ;

    ③ 顺序扩展 : 数据集样本对外扩展时 , 按照该顺序进行扩展 ,

    ④ 族序概念 : 该特定顺序就是 族序 ( Cluster Ordering ) ;


    2 . 聚类顺序 : 从 低层 到 高层 ; 从 稠密 到 稀疏 ;

    聚类时 , 低层 的聚类分组 要首先构建完成 , 也就是 ε \varepsilon ε 参数 较小的聚类分组 ;


    3 . 密度可达的两种情况情况 : 两个样本 密度可达 , 有两种情况 :

    ε \varepsilon ε 参数小 : 一种情况是 ε \varepsilon ε 参数 较小的时候 , 这两个样本就可以密度可达 ;

    ε \varepsilon ε 参数大 : 另一种情况是 ε \varepsilon ε 参数 取值很大时 , 才可以密度可达 ;


    4 . 扩展样本优先级 : 扩展样本对象时 , 优先选择第一种情况 , ε \varepsilon ε 参数 较小的时候 就可以密度可达的样本 ;


    5 . 每个样本对象需要存储两个值 : 核心距离可达距离 ;

    展开全文
  • 近日,Avago Technologies推出一款新的单芯片信号调节IC APDS-9702,该款IC可搭配集成的或分立的接近传感器,有效的提高了接近传感的性能,检测距离可达20mm。它内部集成了I2C写功能模块,晶振、LED驱动电路以及日光...
  • TT electronics OPTEK Technology公司近日开发出一种宽间隙的光传感器OPB856Z,在工业环境中的工作距离可达12英寸。这种非接触型器件适用于装配线和机械自动化等场合。 OPB856Z含有一个LED和一个光敏器件,为...
  • TT electronics OPTEK Technology公司近日开发出一种宽间隙的光传感器OPB856Z,在工业环境中的工作距离可达12英寸。这种非接触型器件适用于装配线和机械自动化等场合。 OPB856Z含有一个LED和一个光敏器件,为...
  • 该代码是通过C语言编程实现,主要是为了快速求解邻接矩阵对应的可达矩阵,邻接矩阵和可达矩阵是系统工程中表征系统元素之间关系的重要工具之一
  • 可达距离(rechability distance):可达距离的定义跟K-邻近距离是相关的,给定参数k时, 数据点 p 到 数据点 o 的可达距离 reach-dist(p, o)为数据点 o 的K-邻近距离 和 数据点p与点o之间的直接距离的最大值。...

    异常检测(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.

    展开全文
  • 距离RFID解决方案,车辆自动识别,通信距离高达50m
  • 然后找到 D 中 p 的所有密度直达样本点 x,计算 x 到 p 的可达距离,如果 x 不在有序队列 O 中,则将 x 以及可达距离放入 O 中,若 x 在 O 中,则如果 x 新的可达距离更小,则更新 x 的可达距离,最后对 O 中数据按...

    OPTICS聚类算法是基于密度的聚类算法,全称是Ordering points to identify the clustering structure。提到基于密度的聚类算法,应该很快会想到前面介绍的DBSCAN聚类算法,事实上,OPTICS也是为了优化DBSCAN而出现的。

    一、原理

    在DBSCAN算法中,有两个比较重要的参数:邻域半径eps和核心对象的最小邻域样本数min_samples,选择不同的参数会导致最终聚类的结果千差万别,而在高维数据中,两个参数的联合调参也不是一件容易的事。OPTICS算法的提出就是为了帮助DBSCAN算法选择合适的参数,降低输入参数的敏感度。实际上,OPTICS并不显式的生成数据聚类结果,只是对数据集中的对象进行排序,得到一个有序的对象列表,通过该有序列表,可以得到一个决策图,通过决策图可以选择不同的eps参数进行DBSCAN聚类。在继续阅读下面的内容之前,需要先了解DBSCAN的相关内容,因为本文的部分概念来自于DBSCAN。

    在DBSCAN的基础上,OPTICS定义了两个新的距离概念:

    (1)核心距离

    对于一个给定的核心对象X,使得X成为核心对象的最小邻域距离 r 就是X的核心距离。这句话乍一看有点绕,其实仔细读两遍就明白了,假如在DBSCAN中我们定义 eps = 1.2 和  min_samples=5,X在eps = 1.2的邻域内有8个样本点,则X是核心对象,但是我们发现距离X最近的第5个点和X的距离是0.8,那么核心对象 X 的核心距离就是 0.8,显然每个核心对象的核心距离并不都是相同的。参考图1,注意在计算 min_samples 的时候,一般也包括样本点自身,所以只需在P点eps邻域内找到7个点,那么P点就是核心点。

    (2)可达距离

    如果X是核心对象,则对象 Y 到对象 X 的可达距离就是Y到X的欧氏距离和X的核心距离的最大值,如果X不是核心对象,则Y和X之间的可达距离就没有意义(不存在可达距离),显然,数据集中有多少核心对象,那么 Y 就有多少个可达距离。在下文介绍 API 的时候,我们会介绍在OPTICS中,一般默认设置 eps 为无穷大,即只要数据集的样本数不少于 min_samples,那么任意一个样本点都是核心对象,即都有核心距离,且任意两个对象之间都存在可达距离。

    图1

    1.1 算法描述

    OPTICS的原理并不复杂,只不过大多数介绍资料都喜欢列举一些广义的算法流程或者伪代码,虽然满足算法介绍的严谨性,但是阅读起来不免显得晦涩难懂,没有阅读的欲望。因此,和之前的文章一样,本文也是先介绍OPTICS的标准算法流程,然后再以案例的形式介绍流程的具体执行逻辑,如果算法流程不能一下子理解的话,可以先跳过直接看后面的案例,然后再回来看标准流程。

    OPTICS算法流程:

    1. 已知数据集 D,创建两个队列,有序队列O和结果队列R(有序队列用来存储核心对象及其该核心对象的密度直达对象,并按可达距离升序排列;结果队列用来存储样本点的输出次序。可以把有序队列里面放的理解为待处理的数据,而结果队列里放的是已经处理完的数据)。
    2. 如果D中所有点都处理完毕或者不存在核心点,则算法结束。否则,选择一个未处理(即不在结果队列R中)且为核心对象的样本点 p,首先将 p 放入结果队列R中,并从D中删除 p。然后找到 D 中 p 的所有密度直达样本点 x,计算 x 到 p 的可达距离,如果 x 不在有序队列 O 中,则将 x 以及可达距离放入 O 中,若 x 在 O 中,则如果 x 新的可达距离更小,则更新 x 的可达距离,最后对 O 中数据按可达距离从小到大重新排序。
    3. 如果有序队列 O 为空,则回到步骤2,否则取出 O 中第一个样本点 y(即可达距离最小的样本点),放入 R 中,并从 D 和 O 中删除 y。如果 y 不是核心对象,则重复步骤 3(即找 O 中剩余数据可达距离最小的样本点);如果 y 是核心对象,则找到 y 在 D 中的所有密度直达样本点,并计算到 y 的可达距离,然后按照步骤2将所有 y 的密度直达样本点更新到 O 中。
    4. 重复步骤2、3,直到算法结束。最终可以得到一个有序的输出结果,以及相应的可达距离。

    已知样本数据集为:D = {[1, 2], [2, 5],  [8, 7], [3, 6],  [8, 8], [7, 3], [4,5]},为了更好地标识索引,我们以表格标识数据如下:

    图2
    表1
    索引0123456核心对象
    元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5) 
    核心距离3.161.411.01.411.03.611.41 
    第一次可达距离inf3.168.604.479.216.084.240
    第二次可达距离----6.321.416.705.382.01
    第三次可达距离----5.09--5.395.01.413
    第四次可达距离----4.47--5.03.61--6
    第五次可达距离----4.12--

    5.0

    (5.10)

    ----5
    第六次可达距离--------1.0----2
    输出顺序0152643 
    可达距离inf3.164.121.411.03.611.41 

    假设eps = inf,min_samples=2,则数据集D在OPTICS算法上的执行步骤如下:

    1. 计算所有的核心对象和核心距离,因为 eps 为无穷大,则显然每个样本点都是核心对象。因为 min_samples=2,则每个核心对象的核心距离就是离自己最近样本点到自己的距离(样本点自身也是邻域元素之一),具体如上表所示。
    2. 随机在 D 中选择一个核心对象,假设选择 0 号元素,将 0 号元素放入 R 中,并从 D 中删除。因为 eps = inf,则其他所有样本点都是 0 号元素的密度直达对象,计算其他所有元素到 0 号元素的可达距离(实际就是计算所有元素到 0 号元素的欧氏距离,如表1第一次可达距离),并按可达距离排序,添加到序列 O 中。
    3. 此时 O 中可达距离最小的元素是 1 号元素,取出 1 号元素放入 R ,并从 D 和 O 中删除,因为 1 号元素是核心对象,找到 1 号元素在 D 中的所有密度直达对象(剩余的所有样本点),并计算可达距离,同时更新 O(如表1第二次可达距离)。
    4. 此时 O 中可达距离最小的元素是 3 号元素,取出 3 号元素放入 R ,并从 D 和 O 中删除,因为 3 号元素是核心对象,找到 3 号元素在 D 中的所有密度直达对象(剩余的所有样本点),并计算可达距离,同时更新 O(如表1第三次可达距离)。
    5. 此时 O 中可达距离最小的元素是 6 号元素,取出 6 号元素放入 R ,并从 D 和 O 中删除,因为 6 号元素是核心对象,找到 6 号元素在 D 中的所有密度直达对象(剩余的所有样本点),并计算可达距离,同时更新 O(如表1第四次可达距离)。
    6. 此时 O 中可达距离最小的元素是 5 号元素,取出 5 号元素放入 R ,并从 D 和 O 中删除,因为 5 号元素是核心对象,找到 5 号元素在 D 中的所有密度直达对象(剩余的所有样本点),并计算可达距离,同时更新 O(如表1第五次可达距离)。注意本次计算的4号元素到5号元素的可达距离是5.10,大于5.0,因此不更新4号元素的可达距离。
    7. 此时 O 中可达距离最小的元素是 2 号元素,取出 2 号元素放入 R ,并从 D 和 O 中删除,因为 2 号元素是核心对象,找到 2 号元素在 D 中的所有密度直达对象(剩余的所有样本点),并计算可达距离,同时更新 O(如表1第六次可达距离)。
    8. 此时 O 中可达距离最小的元素是 4 号元素,取出 4 号元素放入 R ,并从 D 和 O 中删除,因为 D 已空,O 也已空,程序结束。根据表1,最终的结果序列 R 的元素索引输出顺序为:0、1、3、6、5、2、4,可达距离如表1最后一行所示。

    我们按照最终的输出顺序绘制可达距离图(注意,因为第一个元素没有可达距离,或者说可达距离是无穷大,故图中没有标出 0 号元素的可达距离):

    图3

    可以发现,可达距离呈现两个波谷,也即表现为两个簇,波谷越深,表示簇越紧密,只需要在两个波谷之间取一个合适的 eps 分隔值(图中蓝色的直线,例如两个可达距离的平均值),使用 DBSCAN 算法就会聚类为两个簇。即第一个簇的元素为:0、1、3、6、5;第二个簇的元素为:2、4。下面我们通过sklearn库来验证我们的结果。

    二、实践

    sklearn库同样为我们封装了 OPTICS 算法的API,供我们直接使用。

    2.1 验证

    基于1.1的数据集,使用OPTICS验证算法结果如下:

    from sklearn.cluster import OPTICS
    import numpy as np
    
    X = np.array([[1, 2], [2, 5],  [8, 7],[3, 6],  [8, 8], [7, 3], [4,5]])
    
    clustering = OPTICS(min_samples=2).fit(X)
    
    
    print(clustering.core_distances_)
    '''
    array([3.16227766, 1.41421356, 1.  , 1.41421356, 1.  ,3.60555128, 1.41421356])
    '''
    
    print(clustering.ordering_)
    '''
    array([0, 1, 3, 6, 5, 2, 4])
    '''
    
    print(clustering.reachability_)
    '''
    array([inf, 3.16227766, 4.12310563, 1.41421356, 1.        ,3.60555128, 1.41421356])
    '''
    
    print(clustering.labels_)
    '''
    array([0, 0, 1, 0, 1, 0, 0])
    '''

    根据图3,选择 eps=3.8,使用DBSCAN算法验证如下:

    import sklearn
    
    db = sklearn.cluster.DBSCAN(eps=3.8,min_samples=2).fit(X)
    db.labels_
    
    ## array([0, 0, 1, 0, 1, 0, 0])

    参考资料

    [1] https://blog.csdn.net/PRINCE2327/article/details/110412944

     

    展开全文
  • 该txt文件记录的是邻接矩阵转化成可达矩阵的源代码。
  • RIP协议和距离向量算法

    千次阅读 2020-08-06 19:31:31
    RIP(Routing Information Protocol,路由信息协议) 是一种内部网关协议(IGP),是一种动态路由选择...RIP协议基于距离矢量算法(DistanceVectorAlgorithms),使用“跳数”(即metric)来衡量到达目标地址的路由距离

    RIP(Routing Information Protocol,路由信息协议) 是一种内部网关协议(IGP),是一种动态路由选择协议,用于自治系统(AS)内的路由信息的传递。RIP协议基于距离矢量算法(DistanceVectorAlgorithms),使用“跳数”(即metric)来衡量到达目标地址的路由距离。

    简介

    RIP进程使用UDP的520端口来发送和接收RIP分组。RIP仅和相邻的路由器交换信息,交换信息指的是自己知道的全部信息即路由表。RIP分组每隔30s以广播的形式发送一次(当网络拓扑结构发生变化时,路由器会及时向相邻路由器通告拓扑结构变化后的情况),为了防止出现“广播风暴”,其后续的分组将做随机延时后发送。在RIP中,如果一个路由在180s内未被刷新,则相应的距离就被设定成无穷大(不可达),并从路由表中删除该表项。RIP分组分为两种:请求分组和响应分组。

    报文格式
    在这里插入图片描述
    一个RIP最多可以包括25个路由,因此RIP报文最大长度是4+20*25=504字节,当使用鉴别功能的时候,将原来写入第一个路由信息的位置用作鉴别



    距离向量算法

    1.距离(跳数)问题

    (1)从一个路由器到直接连接的路由器距离定义为1
    (2)从一个路由器到另一个非直接相连的路由器距离定义为所经过路由器的个数加一
    (3)距离也就是跳数,每经过一个路由器跳数就加一
    (4)RIP协议认为好的路由就是经过的路由器最少,距离最短(跳数最少)。而且不能在两个网络之间同时使用多条路由,也就是说哪怕还有一条高速(低时延)但路由器较多的路由,RIP也会选择路由器最少的路由。
    (5)因为RIP规定经过的路由器不能超过15个,距离超过16时认为不可达,所以RIP只适用于小型互联网

    2.路由表的建立

    路由器一开始工作的时候只知道相邻路由器的距离(定义为1),路由表为空,之后和相邻的路由器交换并更新路由信息,经过若干次更新后本自制网络中的所有路由器便都会知道任何一个网络的最短距离和下一跳路由器的地址。虽然路由器都拥有了整个自治系统的全局路由信息,但由于路由器位置不同所以他们的路由表自然也不同

    3.路由表更新
    在这里插入图片描述

    假设路由器R6有路由表如图2,现收到R4发来的路由更新信息如图1
    (1)R6先修改收到的路由表的信息:把下一跳路由器都改成R4,并把所有距离字段都加一

    如下图在这里插入图片描述

    (2)对修改后路由表的每一项数据重复以下步骤:
    若目的网络不在自己路由表中则把该项目加到自己(R6)路由表中,
         否则(目的网络在自己(R6)的路由表中)
    若下一跳字段给出的路由器地址是同样的,则用该项目替换自己(R6)路由表中的信息
        否则(目的网络在自己(R6)的路由表中但是路由地址不一样)
    若收到项目中距离小于自己路由表中距离,则用该项目替换自己(R6)路由表中的信息
        否则(目的网络在自己(R6)的路由表中但是路由地址不一样且距离大)
    什么也不做。

    如下图在这里插入图片描述
    所以最终R6更新后的路由表为
    在这里插入图片描述
    好事传的慢,坏事传的快

    正常情况下:
    在这里插入图片描述
    当网1出现故障时:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    所以当网络发生故障时,要经过较长时间(几分钟)才能将此信息传送到所有路由器,也就是慢收敛

    展开全文
  • I . K-Means 算法在实际应用中的缺陷 II . K-Means 初始中心点选择不恰当 III . K-Means 优点 与 弊端 IV . 基于密度的聚类方法 V . 基于密度的聚类方法 ...VI ....VII ....VIII . 直接密度可达 IX . 密度可达 X . 密度连接
  • 因此 p 的 第 k 邻域点的个数 |Nk(p)| >=k (4) reach-distance:可达距离 可达距离(Reachablity distance):可达距离的定义跟K-邻近距离是相关的,给定参数k时,数据点 p 到 数据点o的可达距离 reach-dist(p, o...
  • 而离群点则是距离正常数据点最近邻的点都比较远的数据点。通常有阈值进行界定距离的远近。在基于密度的离群点检测方法中,最具有代表性的方法是局部离群因子检测方法 (Local Outlier Factor, LOF)。 3LOF算法简介 ...
  • 【机器学习】密度聚类算法之OPTICS

    千次阅读 2019-06-04 16:32:18
    ,用小的可达距离代替大的可达距离。 第二步:输出标签(预测) 按照结果队列的输出顺序,变量整个样本集。 如果当前样本的可达距离不大于给定半径 ϵ ϵ ϵ ,则该点属于当前类别 如果当前样本的...
  • 局部异常因子算法-Local Outlier Factor(LOF) 在数据挖掘方面,经常需要在做特征工程和模型训练之前对数据进行清洗,剔除无效数据和异常数据。异常检测也是数据挖掘的一个方向,用于反作弊、伪...基于距离的方法,适...
  • OPTICS聚类算法详解

    2021-03-20 00:51:12
    不断迭代第二步和第三步,直到所有样本点都处理完毕,然后输出结果队列中的样本点及其可达距离 处理完毕之后,根据样本的输出顺序和可达距离,可以绘制如下所示的柱状图,其中不同的峰谷对应不同不同的cluster, ...
  • 有向图中两点是否可达

    千次阅读 2016-08-09 12:39:20
    图结构练习——BFSDFS——判断可达性 Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^ 题目描述 在古老的魔兽传说中,有两个军团,一个叫天灾,一个叫近卫。在他们所在的地域,有n个隘口,编号为1..n,...
  • python计算可达矩阵 从别人那里看到的,原代码貌似有些问题,修改了一下 matrix = [[0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0, 0], .....
  • 用LM386制作半双工对讲机 通话距离 可达2KM
  • (local rechability density):局部可达密度的定义是基于可达距离的,对于数据点 p,那些跟点p的距离小于等于 k-distance(p)的数据点称为它的 k-nearest-neighbor,记为 $N_k(p)$,数据点 p 的局部可达密度为它...
  • RIP协议相关知识总结

    千次阅读 2020-05-17 21:31:06
    文章目录问题引入知识点自治系统RIP距离向量路由选择算法RIP中的信息交换RIP的优缺点收敛问题解答参考资料 问题引入 我们首先引入一个问题,学习完以下相关知识点后可以试着解答这个问题: 请解释RIP协议为什么会有...
  • ZETA SDR网关推动LPWAN2.0泛在物联,覆盖距离可达30km 据悉,纵行科技已推出ZETA SDR网关,为现有LPWAN市场带来了重大革新。该网关采用内置Advanced M-FSK调制方法,解决了目前市场上LPWAN通信速率低、难以覆盖及...
  • A*寻路算法之解决目标点不可达问题

    千次阅读 2018-09-24 13:31:59
    那么,有没有办法来改进一下这种不友好的体验呢? 下面给出两种方法: ...最近可达点替代:当目标点S不可达时,在S点周围寻找一个最近的可达点R,让R替代S作为目标点寻路。 最近点检测法:设置一个最小距...
  • 算法:基于密度的局部离群点检测(lof算法) 输入:样本集合D,正整数K(用于计算第K距离) ...3, 计算每个对象的可达密度 4, 计算每个对象的局部离群点因子 5, 对每个点的局部离群点因子进行排序,输出。
  • 注:也许在不久的将来,传感器中直接内嵌蓝牙或其它通讯方式,仅在有无线信号覆盖的地方,才会被激活加电,或者通过无线信号...高通推近距离位置定位技术,精度可达0.3米左右 时间:2013-12-12 来源:电子工程网 
  • 我的预判断就是Server1到Host1是路由可达的,但是Host1到Server1却不可达,得出这样的判断是基于以下的事实:Server1处在大运营商的机房,而Host1则是一个任意位置的测试客户端,就比如像国内基调这样的......
  •  对于低倍物镜,工作距离一般不成问题,倍数稍高时,采用反远距型物镜满足工作距离的要求,但对高倍物镜用反远距型物镜仍不到要求,且这时共轭距由于工作距变长而大得无法实现。采用图1所示的结构能很好地解决...
  • 详解遗传算法(含MATLAB代码)

    万次阅读 多人点赞 2019-05-29 11:30:47
     传统的优化算法往往使用确定性的搜索方法,一个搜索点到另一个搜索点的转移有确定的转移方向和转移关系,这种确定性可能使得搜索不到最优店,限制了算法的应用范围。  遗传算法是一种自适应搜索技术,其选择...
  • CAN总线原理简介

    万次阅读 多人点赞 2019-09-23 16:43:11
    CAN总线上的节点数可达110个。通信介质可在双绞线,同轴电缆,光纤中选择 报文是短帧结构,短的传送时间使其受干扰概率低,CAN有很好的校验机制,这些都保证了 CAN通信的可靠性: (1)具有实时性强、传输...
  • matlab人脸识别论文

    万次阅读 多人点赞 2019-10-11 17:41:51
    得到了前所未有的重视,国际上发表有关人脸识别等方面的论文数量大幅度增加,仅从1990年到2000年之间,sCl 及EI检索到的相关文献多达数千篇,这期间关于人脸识别的综述也屡屡可见。国外有许多学校在研究人脸识别...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 65,041
精华内容 26,016
关键字:

可达距离