我的博客

pytorch 基本用法:Kmeans

目录
  1. 两个类别
    1. sklearn 版本
    2. pytroch 版本
  2. 多类别,测试不同 K 值
    1. 生成数据
    2. 测试不同 k 值的分数
      1. K = 2
      2. K = 3
      3. K = 4
      4. K = 5
  3. 更多的类
1
torch.__version__

‘1.3.1+cpu’

两个类别

1
2
3
4
5
6
7
8
9
10
n_data = torch.ones(100, 2)
xy0 = torch.normal(2 * n_data, 1) # 生成均值为2,2 标准差为1的随机数组成的矩阵 shape=(100, 2)
c0 = torch.zeros(100)
xy1 = torch.normal(-2 * n_data, 1) # 生成均值为-2,-2 标准差为1的随机数组成的矩阵 shape=(100, 2)
c1 = torch.ones(100)
X = torch.cat((xy0, xy1), 0)
c = torch.cat((c0,c1), 0)
plt.scatter(X[:,0],X[:,1], c=c, s=100, cmap='RdYlGn')
plt.show()
X.shape

数据分布

torch.Size([200, 2])

sklearn 版本

1
2
3
4
5
6
7
8
9
from sklearn.cluster import KMeans
from sklearn import metrics
kmeans = KMeans(n_clusters=2)
y_pred = kmeans.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred, s=20)
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], c='red', s=80, alpha=.8)
plt.show()
# 查看聚类中心,并用 Calinski-Harabasz Index 评估聚类分数
kmeans.cluster_centers_, metrics.calinski_harabasz_score(X, y_pred)

预测结果

红点代表聚类中心

(array([[ 2.18905603, 1.94598238],
[-2.10763696, -1.98111874]]), 864.2674279012733)

pytroch 版本

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 代码修改自 https://www.jianshu.com/p/1c000d9296ae
class KMEANS:
def __init__(self, n_clusters=20, max_iter=None, verbose=True,device = torch.device("cpu")):
self.n_cluster = n_clusters
self.n_clusters = n_clusters
self.labels = None
self.dists = None # shape: [x.shape[0],n_cluster]
self.centers = None
self.variation = torch.Tensor([float("Inf")]).to(device)
self.verbose = verbose
self.started = False
self.representative_samples = None
self.max_iter = max_iter
self.count = 0
self.device = device

def fit_predict(self, x):
# 随机选择初始中心点,想更快的收敛速度可以借鉴sklearn中的kmeans++初始化方法
init_row = torch.randint(0, x.shape[0], (self.n_clusters,)).to(self.device)
init_points = x[init_row]
self.centers = init_points
while True:
# 聚类标记
self.nearest_center(x)
# 更新中心点
self.update_center(x)
if self.verbose:
print(self.variation, torch.argmin(self.dists, (0)))
if torch.abs(self.variation) < 1e-3 and self.max_iter is None:
break
elif self.max_iter is not None and self.count == self.max_iter:
break

self.count += 1

self.representative_sample()
return self.labels

def nearest_center(self, x):
labels = torch.empty((x.shape[0],)).long().to(self.device)
dists = torch.empty((0, self.n_clusters)).to(self.device)
for i, sample in enumerate(x):
dist = torch.sum(torch.mul(sample - self.centers, sample - self.centers), (1))
labels[i] = torch.argmin(dist)
dists = torch.cat([dists, dist.unsqueeze(0)], (0))
self.labels = labels
if self.started:
self.variation = torch.sum(self.dists - dists)
self.dists = dists
self.started = True

def update_center(self, x):
centers = torch.empty((0, x.shape[1])).to(self.device)
for i in range(self.n_clusters):
mask = self.labels == i
cluster_samples = x[mask]
centers = torch.cat([centers, torch.mean(cluster_samples, (0)).unsqueeze(0)], (0))
self.centers = centers

def representative_sample(self):
# 查找距离中心点最近的样本,作为聚类的代表样本,更加直观
self.representative_samples = torch.argmin(self.dists, (0))

