forked from laming-chen/fast-map-dpp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dpp.py
93 lines (88 loc) · 3.54 KB
/
dpp.py
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
import numpy as np
import math
def dpp(kernel_matrix, max_length, epsilon=1E-10):
"""
我们提出了一个更快实现的贪心算法
Our proposed fast implementation of the greedy algorithm
入参：一个二维数组，表示高斯核矩阵
:param kernel_matrix: 2-d array
入参：一个正整数，表示最大长度
:param max_length: positive int
入参：一个小数，表示精度
:param epsilon: small positive scalar
出参：一个列表，表示选择的物品
:return: list
"""
item_size = kernel_matrix.shape[0]
cis = np.zeros((max_length, item_size))
di2s = np.copy(np.diag(kernel_matrix))
print("kaishi")
print(di2s)
selected_items = list()
print(selected_items)
selected_item = np.argmax(di2s)
print("selected_item:" , selected_item)
selected_items.append(selected_item)
while len(selected_items) < max_length:
k = len(selected_items) - 1
ci_optimal = cis[:k, selected_item]
di_optimal = math.sqrt(di2s[selected_item])
elements = kernel_matrix[selected_item, :]
eis = (elements - np.dot(ci_optimal, cis[:k, :])) / di_optimal
cis[k, :] = eis
di2s -= np.square(eis)
di2s[selected_item] = -np.inf
selected_item = np.argmax(di2s)
if di2s[selected_item] < epsilon:
break
selected_items.append(selected_item)
return selected_items
def dpp_sw(kernel_matrix, window_size, max_length, epsilon=1E-10):
"""
Sliding window version of the greedy algorithm
:param kernel_matrix: 2-d array
:param window_size: positive int
:param max_length: positive int
:param epsilon: small positive scalar
:return: list
"""
item_size = kernel_matrix.shape[0]
v = np.zeros((max_length, max_length))
cis = np.zeros((max_length, item_size))
di2s = np.copy(np.diag(kernel_matrix))
selected_items = list()
selected_item = np.argmax(di2s)
selected_items.append(selected_item)
window_left_index = 0
while len(selected_items) < max_length:
k = len(selected_items) - 1
ci_optimal = cis[window_left_index:k, selected_item]
di_optimal = math.sqrt(di2s[selected_item])
v[k, window_left_index:k] = ci_optimal
v[k, k] = di_optimal
elements = kernel_matrix[selected_item, :]
eis = (elements - np.dot(ci_optimal, cis[window_left_index:k, :])) / di_optimal
cis[k, :] = eis
di2s -= np.square(eis)
if len(selected_items) >= window_size:
window_left_index += 1
for ind in range(window_left_index, k + 1):
t = math.sqrt(v[ind, ind] ** 2 + v[ind, window_left_index - 1] ** 2)
c = t / v[ind, ind]
s = v[ind, window_left_index - 1] / v[ind, ind]
v[ind, ind] = t
v[ind + 1:k + 1, ind] += s * v[ind + 1:k + 1, window_left_index - 1]
v[ind + 1:k + 1, ind] /= c
v[ind + 1:k + 1, window_left_index - 1] *= c
v[ind + 1:k + 1, window_left_index - 1] -= s * v[ind + 1:k + 1, ind]
cis[ind, :] += s * cis[window_left_index - 1, :]
cis[ind, :] /= c
cis[window_left_index - 1, :] *= c
cis[window_left_index - 1, :] -= s * cis[ind, :]
di2s += np.square(cis[window_left_index - 1, :])
di2s[selected_item] = -np.inf
selected_item = np.argmax(di2s)
if di2s[selected_item] < epsilon:
break
selected_items.append(selected_item)
return selected_items