我的博客

天池通过 docker 提交

目录
  1. 安装 docker
  2. 开通阿里云镜像服务
  3. 拉去镜像并构造自己的镜像
    1. 拉取镜像
      1. 登录
      2. 选择一个镜像
    2. 提交比赛
  4. 遇到的问题

我用的是 manjaro 系统。

安装 docker

参考资料

1
2
3
4
5
6
7
8
9
10
11
12
13
# Pacman 安装 Docker
sudo pacman -S docker

# 启动docker服务
sudo systemctl start docker


# 查看docker服务的状态
sudo systemctl status docker


# 设置docker开机启动服务
sudo systemctl enable docker

开通阿里云镜像服务

官方文档

用阿里云帐号登录一下,设置一个密码就能开通。

拉去镜像并构造自己的镜像

首先创建一个自己的镜像托管

拉取镜像

点管理进去有一个说明参考这个页面的操作步骤

登录

1
sudo docker login --username=xxx@aliyun.com registry.cn-shanghai.aliyuncs.com

选择一个镜像

镜像列表:

https://tianchi.aliyun.com/forum/postDetail?spm=5176.12586973.0.0.50de2232UKMpd5&postId=67720

我选择:registry.cn-shanghai.aliyuncs.com/tcc-public/pytorch:1.4-cuda10.1-py3

注意这个镜像有 python 和 python3 都是 python 3.7 但是只有 pip 没有 pip3

1
sudo docker pull registry.cn-shanghai.aliyuncs.com/tcc-public/pytorch:1.4-cuda10.1-py3

build 和 push 镜像

1
2
sudo docker build -t registry.cn-shenzhen.aliyuncs.com/xxx-test/tianchi:1.0 .
sudo docker push registry.cn-shenzhen.aliyuncs.com/xxx-test/tianchi:1.0

提交比赛

填写镜像地址,要带版本号

registry.cn-shenzhen.aliyuncs.com/xxx-test/tianchi:1.0

填写用户名和密码

遇到的问题

没有 pip3 而是 pip

无法访问网络,pip 没法用, 预训练模型也不能下载

可以启动 docker 以后对 docker 进行修改并提交为新的镜像 参考

1
curl -O https://s3.amazonaws.com/models.huggingface.co/bert/bert-base-chinese-pytorch_model.bin

读论文:Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics

目录
  1. 全文概括(基本是翻译)
    1. TOWARD FINANCIAL INCLUSION 走向金融包容
      1. AML in a cryptocurrency world 加密货币世界的反洗钱
    2. THE ELLIPTIC DATA SET 椭圆数据集
      1. Graph Construction 图的构造
      2. Notes on Feature Construction 特征构造的说明
    3. TASK AND METHODS 任务和方法
      1. Benchmark Methods 基准方法
      2. Graph Convolutional Networks (GCN) 图卷积网络
      3. Temporal Modeling 时间建模
    4. EXPERIMENTS 实验
    5. DISCUSSION 讨论
    6. GRAPH VISUALIZATION 图的可视化
      1. Visual Investigation of the Elliptic Data Set 椭圆数据集的可视化研究
    7. SUMMARY 总结
    8. ACKNOWLEDGMENTS 致谢
    9. REFERENCES 参考文献

论文地址:https://arxiv.org/abs/1908.02591

文章摘要指出:反洗钱一方面保护金融体系,一方面产生副作用:不仅有高昂的花费,而且会导致世界金融发展更不平衡。

但是加密货币让交易数据公开化,而通过匿名保障隐私。让反洗钱工作可以称谓众包化的工作,也可以更好的发挥机器学习算法的优势。

作者提出了一个数据集:Elliptic Data Set(简介)。包括 20 万笔交易,总价值 60 亿美元。有 4545 个交易(2 %)被标记为非法,42019 个交易(21 %)被标记为合法,剩余的交易是未知的。每个节点都关联了 166 个特征。

文中使用了多种算法:Logistic回归(LR)、随机森林(RF)、多层感知器(MLP)和图卷积网络(GCN),处理这个数据。

全文概括(基本是翻译)

TOWARD FINANCIAL INCLUSION 走向金融包容

“It’s expensive to be poor.” 贫穷是昂贵的。全球有 17 亿成年人没有银行账户。

反洗钱措施给落后地区的人们的金融活动造成更大的阻力。但是这不意味着应该减少反洗钱措施,洗钱不是没有受害者的犯罪,也会给广大受害者造成非常的大伤害。

当前金融体系的反洗钱措施不够完善。

作者希望探讨在金融数据更加开放的时候,可不可以通过使用正确的分析工具是金融变得更包容。

AML in a cryptocurrency world 加密货币世界的反洗钱