结果:

1
2
3
4
5
6
7
8
9
device = torch.device('cpu')
k = KMEANS(n_clusters=2, max_iter=10,verbose=False,device=device)
y_pred = k.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred, s=20)
plt.scatter(k.centers[:, 0], k.centers[:, 1], c='red', s=80, alpha=.8)
representative_samples = x
plt.scatter(X[k.representative_samples][:, 0], X[k.representative_samples][:, 1], c='blue', s=80, alpha=.8)
plt.show()
k.centers, X[k.representative_samples] , metrics.calinski_harabasz_score(X, y_pred)

image.png

红点是聚类的中心,蓝点是该类别距离中心最近的点。

(tensor([[-2.1076, -1.9811],
[ 2.1891, 1.9460]]), tensor([[-2.1868, -2.1051],
[ 2.2467, 1.8789]]), 864.2674279012733)

多类别,测试不同 K 值

生成数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import torch
import matplotlib.pyplot as plt


n_data = torch.ones(100, 2)
xy0 = torch.normal(2 * n_data, 1)
xy1 = torch.normal(-2 * n_data, 1)
xy2 = torch.normal(n_data * torch.tensor([-6, -1]), 1)
xy3 = torch.normal(n_data * 5, 1)
X = torch.cat((xy0, xy1, xy2, xy3), 0)
c = torch.tensor([0]*100+[1]*100+[2]*100+[3]*100)
plt.scatter(X[:,0],X[:,1], c=c, s=20, cmap='RdYlGn')
plt.show()
X.shape

image.png

torch.Size([400, 2])

测试不同 k 值的分数

先上结果

K 值 calinski_harabasz_score
2 1244.8720900338403
3 1103.8048055745687
4 1631.0687149071816
4(局部最优) 772.2547910253841
5 1342.9573128315687

某些初始值的选择可能使算法陷入局部最优,而无法到达全局最优

K = 2

1
2
3
4
5
6
7
8
9
10
K = 2
device = torch.device('cpu')
k = KMEANS(n_clusters=K, max_iter=10,verbose=False,device=device)
y_pred = k.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred, s=20)
plt.scatter(k.centers[:, 0], k.centers[:, 1], c='red', s=80, alpha=.8)
representative_samples = x
plt.scatter(X[k.representative_samples][:, 0], X[k.representative_samples][:, 1], c='blue', s=80, alpha=.8)
plt.show()
k.centers, X[k.representative_samples] , metrics.calinski_harabasz_score(X, y_pred)

(tensor([[-3.9148, -1.5554],
[ 3.3981, 3.4571]]), tensor([[-3.7091, -1.2708],
[ 3.5593, 3.6728]]), 1244.8720900338403)

image.png

K = 3

K=3

(tensor([[ 4.8847, 4.8983],
[ 1.7364, 1.8475],
[-3.9680, -1.5762]]), tensor([[ 4.8437, 4.8178],
[ 1.8517, 1.6753],
[-4.2247, -1.2751]]), 1103.8048055745687)

K = 4

K=4(局部最优)

(tensor([[ 5.6401, 4.8637],
[ 4.0151, 4.9221],
[ 1.7591, 1.8439],
[-3.9527, -1.5693]]), tensor([[ 5.5032, 4.8176],
[ 4.1500, 4.9420],
[ 1.8517, 1.6753],
[-3.7091, -1.2708]]), 772.2547910253841)

K=4

(tensor([[-1.9604, -2.0495],
[ 4.8847, 4.8983],
[-5.8682, -1.0887],
[ 1.7835, 1.8935]]), tensor([[-2.0173, -2.1479],
[ 4.8437, 4.8178],
[-5.8178, -1.0374],
[ 1.8578, 2.0665]]), 1631.0687149071816)

K = 5

image.png

