1 import math 2 import numpy as np 3 4 5 class ClusteringHelper: 6 7 def __init__(self, corpus): 8 self.n = corpus.n 9 self.unigrams = corpus.unigrams 10 self.bigrams = corpus.bigrams 11 12 def count_bigrams(self, cluster1, cluster2): 13 _count = 0 14 for w1 in cluster1: 15 for w2 in cluster2: 16 _count += self.bigrams.get((w1, w2), 0) 17 return _count 18 19 def append_cluster(self, words): 20 raise NotImplementedError() 21 22 def merge_clusters(self, i, j): 23 raise NotImplementedError() 24 25 def get_clusters(self): 26 raise NotImplementedError() 27 28 def get_cluster(self, i): 29 raise NotImplementedError() 30 31 def compute_benefit(self): 32 raise NotImplementedError() 33 34 35 class EnhancedClusteringHelper(ClusteringHelper): 36 def __init__(self, corpus): 37 super().__init__(corpus) 38 self.m = 0 39 self.clusters = [] 40 self.p1 = np.zeros(0, dtype=float) 41 self.p2 = np.zeros((0, 0), dtype=float) 42 self.q2 = np.zeros((0, 0), dtype=float) 43 self.l2 = np.zeros((0, 0), dtype=float) 44 45 def append_cluster(self, words): 46 """ 47 O(m (+ n)) 48 """ 49 50 self.p1 = np.insert(self.p1, self.m, 0, axis=0) 51 _sum = 0 52 for w in words: 53 _sum += self.unigrams[w] 54 self.p1[self.m] = _sum / self.n 55 56 self.p2 = np.insert(self.p2, self.m, 0, axis=1) 57 self.p2 = np.insert(self.p2, self.m, 0, axis=0) 58 for i in range(self.m): 59 self.p2[self.m, i] = self.count_bigrams(words, self.clusters[i]) / self.n 60 self.p2[i, self.m] = self.count_bigrams(self.clusters[i], words) / self.n 61 self.p2[self.m, self.m] = self.count_bigrams(words, words) / self.n 62 63 self.q2 = np.insert(self.q2, self.m, 0, axis=1) 64 self.q2 = np.insert(self.q2, self.m, 0, axis=0) 65 for i in range(self.m): 66 self.q2[self.m, i] = self._q(self.m, i) 67 self.q2[i, self.m] = self._q(i, self.m) 68 self.q2[self.m, self.m] = self._q(self.m, self.m) 69 70 self.l2 = np.insert(self.l2, self.m, 0, axis=1) 71 self.l2 = np.insert(self.l2, self.m, 0, axis=0) 72 73 self.m = self.m + 1 74 self.clusters.append(words.copy()) 75 76 self._update_deltas() 77 78 def _update_deltas(self): 79 80 for i in range(self.m - 1): 81 self.l2[i, self.m - 1] = self._delta(i, self.m - 1) 82 for j in range(i + 1, self.m - 1): 83 self.l2[i, j] -= self.q2[i, self.m - 1] 84 self.l2[i, j] -= self.q2[j, self.m - 1] 85 self.l2[i, j] -= self.q2[self.m - 1, i] 86 self.l2[i, j] -= self.q2[self.m - 1, j] 87 self.l2[i, j] += self._q_l(i, j, self.m - 1) 88 self.l2[i, j] += self._q_r(self.m - 1, i, j) 89 90 def get_clusters(self): 91 return self.clusters.copy() 92 93 def get_cluster(self, i): 94 return self.clusters[i].copy() 95 96 def merge_clusters(self, i, j): 97 98 for _i in range(self.m): 99 for _j in range(_i+1, self.m): 100 _tmp = 0 101 _tmp += self._q_l(_i, _j, i) 102 _tmp += self._q_l(_i, _j, j) 103 _tmp += self._q_r(i, _i, _j) 104 _tmp += self._q_r(j, _i, _j) 105 106 _tmp -= self.q2[i, _i] 107 _tmp -= self.q2[_i, i] 108 _tmp -= self.q2[i, _j] 109 _tmp -= self.q2[_j, i] 110 111 _tmp -= self.q2[j, _i] 112 _tmp -= self.q2[_i, j] 113 _tmp -= self.q2[j, _j] 114 _tmp -= self.q2[_j, j] 115 116 self.l2[_i, _j] -= _tmp 117 118 self.clusters[i].extend(self.clusters[j]) 119 del self.clusters[j] 120 self.m = self.m - 1 121 122 self.p1[i] = self.p1[i] + self.p1[j] 123 self.p1 = np.delete(self.p1, j, axis=0) 124 125 self.p2[i, :] = self.p2[i, :] + self.p2[j, :] 126 self.p2[:, i] = self.p2[:, i] + self.p2[:, j] 127 self.p2 = np.delete(self.p2, j, axis=0) 128 self.p2 = np.delete(self.p2, j, axis=1) 129 130 self.q2 = np.delete(self.q2, j, axis=0) 131 self.q2 = np.delete(self.q2, j, axis=1) 132 for _x in range(self.m): 133 self.q2[i, _x] = self._q(i, _x) 134 self.q2[_x, i] = self._q(_x, i) 135 self.q2[i, i] = self._q(i, i) 136 137 self.l2 = np.delete(self.l2, j, axis=0) 138 self.l2 = np.delete(self.l2, j, axis=1) 139 140 for _i in range(self.m): 141 for _j in range(_i+1, self.m): 142 _tmp = 0 143 _tmp += self._q_l(_i, _j, i) 144 _tmp += self._q_r(i, _i, _j) 145 146 _tmp -= self.q2[i, _i] 147 _tmp -= self.q2[_i, i] 148 _tmp -= self.q2[i, _j] 149 _tmp -= self.q2[_j, i] 150 151 self.l2[_i, _j] += _tmp 152 153 for x in range(i): 154 # print("%d %d " % (x, i)) 155 self.l2[x, i] = self._delta(x, i) 156 for x in range(i+1, self.m): 157 # print("%d %d " % (i, x)) 158 self.l2[i, x] = self._delta(i, x) 159 160 def compute_benefit(self): 161 return self.l2.copy() 162 163 def _q_l(self, _i, _j, _x): 164 """ 165 O(1) 166 """ 167 pcx = (self.p2[_i, _x] + self.p2[_j, _x]) 168 pc = (self.p1[_i] + self.p1[_j]) 169 px = self.p1[_x] 170 171 return pcx * math.log(pcx / (pc * px)) 172 173 def _q_r(self, _x, _i, _j): 174 """ 175 O(1) 176 """ 177 pxc = (self.p2[_x, _i] + self.p2[_x, _j]) 178 pc = (self.p1[_i] + self.p1[_j]) 179 px = self.p1[_x] 180 return pxc * math.log(pxc / (pc * px)) 181 182 def _q_x(self, _i, _j): 183 """ 184 O(1) 185 """ 186 pxc = (self.p2[_j, _i] + self.p2[_i, _j] + self.p2[_i, _i] + self.p2[_j, _j]) 187 pc = (self.p1[_i] + self.p1[_j]) 188 px = (self.p1[_i] + self.p1[_j]) 189 return pxc * math.log(pxc / (pc * px)) 190 191 def _q(self, _i, _x): 192 """ 193 O(1) 194 """ 195 pcx = self.p2[_i, _x] 196 pc = self.p1[_i] 197 px = self.p1[_x] 198 199 return pcx * math.log(pcx / (pc * px)) 200 201 def _delta(self, i, j): 202 count_i_new = self.p1[i] + self.p1[j] 203 count_2_new_s = self.p2[i, :] + self.p2[j, :] 204 count_2_new_e = self.p2[:, i] + self.p2[:, j] 205 206 # O(1) 207 def _weight_new_1(_x): 208 pij = count_2_new_s[_x] 209 pji = count_2_new_e[_x] 210 pi = count_i_new 211 pj = self.p1[_x] 212 return pij * math.log(pij / (pi * pj)) + pji * math.log(pji / (pi * pj)) 213 214 # O(1) 215 def _weight_new_2(): 216 pij = (self.p2[i, i] + self.p2[i, j] + self.p2[j, i] + self.p2[j, j]) 217 pji = pij 218 pi = count_i_new 219 pj = count_i_new 220 return pij * math.log(pij / (pi * pj)) + pji * math.log(pji / (pi * pj)) 221 222 # O(m) 223 loss = 0 224 for x in range(self.m): 225 loss -= self.q2[i, x] 226 loss -= self.q2[x, i] 227 loss -= self.q2[j, x] 228 loss -= self.q2[x, j] 229 if x == i or x == j: 230 continue 231 loss += _weight_new_1(x) 232 loss += _weight_new_2() / 2 233 loss += self.q2[i, j] 234 loss += self.q2[j, i] 235 loss += self.q2[i, i] 236 loss += self.q2[j, j] 237 238 return loss 239 240 241 class RawClusteringHelper(ClusteringHelper): 242 def __init__(self, corpus): 243 super().__init__(corpus) 244 self.clusters = [] 245 246 def append_cluster(self, words): 247 self.clusters.append(words.copy()) 248 249 def merge_clusters(self, i, j): 250 self.clusters[i].extend(self.clusters[j]) 251 del self.clusters[j] 252 253 def get_clusters(self): 254 return self.clusters.copy() 255 256 def get_cluster(self, i): 257 return self.clusters[i].copy() 258 259 def count(self, c1, c2=None): 260 ret = 0 261 if c2 is None: 262 for w in c1: 263 ret += self.unigrams[w] 264 else: 265 for w1 in c1: 266 for w2 in c2: 267 ret += self.bigrams[w1, w2] 268 return ret 269 270 def compute_average_mutual_information(self, clusters): 271 k = len(clusters) 272 counts = dict() 273 for i in range(k): 274 counts[i] = self.count(clusters[i]) 275 for i in range(k): 276 for j in range(k): 277 counts[(i, j)] = self.count(clusters[i], clusters[j]) 278 279 def _prob(_i, _j=None): 280 if _j is None: 281 return counts[_i]/self.n 282 return counts[(_i, _j)]/self.n 283 284 ret = 0 285 for i in range(k): 286 for j in range(k): 287 ret += _prob(i, j) * math.log(_prob(i, j) / (_prob(i) * _prob(j))) 288 return ret 289 290 def compute_benefit(self): 291 tmp = self.compute_average_mutual_information(self.clusters) 292 293 294 k = len(self.clusters) 295 296 _benefit = np.zeros((k, k)) 297 for i in range(k): 298 for j in range(i + 1, k): 299 clusters_candidate = [x.copy() for x in self.clusters] 300 clusters_candidate[i].extend(clusters_candidate[j]) 301 del clusters_candidate[j] 302 _benefit[i, j] = self.compute_average_mutual_information(clusters_candidate) - tmp 303 return _benefit 304 305 306 class ModerateClusteringHelper(ClusteringHelper): 307 def __init__(self, corpus): 308 super().__init__(corpus) 309 self.m = 0 310 self.clusters = [] 311 self.counts_1 = np.zeros(0, dtype=float) 312 self.counts_2 = np.zeros((0, 0), dtype=float) 313 314 def append_cluster(self, words): 315 """ 316 O(m (+ n)) 317 """ 318 319 self.counts_1 = np.insert(self.counts_1, self.m, 0, axis=0) 320 _sum = 0 321 for w in words: 322 _sum += self.unigrams[w] 323 self.counts_1[self.m] = _sum 324 325 self.counts_2 = np.insert(self.counts_2, self.m, 0, axis=1) 326 self.counts_2 = np.insert(self.counts_2, self.m, 0, axis=0) 327 for i in range(self.m): 328 self.counts_2[self.m, i] = self.count_bigrams(words, self.clusters[i]) 329 self.counts_2[i, self.m] = self.count_bigrams(self.clusters[i], words) 330 self.counts_2[self.m, self.m] = self.count_bigrams(words, words) 331 332 self.m = self.m + 1 333 self.clusters.append(words.copy()) 334 335 def get_clusters(self): 336 return self.clusters.copy() 337 338 def get_cluster(self, i): 339 return self.clusters[i].copy() 340 341 def merge_clusters(self, i, j): 342 self.counts_1[i] = self.counts_1[i] + self.counts_1[j] 343 self.counts_1 = np.delete(self.counts_1, j, axis=0) 344 345 self.counts_2[i, :] = self.counts_2[i, :] + self.counts_2[j, :] 346 self.counts_2[:, i] = self.counts_2[:, i] + self.counts_2[:, j] 347 self.counts_2 = np.delete(self.counts_2, j, axis=0) 348 self.counts_2 = np.delete(self.counts_2, j, axis=1) 349 350 self.clusters[i].extend(self.clusters[j]) 351 del self.clusters[j] 352 self.m = self.m - 1 353 354 def compute_benefit(self): 355 deltas = np.zeros((self.m, self.m), dtype=float) 356 for i in range(self.m): 357 for j in range(i + 1, self.m): 358 deltas[i, j] = self._delta(i, j) 359 return deltas 360 361 def _q_l(self, _i, _j, _x): 362 """ 363 O(1) 364 """ 365 pcx = (self.counts_2[_i, _x] + self.counts_2[_j, _x]) / self.n 366 pc = (self.counts_1[_i] + self.counts_1[_j]) / self.n 367 px = self.counts_1[_x] / self.n 368 369 return pcx * math.log(pcx / (pc * px)) 370 371 def _q_r(self, _x, _i, _j): 372 """ 373 O(1) 374 """ 375 pxc = (self.counts_2[_x, _i] + self.counts_2[_x, _j]) / self.n 376 pc = (self.counts_1[_i] + self.counts_1[_j]) / self.n 377 px = self.counts_1[_x] / self.n 378 return pxc * math.log(pxc / (pc * px)) 379 380 def _q_x(self, _i, _j): 381 """ 382 O(1) 383 """ 384 pxc = (self.counts_2[_j, _i] + self.counts_2[_i, _j] + self.counts_2[_i, _i] + self.counts_2[_j, _j]) / self.n 385 pc = (self.counts_1[_i] + self.counts_1[_j]) / self.n 386 px = (self.counts_1[_i] + self.counts_1[_j]) / self.n 387 return pxc * math.log(pxc / (pc * px)) 388 389 def _q(self, _i, _x): 390 """ 391 O(1) 392 """ 393 pcx = self.counts_2[_i, _x] / self.n 394 pc = self.counts_1[_i] / self.n 395 px = self.counts_1[_x] / self.n 396 397 return pcx * math.log(pcx / (pc * px)) 398 399 def _delta(self, i, j): 400 """ 401 O(m) 402 """ 403 404 # O(m) 405 406 # O(m) 407 count_i_new = self.counts_1[i] + self.counts_1[j] 408 count_2_new_s = self.counts_2[i, :] + self.counts_2[j, :] 409 count_2_new_e = self.counts_2[:, i] + self.counts_2[:, j] 410 411 # O(1) 412 def _weight_new_1(_x): 413 pij = count_2_new_s[_x] / self.n 414 pji = count_2_new_e[_x] / self.n 415 pi = count_i_new / self.n 416 pj = self.counts_1[_x] / self.n 417 return pij * math.log(pij / (pi * pj)) + pji * math.log(pji / (pi * pj)) 418 419 # O(1) 420 def _weight_new_2(): 421 pij = (self.counts_2[i, i] + self.counts_2[i, j] + self.counts_2[j, i] + self.counts_2[j, j]) / self.n 422 pji = pij 423 pi = count_i_new / self.n 424 pj = count_i_new / self.n 425 return pij * math.log(pij / (pi * pj)) + pji * math.log(pji / (pi * pj)) 426 427 # O(m) 428 loss = 0 429 for x in range(self.m): 430 loss -= self._q(i, x) 431 loss -= self._q(x, i) 432 loss -= self._q(j, x) 433 loss -= self._q(x, j) 434 if x == i or x == j: 435 continue 436 loss += _weight_new_1(x) 437 loss += _weight_new_2() / 2 438 loss += self._q(i, j) 439 loss += self._q(j, i) 440 loss += self._q(i, i) 441 loss += self._q(j, j) 442 443 return loss 444