世界范围内,资金转移(money transfer)初创公司开始崛起,并与传统银行竞争。它们使用加密货币作为 rails 实现低成本的资金跨境点对点转移。它们的工作提高了金融的包容性。(是落后地区的人们的金融活动成本更低)

但是比特币系统中有很多非法交易。

2019年5月,美国金融犯罪执法网络(Financial Crimes Enforcement Network,FinCEN)发布了关于1970年《银行保密法》(Bank Secrecy Act,BSA)如何适用于加密货币,或FinCEN称之为可转换虚拟货币(convertible virtual currencies,CVC)的新指南。与BSA一致,该指南要求最高服务商生成个性化的风险评估,以衡量洗钱、恐怖主义金融和其他金融犯罪的风险。

这些评估基于客户构成、服务地区和提供的金融产品或服务。评估必须告知客户关系管理层,并实施与风险相称的控制措施;换言之,MSBs 不仅必须报告可疑账户,而且还必须对其采取行动(例如冻结或关闭账户)。该指南将“完善的风险评估”定义为“协助 MSBs 识别并提供其个人风险状况的综合分析”。为了加 MSBs 对了解你的客户(Know Your Customer,KYC)的要求,该指南要求 MSBs 对其客户有足够的了解,以确定他们的风险水平对机构的代表。“充分了解”客户意味着什么是合规和政策界争论的话题。

在实践中,最具挑战性的一个方面是一个隐含但有效实施的要求,不仅要了解客户,还要了解客户的客户。在传统金融零散的数据生态系统中,这方面的合规性通常是通过 MSBs 之间的电话来执行的。但在比特币的开放系统中,完整的图形交易网络数据是公开的,尽管是以假名和未标记的形式。为了迎接这一公开数据带来的机遇,加密货币情报公司应运而生,为加密货币领域提供量身定制的反洗钱解决方案。虽然比特币的假名是犯罪分子的优势,但公开数据是调查人员的关键优势。

THE ELLIPTIC DATA SET 椭圆数据集

椭圆是一家加密货币情报公司,致力于保护加密货币生态系统免受犯罪活动的影响。在本教程中,作为对研究社区的贡献,我们介绍了椭圆数据集,一个具有手工提取特征的比特币交易的图形网络。作为对研究和反洗钱社区的贡献,椭圆公司同意公开共享该数据集。据我们所知,它是以任何加密货币公开提供的世界上最大的标记交易数据集。

Graph Construction 图的构造

椭圆数据集将比特币交易映射到属于合法类别(交易所、钱包提供商、矿工、合法服务等)的真实实体,和与之相对的非法实体(诈骗、恶意软件、恐怖组织、勒索软件、庞氏骗局等)。根据原始比特币数据,构造并标记一个图,使得节点表示交易,边表示比特币从一个交易流向下一个交易。如果发起交易的实体(即控制与特定交易的输入地址相关联的私钥的实体)属于合法(非法)类别,则将给定交易视为合法(非法)。重要的是,所有的特征都是使用公共信息构建的。

节点和边

有 203769 个节点(交易)和 234355 个有向边(支付流)。从全局看,使用相同的图形表示,截至本文撰写之时,整个比特币网络大约有 4 亿 3 千 8 百万个节点和 11 亿个边。在椭圆数据集中,百分之二(4545)标记为类别 1(非法)。百分之二十一(42019)被标记为类别 2(合法)。其余的交易没有合法与非法的标签,但有其他特征。

特征

每个节点都关联了166个特征。前94个特征表示有关交易的本身的(局部的)信息,包括时间步、输入/输出数量、交易费用、输出量和合计金额,例如输入/输出接收(花费)的平均BTC和与输入/输出关联的平均转入(转出)交易数量。其余的72个特征称为聚合特征,通过从中心节点向后/向前一跳聚合事务信息来获得-给出相同信息数据(输入/输出数量、事务费用等)的相邻事务的最大、最小、标准差和相关系数。

时间信息

时间戳与每个节点相关联,表示比特币网络确认交易时的估计时间。共有49个不同的时间步,平均间隔约两周。每个时间步骤包含在区块链上出现的、彼此之间不到三小时的交易的单个连接组件;没有连接不同时间步骤的边。很明显,特定时间步中的节点彼此关联的时间戳非常接近,因此可以有效地将它们中的每一个视为时间上的即时“快照”。每个时间步的节点数随时间的推移是相当均匀的(从1000到8000个节点)。见图1。

Notes on Feature Construction 特征构造的说明