(tensor([[ 1.7743, 1.8489],
[-5.8682, -1.0887],
[ 3.9343, 4.8072],
[ 5.5917, 4.9437],
[-1.9604, -2.0495]]), tensor([[ 1.8517, 1.6753],
[-5.8178, -1.0374],
[ 3.8467, 4.7662],
[ 5.5032, 4.8176],
[-2.0173, -2.1479]]), 1342.9573128315687)

更多的类

1
2
3
4
5
6
7
8
N, D, K = 10000, 2, 50
x = torch.randn(N, D) / 6 + .5
kmeans = KMeans(n_clusters=50)
y_pred = kmeans.fit_predict(x)
plt.figure(figsize=(8,8))
plt.scatter(x[:, 0].cpu(), x[:, 1].cpu(), c=y_pred, s= 30000 / len(x), cmap="tab10")
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], c='black', s=50, alpha=.8)
plt.axis([0,1,0,1]) ; plt.tight_layout() ; plt.show()

image.png

参考:

https://www.jianshu.com/p/1c000d9296ae

https://www.jianshu.com/p/4902096f6d4b

https://www.kernel-operations.io/keops/_auto_tutorials/kmeans/plot_kmeans_torch.html

复现 elliptic 数据集去匿名

目录
  1. 载入数据
  2. 根据 edgelist 统计出度入度
  3. 查看特征与入度的关系
  4. 分析 local feature 3
  5. 推测 lf_0、lf_1、 lf_3、 lf_4、 lf_5、 lf_13 的含义
  6. 寻找真实交易

系列文章:

复现 Elliptic Data Set 的分类算法(在 Kaggle 上)

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

Elliptic Data Set 椭圆比特币交易数据集

参考:

BenZik 提出的去匿名化方案:

  1. 去匿名化后的结果:https://www.kaggle.com/alexbenzik/deanonymized-995-pct-of-elliptic-transactions
  2. 在 elliptic 数据集后的讨论:https://www.kaggle.com/ellipticco/elliptic-data-set/discussion/117862
  3. 介绍实现过程的博客(俄语):https://habr.com/ru/post/479178/

我通过借助翻译,根据 BenZ 博客上的介绍,在原数据集上做了实验,基本复现了这个过程。

载入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pandas as pd
import seaborn as sns
from matplotlib import pyplot as plt

import plotly.offline as py
import plotly.graph_objs as go
from sklearn.model_selection import train_test_split
from sklearn.metrics import precision_recall_fscore_support
from sklearn.metrics import f1_score

df_classes = pd.read_csv('/kaggle/input/elliptic-data-set/elliptic_bitcoin_dataset/elliptic_txs_classes.csv')
df_features = pd.read_csv('/kaggle/input/elliptic-data-set/elliptic_bitcoin_dataset/elliptic_txs_features.csv', header=None)
df_edgelist = pd.read_csv('/kaggle/input/elliptic-data-set/elliptic_bitcoin_dataset/elliptic_txs_edgelist.csv')

df_classes.shape, df_features.shape, df_edgelist.shape,

((203769, 2), (203769, 167), (234355, 2))

1
2
3
df_features.columns = ['id', 'time step'] + [f'trans_feat_{i}' for i in range(93)] + [f'agg_feat_{i}' for i in range(72)]
df_features = pd.merge(df_features, df_classes, left_on='id', right_on='txId', how='left')
df_features['class'] = df_features['class'].apply(lambda x: '0' if x == "unknown" else x)

根据 edgelist 统计出度入度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 统计入度出度
import collections
in_d = collections.Counter()
out_d = collections.Counter()
for i in range(df_edgelist.shape[0]):
s, d = df_edgelist.iloc[i]
in_d[d] += 1
out_d[s] += 1
print(len(in_d), len(out_d))
# 把入度、出度加入特征
i_d = []
o_d = []
for i in range(df_features.shape[0]):
i_d.append(in_d[df_features.iloc[i]['id']])
o_d.append(out_d[df_features.iloc[i]['id']])
df_features['i_d'] = i_d
df_features['o_d'] = o_d
len(i_d), len(o_d)

