/
decomp1.py
98 lines (83 loc) · 3.33 KB
/
decomp1.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
94
95
96
97
98
"""Decompose heterogeneous matrices."""
from typing import List
from common import make_rows, coefficient, move, join
global rows #: Dict[int,Set[int]]
global g
def attract(i:int, j:int) -> float:
"""
Calculate the attraction between rows i and j.
Parameters
----------
i : the first row
j : the second row
Returns
-------
float: the force between rows.
"""
global rows
global g
if i==j:
return 0.0
else:
s = coefficient(rows[i]|set([i]), rows[j]|set([j]),g) # similarity
# s = coefficient(rows[i], rows[j],g) # variant
# different conversions:
#return 3.125*s*s*s-7.5*s*s+6.375*s-1 # green
#return 2* s**0.5-1 # red
#return -1.5*s*s + 3.5*s -1 # blue
return s **(1./5.)*2-1 # black
#return 2*s-1 # noname
#%% correlation clustering
def calc(matrix: List[List[int]]) -> List[List[int]]:
"""
Biclustering.
Parameters
----------
m: homogeneous matrix of a relation
Returns
-------
solution: "set of set of" objects, a clustering
"""
global rows
rows = make_rows(matrix)
#transposed :List[List[int]] = list(map(list, zip(*matrix)))
#trans: Dict[int,Set[int]] =alist(transposed)
global g
g = {x:x for x in range(len(rows))}
change=False
while True:
change = False
for i in g:
if move(i,g,attract):
change=True
# print("after move:", [list({i+1 for i in g if g[i]==v}) for v in set(g.values())])
if join(g,attract):
change=True
# print("after join:", [list({i+1 for i in g if g[i]==v}) for v in set(g.values())])
if not change:
break
solution = [list({i+1 for i in g if g[i]==v}) for v in set(g.values())]
return solution
if __name__ == "__main__":
# example from Gunther Schmidt tech. rep. p12
m = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], # 1
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 2
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 3
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 4
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], # 5
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], # 6
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 7
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 8
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 9
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 11
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 12
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], # 13
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 14
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], # 15
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 16
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 17
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 18
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] # 19
sol = calc(m)
print(sol)