合法与非法的标签的处理是通过基于启发式的推理过程来实现的。例如,较高数量的输入和相同地址的重用通常与较高的地址集群相关[10],这导致签名事务的实体的匿名性降低。另一方面,将由多个地址控制的资金合并到一笔交易中,在交易成本(费用)方面提供了好处。因此,对于大量用户请求,避免匿名保护措施的实体可能是合法的(例如,交换)。相反,非法活动可能倾向于使用较少输入的交易,以减少去匿名地址群集技术的影响。此外,在为比特币交易构建功能方面还有两大挑战。第一个原因是比特币区块链的规模相当于200GB的压缩数据和约4亿个交易。虽然并非所有交易都包含在本研究中使用的子集中,但仍有必要访问完整的区块链,以便观察参与所选交易的钱包的完整历史。为了克服这个问题,椭圆函数使用了一个高性能的全内存图引擎来计算特征。第二个挑战来自数据的底层图形结构和事务可以拥有的邻居数量的异构性。在构建72个聚合特征时,通过简单地构建邻居事务的本地特征的统计聚合(最小、最大等)来解决异构邻居的问题。一般来说,这个解决方案是次优的,因为它会带来很大的信息损失。我们将在即将到来的关于图深度学习方法的讨论中讨论这个问题,这可能更好地解释局部图拓扑。

TASK AND METHODS 任务和方法

在高层次上,反洗钱分析是一项异常检测挑战,它要求在不断增长的海量数据集中准确分类少量非法交易。行业标准高达90%以上的假阳性率抑制了这一努力。我们希望在不增加假阴性率的情况下降低假阳性率。Logistic 回归和随机森林是这项任务的基准方法。图深度学习也已成为 AML 的潜在工具[21]。在椭圆数据集的情况下,要对该数据执行的任务是事务筛选,以评估与给定的往来于加密货币钱包的事务相关联的风险。具体来说,每一笔未标记的比特币交易都将被归类为非法或合法交易。

Benchmark Methods 基准方法

鉴于前面描述的特征,基准机器学习方法使用监督学习中的前 94 个特征进行二分类。这些技术包括 Logistic 回归[1]、多层感知器(MLP)(同上)和随机森林[2]。在 MLP 中,每个输入神经元接受一个数据特征,输出是一个 softmax,每个类有一个概率向量。Logistic 回归和随机林是 AML 的两种常用方法,特别是它们各自的优点:随机林用于实现较高准确率,Logistic 回归则有较好的可解释性。但是,这些方法不利用任何图形信息。在椭圆数据集中,局部特征被一组包含邻域信息的72个特征增强。我们将看到这些特性的利用提高了性能。虽然这种方法显示了二值分类问题中的图结构,并且可以与标准的机器学习技术一起使用,但是将纯粹基于特征的方法扩展到直接邻域之外是一个挑战。这一缺点促使人们使用图卷积网络。

Graph Convolutional Networks (GCN) 图卷积网络

对图形结构数据的深入学习是一个兴趣迅速增长的课题[3,6,8,9,14]。处理图形结构固有的组合复杂性给实际应用带来了可伸缩性挑战,在解决这些挑战方面已经取得了重大进展[5,11,24]。具体地说,我们考虑了图卷积网络(GCNs)。GCN由多层图卷积组成,它类似于感知器,但还使用由谱卷积驱动的邻域聚合步骤。假设来自椭圆数据集的比特币事务图为G=(N,E),其中N是节点事务集,E是表示BTC流的边集。GCN的第l层以邻接矩阵A和节点嵌入矩阵H(l)为输入,用权值矩阵W(l)将节点嵌入矩阵更新为H(l+1)作为输出。

Temporal Modeling 时间建模

金融数据本质上是时间性的,因为交易是有时间戳的。有理由假设存在某种动力,尽管是隐藏的,驱动着系统的进化。如果一个预测模型是以捕捉动态的方式设计的,那么它将更加有用。这样,在给定时间段上训练的模型可以更好地推广到后续的时间步。模型捕捉到的系统动力学(也在进化)越好,它所能进入的视界就越长。扩展 GCN 的时间模型是 EvolveGCN[19],它为每个时间步计算单独的 GCN 模型。然后通过循环神经网络(RNN)将这些 GCN 连接起来,以捕捉系统动力学。因此,未来时间步的 GCN 模型是从过去的模型演变而来的,在过去的模型中,进化捕捉到了动力。在 EvolveGCN 中,GCN 权重被集体地视为系统状态。通过使用 RNN(例如 GRU),每次在系统输入时更新模型。输入是当前时间点的图形信息。图信息可以通过多种方式实例化;在 EvolveGCN 中,它由图中 top-k 个有影响的节点的嵌入来表示。

EXPERIMENTS 实验