148447 166345
(203769, 203769)

顺便检验一下是否有跨过时间步的边

1
2
3
4
5
6
7
8
9
10
# 检查是否有跨时间步的边
# 构建 id 到 时间步的映射
id2time_step = {}
for i in range(df_features.shape[0]):
id2time_step[df_features.iloc[i]['id']] = df_features.iloc[i]['time step']
for i in range(df_edgelist.shape[0]):
s, d = df_edgelist.iloc[i]
if id2time_step[s] != id2time_step[d]:
print(i, s, d)
# 结果是:没有

查看特征与入度的关系

1
2
plt.figure(figsize=(15,10))
plt.bar([f'lf_{i}' for i in range(20)],df_features[[f'trans_feat_{i}' for i in range(20)]].corrwith(df_features['i_d']))

入度和部分特征的关系

lf 指的是 local feature,实际上就是 trans_feat_。

这里 lf_3 是俄文博客里说的 V6,因为他的 V 从 1 开始编号,而 lf 从 0 开始,而且 V1 是 id,V2 是时间步。

博客里提到 cor(in-degree,V6) = 0.589,

我这里的结果是:0.508025。有一些差异,还没有弄清楚原因。

1
2
3
4
plt.figure(figsize=(10,10))
plt.axes()
#plt.scatter(df_features['trans_feat_3'] - df_features['trans_feat_3'].min(), df_features['i_d'])
plt.loglog(df_features['trans_feat_3'] - df_features['trans_feat_3'].min(), df_features['i_d'] , '.')

lf3 和入度的双对数坐标图

分析 local feature 3

1
2
3
4
5
6
7
8
9
10
tf3cnt = collections.Counter(df_features['trans_feat_3'])
l = list(tf3cnt.items())
l.sort()
diff_trans_feat_3 = []
for i in range(1, len(l)):
diff_trans_feat_3.append(l[i][0] - l[i-1][0])
dtf3cnt = collections.Counter(['%.5f' % x for x in diff_trans_feat_3])
dtf3list = list(dtf3cnt.items())
dtf3list.sort()
dtf3list

[(‘0.07504’, 202),
(‘0.15008’, 36),
(‘0.22511’, 20),
(‘0.30015’, 9),
(‘0.37519’, 10),
(‘0.45023’, 4),
(‘0.52526’, 3),
(‘0.60030’, 3),
(‘0.67534’, 3),
(‘0.75038’, 2),
(‘0.82541’, 2),
(‘1.05053’, 1),
(‘1.12556’, 1),
(‘1.65083’, 1),
(‘1.72586’, 2)]

这个就是博客中的那个表格

lf3 差值(间隔) 出现次数 差值/0.07504
0.07504 202 1
0.15008 36 2
0.22511 20 3
0.30015 9 4
0.37519 10 5
0.45023 4 6
0.52526 3 7
0.6003 3 8
0.67534 3 9
0.75038 2 10
0.82541 2 11
1.05053 1 14
1.12556 1 15
1.65083 1 22
1.72586 2 23

推测 lf_0、lf_1、 lf_3、 lf_4、 lf_5、 lf_13 的含义

input_count_lf3 = (lf3- min(lf3)) / min(diff_lf3)+ 1。

对lf_4,lf_5,lf_13进行类似分析后:

  • input_count_lf3 = 13.3266685112665 * lf3 + 2.62544842444139,
  • input_unique_count_lf5 = 11.9243179897452 * lf5 + 2.34747189219164,
  • outputs_count_lf4 = 50.3777694891647 * lf4 + 4.21030186142152,
  • outputs_unique_count_lf13 = 49.3957564403755 * lf13 + 4.121809499973
  • fee_lf1 = 81341.4537626213 + 386323.710952989 * lf1,
  • total_out_value_lf0 = 2742460603.92287 + 15853961614.9796 * lf0
  • 近似时间= 1450468509.80488 + 1155672.19512195 * elliptic_time

