① MapRece之金庸的江湖人物分析项目
通过一个综合数据分析案例：”金庸的江湖——金庸武侠小说中的人物关系挖掘“，来学习和掌握MapRece程序设计。通过本项目的学习，可以体会如何使用MapRece完成一个综合性的数据挖掘任务，包括全流程的数据预处理、数据分析、数据后处理等。
1 任务1 数据预处理
1.1 任务描述
从原始的金庸小说文本中，抽取出与人物互动相关的数据，而屏蔽掉与人物关系无关的文本内容，为后面的基于人物共现的分析做准备。
1.2 关键问题
1.2.1 中文分词和人名提取
使用开源的Ansj_seg进行分词。Ansj_seg不仅支持中文分词，还允许用户自定义词典，在分词前，将人名列表到添加用户自定义的词典，可以精确识别金庸武侠小说中的人名。
但实际测试的时候发现，Ansj_seg分词会出现严重的歧义问题，比如“汉子”属于人名列表中的人名(nr)，但Ansj_seg可能会错误地将它分类为名词(n)。因此，如果根据词性提取人名，会导致最后提取的人名太少。解决方法是在提取人名的时候，需要在将人名加入用户自定义词典的同时，构造一个包含所有人名的字典，对分词的结果逐个进行测试，如果在字典里，就是人名。
1.2.2 文件传输
使用HDFS传递数据。考虑到人名列表文件已经存放在了HDFS里，所以使用HDFS的方式不需要移动人名列表文件，只需要在Configuration中设置文件在HDFS文件系统中的路径，然后在Mapper的setup()函数里调用HDFS的函数获取文件内容即可。
1.2.3 单词同现算法
两个单词近邻关系的定义：实验要求中已经说明，同现关系为一个段落。
段落划分：非常庆幸的是，小说原文中一个段落就是一行，因此，不需要自己定义FileInputFormat和RecordReader。
1.3 MapRece设计
1.3.1 Mapper
1.3.2 Recer
1.3.3 Driver
2 任务2 特征抽取：人物同现统计
2.1 任务描述
完成基于单词同现算法的人物同现统计。在人物同现分析中，如果两个人在原文的同一段落中出现，则认为两个人发生了一次同现关系。我们需要对人物之间的同现关系次数进行统计，同现关系次数越多，则说明两人的关系越密切。
2.2 关键问题
2.2.1 人名冗余
在同一段中，人名可能多次出现，任务一只负责提取出所有的人名，没有剔除多余的人名，任务必须在输出同现次数之前处理冗余人名。我的做法是在Mapper中创建一个集合，把所有人名放入集合中，集合会自动剔除冗余的人名。
2.2.2 同现次数统计
两个人物之间应该输出两个键值对，如“狄云”和“戚芳”，应该输出“<狄云，戚芳> 1”和“<戚芳，狄云> 1”。多个段落中允许输出相同的键值对，因此，Recer中需要整合具有相同键的输出，输出总的同现次数。
2.3 MapRece设计
2.3.1 Mapper
2.3.2 Recer
3 任务3 特征处理：人物关系图构建与特征归一化
3.1 任务描述
根据任务2人物之间的共现关系，生成人物之间的关系图。人物关系使用邻接表的形式表示，人物是顶点，人物之间关系是边，两个人的关系的密切程度由共现次数体现，共现次数越高，边权重越高。另外需要对共现次数进行归一化处理，确保某个顶点的出边权重和为1。
3.2 关键问题
3.2.1 确保人物的所有邻居输出到相同结点处理
在Mapper结点将输入的键值对“<狄云，戚芳> 1”拆分，输出新的键值对“<狄云> 戚芳:1”，“狄云”的所有邻居会被分配给同一个Recer结点处理。
3.2.2 归一化
在Recer结点首先统计该人物与所有邻居同现的次数和sum，每个邻居的的同现次数除以sum就得到共现概率。为了提高效率，在第一次遍历邻居的时候，可以把名字和共现次数保存在链表里，避免重复处理字符串。
3.3 MapRece设计
3.3.1 Mapper
3.3.2 Recer
4.1 任务描述
经过数据预处理并获得任务的关系图之后，就可以对人物关系图作数据分析，其中一个典型的分析任务是：PageRank 值计算。通过计算 PageRank，我们就可以定量地获知金庸武侠江湖中的“主角”们是哪些。
4.2 PageRank原理
PageRank算法由Google的两位创始人佩奇和布林在研究网页排序问题时提出，其核心思想是：如果一个网页被很多其它网页链接到，说明这个网页很重要，它的PageRank值也会相应较高；如果一个PageRank值很高的网页链接到另外某个网页，那么那个网页的PageRank值也会相应地提高。
相应地，PageRank算法应用到人物关系图上可以这么理解：如果一个人物与多个人物存在关系连接，说明这个人物是重要的，其PageRank值响应也会较高；如果一个PageRank值很高的人物与另外一个人物之间有关系连接，那么那个人物的PageRank值也会相应地提高。一个人物的PageRank值越高，他就越可能是小说中的主角。
PageRank有两个比较常用的模型：简单模型和随机浏览模型。由于本次设计考虑的是人物关系而不是网页跳转，因此简单模型比较合适。简单模型的计算公式如下，其中Bi为所有连接到人物i的集合，Lj为认为人物j对外连接边的总数：
在本次设计的任务3中，已经对每个人物的边权值进行归一化处理，边的权值可以看做是对应连接的人物占总边数的比例。设表示人物i在人物j所有边中所占的权重，则PageRank计算公式可以改写为：
4.3.2 PageRanklter类
GraphBuilder将数据处理成可供迭代的格式，PageRank的迭代过程由PageRanklter类实现，包含一个Map和Rece过程。Map过程产生两种类型的<key,value>：<人物名，PageRrank值>，<人物名，关系链表>。第一个人物名是关系链表中的各个链出人物名，其PR值由计算得到；第二个人物名是本身人物名，目的是为了保存该人物的链出关系，以保证完成迭代过程。以上面的输出为例，则Map过程产生的键值对为<完颜萍, 1.0 0.005037>，<小龙女, 1.0 0.017632>，……，<一灯大师, #完颜萍:0.005037783;……>。
Rece过程将同一人物名的<key,value>汇聚在一起，如果value是PR值，则累加到sum变量；如果value是关系链表则保存为List。遍历完迭代器里所有的元素后输出键值对<人物名，sum#List>，这样就完成了一次迭代过程。
PR值排名不变的比例随迭代次数变化的关系图如下，由于我们考虑的是找出小说中的主角，所以只要关心PR值前100名的人物的排名的变化情况，可以看到迭代次数在10以后，PR值排名不变的比例已经趋于稳定了，所以基于效率考虑，选取10作为PR的迭代次数。
4.3.3 PageRankViewer类
当所有迭代都完成后，我们就可以对所有人物的PageRank值进行排序，该过程由PageRankViewer类完成，包含一个Map和Rece过程。Map过程只提取迭代过程输出结果中的人物名以及对应的PageRank值，并以PageRank值作为key，人物名作为value输出。为了实现PageRank值从大到小排序，需要实现DescFloatComparator类来重写compare方法以达成逆序排序。由于可能存在PageRank值相同的情况，所以还需要一个rece过程来把因PageRank值相同而汇聚到一起的人物名拆开并输出。
PageRankMapper
PageRankRecer
Driver类
5.1 任务描述
标签传播（Label Propagation）是一种半监督的图分析算法，他能为图上的顶点打标签，进行图顶点的聚类分析，从而在一张类似社交网络图中完成社区发现。在人物关系图中，通过标签传播算法可以将关联度比较大的人物分到同一标签，可以直观地分析人物间的关系。
5.2 标签传播算法原理
标签传播算法（Label Propagation Algorithm，后面简称LPA）是由Zhu等人于2002年提出，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。LPA基本过程为：（1）每个结点初始化一个特定的标签值；（2）逐轮更新所有节点的标签，直到所有节点的标签不再发生变化为止。对于每一轮刷新，节点标签的刷新规则如下：对于某一个节点，考察其所有邻居节点的标签，并进行统计，将出现个数最多的那个标签赋值给当前节点。当个数最多的标签不唯一时，随机选择一个标签赋值给当前节点。
LPA与PageRank算法相似，同样需要通过迭代过程来完成。在标签传播算法中，节点的标签更新通常有同步更新和异步更新两种方法。同步更新是指，节点x在t时刻的更新是基于邻接节点在t-1时刻的标签。异步更新是指，节点x在t时刻更新时，其部分邻接节点是t时刻更新的标签，还有部分的邻接节点是t-1时刻更新的标签。若LPA算法在标签传播过程中采用的是同步更新，则在二分结构网络中，容易出现标签震荡的现象。在本次设计中，我们考虑到了两种更新方法，并进行了比较。
5.3 标签传播算法在maprece上的实现细节
5.3.1 LPAInit类
为实现LPA的迭代过程，需要先给每个人物赋予一个独特标签，标签初始化由LPAInit类完成，仅包含一个Map过程。标签由数字表示，Map过程由1开始，为每一个人物名赋予一个独特的标签。为了便于后面的可视化分析，我们需要把PageRank值和标签整合在一起，所以LPAInit的输入文件直接采用PageRank过程的输出文件，格式如下：
5.3.2 LPAIteration类
LPAIteration类完成标签的更新过程，其格式与LPAInit的输出格式一致，包含一个Map和Rece过程。Map过程对输入的每一行进行切割，输出四种格式的<key,value>：<人物名，关系链表>，<人物名，PageRank值>，<人物名，标签>，<链出人物名，标签#起点人物名>。第四种格式个键值对是为了将该节点的标签传给其所有邻居。
Rece过程对value值进行识别，识别可以通过Map过程把预先定义好的特殊字符如‘#’、‘@’来实现前缀到value上来实现。由于人物关系图中的各个边都是有权重的，并且代表两个人物的相关程度，所以标签更新过程不是用边数最多的标签而是权重最大标签来更新，我们可以预先把权重最大的若干个保存到一个链表中，如果存在多个权重相同的标签，则随机选取一个作为该人名新的标签。异步方法更新标签需要使用一个哈希表来存储已经更新标签的人物名和它们的新标签，并且在更新标签时使用该哈希表里面的标签。同步方法更新标签则不需要存储已更新的标签。
本次设计中比较了同步和异步更新两种方法，下图为标签不变的比例随迭代次数的变化。可以发现，异步收敛速度更快，只要6次迭代即可完全收敛，且标签不变的比例可达100%。而同步更新方法则不能达到100%，说明人物关系图中存在子图是二部子图。
5.3.3 LPAReorganize类
LPA算法迭代收敛后，所有人物名的标签不再变化，但是此时的标签排列是散乱的，需要把同一标签的人物名整合在一起。该过程由LPAReorganize类完成，包含一个Map和Rece过程。Map过程对输入的每一行进行切割，以<标签，人物名#PageRank值#关系链表>格式输出。Rece过程中，同一标签的人物名汇聚在一起，然后根据每个标签人物集合的大小从大到小排序，重新赋予标签（从1开始）。这样输出文件中同一标签的人物名就会聚集在一起。最后的输出格式如下：
5.3.2 LPAMapper类
LPAIteration类完成标签的更新过程，其格式与LPAInit的输出格式一致，包含一个Map和Rece过程。Map过程对输入的每一行进行切割，输出四种格式的<key,value>：<人物名，关系链表>，<人物名，PageRank值>，<人物名，标签>，<链出人物名，标签#起点人物名>。第四种格式个键值对是为了将该节点的标签传给其所有邻居。
5.3.2 LPARecer类
Rece过程对value值进行识别，识别可以通过Map过程把预先定义好的特殊字符如‘#’、‘@’来实现前缀到value上来实现。由于人物关系图中的各个边都是有权重的，并且代表两个人物的相关程度，所以标签更新过程不是用边数最多的标签而是权重最大标签来更新，我们可以预先把权重最大的若干个保存到一个链表中，如果存在多个权重相同的标签，则随机选取一个作为该人名新的标签。异步方法更新标签需要使用一个哈希表来存储已经更新标签的人物名和它们的新标签，并且在更新标签时使用该哈希表里面的标签。同步方法更新标签则不需要存储已更新的标签。
Driver类
6.1 可视化工具Gephi
Gephi是一款开源的跨平台的基于JVM的复杂网络分析软件。把PageRank和LPA的结果，转化为gexf格式，在Gephi中绘制图像并分析大数据实验结果，更加直观、易于理解。
gexf实际上是一种特殊的XML文件，python的gexf库提供了接口方便我们编辑和生成gexf文件，因此我们选择使用python处理PageRank和LPA的结果。顶点有两种属性，LPA生成的标签和PageRank计算的PR值，每条边的权重是PageRank计算出的值。在可视化的时候，标签决定顶点显示的颜色，PR值决定标签的
6.2 可视化预处理
编写一个python程序transform2xml.py，将数据分析部分得到的PR值，标签以及点连接关系处理成一个可供Gephi读取的gexf文件。
6.3 可视化结果
7 输出结果截图
7.2 同现次数统计
7.4 PageRank
② 综述：广义的分布外检测（异常检测、开集识别、OOD检测）
Generalized Out-of-Distribution Detection: A Survey Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu https://github.com/Jingkang50/OODSurvey
分布外（Out-Of-Distribution，OOD）检测对确保机器学习系统的可靠性和安全性至关重要。例如，在自动驾驶中，当遇到它从未见过、无法给出安全决策的非常规情形或物体，我们需要驾驶系统发出警告并且将控制权交给人类。自2017年被提出起，这个问题越来越受研究者关注，各种解决方案层出不穷，大致包括：基于分类的、基于密度的、基于重构的、基于距离的方法。与此同时，其他几个问题在动机和方法上与分布外检测紧密相关，这些问题包括：异常检测（Anomaly Detection，AD）、新类检测（Novelty Detection）、开集识别（Open Set Recognition，OSR）和离群检测（Outlier Detection，OD）。尽管他们各自定义和问题设定不同，这些问题经常使读者和实践者感到困惑，这导致有些现有工作误用了这些术语。实际上，AD、ND、OSR、OOD、OD这五个问题能够统一在广义的分布外检测框架下，都可以视作分布外检测的特例或子任务，并且能够轻易地被区分。这篇综述通过总结最新的技术发展对这五个问题做了深入的回顾，并以该领域的开放挑战和潜在的研究方向作结。
可信的视觉识别系统不仅仅在已知的情境下能给出精确预测，还应该能检测到未知的样本并且丢弃或将它们交给用户来做安全地处理。
比如，一个训练良好的食物分类器应该丢弃像用户自拍照之类的非食物图片，而不是胡乱判定其属于某已知的食物类别。在安全要求极高的应用中，比如无人驾驶，系统应该在它碰到不寻常的、未在训练中见到的情形或物体时发出警告并将控制权交给司机。
大多数现有机器学习模型都基于封闭世界假设（the closed-world assumption）来训练，即测试集和训练集独立同分布，或者说两者来源于同一分布（in-distribution）。然而，当模型被部署在开放世界场景（open-world scenario）中，测试样本的分布可以是取自不同于训练集分布的分布的（out of distribution），因而需要被谨慎处理。分布的变化可能是语义漂移（比如，OOD样本取自别的类别）、协变量漂移（也称输入漂移，比如OOD样本取自其他领域？？）。
只考虑语义漂移和协变量漂移两类漂移。
异常检测目的在于在测试阶段检测异常的样本，“异常”指的是偏离预定义的“正常”。这种偏离可能是协变量漂移或是语义漂移导致的。异常检测可以分为两个子任务：
与异常检测的区别 ：1） 动机上，新类检测中并不像异常检测把没见过的“新”样本看做错误的或是有害的，而是将珍视这些新样本为后续模型的学习资源；2）新类检测首要关注的是语义漂移；3）新类检测中，没有限制ID样本属于单个类，在训练集中可以有多个类别的样本。
新类检测目的在于检测出不属于任何训练类别的测试样本。检测到的新奇样本通常预备用于未来程序的构建，比如特异性更强的分析、当前模型的增量学习等。依据训练类别数量的差异，新类检测分为：
OSR需要一个多类别分类器来同时1）精确地分类 训练类别的 测试样本（ID）；2）识别出测试样本中 不属于训练类别 的样本（OOD）。
OSR = multi-class ND
需要模型拒绝标签迁移的样本以保证预测可靠性和安全性
分布外检测目的在于检测测试样本
当某个样本显着区别于其他的样本时，认为它是“离群”的。在异常检测、新类检测、开集识别、分布外检测的问题设定中，都存在这训练-测试的流程，要挑出测试中出现的不属于训练分布的样本。
而离群检测无“训练分布”、“测试分布”，而是直接挑出所有可见样本中显着区别于其他的那些样本。
给定同构的ID数据，最直接的方法是1）基于密度的方法，这些方法估计ID的密度，拒绝那些偏离估计的OOD的测试样本。其他的方法包括：2）依靠图片重构的质量来识别异常样本，3）直接学习一个决策边界来区分ID和OOD样本，4）基于距离的方法，5）基于元学习的方法
基于密度的方法尝试去建模正常数据（ID数据）的分布，这种做法基于一个实践假设：异常的测试样本在估计的密度模型下游较低的概率值，而正常样本概率值较高。
参数密度估计假设ID样本的密度能够被表示为某种定义好的分布。一种方法是在训练数据上拟合一个多变量高斯分布，并且度量测试样本与训练样本的期望之间的马氏距离（协方差距离，计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系）。其他的工作采用了更复杂的假设，认为训练分布是混合的高斯分布或是泊松分布等。
非参数密度估计考虑了更贴合实际的情形：预定义的分布不能够建模真实分布。可以简单地用直方图对训练分布进行建模。核密度估计（KDE）进一步使用核函数作为离散直方图的连续替代版，它可以灵活地使用点权重和带宽去控制估计的分布。
虽然经典的密度估计方法在很多任务上获得了很好的AD性能，但它们更适合低维任务。
对于计算机视觉任务中的高维数据，这些方法的计算性和可伸缩性受到影响。为缓解维数灾难，有些方法通过特征工程降维[277]，[278]。
通过由潜在嵌入重建出输入，自编码器能学到无标签数据的高效表达。变分自编码器将输入的图片编码为服从高斯分布的潜在向量。习得的潜在嵌入可被视为输入的低维表示。传统密度估计方法可以应用在这些深度表示之上。
生成对抗网络由一个生成网络和一个判别网络构成，两者在零和博弈中相互竞争。典型地，生成网络学习从潜在空间到所研究数据分布的映射，而判别网络试图分辨生成器生成的数据和真实数据。然而，不同于基于自编码器/变分自编码器的范式，少了一个编码器使得GAN难以直接为一张输入图片找到相应的嵌入。针对这个问题，ADGAN [90] 对一个给定的样本，在潜在空间搜索一个好的表示。如果找不到这样的表示，这个样本被认为是异常的。该方法计算代价极高。
规范化的流描述了一个概率分布经过一系列可逆映射的转化过程。通过重复施加变量变化的规则，初始的密度“流”过了一系列可逆映射。因此，使用规范化的流的方法能够直接估计输入空间的可能性。基于流的方法有优雅的数学表示，但是它们同样仅对低维特征敏感。若不进行降维，基于流的方法计算代价高。
除通过生成式模型获取可视化嵌入外，一些方法主要通过扩充模型容量来增加提取到的特征的表示能力，这或许可以让正常（ID）能被更精确地特征化为密度估计。这些策略包括数据增强，对抗训练，蒸馏，损失函数增强，使用浅表/局部特征。
基于能量的方法使用一个标量能量评分来表述变量概率密度，这个标量采用非标准化的负对数概率，
然而，和标准的深度学习模型相比，训练基于能量的方法代价昂贵，因为马尔可夫链蒙特卡罗法（MCMC，在概率空间，通过随机采样估算兴趣参数的后验分布）采样和估计需要积分运算。
为解决这个难题，研究者提出了评分匹配方法和随机梯度之类的方法来支持高效训练。
现有工作也探索了使用频域分析方法做异常检测。人类通过图片的低频信息来理解图片，而CNN更多依赖高频信息来做决策。人们提出了CNN核平滑和谱引导的数据增强之类的方法去抑制高频分量的影响。还有一些工作发现，对低频分量的对抗攻击也很难被检测到，因此提出
基于频率的方法专注于感官异常检测（尤其是检测对抗样本），或许不适用于语义异常检测。
基于重构的方法的核心在于在ID数据上训练得到的编解码器（encoder-decoder）框架通常对ID和OOD样本返回不同的效果。
模型表现的差异可以被用作异常检测的指标。模型表现的差异可以用特征空间的差异或是重构误差来度量。
系数重构假定每个正常样本都能被有限个基础函数精确重构，而异常数据的重构开销则更大，因此生成了稠密表示。稀疏表示的典型技巧包括基于L1正则的核PCA和低阶嵌入网络。
重构误差方法依赖于以下假设：在正常数据上训练得到的重构模型在输入为正常测试样本时会输出更高质量的结果。深度重构模型（包括自编码器AE、变分自编码器VAE、生成对抗网络GAN和U-Net等）都能够被用作这类方法的backbone。
除去这种结合AE/VAE和重构误差这种标准做法，其他方法使用了更加精细的策略，比如通过memorized normality重构，调整模型架构、部分/有条件的重构。
在半监督设定下的异常检测中，CoRA分别在ID样本和OOD样本上训练，得到两个自编码器。这两个自编码器的重构误差被用作异常检测的指标。
GAN中的判别器本质上是 通过计算重构误差 实现异常检测。更进一步，GAN的变种，比如去噪声的GAN和类别-条件GAN通过 增加重构难度 获得了更好的性能。有些方法 利用重构图片在下游任务中的表现来进一步放大异常样本的重构误差 。集成也能够优化模型性能。
异常检测、单类别的新类检测通常被形式化为无监督学习问题，将所有的ID样本看做一类。
【283】做了完全有监督的异常检测
半监督的异常检测中，模型训练时用到了无标签数据。
PU学习针对这个问题被提出
自监督方法3.3.3
单个类别分类直接学到一个决策边界
未完成
共性：ID样本的类别（训练类别）为多个。
差异：开集识别还需要精确地给ID样本分类，而新类检测只需得到区分ID/OOD的二分类器。
由于开集识别和多类别新类检测的训练类别为多个，大多数方法都是基于分类的。其余方法包括基于ID原型的以及基于重构的。极少数模型是基于密度的。
为了解决
开集识别和多类新类检测都关注ID样本包含多个类别的情形。分类问题中，一般采用独热编码来编码类别信息。然而，独热编码忽略了类别间的内在联系。举例来说，“狗”-“猫”，“狗”-“车”之间有相同的距离显然不合情理。有些工作考虑这一点，尝试利用新类的标签空间上的信息来解决这个新类检测问题。重分配大的语义空间，形成已知类别的层次化分类
基于标签组织重设，自上而下的分类策略和分组softmax训练被证实有效。应一组工作使用词向量嵌入来自动地构建标签空间。【169】中稀疏独热标签被几组产生自不同NLP模型的稠密词向量替代，形成了多个回归头来做鲁棒的训练。
测试时，标签（同所有不同头给出的嵌入向量距离最小的标签被作为预测结果输出，
如果这个最小距离超出阈值，这个样本被分类为“新”。近期工作进一步采用语言-图片预训练模型输出的特征来更好地检测新类，图片编码空间中也包含来自标签空间的丰富特征。）
基于距离的开集识别方法需要“原型”来实现class-conditional。维持ID样本的分类性能。
基于类别的聚类和原型（prototyping）操作在分类器提取到的视觉特征上进行。
OOD样本能够通过计算样本与聚类之间的距离而被识别。
有些方法还引入了对比学习来为已知类别学到更加紧密的聚类，从而拉远ID和OOD样本之间的距离。
CROSR【177】通过拼接分类器和用于距离计算的重构模型给出的可视化嵌入来在拓展的特征空间中得到强化的特征。除了使用分类器给出的特征，GMVAE【178】使用重构VAE来提取特征，将训练集的嵌入建模为一个多中心的混合高斯分布以便后续基于距离的操作。使用最近邻的分类器也适用于开集识别问题。通过存储训练样本，最近邻距离比值被用于在测试中识别未知样本。
基于重构的方法希望ID和OOD样本被重构时表现不同。这种差异能够在潜在特征空间或重构图片的像素空间中被捕捉到。
通过将已知类别的图片转化为稀疏表示，开集样本由于相对稠密能被识别出。用于稀疏编码的技巧包括：疏密指数（sparsity concentration index）【180】和核虚空间方法（kernel null space method）【181，182】。
通过固定在ID样本训练得到的多分类视觉编码器来维持在ID样本上的分类性能，C2AE训练一个以表情按向量为条件的解码器，使用极值理论估计重构后的图片来区分未知类别。后续的工作使用条件高斯分布，使得不同潜在特征逼近类内（class-wise）高斯模型，以达到在分类已知类别样本的同时能拒绝未知类别样本。其他方法生成反事实（counterfactual）图片来帮助模型更关注语义。对抗防御【186】也以这种思路去增强模型鲁棒性。
后处理检测的方法优点在于无需修改训练程序和目标就可以轻易应用。这一点对现实生产环境中的OOD检测方法很重要。早期的ODIN是一个使用temperature scaling和输入扰动来放大ID/OOD差别的后处理方法。该方法中，一个足够大的temperature有很强的平滑作用，能够将softmax值转换到logit空间（），从而有效区分ID和OOD样本。注意这种方式与信心校准不同，它采用了更温和的T
而校准更关注表达ID样本真实的正确概率
ODIN的评分最大化了ID和OOD样本之间的差异，可能从预测信心的角度看不再有意义。
基于这个见解，近期【189】提出使用能量分值来做OOD检测，该方法不需要超参数并且性能与ODIN相当甚至更好。能量函数将logit输出通过便捷的 logsumexp 运算符映射为标量。能量值相对低的测试样本被认为是ID的，反之为OOD。
【55】进一步提出了联合能量值（JointEnergy score）
为OOD检测定制的基于信心的方法能够通过设计信心估计分支和类别数据增强（结合leaving-out留一策略、对抗训练、更强的数据增强、不确定性建模、利用理想深度的特征）来实现。
特别地，为了增强对协变量偏移的敏感性，一些方法关注神经网络中间层的隐藏表示。泛化的ODIN通过使用DeConf-C作为训练目标来扩展ODIN，选择ID数据上的扰动尺度作为超参。
由于ODIN需要模型训练过程，它未被归类到后处理方法。
为了得到质量更优的隐藏层特征以便进行密度估计，分层的 Mahalanobis距离、 Gram Matrix等技巧被引入。
OOD检测的另一分支利用收集到的OOD样本集（离群样本集），在训练中帮助模型学到ID和OOD的差异。
总的来说，采用离群点暴露的OOD检测能达到明显更优的性能。然而，其性能受给定OOD样本和真实OOD样本间相关性强弱影响明显，如何将OOD由已经暴露的OOD泛化到更广泛的OOD还需进一步探索。
离群点暴露方法依赖于OOD训练数据可获取这一强假设，该条件在实际可能不成立。在OOD数据不可获取时，一些方法尝试去合成OOD样本从而让ID和OOD可区分。现有工作利用GAN来生成OOD训练样本并使模型输出均匀（uniform 正态？？？）的预测，从而在低密度区域生成边界样本，或者类似地，生成高置信度的OOD样本。
现有的OOD检测方法主要依赖输出或特征空间来给出OOD评分，而忽视了梯度空间的信息。ODIN【188】首次探索了使用梯度信息检测OOD。ODIN使用经过预处理的输入，其预处理为施加由输入梯度得来的细微扰动。ODIN扰动的目标在于增强模型对预测标签的信心从而增加任何给定输入的softmax值。最终，可以找到能使ID和OOD输入的softmax评分差异更大的扰动，从而使得它们更能被区分，使得OOD检测性能更好。ODIN仅隐式地通过扰动来利用梯度。GradNorm则使用梯度向量的范数，从softmax输出和正态概率分布的KL散度反向传播。
贝叶斯模型是一类统计模型，应用贝叶斯法则来推测模型中所有的不确定性。其中，最有代表性的是贝叶斯神经网络，该方法通过马尔可夫链蒙特卡洛方法、拉普拉斯方法、变分推断来构成模型的认知不确定性，从模型的后验分布中采样。它们最明显的缺陷在于预测不精确，计算代价高使得它们难以用于实际。近期工作尝试了几种less principled（理论性较弱??）的近似，包括 MC-dropout [224] 和深度融合 [225]，299] 用于更快、更好地估计不确定性。这些方法在OOD不确定性估计上不太有竞争力。更进一步的探索需要在保留贝叶斯原理的优势的同时，采用自然梯度变分推理，从而能够采用实用且可负担的现代深度学习训练。狄利克雷先验网络Dirichlet Prior Network (DPN) 也在OOD检测中被运用，使用对模型不确定性、数据不确定性以及分布不确定性三个不同来源的不确定性进行不确定性建模，出现了一系列工作 [227], [228], [229]。
近期工作推进了更贴近实际应用的大规模OOD检测。研究的两个方向是：将OOD检测扩展到大的语义空间、利用大型的预训练模型。例如，【168】指出，在基于CIFAR benchmark数据得到的方法在语义空间更大的benchmark ImageNet上并不奏效，这强调了在大型真实设定下评估OOD检测的必要性。为解决上述挑战，MOS的关键理念是将大的语义空间解构为有相似概念的更小的群组，这简化了已知和未知数据之间的决策边界。强有力的预训练模型在各种任务、模态都达到了惊人的性能。同期的工作 [171], [230], [231] 证实预训练过的transformer在特定的困难的OOD任务上性能显着改善。
OOD检测领域中，基于密度的方法用一些概率模型显式地建模分布内数据，并将低密度区域的测试数据标记为OOD。即使OOD检测在分布内数据为多类别的情形下和异常检测不同，3.1.2节中的密度估计方法能够通过将分布内数据统一成一个整体而直接适用于OOD检测。当分布内含多个类别时，class-conditional高斯分布能够显式地建模分布内数据，因而分布外样本能够根据输出的预测概率而被识别【207】。基于流的方法 [92], [232], [233], [234]也可被用于概率建模。直接估计OOD概率似乎是一种自然的解决方法，也有一些方法 [235], [236], [237] 通过给OOD样本输出更高的概率预测值来实现OOD检测。【238】尝试使用likelihood ratio来解决这个问题。【239】发现，对输入复杂度，概率值存在明显偏差，提出了一种基于概率值比例的方法来削减输入复杂度的影响。近期的方法转而使用新的评分，例如likelihood regret【240】或是集成多个密度模型【236】。整体上，生成式模型的训练和优化难度几乎是不可接受的，它们的性能也往往落后于基于分类的方法（3.3）
基于距离的方法基本理念在于，测试中OOD样本应当相对远离分布内类别的中心（centroid）或原型（prototype）。【207】使用相对所有类别中心的最小Mahalanobis距离来检测。一个后续工作【241】将图片分为前景和背景，再计算这两个空间间的Mahalanobis距离比例。一些工作使用测试样本特征和类别特征间的余弦相似度来确定OOD样本【242】、【243】。被训练特征的的第一奇异向量一维的子空间
更进一步，其他工作利用了径向基函数核距离（distance with radial basis function kernel）、输入的嵌入向量到类别中心的欧拉距离。
OOD检测领域自出现以来发展迅速，其解决方案从基于分类的、基于密度的、再到基于距离的。在多类别设定下，典型的OOD检测是开集识别问题（第4节），在类别空间Y中精确分类分布内的测试样本，并且丢弃语义不被Y所支持的分布外样本。然而，OOD检测包含了更广泛的学习任务（比如，多标签分类）和解法（比如，密度估计和离群点暴露）。一些方法放宽了开集检测的限制条件，并且达到了更强的性能。
离群检测需要所有样本可见，其目标是检测出那些显着偏离大多数的分布的样本。离群检测方法通常是转导式的，而不是归纳式的。 [13], [14], [15], [16]综述主要回顾了数据挖掘领域的离群检测方法。以下主要回顾离群检测方法，尤其是为计算机视觉设计的使用深度神经网络的方法。即使深度学习方法极少能直接解决离群检测问题，数据清洗程序（从开集脏数据学习的先决条件）和开集半监督学习的方法也在解决离群检测问题。
离群检测模型的基本理念是将整个数据集建模为一个高斯分布，将偏离均值超过三杯标准差的样本标记为离群【300】【301】。其他带参数的概率方法利用Mahalanobis距离[266] 和高斯混合模型 [302]来建模数据密度。和“三倍标准偏离”规则类似，四分位距也可通过构建传统的无参数概率模型来检测离群样本【247】。为了鲁棒和简化，局部离群因子（local outlier factor）方法【248】借助给定点的邻居和它自身局部可达性的比值，去估计给定点的密度。RANSAC【252】迭代地估计数学模型的参数来拟合数据并且找到对估计贡献较少的样本作为离群点。
总体上，经典的异常检测的密度方法比如，核密度估计（3.1节），也可应用于离群检测。即便这些方法由于图片数据维度太高而应用困难，也可以通过降维方法【253,254】和基于最近邻的密度方法(3.1节)来缓解。
检测离群的一个简易方法是计数某特定半径内的邻居数量，或者度量第k近邻居的距离【303,304】。以下主要介绍基于聚类的方法和基于图的方法。
DBSCAN【255】依照基于距离的密度来积聚样本构成聚类。处在主要聚类之外的样本被识别为离群样本。后续工作通过考虑聚类标签的信心改良了聚类的方式【256】。
另一类方法利用数据点之间的关系，并构造邻域图[305], [306]（或其变体[307]），利用图的属性和图挖掘技巧来找到异常的样本【257，258】，比如图聚类[259], [260]、图分割【308】、使用图神经网络的标签传播【261】。
③ Neo4j中使用Louvain算法和标签传播算法(LPA)对漫威英雄进行社群分析
在本系列第一篇 在Neo4j中构建漫威世界的社交网络 中我们从英雄到漫画的二分图推导出英雄到英雄的一分图。接着在第二篇 在Neo4j中对漫威社交网络进行初步分析 中得到一些基本的网络信息以帮助我们了解正在处理的网络情况。
在本篇中我将会在漫威英雄的网络上使用Louvain算法和标签传播算法(LPA)，发现一些有趣的社群。
本文中的可视化是使用Gephi来进行呈现，关于Gephi的更多信息可以看我之前的文章《Neo4j to Gephi》(https://tbgraph.wordpress.com/2017/04/01/neo4j-to-gephi/)。关于社群可视化还可以使用neovis.js(https://github.com/johnymontana/neovis.js)。
Neo4j图算法一般是在图的子集上进行，而这个子集通常是一个虚拟图，Neo4j图算法加载这种图有两种办法。第一种简单的办法是通过指定结点的标签和关系的类型将其加载到图算法中。
但是，如果我们要运行的逻辑是在一个特定的子图上，而仅使用结点标签和关系类型无法描述出这个子图，同时也不想去修改实体图，这时要怎么办呢？
不用担心，我们还可以使用Cypher语句来指定要加载的子图。使用查询结点的Cypher语句代替结点标签参数，使用查询关系的Cypher语句来代替关系类型参数。
但是注意，在参数中一定要指明 graph:'cypher' 。
如下示例：
CALL algo.unionFind(
//第一个Cypher语句指定了要加载的结点。
'MATCH (p:User)
WHERE p.property = 'import'
RETURN id(p) as id',
//第二个Cpyher语句指定要加载的关系
'MATCH (p1:User)-[f:FRIEND]->(p2:User)
RETURN id(p1) as source, id(p2) as target,f.weight as weight',
{graph:'cypher',write:true})
通过Cypher语句映射和加载子图，可以非常好的描述要运行算法的子图。不仅如此，我们还可以剔除一些关系，间接的映射一个虚拟图用于运行算法，而那些剔除的关系又并不会从实际图中删除。
Cpyher映射使用场景：
* 过滤结点和关系
* 加载间接关系
* 映射双向图
* 相似性阈值（后面详情介绍）
在对各种网络的研究过程中，如计算机网络、社交网络以及生物网络，我们发现了许多不同的特征，包括小世界特性，重尾分布以及聚类等等。另外，网络都有一个共同的特征即社群结构，也就是连通和分组。而现实网络世界的连通并不是随机或同质的，而是存在着某种自然的联系。
社群识别算法在一个全连通的图上运行，效果并不会很好。因为大多数据结点都是紧密连接的，他们是属于一个社群的。在这些的图上运行算法，最终结果就是：得到一个覆盖图大部分区域的大社群和一些边边角角小社群。
这时我们可以使用相似性阈值来进行调控，将大于某个值的关系保留，而小于此值的关系将会剔除。而这个虚拟图就可以通过Cypher语句轻松的映射出来了。
在本文中，我会将漫威社交网络中KNOWS的weight作为阈值，将其设置到100，大于100的关系将会保留，小于100的关于将会剔除，这样，得到的社群将会非常紧密。
连通分量或并查集算法都是找到相互连接的结点集，或者称之为岛，而在这个集合中的所有点都是可以相互连通的。
在图论中，无向图的连通分量（或者仅分量）是一个子图，其中此子图任何两个顶点通过路径相互连接。
当我遇到一个新的网络时，我第一时间想知道是：这个网络有多少个连通分量，以及他们每个都包含多少结点。在漫威英雄的网络中，当前我们已经把KNOWS的weight阈值设置到100了，而前一篇文章的阈值是10，因此，本文得到的连接肯定要比前一篇文章()中的连接要少。
在下面的示例中，我们直接使用结点标签和关系类型，所有标签为Hero的结点和所有类型为KNOWS的关系都将被加载到算法中。由于我们将阈值设置到100，所以，当前算法只考虑weight大于100的关系。
CALL algo.unionFind.stream('Hero', 'KNOWS',
{weightProperty:'weight', defaultValue:0.0, threshold:100.0,concurrency:1})
YIELD nodeId,setId
RETURN setId as component,count(*) as componentSize
ORDER BY componentSize DESC LIMIT 10;
正如我所料，漫威英雄网络是一个稀疏图，有1个大社群和6小社群组成，大社群有101个英雄，而小社群基本也就2~4个英雄。这表示，在6439个英雄中，有116个英雄至少一个KNOWS关系的weight值是大于100的。
如果想在浏览器中仔细浏览那个包含101英雄的大社群，会很容易发现隐藏在这里面的一些直观的东西以及社群之间的桥梁结点。接下来我们将尝试使用Louvain算法和标签传播算法来看看这个116个英雄的子图的社群结构。
社群就是网络中结点集合，它们彼此之间的连接比其他节点更紧密。Molarity是一种度量刻度，被用于衡量社群发现算法结果的质量，它能够刻画社区的紧密程度。在一个随机的网络中，将一个结点归类到某一个社群，Molarity值就是会生变化，进而给出这种分配后社区的质量。Molarity即量化了此结点与社群中其他结点的连接紧密程度。社群识别的Louvain方法，是一种基于启发式Molarity最大化的网络社群检测算法。
如前所述，我们将通过Cypher查询来仅映射weight大于110的关系到算法中。
CALL algo.louvain.stream(
// load nodes
'MATCH (u:Hero) RETURN id(u) as id',
// load relationships
'MATCH (u1:Hero)-[rel:KNOWS]-(u2:Hero)
// similarity threshold
WHERE rel.weight > 100
RETURN id(u1) as source,id(u2) as target',
{graph:"cypher"})
YIELD nodeId,community
MATCH (n:Hero) WHERE id(n)=nodeId
RETURN community,
count(*) as communitySize,
collect(n.name) as members
order by communitySize desc limit 5
我使用Gephi进行社群结果可视化，因为Gephi的表现力比表格更好，更有洞察力。
我并不是漫威漫画的专家，所以我只能根据数据来做一个简单的解释。我们总共划分出8个社群。最大的社群是紫色的社群，它由以美国队长为首的神盾局和复仇者联盟组成。在左边我们能看到神奇先生和神奇四侠也在紫色社群里。亮兰色是蜘蛛侠团队，蜘蛛侠帕克是他们与外界联系的唯一桥梁，其他人都是内部交流，与外界并无联系。深兰色是阿斯加德人，他们也是比较封闭，他们仅仅和雷神托尔有联系。哦？难以置信，绿巨人也是自己的社群（粉红色），而绿巨人是这个社群唯一与外界有联系的英雄。我们还看到野兽亨利是紫色社群与绿色社群的桥梁，位置特殊，而绿色是X-Men社群。
标签传播算法是由Raghavan等人于2007年首次提出，（译者言：网络显示此算法于2002年由Zhu等人提出）此算法是由每个结点使用其唯一标识作为标签，然后根据大多数邻居结点的标签为基础进行标签传播，每个结点再从他的邻居结点身上取出现次数最多的标签加到自己身上。LPA算法的具体步骤是这样：结点X有一些邻居结点，且每个邻居结点都有一个标签，标明他们所属的社群。然后网络中的每个结点都选择加入其大多数邻居所属的那个社群，同时再随机的断开一些连接。在开始时，每个节点都用唯一标签进行初始化，然后这些标签开始在网络中进行传播，传播的每一步，每个结点都会根据邻居标签的情况更新自己的标签，随着标签的传播，最终连接紧密的结点集合将会达成一个共识，而他们身上的标签也将不再发生变化。
与Louvaint算法类似，我们也采用Cypher语句进行图映射，在映射时仅加载weight值大于KNOWS关系。同时会将对结点进行回写，导出结果到Gephi中进行可视化展示。
CALL algo.labelPropagation(
// supports node-weights and defining
// initial communities using parameter value
'MATCH (u:Hero) RETURN id(u) as id, 1 as weight,id(u) as value',
// load relationships
'MATCH (u1:Hero)-[rel:KNOWS]-(u2:Hero)
// Similarity threshold
WHERE rel.weight > 100
RETURN id(u1) as source,id(u2) as target, rel.weight as weight',
'OUT',{graph:"cypher",partitionProperty:"lpa" })
YIELD computeMillis
最终我们得到21个社群，包括单点社群。复仇者联盟（紫色）和神奇四侠（亮兰色）被分为两个社群了。蜘蛛侠（绿色），绿巨人（青绿色）和阿斯加德人（红色）三个社群的结果与Louvain算法一致。我们还发现X-Man被划分成两个社群，加农炮小组比Louvain的结果要稍微大点，同时也显的不那么孤立。
你发现没有？Neo4j图算法库真的很神奇，用起来也简单。通过与Cypher查询语句结合进行虚拟图映射，可以简单有效的对图进行分析和理解。
本来，我打算在本文中介绍中心性算法的使用，但那样本文将会非常长，不便于阅读，所以， 我后续将会再写文章来介绍使用Cypher映射进行中心性算法的示例。敬请期待吧。