本文给出了在椭圆数据集上的实验结果。我们分别对训练和测试数据进行了 7:3 的时间分割。也就是说,前 34 个时间步用于训练模型,后 15 个用于测试。我们使用时间分割,因为它反映了任务的性质。因此,GCN 是在归纳环境中训练的。我们首先使用三种标准方法测试合法/非法预测的标准分类模型:Logistic 回归(使用 scikit-learn-Python 包[4]中的默认参数)、随机森林(也来自 scikit-learn,具有 50 个估计器和 50 个最大特征)和多层感知器(在 PyTorch 中实现)。我们的 MLP 有一个隐藏层,由 50 个神经元组成,使用 Adam 优化器训练 200 个 epochs,学习率为0.001。我们通过使用所有 166 个特征(称为 AF )以及仅使用本地特征(即前 94 个特征(称为 LF))来评估这些模型。结果汇总在 表 1 的上半部分。表 1 的下半部分报告了当我们利用数据的图表结构时所取得的结果。我们使用 Adam 优化器对 GCN 模型进行了 1000 个 epochs 的训练,学习率为0.001。在我们的实验中,我们使用了一个2层的GCN,然后超参数调整,我们将节点嵌入的大小设置为100。

表 1

这个任务是一个二分类,两个类是不平衡的。对于反洗钱来说,更重要的是少数的类(即非法的类)。因此,我们使用加权交叉熵损失训练 GCN 模型,以提供更高的非法样本重要性。在超参数调整之后,我们为合法类和非法类选择了 0.3/0.7 的比率。表1显示了针对非法类的精确性、召回率和F1分数的测试结果。为了完整起见,我们还展示了微观平均 F1 分数。

注意,GCN 和变量 Skip-GCN 的性能优于 Logistic 回归,这表明基于图的方法与不可知的图信息相比是有用的。另一方面,在本例中,输入特征已经相当丰富了。仅使用这些特性,Random Forest 就可以获得最佳的 F1 成绩。输入特征的表示能力也反映在 Skip-GCN 的增益上。

表 1 中的另一个细节来自于对所有特征(AF)和仅对94个局部特征(LF)训练的方法的比较。对于所有三个被评估的模型,聚合的信息导致了更高的准确性,这表明了图结构在这个上下文中的重要性。通过这一观察,我们进一步评估了增强输入特征集的方法。这个实验的目的是证明图形信息对于增强事务的表示是有用的。在该设置中,我们将从 GCN 获得的节点嵌入与原始特征 X 连接起来。结果表明,对于全特征(AF+N E)和局部特征(LF+ne),使用增强的特征集可以提高模型的精度。

表 2 比较了非时间 GCN 和时间 EvolveGCN 的预测性能。EvolveGCN 的性能一直优于 GCN,尽管这一数据集的改进并不显著。进一步研究的一个途径是使用其他形式的系统输入来驱动 GRU 内部的重复更新。

The Dark Market Shutdown(黑市关闭)。反洗钱的一个重要考虑因素是预测模型对新出现事件的稳健性。这个数据集的一个有趣的方面是在数据的时间跨度内(在时间 43)有一个黑市关闭了。如图2所示,此事件导致所有方法在关闭后性能不佳。即使是随机的森林模型,在每一个测试时间步骤后重新训练,假设每次测试后都能获得真实的信息,也无法可靠地捕获黑市关闭后的新的非法交易。方法对此类事件的稳健性是一个需要解决的重大挑战。

图2

DISCUSSION 讨论

我们已经看到随机森林显著优于Logistic回归;事实上,它也优于GCN,即使后者是由图结构信息授权的。随机森林使用投票机制对来自多个决策树的预测结果进行集成,每个决策树使用数据集的子样本进行训练。与之相反,与大多数深度学习模型一样,GCN使用Logistic回归作为最终输出层;因此,它可以被视为Logistic回归的一个重要推广。

问题是:是否可以将随机森林与图形神经网络相结合?一个简单的想法是在运行随机林之前,使用从GCN计算的嵌入来增加节点特征。根据先前的实验,这个想法只能起到很小的作用。文献[13]提出的另一种思想是,利用前向神经网络对决策树中的每个节点进行参数化。这种思想将随机森林和神经网络有机地结合在一起,但并没有提出如何整合图形信息。一种可能的方法是用决策树的可微版本替换GCN中的Logistic回归输出层,从而实现端到端的训练。我们把这个想法的执行留待将来的调查。

GRAPH VISUALIZATION 图的可视化

最后,为了支持 AML 合规性的分析和解释,我们创建了一个名为 Chronograph 的可视化原型。在解释模型性能时,高维图形的可视化在普通特征向量的基础上增加了一层复杂性。Chronograph 的目的是解决这个问题,通过支持人类分析师与模型的综合表现。

Visual Investigation of the Elliptic Data Set 椭圆数据集的可视化研究