寻找真实交易

根据以上信息可以找到 92.9% 的交易的真实 txid。然后通过图信息,可以再找到 6.6%。

一共找到了 99.5 % 的交易也就是:Elliptic Data 一共 203769 个交易中的 202805 个。有 965 个是未确定的。

dataframe 参考:

https://www.jianshu.com/p/8024ceef4fe2

复现 Elliptic Data Set 的分类算法(在 Kaggle 上)

目录
  1. 载入数据
  2. 数据处理
    1. 时间维度上交易分布
    2. 选取非法和合法交易
  3. 训练和测试模型(使用聚合数据)
    1. 随机森林
    2. 线性回归
  4. 训练和测试模型(不使用聚合数据)
    1. 随机森林
    2. 线性回归

载入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pandas as pd
import seaborn as sns
from matplotlib import pyplot as plt

import plotly.offline as py
import plotly.graph_objs as go
from sklearn.model_selection import train_test_split
from sklearn.metrics import precision_recall_fscore_support
from sklearn.metrics import f1_score

df_classes = pd.read_csv('/kaggle/input/elliptic-data-set/elliptic_bitcoin_dataset/elliptic_txs_classes.csv')
df_features = pd.read_csv('/kaggle/input/elliptic-data-set/elliptic_bitcoin_dataset/elliptic_txs_features.csv', header=None)
df_edgelist = pd.read_csv('/kaggle/input/elliptic-data-set/elliptic_bitcoin_dataset/elliptic_txs_edgelist.csv')

df_classes.shape, df_features.shape, df_edgelist.shape,
1
2
> ((203769, 2), (203769, 167), (234355, 2))
>

df_features 中有 166 个特征,第一列是交易 id(是 int 类型,不是链上真实的 txid),第二列是 time setp,然后是 93 个自身特征和 72 个聚合特征。

交易数量是 20 万零 3 千。边数是 23 万零 4 千。

数据处理

df_features 没有表头,先加上表头

1
df_features.columns = ['id', 'time step'] + [f'trans_feat_{i}' for i in range(93)] + [f'agg_feat_{i}' for i in range(72)]

查看时间步的分布:

1
df_features['time step'].value_counts().sort_index()
1
2
3
4
5
6
7
8
9
10
11
> 1     7880
> 2 4544
> 3 6621
> 4 5693
> ...
> 46 3519
> 47 5121
> 48 2954
> 49 2454
> Name: time step, dtype: int64
>

是从 1 到 49。

再看类别分布

1
df_classes['class'].value_counts()
1
2
3
4
5
> unknown    157205
> 2 42019
> 1 4545
> Name: class, dtype: int64
>

把特征和类别合起来

1
df_features = pd.merge(df_features, df_classes, left_on='id', right_on='txId', how='left')

把类别都统一为数字

1
df_features['class'] = df_features['class'].apply(lambda x: '0' if x == "unknown" else x)

时间维度上交易分布

1
2
3
4
5
#plt.figure(figsize=(12, 8))
grouped = df_features.groupby(['time step', 'class'])['id'].count().reset_index().rename(columns={'id': 'count'})
sns.lineplot(x='time step', y='count', hue='class', data=grouped);
plt.legend(loc=(1.0, 0.8));
plt.title('Number of transactions in each time step by class');

image.png

条形图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
count_by_class = df_features[["time step",'class']].groupby(['time step','class']).size().to_frame().reset_index()
illicit_count = count_by_class[count_by_class['class'] == '1']
licit_count = count_by_class[count_by_class['class'] == '2']
unknown_count = count_by_class[count_by_class['class'] == "0"]

