我的博客

Round A 2020 - Kick Start 2020 - python 版代码

目录
  1. Allocation
  2. Plates
  3. Workout
  4. Bundling
    1. 字典树
    2. 递归(测试数据 2 会超过递归层数限制)

https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7

Allocation

T 组数据,每组两行,第一行 N,B 代表有 N 个待售房屋,你拥有的钱是 B。第二行是 N 个整数,代表每个房屋的价格。
求能购买的最多房屋数量。

1
2
3
4
5
6
7
8
9
10
11
12
T = int(input())
for t in range(T):
N, B = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = 0
for x in a:
if B < x:
break
cnt += 1
B -= x
print('Case #%d: %d' % (t+1, cnt))

Plates

T 组数据。每组数据 N + 1 行:第一行 N, K, P,代表有 N 摞盘子,每摞都是 K 个。一共需要挑出 P 个。后面 N 行每行是 K 个整数代表这摞盘子中每个盘子的颜值,顺序是从上到下。

需要保证挑出的盘子的颜值的和最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
T = int(input())
for t in range(T):
N, K, P = map(int, input().split())
s = []
for _ in range(N):
s.append(list(map(int, input().split())))
for i in range(N):
for j in range(1, K):
s[i][j] += s[i][j-1]
s[i].append(0)
dp = [[0] * (P+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, P+1):
for x in range(0, min(j, K)+1):
dp[i][j] = max(dp[i][j], dp[i-1][j-x] + s[i-1][x-1])
print('Case #%d: %d' % (t+1, dp[N][P]))

Workout

T 组数据,每组两行,第一行 N,K 代表一个严格递增数列中有 N 个数,我们可以向其中插入 K 个任意数字。第二行是这 N 个整数。
插入数字后我们希望数列的相邻数字差的最大值尽可能小,求这个最小值。

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
import math
T = int(input())
for t in range(T):
N, K = map(int, input().split())
s = list(map(int, input().split()))
d = []
for i in range(1, len(s)):
d.append(s[i]-s[i-1])
maxv = max(d)
if maxv < 2:
print('Case #%d: %d' % (t+1, maxv))
else:
d.sort(reverse=True)
l, r = 1, maxv
while l < r:
m = l + r >> 1
ks = 0
for dd in d:
if dd <= m:
break
ks += math.ceil(dd/m)-1
if ks > K:
l = m + 1
else:
r = m
print('Case #%d: %d' % (t+1, r))

Bundling

把 N 个字符串分成 K 个组(N 一定被 K 整除)。每组的分数是这一组字符串最长公共前缀的和。求全局分数最大

字典树

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
T = int(input())
for tt in range(T):
N, K = map(int, input().split())
ss = []
for _ in range(N):
ss.append(input())
base = ord('A')
class TrieNode:
def __init__(self):
self.cnt = 0
self.children = [None] * 26
def add(self, s):
self.cnt += 1
if not s:
return

if not self.children[i]:
self.children[i] = TrieNode()
self.children[i].add(s[1:])
root = TrieNode()
for s in ss:
t = root
for ch in s:
t.cnt += 1
i = ord(ch) - base
if not t.children[i]:
t.children[i] = TrieNode()
t = t.children[i]
t.cnt += 1
cnt = 0
root.cnt = 0
stack = [root]
while stack:
t = stack.pop()
cnt += t.cnt // K
for c in t.children:
if c and c.cnt >= K:
stack.append(c)
print('Case #%d: %d' % (tt+1, cnt))

递归(测试数据 2 会超过递归层数限制)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
T = int(input())
for t in range(T):
N, K = map(int, input().split())
ss = []
for _ in range(N):
ss.append(input())
ss.sort()
cnt = [0]
def find(i, j, k):
s = i
while s < j and k >= len(ss[s]):
s += 1
x = s
while s < j:
while x < j and ss[x][k] == ss[s][k]:
x += 1
if x - s >= K:
cnt[0] += (x - s) // K
find(s, x, k+1)
s = x
find(0, len(ss), 0)
print('Case #%d: %d' % (t+1, cnt[0]))

3月20日笔试题第二题

目录
  1. 题目
  2. 思路
    1. 预处理
    2. 深搜或动态规划
      1. 深搜
      2. 动态规划
  3. 代码
    1. 深搜
    2. 动态规划
  4. 测试

更新:

2020 年 3 月 21 日,最初代码的预处理有问题,字符串开始与结尾字母相同时,应该累加字符串长度。

题目

给出一组 n 个字符串。每个字符串都是小写字母组成,且 ascii 码非递减。

求使用这 n 个字符串,最大能拼接出长度为多少的非递减字符串。

1 <= n <= 10^6

思路

可以转化为有向图,然后求图上最大路径和。每一个字符串做点,两个可以拼接字符串之间连边(这里可以优化)。

预处理

1e6 个点,太多了,可以通过预处理,把点数控制到不超过 351 个。因为一共只有 26 个字母,比如对于 a 开头,b 结尾的字符串,只保留长度最大的即可,其他全都舍掉。如 ab, abbbb 和 abb,只保留最长的一个就可以。

定义 26 × 26 的数组 edges,edges[i][j] 代表 i 字母到 j 字母的最长的字符串,26*26 = 676,因为只可能有 a b,不能有 b a,所以数组有半是空的。最多有 351 个点。

构造边,两个字符串,只要 S2 的开头小于等于 S1 的结尾就认为有 S1 到 S2 的边

这里可以优化,比如 aaa,bbbb,efg, hij。这里 aaa 到了 bbb,就不用再看 aaa 直接到 efg 和 hij 了。因为 bbbb 也可以到他们,aaa 直接到他们,肯定不如经过 bbbb 长。

深搜或动态规划

深搜

直接深搜会超时,需使用 functools.lru_cache 装饰器,做记忆化搜索,实际上相当于动态规划。

使用 node_s_e 记录每一个点的 start 字母,和 end 字母

使用 s2node_list,s2node_list[i] 是所有以 i 开头的点的列表

动态规划

定义 dp 为长度 26 的数组,dp[i] 代表结尾字母小于等于 i 的串的最大长度。

代码

深搜

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
import functools

x = ['az', 'bcd', 'zzz', 'bcdef']
x = ['aaa', 'bcd', 'zzz', 'bcdef']

edges = [[0] *26 for _ in range(26)]
base = ord('a')
for s in x:
if s[0] == s[-1]:
edges[ord(s[0])-base][ord(s[-1])-base] += len(s)
else:
edges[ord(s[0])-base][ord(s[-1])-base] = max(len(s), edges[ord(s[0])-base][ord(s[-1])-base])

nodes = [0]
node_s_e = [0]
s2node_list = [[] for _ in range(26)]
for i in range(26):
for j in range(26):
if edges[i][j] > 0:
nodes.append(edges[i][j])
edges[i][j] = len(nodes)-1
node_s_e.append((i, j))
s2node_list[i].append(len(nodes)-1)
flag = [True] * len(nodes)

@functools.lru_cache(355)
def dfs(i):
flag[i] = False
s, e = node_s_e[i]
# print(i, e)
cur_max = 26
ans = 0
while e < cur_max:
for j in s2node_list[e]:
if not flag[j]: continue
ans = max(ans, dfs(j))
cur_max = min(cur_max, node_s_e[j][1])
e += 1

flag[i] = True
return nodes[i] + ans
ans = 0

for i in range(1, len(nodes)):
ans = max(ans, dfs(i))
print(ans)

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
x = ['aaa', 'bcd', 'zzz', 'bcdef']

edges = [[0] *26 for _ in range(26)]
base = ord('a')
for s in x:
if s[0] == s[-1]:
edges[ord(s[0])-base][ord(s[-1])-base] += len(s)
else:
edges[ord(s[0])-base][ord(s[-1])-base] = max(len(s), edges[ord(s[0])-base][ord(s[-1])-base])
dp = [0] * 26

dp[0] = edges[0][0]

for i in range(1, 26):
maxv = 0
for j in range(0, i):
maxv = max(maxv, dp[j] + edges[j][i])
dp[i] = maxv + edges[i][i]
print(dp[-1])

测试

最极端情况 edges 数组是满的,所以生成随机数填充的 edges 数组做测试

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import time
import random
import functools
bt = time.time() * 1000
edges = [[0] *26 for _ in range(26)]
for i in range(26):
for j in range(i, 26):
edges[i][j] = random.randint(1,99999)
dp = [0] * 26

dp[0] = edges[0][0]

for i in range(1, 26):
maxv = 0
for j in range(0, i):
maxv = max(maxv, dp[j] + edges[j][i])
dp[i] = maxv + edges[i][i]
print(dp[-1])
nodes = [0]
node_s_e = [0]
s2node_list = [[] for _ in range(26)]
for i in range(26):
for j in range(26):
if edges[i][j] > 0:
nodes.append(edges[i][j])
edges[i][j] = len(nodes)-1
node_s_e.append((i, j))
s2node_list[i].append(len(nodes)-1)
flag = [True] * len(nodes)

@functools.lru_cache(355)
def dfs(i):
flag[i] = False
s, e = node_s_e[i]
# print(i, e)
cur_max = 26
ans = 0
while e < cur_max:
for j in s2node_list[e]:
if not flag[j]: continue
ans = max(ans, dfs(j))
cur_max = min(cur_max, node_s_e[j][1])
e += 1

flag[i] = True
return nodes[i] + ans
ans = 0
for i in range(1, len(nodes)):
ans = max(ans, dfs(i))
print(ans)
time.time() * 1000 - btimport time
import random
import functools
bt = time.time() * 1000
edges = [[0] *26 for _ in range(26)]
for i in range(26):
for j in range(i, 26):
edges[i][j] = random.randint(1,99999)
dp = [0] * 26

dp[0] = edges[0][0]

for i in range(1, 26):
maxv = 0
for j in range(0, i):
maxv = max(maxv, dp[j] + edges[j][i])
dp[i] = maxv + edges[i][i]
print(dp[-1])
nodes = [0]
node_s_e = [0]
s2node_list = [[] for _ in range(26)]
for i in range(26):
for j in range(26):
if edges[i][j] > 0:
nodes.append(edges[i][j])
edges[i][j] = len(nodes)-1
node_s_e.append((i, j))
s2node_list[i].append(len(nodes)-1)
flag = [True] * len(nodes)

@functools.lru_cache(355)
def dfs(i):
flag[i] = False
s, e = node_s_e[i]
# print(i, e)
cur_max = 26
ans = 0
while e < cur_max:
for j in s2node_list[e]:
if not flag[j]: continue
ans = max(ans, dfs(j))
cur_max = min(cur_max, node_s_e[j][1])
e += 1

flag[i] = True
return nodes[i] + ans
ans = 0
for i in range(1, len(nodes)):
ans = max(ans, dfs(i))
print(ans)
time.time() * 1000 - bt

输出:

2424978
(3.804931640625, ‘ms’)

edges[i][j] = random.randint(1,99999) 换成 edges[i][j] = random.randint(1,99999) if random.random() > 0.3 else 0 可以生成随机数据。

Manjaro 安装完成后的配置

目录
  1. 中文输入法
  2. 安装 Node.js
  3. 安装 typora
  4. 默认启动命令模式
  5. 安装显卡驱动
  6. 安装 wps office
  7. 安装 chrome
  8. 安装深度截图
  9. 安装 wine
    1. 字体

中文输入法

系统语言不一定选中文

参考:https://www.zhihu.com/question/330715155

编辑 /etc/pacman.conf,添加

1
2
[archlinuxcn] SigLevel = Never 
Server = https://mirrors.tuna.tsinghua.edu.cn/archlinuxcn/$arch
1
sudo pacman -Syy
1
2
3
sudo pacman -S fcitx-im fcitx-sogoupinyin fcitx-configtool 
sudo pacman -S yay
yay -S fcitx-qt4

编辑 ~/.pam_environment(存在就添加),

添加以下内容:

1
2
3
GTK_IM_MODULE=fcitx 
QT_IM_MODULE=fcitx
XMODIFIERS=@im=fcitx

安装 Node.js

官网下载 https://nodejs.org/en/

解压,并安装

1
2
3
xz -d node-v12.16.1-linux-x64.tar.xz 
tar -xf node-v12.16.1-linux-x64.tar
sudo mv node-v12.16.1-linux-x64 /usr/local/

添加 bin 至 PATH

sudo vi /etc/profile

添加一句

1
PATH=${PATH}:/usr/local/node-v12.16.1-linux-x64/bin/

安装 typora

https://www.typora.io/#linux

1
2
3
tar -xzvf Typora-linux-x64.tar.gz 
sudo mv Typora-linux-x64/ /usr/local/
sudo ln -s /usr/local/Typora-linux-x64/Typora /usr/bin/typora

默认启动命令模式

systemctl set-default multi-user.target

图形模式

systemctl set-default graphical.target

安装显卡驱动

首先去官网下载驱动,然后禁用系统自带的开源驱动。

实际上安装程序会自动生成文件 /etc/modprobe.d/nvidia-installer-disable-nouveau.conf 帮助我们禁用,文件的内容是:

1
2
3
# generated by nvidia-installer
blacklist nouveau
options nouveau modeset=0

然后需要重启,确认 lsmod | grep nouveau 命令无任何输出后,说明 nouveau 被禁用。

然后启动为命令模式。

sudo ./NVIDIA-Linux-x86_64-440.64.run 执行安装程序

安装 wps office

1
2
sudo pacman -S wps-office
sudo pacman -S ttf-wps-fonts

安装 chrome

1
sudo pacman -S google-chrome

安装深度截图

1
sudo pacman -S deepin-screenshot

添加快捷键:设置 - 键盘

剪贴板支持:sudo pacman -S gnome-settings-daemon

安装 wine

sudo pacman -S wine winetricks

sudo pacman -S wine wine_gecko wine-mono

sudo pacman -S lib32-mesa lib32-nvidia-utils

字体

参考https://blog.csdn.net/zbgjhy88/article/details/85110956

新建 reg 文件,并通过 wine regedit 导入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
REGEDIT4
[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\FontLink\SystemLink]
"Lucida Sans Unicode"="wqy-microhei.ttc"
"Microsoft Sans Serif"="wqy-microhei.ttc"
"Microsoft YaHei"="wqy-microhei.ttc"
"微软雅黑"="wqy-microhei.ttc"
"MS Sans Serif"="wqy-microhei.ttc"
"Tahoma"="wqy-microhei.ttc"
"Tahoma Bold"="wqy-microhei.ttc"
"SimSun"="wqy-microhei.ttc"
"Arial"="wqy-microhei.ttc"
"Arial Black"="wqy-microhei.ttc"
"宋体"="wqy-microhei.ttc"
"新細明體"="wqy-microhei.ttc"

用命令LC_ALL=zh_CN.UTF-8 winecfg打开wine设置
添加库加载项,注意是 native 优先,这个就是导致无法显示消息和无法输入的原因,可能是 wine 的库不支持 QQ 的某些调用吧
添加这两个库

riched20

riched32

然后执行 winetricks riched20

启动微信:LC_ALL=zh_CN.UTF-8 wine .wine/drive_c/Program\ Files\ \(x86\)/Tencent/WeChat/WeChat.exe

LR LR_fast resnet_fea_len Epoch loss F1
2e-5 1e-3 1+49 11 0.0341 0.8567 0.8516 0.8504
1e-5 1e-3 1+49 9 0.1738 0.8608 0.8527 0.8511
2e-5 5e-3 1+49+196 3 0.5480 0.7407 0.7616 0.7570

参考:

https://zhuanlan.zhihu.com/p/90634218

深度截图:

https://www.cnblogs.com/lemonblue/p/8977055.html

https://www.jianshu.com/p/23ab7364fdf6

wine:

https://blog.csdn.net/zbgjhy88/article/details/85110956

https://blog.csdn.net/qq_38656841/article/details/100568125

https://www.cnblogs.com/jikexianfeng/p/5769430.html

https://www.cnblogs.com/jikexianfeng/p/5769430.html

面试代码总结

目录
  1. 2020-03-04
    1. 链表反转
    2. 面试题32 - III. 从上到下打印二叉树 III
  2. 2020-03-17 - 1
    1. 二叉树上最大连续元素和
    2. 解码方法
    3. 时间复杂度分析,数组中第 k 小元素
  3. 2020-03-17 - 2
  4. 2020-03-18 - 1
    1. 题目一
    2. 题目二
  5. 2020-03-18-2
  6. 2020-03-19-1

更新中

常问问题:

  1. 线程与进程的区别,进程间通信的方法
  2. bert 原理,结构,预训练任务

2020-03-04

这个时间太久记得不是很清楚了,一共三面

一面

链表反转

由于题目要求用 C++,我对牛客系统也不太适应,居然没写出来。

第二个题忘记了,似乎也没写好

二面

面试题32 - III. 从上到下打印二叉树 III

我今天才发现是剑指 offer 的原题。

方法一:排序

我当时想到的做法,O(nlogn) 的时间复杂度,面试官表示很奇葩。当时不太清醒,实际上可以 O(n) 的

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
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
l = []
import queue
q = queue.Queue()
q.put((root, 1))
cid = 1
last_l = 1
while not q.empty():
t, level = q.get()
if level != last_l:
last_l = level
cid = 1
if t:
flag = 1
if level % 2 == 0:
flag = -1
l.append((level, cid*flag, t.val))
q.put((t.left, level+1))
q.put((t.right, level+1))
cid += 1
l.sort()
ans = [[] for _ in range(level-1)]
for x in l:
ans[x[0]-1].append(x[2])
return ans

方法二:

只需要把每一层分开放入 list,偶数层 reverse 一下就好了,O(n)时间

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 levelOrder(self, root: TreeNode) -> List[List[int]]:
l = []
import queue
q = queue.Queue()
q.put((root, 1))
last_l = 1
ans = []
while not q.empty():
t, level = q.get()
if t:
if level != last_l:
last_l = level
if level % 2 == 1:
l.reverse()
ans.append(l)
l = []
l.append(t.val)
q.put((t.left, level+1))
q.put((t.right, level+1))
if l:
if level % 2 == 1:
l.reverse()
ans.append(l)
return ans

2020-03-17 - 1

二叉树上最大连续元素和

节点可能有负数和 0。动态规划

解码方法

也是动归

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

时间复杂度分析,数组中第 k 小元素

我记不清楚了,只记得 O(n) 复杂度

2020-03-17 - 2

这个面试我面的不好

只有一道题目

实现二叉搜索树,用数组表示。

刚开始我就直接用 1 号为根,i << 1 , i << 1 | 1 为左右孩子。

但是我理解偏了题意,他出这个问题更想考察工程方面。

  1. 数组空间要连续使用,即数组下标模拟指针
  2. 使用了递归不应该有双层 if else 嵌套,需要优化
  3. find 和 insert 的相同流程应该提出了。

2020-03-18 - 1

题目一

/
一个升序数组,寻找给定数值的开始和结束位置。找不到返回[-1, -1]
Given [5, 7, 7, 8, 8, 8, 10] and target value 8, return [3, 5].
请给出足够的测试用例。
/

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
#include <iostream>
#include <vector>

class Solution {
public:
std::vector<int> searchRange(std::vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] < target) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
std::vector<int> ans;
if (nums[i] != target) {
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
ans.push_back(l);

l = 0, r = nums.size();
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] <= target) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
ans.push_back(r);
return ans;
}
};