在 Chronograph 中,交易被可视化为一个图上的点,边表示 BTC 从一个交易到另一个交易的流。使用投影技术UMAP[15]在所有时间步同时计算节点坐标。这种全局计算使布局在时间上具有可比性。界面顶部的时间 setp 滑块控件允许用户通过仅渲染选定时间步中的节点来浏览时间。非法交易被染成红色;合法交易被染成蓝色。未分类的不着色。单击事务节点或在左侧控件中输入 TXID(作为子字符串筛选)时,可视化将以橙色突出显示选定的事务,并以绿色突出显示所有相邻事务(流入或流出)。在界面的左侧,用户可以看到关于不同事务类之间传输号的图和表的一般统计信息。在这个简单的原型中,Chronograph 使简单的探索场景能够直观地检查集群及其随时间的存在,观察明显的转移模式,或检测其他偏差,如单个离群值。作为一个更复杂的用例,我们还提高了 UMAP 计算输入的自由度:原始交易特征数据(图4a)和网络最后一层的神经元激活(图4b)似乎是两个有趣的选择;已经为一般的神经网络 Rauber 等人提出了类似的方法[20]。由此产生的可视化效果的差异将暗示模型的特性,即我们假设数据之间相似性的变化可以指示解释哪些基本特征对模型重要。图 4 显示了一个时间步的两个可选输入的结果,原始特性数据在顶部,模型激活在底部。我们进一步使用左栏中的实际标签和右栏中的 GCN 预测标签对节点进行染色,得到总共 4 个网络可视化结果。在基于模型的布局中,非法节点较少分散但更为集中,这似乎是一个可取的特性:非法节点应该具有一些重要的特征,节点的相似性使得布局更接近。然而,由于它们并没有在一个位置完全崩溃,因此在非法节点集内存在着质的差异是很有可能的。可视化进一步揭示了模型无法检测非法节点的确切位置。在附近地区出现多个错误预测的情况下,这可能进一步暗示该模型的系统表现不佳。详细研究这些事务的特性可以从新的角度启发讨论,并导致模型的进一步改进。

SUMMARY 总结

总之,我们提出了加密货币非法交易鉴别方法,特别是对比特币,作为一个独特的生态系统,为众包开发新的方法,打击犯罪活动。我们已经向反洗钱社区提供了一个大的、有标签的交易数据集,这类数据以前从未公开过。我们分享了早期的实验结果,使用了各种方法,包括图卷积网络,并讨论了算法改进的可能下一步。我们为这些数据的可视化提供了一个原型,并为增强人类的分析和解释能力提供了模型。最重要的是,我们希望能够激励其他人努力应对这一社会性的重大挑战,使我们的金融体系更安全、更具包容性。

ACKNOWLEDGMENTS 致谢

这项工作是由 MIT-IBM Watson 人工智能实验室(mitibm.mit.edu)资助的,该实验室是麻省理工学院和IBM research的联合研究计划。数据和领域专业知识由椭圆公司(www.elliptic.co)提供。

REFERENCES 参考文献

[1] Christopher Bishop. 2006. Pattern Recognition and Machine Learning. SpringerVerlag.
[2] Leo Breiman. 2001. Random forests. Machine learning 45, 1 (2001), 5–32.
[3] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2014. Spectral Networks and Locally Connected Networks on Graphs. In ICLR.
[4] Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. 2013. API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning. 108–122.
[5] Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In ICLR.
[6] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In NIPS.
[7] Demirguc-Kunt, Leora Klapper, Dorothe Singer, Sinya Ansar, and Jake Hess. 2017. The Global Findex Database 2017: Measuring Financial Inclusion and the Fintech Revolution.
[8] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. In ICML.
[9] William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS.
[10] Martin Harrigan and Christoph Fretter. 2016. The unreasonable effectiveness of address clustering. In 2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld). IEEE, 368–373.
[11] Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR.
[12] Knomad and World Bank Group. 2019. Migration and Remittances: Recent Developments and Outlook. Migration and Development Brief 31.
[13] Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. 2015. Deep Neural Decision Forests. In ICCV.
[14] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. 2016. Gated Graph Sequence Neural Networks. In ICLR.
[15] Leland McInnes, John Healy, and James Melville. 2018. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426 (2018).
[16] Daniel J. Mitchell. 2012. World Bank Study Shows How Anti-Money Laundering Rules Hurt the Poor. Forbes.
[17] Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008). [18] Financial Crimes Enforcement Network. 2019. Application of FinCENâĂŹs Regulations to Certain Business Models Involving Convertible Virtual Currencies. FIN-2019-G001 (May 2019).
[19] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, and Charles E. Leiserson. 2019. EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs. Preprint arXiv:1902.10191.
[20] Paulo E Rauber, Samuel G Fadel, Alexandre X Falcao, and Alexandru C Telea. 2016. Visualizing the hidden activity of artificial neural networks. IEEE transactions on visualization and computer graphics 23, 1 (2016), 101–110.
[21] Mark Weber, Jie Chen, Toyotaro Suzumura, Aldo Pareja, Tengfei Ma, Hiroki Kanezashi, Tim Kaler, Charles E. Leiserson, and Tao B. Schardl. 2018. Scalable Graph Learning for Anti-Money Laundering: A First Look. CoRR abs/1812.00076 (2018). arXiv:1812.00076 http://arxiv.org/abs/1812.00076
[22] Wikipedia. [n. d.]. 1Malaysia Development Berhad scandal.
[23] Wikipedia. [n. d.]. Danske Bank money laundering scandal.
[24] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In KDD.