x_list = list(range(1,50))
fig = go.Figure(data = [
go.Bar(name="Unknown",x=x_list,y=unknown_count[0],marker = dict(color = 'rgba(120, 100, 180, 0.6)',
line = dict(
color = 'rgba(120, 100, 180, 1.0)',width=1))),
go.Bar(name="Licit",x=x_list,y=licit_count[0],marker = dict(color = 'rgba(246, 78, 139, 0.6)',
line = dict(
color = 'rgba(246, 78, 139, 1.0)',width=1))),
go.Bar(name="Illicit",x=x_list,y=illicit_count[0],marker = dict(color = 'rgba(58, 190, 120, 0.6)',
line = dict(
color = 'rgba(58, 190, 120, 1.0)',width=1)))
])
fig.update_layout(barmode='stack')
py.iplot(fig)

image.png

选取非法和合法交易

1
2
data = df_features[(df_features['class']=='1') | (df_features['class']=='2')]
data.shape
1
2
> (46564, 169)
>

只有 4 万 6 千。

选取特征

1
2
3
4
5
6
tx_features = [f'trans_feat_{i}' for i in range(93)]
agg_features = [f'agg_feat_{i}' for i in range(72)]

X = data[tx_features+agg_features]
y = data['class']
y = y.apply(lambda x: 0 if x == '2' else 1 )

分割测试集和训练集

1
X_train, X_test, y_train, y_test = train_test_split(X,y,test_size=0.3,random_state=15,shuffle=False)

训练和测试模型(使用聚合数据)

随机森林

1
2
3
4
5
6
7
8
9
from sklearn.ensemble import RandomForestClassifier
clf = RandomForestClassifier(n_estimators=50, max_depth=100,random_state=15).fit(X_train,y_train)
preds = clf.predict(X_test)

prec,rec,f1,num = precision_recall_fscore_support(y_test,preds, average=None)
print("Random Forest Classifier")
print("Precision:%.3f \nRecall:%.3f \nF1 Score:%.3f"%(prec[1],rec[1],f1[1]))
micro_f1 = f1_score(y_test,preds,average='micro')
print("Micro-Average F1 Score:",micro_f1)
1
2
3
4
5
6
> Random Forest Classifier
> Precision:0.981
> Recall:0.651
> F1 Score:0.782
> Micro-Average F1 Score: 0.9772369362920544
>

线性回归

1
2
3
4
5
6
7
8
from sklearn.linear_model import LogisticRegression
reg = LogisticRegression().fit(X_train,y_train)
preds = reg.predict(X_test)
prec,rec,f1,num = precision_recall_fscore_support(y_test,preds, average=None)
print("Logistic Regression")
print("Precision:%.3f \nRecall:%.3f \nF1 Score:%.3f"%(prec[1],rec[1],f1[1]))
micro_f1 = f1_score(y_test,preds,average='micro')
print("Micro-Average F1 Score:",micro_f1)
1
2
3
4
5
6
> Logistic Regression
> Precision:0.454
> Recall:0.633
> F1 Score:0.529
> Micro-Average F1 Score: 0.928990694345025
>

训练和测试模型(不使用聚合数据)

1
2
3
4
X = data[tx_features]#+agg_features]
y = data['class']
y = y.apply(lambda x: 0 if x == '2' else 1 )
X_train, X_test, y_train, y_test = train_test_split(X,y,test_size=0.3,random_state=15,shuffle=False)
1
2
> ((32594, 93), (13970, 93))
>

随机森林

1
2
3
4
5
6
> Random Forest Classifier
> Precision:0.909
> Recall:0.648
> F1 Score:0.757
> Micro-Average F1 Score: 0.9738010021474588
>

线性回归

1
2
3
4
5
6
> Logistic Regression
> Precision:0.433
> Recall:0.653
> F1 Score:0.521
> Micro-Average F1 Score: 0.9243378668575519
>

参考:

https://www.kaggle.com/dhruvrnaik/illicit-transaction-detection

https://www.kaggle.com/artgor/elliptic-data-eda/

识别 coinjoin 交易

