图神经网络——基本图论与PyG库
图神经网络——基于图神经网络的图表征学习方法图表征学习要求在输入节点属性、边和边的属性（如果有的话）得到一个向量作为图的表征，基于图表征进一步的我们可以做图的预测，而图同构网络（Graph Isomorphism Network, GIN）的图表征网络是当前最经典的图表征学习网络。 1.GNN的邻域聚合(消息传递)GNN的目标是以图结构数据和节点特征作为输入，以学习到节点（或图）的embedding，用于分类任务。基于邻域聚合的GNN可以拆分为以下三个模块： Aggregate：聚合一阶邻域特征。 Combine：将邻居聚合的特征 与 当前节点特征合并， 以更新当前节点特征。 Readout（可选）：如果是对graph分类，需要将graph中所有节点特征转变成graph特征。 但是Aggregate的三种方式sum、mean、max的表征能力不够强大。 如上图，节点v和v’为中心节点，通过聚合邻居特征生成embedding来分析不同aggregate设置下是否能区分不同的结构。设红绿蓝色节点特征值分别为r,g,b，不考虑combine。 图a中：mean：左$\frac{1...
图神经网络——超大图上的节点表征学习
图卷积网络(GCN)已经成功地应用于许多基于图形的应用，然而大规模的GCN的训练仍然具有挑战性。目前基于SGD的算法要么面临着随GCN层数呈指数增长的高计算成本，要么面临着保存整个图形和每个节点的embedding到内存的巨大空间(显存)需求。于是论文Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Network提出了Cluster-GCN方法来解决超大图的训练问题。 1.Cluster-GCN方法简单概括 利用图节点聚类算法将一个图的节点划分为$c$个簇，每一次选择几个簇的节点和这些节点对应的边构成一个子图，然后对子图做训练。 由于是利用图节点聚类算法将节点划分为多个簇，所以簇内边的数量要比簇间边的数量多得多，所以可以提高表征利用率，并提高图神经网络的训练效率。 每一次随机选择多个簇来组成一个batch，这样不会丢失簇间的边，同时也不会有batch内类别分布偏差过大的问题。 基于小图进行训练，不会消耗很多内存空间，于是我们可以训练更深的神经网络，进而可以达到更...
图神经网络——节点分类与边预测
1.InMemoryDataset基类在PyG中，可以通过继承InMemoryDataset类来自定义一个数据可全部存储到内存的数据集类。(继承Dataset是分次加载到内存，继承InMemoryDataset是一次性加载所有数据到内存) 1 class InMemoryDataset(root: Optional[str] = None, transform: Optional[Callable] = None, pre_transform: Optional[Callable] = None, pre_filter: Optional[Callable] = None) 参数说明： transform：数据转换函数，用于转换Data对象，每一次数据获取过程中都会被执行。pre_transform：数据转换函数，用于转换Data对象，在Data对象被保存到文件前调用。pre_filter：检查数据是否要保留的函数，接收一个Data对象，返回此Data对象是否应该被包含在最终的数据集中，在Data对象被保存到文件前调用。 2.Sequential容器nn....
图神经网络——基于图神经网络的节点表征学习
Graph的特征表示非常复杂： 1.复杂的拓扑结构，较难从图像中的感受野提取有效信息；2.无特定的节点顺序；3.通常graph会是动态变化的， 且使用多模态特征。 高质量的节点表征能够用于衡量节点的相似性，同时高质量的节点表征也是准确分类节点的前提。 本文以Cora论文引用网络数据集为例，对MLP、GCN、GAT三种神经网络的分类性能进行对比。首先载入数据集并定义可视化函数： 1 2 3 4 5 #载入数据集 from torch_geometric.datasets import Planetoid from torch_geometric.transforms import NormalizeFeatures dataset = Planetoid(root='dataset', name='Cora', transform=NormalizeFeatures()) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #定义可视化函数，并观察整体数据分布 from sklearn.mani...
图神经网络——消息传递网络
消息传递(Message Passing) 指的是目标节点$S1$的邻居$\mathcal{N(S1)}$——B1、B2、B3，这些邻居节点根据一定的规则将信息(特征)，汇总到目标节点上。信息汇总中最简单的规则就是逐个元素相加。在pytorch-geometric的官方文档中，消息传递图神经网络被描述为:$$\mathbf{x}_i^{(k)} = \gamma^{(k)} \left( \mathbf{x}i^{(k-1)}, \square{j \in \mathcal{N}(i)} , \phi^{(k)}\left(\mathbf{x}i^{(k-1)}, \mathbf{x}j^{(k-1)},\mathbf{e}{j,i}\right) \right),$$其中，$\mathbf{e}{j,i} \in \mathbb{R}^D$ 表示从节点$j$到节点$i$的边的属性，$\mathbf{x}^{(k-1)}_i\in\mathbb{R}^F$表示$(k-1)$层中节点$i$的节点表征，$\square$表示聚合策略，$\gamma$和$\phi$表示一些神...
图神经网络——基本图论与PyG库
在以往的深度学习中，主要的数据形式包括矩阵、张量、序列(sequence)和时间序列(time series)，然而还有许多数据是图的结构，如社交网络、知识图谱等。图结构数据具有以下特点： 任意的大小和复杂的拓扑结构；没有固定的节点排序或参考点；通常是动态的，并具有多模态的特征；图的信息包括节点信息、边信息和拓扑结构信息。 1. 图结构数据1.1 图(Graphs)· 一个图记作$\mathcal{G}={\mathcal{V}, \mathcal{E}}$，其中 $\mathcal{V}=\left{v_{1}, \ldots, v_{N}\right}$是数量为$N=|\mathcal{V}|$ 的节点的集合， $\mathcal{E}=\left{e_{1}, \ldots, e_{M}\right}$ 是数量为 $M$ 的边的集合。· 节点表示实体(entities)，边表示实体间的关系(relations)；节点和边的信息可以是类别型或数值型的。· 只有一种类型的节点和一种类型的边的图称为同质图(Homogeneous Gra...
异常检测——集成方法
一般情况下，可以把异常检测看成是数据不平衡下的分类问题，如果数据条件允许，优先使用有监督异常检测如XGBOOST；仅有少量标签时，可以用无监督学习作为一种特征抽取方式，最后喂给有监督的分类模型。之前介绍的统计与概率模型、线性模型、基于相似度的模型，和今天要介绍的集成学习都是无监督模型。 为什么要使用集成学习？——①适合高维度数据(空间稀疏)，②提高模型鲁棒性。值得注意的时，异常检测没有标签，所以feature bagging、bagging比boosting多。而使用boosting进行异常检测，需要生成伪标签。 1. Feature BaggingFeature Bagging，基本思想与bagging相似，只是对象是feature。基本检测器可以彼此完全不同，或不同的参数设置，或使用不同采样的子数据集。Feature bagging常用lof算法为基算法。 1.1 算法原理 1.2 不同检测器的分数标准化不同检测器可能会在不同的尺度上产生分数。例如，平均k近邻检测器会输出原始距离分数，而LOF算法会输出归一化值。另外，检测器输出的异常值分数大小不一，因此需要归一化，常见方...
异常检测——基于相似度的方法
异常值通常具有更高的离群程度分数值，同时也更具有可解释性。在基于相似度的异常检测方法中，主要思想是异常点的表示与正常点不同。 1. 基于距离的度量基于距离的异常检测有这样一个前提假设，即异常点的k近邻距离要远大于正常点。常见的方法是嵌套循环，第一层循环遍历每个数据，第二层循环进行异常判断计算当前点与其他点的距离，一旦发现多于k个数据点与当前点的距离在D之内，则将该点标记为非异常值。 此法计算的时间复杂度为O(N2)，当数据量比较大时需要修剪方法以加快距离计算。 1.1 基于单元的方法在基于单元格的技术中，数据空间被划分为单元格，单元格的宽度是阈值D和数据维数d的函数。L1邻居表示通过最多1个单元间的边界可从该单元到达的单元格的集合，L2邻居表示通过跨越2个或3个边界而获得的那些单元格。以二维数据为例，网格间的距离为D/2√d，其具有以下性质：①单元格中两点之间的距离最多为D/2 。②一个点与L1邻接点之间的距离最大为D。③一个点与它的Lr邻居(其中r>2)中的一个点之间的距离至少为D。 但是L2中并不能直接得出结论，需要另外定义规则，如：①如果一个单元格...
异常检测——线性相关方法
真实数据集中不同维度的特征可能具有高度相关性，这是因为不同的特征往往是由相同的基础过程以密切相关的方式产生的。这被称为——回归建模，是一种参数化的相关性分析。一类相关性分析通过其他变量预测单独的属性值，另一类方法用一些潜在变量来代表整个数据。前者的代表是线性回归，后者一个典型的例子是主成分分析。线性相关分析基于的假设是：①近似线性相关假设；②子空间假设。为了确定线性模型是否适合数据集，需要进行探索性和可视化分析。 0. 探索性和可视化分析 1 2 train_data.describe() train_data.info() 1 2 3 4 5 6 7 8 9 #相关性分析 numeric_features = ['f'+str(i) for i in range(20)] numeric = train_data[numeric_features] correlation.numeric.corr() f,ax = plt.subplots(figsize=(15,15)) sns.heatmap(correlation,sq...
异常检测——基于统计学的方法
异常检测的统计方法包含两种主要类型：参数方法和非参数方法。**参数方法：**假定数据服从以θ为参数的参数分布，该参数分布的概率密度函数f(x,θ)给出x属于该分布的概率，该值越小，x越可能是异常点。(仅对数据做的统计假定满足实际约束时可行)非参数方法：不假定先验统计模型，假定参数的个数较为灵活，并非完全无参。 1. 参数方法1.1 基于正态分布的一元异常点检测仅涉及单变量的数据称为一元数据，假定数据由正态分布产生，由输入数据学习正态分布的参数，并把低概率的点识别为异常点。输入数据集 ，根据公式可以求出参数均值μ和方差σ，和概率密度函数p(x)。$$\mu =\frac{1}{n}\sum_{i=1}^n{x_i}$$$$\sigma ^2=\frac{1}{n}\sum_{i=1}^n{\left( x_i-\mu \right)}^2$$$$p\left( x \right) =\frac{1}{\sqrt{2\pi}\sigma}\exp \left( -\frac{\left( x-\mu \right) ^2}{2\sig...