Leetcode 354. 俄罗斯套娃信封问题 Russian Doll Envelopes

目录

https://leetcode-cn.com/problems/russian-doll-envelopes

这道题目用了巧妙的方法,关于 lengthOfLIS 函数可以参见 300. 最长上升子序列的解答 这个函数就是从这个题目中复制过来的。

本题目用了一个巧妙的方法处理信封顺序。信封的宽度是按升序排序,但是宽度相同时却按高度的降序排序。

这是因为宽度相同的信封无法套娃,所以这时把高度按降序排列,就无法利用同宽度的信封了。由于传入 lengthOfLIS 函数的只有高度信息,这种排序方法相当于把宽度信息传递到高度中了(通过把同宽度的信封高度按逆序排列)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for i in range(len(nums)):
idx = bisect.bisect_left(dp, nums[i])
if idx == len(dp):
dp.append(nums[i])
else:
dp[idx] = nums[i]
return len(dp)

def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
envelopes.sort(key=lambda x:(x[0], -x[1]))
return self.lengthOfLIS([x[1] for x in envelopes])

欢迎来我的博客: https://codeplot.top/
我的博客刷题分类:https://codeplot.top/categories/%E5%88%B7%E9%A2%98/

Leetcode 300. 最长上升子序列 Longest Increasing Subsequence

目录
  1. 动态规划 O(n^2)
  2. 保存每个长度的序列的尾部元素

https://leetcode-cn.com/problems/longest-increasing-subsequence/

动态规划 O(n^2)

1
2
3
4
5
6
7
8
9
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

保存每个长度的序列的尾部元素

tail[i] 代表长度 i + 1 的子序列的最后一个元素,最小可能是几。

理解对 tail 数组的更新:
如果当前数大于 tail 中最后一位,那么 tail 长度可以加一,新的最长序列的尾部元素自然就是当前的数

如果当前数不大于,虽然不能延伸最长序列,但是可能能降低前面的尾部元素的大小,可以找到前面第一个大于该数的尾部元素,把它替换掉。

第一种写法仍是 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
tail = [0] * len(nums)
tail[0] = nums[0]
max_l = 0
for i in range(1, len(nums)):
if nums[i] > tail[max_l]:
tail[max_l+1] = nums[i]
max_l += 1
else:
for j in range(max_l, -1, -1):
if nums[i] > tail[j]:
break
if tail[j] < nums[i]:
tail[j+1] = nums[i]
else:
tail[j] = nums[i]
return max_l+1

第二种写法,加入二分搜索,时间复杂度降为 O(nlogn)

这里使用了 bisect 库中的二分搜索,(但是不能用二分插入,因为这里要替换) bisect 库介绍
其他使用 bisect 库的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
tail = [0] * len(nums)
tail[0] = nums[0]
max_l = 0
for i in range(1, len(nums)):
if nums[i] > tail[max_l]:
tail[max_l+1] = nums[i]
max_l += 1
else:
idx = bisect.bisect_left(tail[:max_l], nums[i]) # bisect 二分查找
tail[idx] = nums[i]
return max_l+1

Leetcode 1292. 元素和小于等于阈值的正方形的最大边长 - Maximum Side Length Of A Square With Sum Less Than Or Equal To Threshold

目录
  1. 二分搜索
  2. 枚举

题目链接

官方题解提供了两种方法,而且也有详细解释

两个方法的共同的地方是使用前缀数组以 O(1) 时间求任意矩形内元素和。(正方形也是矩形,但这里前缀数组不仅可以求正方形)

第一个方法二分的是正方形的边长,官方题解里说如果直接迭代找会超时。

第二个方法是对迭代的优化,思路就是每次都从当前找到的最大正方形边长开始迭代。

二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
n, m = len(mat), len(mat[0])
P = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]
l, r = 0, min(m,n)
ans = 0
def get_sum(x1, y1, x2, y2):
return P[x2][y2] + P[x1][y1] - P[x1][y2] - P[x2][y1]
while l <= r:
mid = (l+r) >> 1
find = any(get_sum(i, j, i+mid, j+mid)<=threshold for i in range(0, n-mid+1) for j in range(0, m-mid+1))
if find:
ans = max(ans, mid)
l = mid+1
else:
r = mid-1
return ans

枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
n, m = len(mat), len(mat[0])
P = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]
ans = 0
#for p in P: print(p)
def get_sum(x1, y1, x2, y2):
return P[x2][y2] + P[x1][y1] - P[x1][y2] - P[x2][y1]
i = 0
while i < n - ans:
j = 0
while j < m - ans:
k = ans + 1
while i + k <= n and j + k <= m:
if get_sum(i, j, i+k, j+k) <= threshold:
ans = k
else:
break
k += 1
j += 1
i += 1
return ans

Leetcode 91. 解码方法 Decode Ways

目录
  1. 递归解法
  2. 动态规划

https://leetcode-cn.com/problems/decode-ways/

递归解法

不用 functools.lru_cache 会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import functools
class Solution:
@functools.lru_cache()
def numDecodings(self, s: str) -> int:
if len(s) == 0 or s[0] == '0':
return 0
if len(s) == 1:
return 1
if len(s) == 2:
x = 2 if (s[0] == '1' or s[0] == '2' and s[1] < '7') else 1
if s[1] == '0': x -= 1
return x
x = self.numDecodings(s[1:])
if s[0] == '1' or s[0] == '2' and s[1] < '7':
x += self.numDecodings(s[2:])
return x

如果 s 以 0 开头则无法解码,返回 0
(如果 s 不以 0 开头) s 长度为 1 返回 1
长度为 2,有四种情况:既可以作为两个一位数字(都不是 0),也可以作为两位数字,例如 ‘12’。只能作为两个数字,如 ‘32’。只能作为一个两位数,只有两种情况 ‘10’ 、‘20’。无法解析,如 ‘30’。

然后如果长度大于 2 则可以尝试把字符串分成:
第一位和后面的
前两位和后面的(需要前两位构成的数字在 1 - 26 范围内)

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def numDecodings(self, s: str) -> int:
l = len(s)
if l == 0 or s[0] == '0': return 0
if l == 1: return 1
dp = [0] * l
dp[0] = 1
dp[1] = 2 if s[0] == '1' or s[0] == '2' and s[1] < '7' else 1
if s[1] == '0': dp[1] -= 1
print(dp)
for i in range(2, l):
if s[i] != '0':
dp[i] += dp[i-1]
if s[i-1] == '1' or s[i-1] == '2' and s[i] < '7':
dp[i] += dp[i-2]
return dp[-1]

dp[i] 有两种情况:
前一个如果不是 0 就可以累加前一个的值,
如果前一个加当前的值大于 0 且小于 27 可以累加前一个的前一个的值。

leetcode 89. 格雷编码 Gray Code

目录
  1. 搜索
  2. 镜像法
  3. 公式法

https://leetcode-cn.com/problems/gray-code/

我自己写的是第一种方法,又总结了题解中看到的两种方法

搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def grayCode(self, n: int) -> List[int]:
f = [False] * (2 ** n)
f[0] = True
r = [0]
def dfs(x):
if len(r) == 2 ** n: return
cur = 1
for i in range(n):
if x & cur:
if not f[x-cur]:
f[x-cur] = True
r.append(x-cur)
dfs(x-cur)
return
else:
if not f[x|cur]:
f[x|cur] = True
r.append(x|cur)
dfs(x|cur)
return
cur <<= 1
dfs(0)
return r

镜像法

出自题解 https://leetcode-cn.com/problems/gray-code/solution/gray-code-jing-xiang-fan-she-fa-by-jyd/

n + 1 的答案是 n 的答案复制两份,一上一下拼起来,上面的最高位补 0 (实际上就是不变)下面最高为补 1,并倒序。

1
2
3
4
5
6
7
8
class Solution:
def grayCode(self, n: int) -> List[int]:
if n == 0:
return [0]
if n == 1:
return [0, 1]
r = self.grayCode(n-1)
return r + [r[i] + (1<<n-1) for i in range(len(r)-1,-1,-1)]

公式法

这个就更强了,方法出自 https://leetcode-cn.com/problems/gray-code/solution/ge-lei-ma-shu-xue-xing-zhi-by-world-16/

直接根据公式算出来了:

gray_code\[i\] = (i >> 1) ^ i

1
2
3
class Solution:
def grayCode(self, n: int) -> List[int]:
return [(i>>1)^i for i in range(2**n)]

dd 命令把 iso 镜像写入 u 盘

目录
  1. 查看 U 盘
  2. umount U 盘
  3. 格式化 U 盘
  4. 写入镜像

查看 U 盘

1
sudo fdisk -l

Disk /dev/sdc:14.43 GiB,15483273216 字节,30240768 个扇区
磁盘型号:DataTraveler 2.0
单元:扇区 / 1 * 512 = 512 字节
扇区大小(逻辑/物理):512 字节 / 512 字节
I/O 大小(最小/最佳):512 字节 / 512 字节
磁盘标签类型:dos
磁盘标识符:0x2f10bd40