目录
  1. Meiklejohn S , Orlandi C . Privacy-Enhancing Overlays in Bitcoin[J]. 2015.
  2. F. K. Maurer, T. Neudecker and M. Florian, “Anonymous CoinJoin Transactions with Arbitrary Values,” 2017 IEEE Trustcom/BigDataSE/ICESS, Sydney, NSW, 2017, pp. 522-529.
  3. SharedCoin
    1. 对 SharedCoin 的分析
  4. JoinMarket

之前文章介绍过 blockstream.info 检测 coinjoin 方法分析与复现

这里我再根据其他文章总结一些识别 coinjoin 交易的方法。

Meiklejohn S , Orlandi C . Privacy-Enhancing Overlays in Bitcoin[J]. 2015.

提出一种 pattern:拥有 5 个以上 inputs 和 5 个以上 outputs 的交易。论文认为,这种交易和 coinjoin 是大致(roughly)相关的。

2013年8月之前,每个区块平均零个这样的交易,但之后数字在稳步增长:先是2013年12月平均每个区块两个匹配交易,然后在2014年3月达到峰值14个,最后在2014年7月达到平均10个匹配交易,此后一直保持不变。

文中定义了一个污染的概念,一个交易有 n 个输入,m 个输出,那么,输出的比特币(UTXO)就被输入污染了。污染只对于混币交易才有意义。

F. K. Maurer, T. Neudecker and M. Florian, “Anonymous CoinJoin Transactions with Arbitrary Values,” 2017 IEEE Trustcom/BigDataSE/ICESS, Sydney, NSW, 2017, pp. 522-529.

提出了对 coinjoin 的改进 https://ieeexplore.ieee.org/document/8029483

SharedCoin

Blockchain.info 发布自己的 CoinJoin 实现 SharedCoin,作为其钱包服务的一部分。

SharedCoin 于 2013 年 9 月至 2013 年 10 月之间发布,[7]。SharedCoin的源代码于2013年12月22日首次公开发布到其 GitHub 上但是现在已经被删了。在Coin Validation计划有意颠覆整个比特币隐私的计划之后,Blockchain.info宣布2013年11月17日将免费提供SharedCoin [9]。

https://github.com/blockchain/

对 SharedCoin 的分析