题目二

/*
一个特殊的 urlparse ,规则如下
SCHEME://<?PARAM>/PATH
PARAM = <K1=V1><K2=V2>…

<1> hdfs://cluster?ssd=true&cache=1/dir/file
分解:
scheme = hdfs
netloc = cluster
param = ssd=true&cache=1
path = /dir/file

<2> hdfs://cluster/?ssd=true&cache=1/dir/file
scheme = hdfs
netloc = cluster
param =
path = /?ssd=true&cache=1/dir/file

<3> local:///home/xx/
scheme = local
netloc =
param =
path = /home/xx/
*/

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
using namespace std;
map<string, string > fun(string url) {
int i = 0;
map<string, string> ans;
while (url[i] != ':') {
i += 1;
}
string scheme = url.substr(0, i);
int ii = i;
i += 3;
while (url[i] != '/') {
i += 1;
}
string netloc = url.substr(ii+1, i);
ii = i;
i += 1;
while (i < url.length() && (url[i] != '?' || url[i-1] == '/')) {
i += 1;
}
string path = url.substr(ii, i);
string param = "";
if (i < url.length() && url[i] == '?')
param = url.substr(i, url.length());
map["scheme"] = scheme;
map["netloc"] = netloc;
map["path"] = path;
map["param"] = param;
return map;
}