设备 启动 起点 末尾 扇区 大小 Id 类型
/dev/sdc1 * 0 1736703 1736704 848M 0 空
/dev/sdc2 1295064 1299991 4928 2.4M ef EFI (FAT-12/16/32)

里面原本是一个 Ubuntu Server 系统

umount U 盘

1
sudo umount /dev/sdc*

格式化 U 盘

1
sudo mkfs.vfat /dev/sdc -I

写入镜像

1
sudo dd if=manjaro.iso of=/dev/sdc

blockstream.info 检测 coinjoin 方法分析与复现

目录
  1. 一些弯路
    1. 用 google 搜索 blockstream.info 中的 coinjoin

比特币 wiki 对 coinjoin 的解释:https://en.bitcoin.it/wiki/CoinJoin

bitcoinops 的 coinjoin 主题:https://bitcoinops.org/en/topics/coinjoin/

因为毕业论文涉及到混币,搜集了一些关于混币的资料。其中 blockstream.info 这个区块链浏览器中,对于比特币交易会有一个隐私判断,其中有一条:是否疑似为 coinjoin。本文分析了他的策略。

image.png

一开始我认为这个数据一定是存储在后端。

所以对页面请求进行了分析,blockstream 是 restful 的(API 文档),前端开源

结果发现 coinjoin 判断的逻辑在前端。到 github 仓库一搜 coinjoin 马上找到源码位置:

https://github.com/Blockstream/esplora/blob/e8ab97c60a40ac92a558f227af0a3b1f30aca079/client/src/lib/privacy-analysis.js

具体代码就是:

1
2
3
4
5
6
7
8
9
const counter = (T={}) => key => T[key] = (T[key] || 0) + 1

// Detect transactions that looks like equal-output CoinJoin
// checks if more than N outputs are of the same size, where N is half the
// number of outputs capped between 2 and 5
const isCoinJoinLike = tx => {
const inc = counter(), target = Math.min(Math.max(tx.vout.length/2|0, 2), 5)
return tx.vin.length > 1 && tx.vout.some(out => inc(out.value) >= target)
}

又把它改成了适用于 bcoin 数据格式的 python 版本。

一些弯路

用 google 搜索 blockstream.info 中的 coinjoin

因为最开始以为数据是后端生成的,所以有了这个操作。

使用 google 搜索 site:blockstream.info coinjoin 找到了 77 个页面,都是混币交易的页面,例如:

1
2
3
4
5
https://blockstream.info/tx/c5896168e962fde53575cc63451691356693bcd60cb6e12ceaa06a7c8d09bdc0?expand
https://blockstream.info/tx/e4a789d16a24a6643dfee06e018ad27648b896daae6a3577ae0f4eddcc4d9174
https://blockstream.info/tx/f82206145413db5c1272d5609c88581c414815e36e400aee6410e0de9a2d46b5
https://blockstream.info/tx/a7157780b7c696ab24767113d9d34cdbc0eba5c394c89aec4ed1a9feb326bea5
https://blockstream.info/tx/ef329b3ed8e790f10f0b522346f1b3d9f1c9d45dfa5b918e92d6f0a25d91c7ce

我写了一个小脚本粘贴到浏览器 console 里可以输出谷歌搜索结果的 url

1
2
3
4
let gs = document.getElementsByClassName('g');
for (let i = 0; i < gs.length; i++) {
console.log(gs[i].children[0].children[0].children[0].children[0].href)
}

leetcode 497. 非重叠矩形中的随机点 random point in non overlapping rectangles - python

目录

https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles/

这道题目很独特,要求返回随机的答案,应该是通过检查答案分布情况来判断是否通过。

因为前提是所有矩形不重合。所以可以分为两步做,第一步是随机选择矩形,第二步则是在矩形上随机选点。

难点在于如何高效的随机选择矩形。可以计算每个矩形的点数,然后做一个累加的数组,数组第一位是第一个矩形的点数,第 n 位是前 n 个矩形的点数和。

然后从 0 到面积和取随机数,看落到那个矩形上,就选哪个矩形。可以使用二分搜索提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import bisect
class Solution:

def __init__(self, rects: List[List[int]]):
self.r = rects
self.p = []
cur = 0
for r in rects:
cur += (abs(r[2] - r[0])+1) * (abs(r[3] - r[1])+1)
self.p.append(cur)

def pick(self) -> List[int]:
c = random.randint(0, self.p[-1]-1)
i = bisect.bisect(self.p, c)
x = random.randint(self.r[i][0], self.r[i][2])
y = random.randint(self.r[i][1], self.r[i][3])
return [x, y]