Kristov Atlas 发布的 coinjoin-sudoku 是专门用于分析 SharedCoin(coinjoin) 交易的开源工具(https://github.com/kristovatlas/coinjoin-sudoku)

主页是:http://www.coinjoinsudoku.com/

这个网站上还有一个对于 CoinJoin 弱点的论述:http://www.coinjoinsudoku.com/advisory/

这是来自区块链的SX的CoinJoin交易之一的示例:

交易哈希:9256332b9ca52cbcb06f57296dfd982d8da3f7d4696b4c10cf9bb93dae6edf58日期
:2013-08-27 06:55:31

输入#1:来自地址1MzpcbFKrR4g9wyu1wBKGApyktsf4wteDe的0.0101 BTC
输入#2:来自地址18oXQcw6gyGbTq3VrKAJQN2zZ2giTbrUu8来自地址的0.0101 BTC
输入#3:来自地址17PU5P2Qy3bdNb的0.0101 BTC

输出#1:指向地址1Fufjpf9RM2aQsGedhSpbSCGRHrmLMJ7yY的0.01 BTC
输出#2:指向地址1Evy47MqD82HGx6n1KHkHwBgCwbsbQQT8m的地址0.01BTC
输出#3:指向地址18f5VuUggss5HL7d7Lh

在此交易中,三个不同的用户(或一个使用SX客户端的三个实例的用户)提供了0.0101 BTC作为交易的输入。交易结束时,三个地址收到0.01 BTC。剩余的0.0003 BTC被用作矿工的费用,以使交易迅速被网络确认。因为所有输入量都是相同的(0.0101 BTC)并且所有输出量都是相同的(0.01 BTC),所以这是一个完美的CoinJoin标本,因为该量没有泄漏有关0.01 BTC输出中的哪个对应于哪个BTC输出的信息。 0.0101 BTC输入。他们每个人拥有共同所有权的机会是三分之一。

扩展阅读:

该作者还有一个专门介绍暗网和黑市的新闻节目(http://darknews.tv/,目前已经不能访问)

https://www.scribd.com/document/227369807/Bitcoin-Coinjoin-Not-Anonymous-v01

Blockchain’s SharedCoin Users Can Be Identified, Says Security Expert

比特币隐私加固 — CoinJoin 技术简析

JoinMarket

混币类型介绍

目录
  1. 混币类型
    1. Mixcoin
    2. CoinJoin
    3. CoinShuffle
    4. CoinSwap/Fair Exchange
    5. Altcoins
    6. CoinParty
    7. Blindcoin
  2. 混币服务提供者
  3. 安全性
  4. 被盗币
  5. 参考

混币类型

Mixcoin

缺点是混币服务提供者知道混币的情况。

提出: Bonneau, J., Narayanan, A., Miller, A., Clark, J., Kroll, J.A., Felten, E.W.: Mixcoin: anonymity for bitcoin with accountable mixes. IACR Cryptology ePrint Archive, 2014:77 (2014)

CoinJoin

一种去中心化的混币方法。最开始的 coinjoin 需要中心服务器来帮助参与者同步信息,同时他能获取到混币的细节。后来有一些 coinjoin 的改进版本不再需要中心服务器。

优点:多个参加混币的人要共同签名一个联合交易。不存在盗币风险,因为对于每个用户只有他同意这个交易的时候,用户才会给他签名。每个用户都签名了交易才生效。

缺点:容易被 Dos 攻击。恶意用户假装参加混币,但是最后不签名导致混币失败。

coinjoin 客户端: https://github.com/JoinMarket-Org/joinmarket-clientserver

出处: Maxwell, G.: Coinjoin: Bitcoin privacy for the real world, August 2013. https:// bitcointalk.org/index.php?topic=279249

CoinShuffle

基于 CoinJoin。拥有排除故意终止混币交易的恶意攻击者的机制。但是易于受到 Sybil attack 攻击。

提出:Ruffing, T., Moreno-Sanchez, P., Kate, A.: Practical decentralized coin mixing for bitcoin. HotPETS, Coinshuffle, July 2014

CoinSwap/Fair Exchange

Coinswap, October 2013. https://bitcointalk.org/index.php?topic=321228

Barber, S., Boyen, X., Shi, E., Uzun, E.: Bitter to better — how to make bitcoin a better currency. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 399–414. Springer, Heidelberg (2012)

Altcoins

Altcoins 的意思是其他的代替币。意思是先把比特币换成别的币,再把别的币换成比特币。

CoinParty

去中心化的混币。

提出:Ziegeldorf J H , Grossmann F , Henze M , et al. CoinParty: Secure Multi-Party Mixing of Bitcoins[C]// The Fifth ACM Conference on Data and Application Security and Privacy (CODASPY 2015). ACM, 2015.

Blindcoin

基于 Mixcoin。但是可以阻止混币服务提供者获取到用户资金信息。

提出: Valenta L , Rowan B . Blindcoin: Blinded, Accountable Mixes for Bitcoin[C]// International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2015.

混币服务提供者

Bitcoin fog. http://www.bitcoinfog.com/

Bitlaundry. http://app.bitlaundry.com/

Bitmixer.io. https://bitmixer.io/

安全性

被盗币

有 Bitcoin Fog 用户表示它们被盗币 The current state of coin-mixing services. http://www.thebitcoinreview.com/site.php?site_id=759

混币被检测

参考

[1] Valenta L , Rowan B . Blindcoin: Blinded, Accountable Mixes for Bitcoin[C]// International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2015.
这篇文章提出一种新混币方式,同时介绍了之前存在的混币技术的问题。

[2] Yang, E.Z.: Secure multiparty bitcoin anonymization, July 2013. http://blog.ezyang.com/2012/07/secure-multiparty-bitcoin-anonymization/
提出一种 multiparty sorting protocol

天池通过 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