2020-03-18-2

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
#评测题目:请实现一个函数用来找出字符流中第一个只出现一次的字符。
#例如,当从字符流中只读出前两个字符"to"时,第一个只出现一次的字符是"t"。
#当从该字符流中读出前六个字符“tomato"时,第一个只出现一次的字符是"m"。

def fun(s):
import queue
import collections
x = ''
cnt = collections.Counter()
q = queue.Queue()
for ch in s:
cnt[ch] += 1
if cnt[ch] == 1:
q.put(ch)
if x == '' or ch == x:
if not q.empty():
while True:
xx = q.get()
if cnt[xx] == 1:
break
if cnt[xx] == 1:
x = xx
else:
x = ''
else:
x = ''
print(ch, x)

fun('tomato')

问快速排序,如何更好的选择枢轴的值。

2020-03-19-1

二叉树中序遍历,非递归:栈

查找链表是否有环:双指针,一个每次走一步,另一个每次走两步

T4SA Dataset 介绍

目录

http://www.t4sa.it/

来自 2017 年的论文 Cross-Media Learning for Image Sentiment Analysis in the Wild。

在网站上提交一个表单可以获得用于下载的用户名和密码。

这个数据集提供 5 个文件下载。除了原数据集 T4SA 还有一个 B-T4SA 是从 T4SA 中挑选出来的种类平衡的子集。

T4SA 有 117 万条 twitter,147 万图片。B-T4SA 有 15 万图片。

该论文还使用另一个数据集做测试:

https://www.cs.rochester.edu/u/qyou/DeepSent/deepsentiment.html

这个数据集似乎是只有图片。使用多种算法给图片打标签,把有多个模型得到相同结果的图片作为有标记的数据。

2019 年的文章 A Multimodal Approach to Image Sentiment Analysis 也使用了该数据集。并提出一种结合文字与图片信息判断情感的方法。

还有类似的数据集:

http://www.ee.columbia.edu/ln/dvmm/vso/download/twitter_dataset.html

605 个图片(也包含一些推文和评论)

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