Changeset 7849:2249037f6108 in orange
 Timestamp:
 04/15/11 15:24:42 (3 years ago)
 Branch:
 default
 Convert:
 55048a9e5d9f249b7cc62e47db68324cf06057c6
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

orange/Orange/clustering/hierarchical.py
r7846 r7849 99 99 visitedClusters = set() 100 100 101 def _optOrderingRecursive(tree): 102 if len(tree)==1: 103 for leaf in tree: 104 M[tree, leaf, leaf] = 0 105 else: 106 _optOrderingRecursive(tree.left) 107 _optOrderingRecursive(tree.right) 108 109 Vl = set(tree.left) 110 Vr = set(tree.right) 111 Vlr = set(tree.left.right or tree.left) 112 Vll = set(tree.left.left or tree.left) 113 Vrr = set(tree.right.right or tree.right) 114 Vrl = set(tree.right.left or tree.right) 115 other = lambda e, V1, V2: V2 if e in V1 else V1 116 tree_left, tree_right = tree.left, tree.right 117 for u in Vl: 118 for w in Vr: 119 # if True: #Improved search 120 C = min([matrix[m, k] for m in other(u, Vll, Vlr) for k in other(w, Vrl, Vrr)]) 121 orderedMs = sorted(other(u, Vll, Vlr), key=lambda m: M[tree_left, u, m]) 122 orderedKs = sorted(other(w, Vrl, Vrr), key=lambda k: M[tree_right, w, k]) 123 k0 = orderedKs[0] 124 curMin = 1e30000 125 curM = curK = None 126 for m in orderedMs: 127 if M[tree_left, u, m] + M[tree_right, w, k0] + C >= curMin: 128 break 129 for k in orderedKs: 130 if M[tree_left, u, m] + M[tree_right, w, k] + C >= curMin: 131 break 132 testMin = M[tree_left, u, m] + M[tree_right, w, k] + matrix[m, k] 133 if curMin > testMin: 134 curMin = testMin 135 curM = m 136 curK = k 137 M[tree, u, w] = M[tree, w, u] = curMin 138 ordering[tree, u, w] = (tree_left, u, curM, tree_right, w, curK) 139 ordering[tree, w, u] = (tree_right, w, curK, tree_left, u, curM) 140 # else: 141 # def MFunc((m, k)): 142 # return M[tree_left, u, m] + M[tree_right, w, k] + matrix[m, k] 143 # m, k = min([(m, k) for m in other(u, Vll, Vlr) for k in other(w, Vrl, Vrr)], key=MFunc) 144 # M[tree, u, w] = M[tree, w, u] = MFunc((m, k)) 145 # ordering[tree, u, w] = (tree_left, u, m, tree_right, w, k) 146 # ordering[tree, w, u] = (tree_right, w, k, tree_left, u, m) 147 148 if progressCallback: 149 progressCallback(100.0 * len(visitedClusters) / len(tree.mapping)) 150 visitedClusters.add(tree) 151 152 if False: 153 with recursion_limit(sys.getrecursionlimit() + len(tree)): 154 _optOrderingRecursive(tree) 101 # def _optOrderingRecursive(tree): 102 # if len(tree)==1: 103 # for leaf in tree: 104 # M[tree, leaf, leaf] = 0 105 # else: 106 # _optOrderingRecursive(tree.left) 107 # _optOrderingRecursive(tree.right) 108 # 109 # Vl = set(tree.left) 110 # Vr = set(tree.right) 111 # Vlr = set(tree.left.right or tree.left) 112 # Vll = set(tree.left.left or tree.left) 113 # Vrr = set(tree.right.right or tree.right) 114 # Vrl = set(tree.right.left or tree.right) 115 # other = lambda e, V1, V2: V2 if e in V1 else V1 116 # tree_left, tree_right = tree.left, tree.right 117 # for u in Vl: 118 # for w in Vr: 119 ## if True: #Improved search 120 # C = min([matrix[m, k] for m in other(u, Vll, Vlr) for k in other(w, Vrl, Vrr)]) 121 # orderedMs = sorted(other(u, Vll, Vlr), key=lambda m: M[tree_left, u, m]) 122 # orderedKs = sorted(other(w, Vrl, Vrr), key=lambda k: M[tree_right, w, k]) 123 # k0 = orderedKs[0] 124 # curMin = 1e30000 125 # curM = curK = None 126 # for m in orderedMs: 127 # if M[tree_left, u, m] + M[tree_right, w, k0] + C >= curMin: 128 # break 129 # for k in orderedKs: 130 # if M[tree_left, u, m] + M[tree_right, w, k] + C >= curMin: 131 # break 132 # testMin = M[tree_left, u, m] + M[tree_right, w, k] + matrix[m, k] 133 # if curMin > testMin: 134 # curMin = testMin 135 # curM = m 136 # curK = k 137 # M[tree, u, w] = M[tree, w, u] = curMin 138 # ordering[tree, u, w] = (tree_left, u, curM, tree_right, w, curK) 139 # ordering[tree, w, u] = (tree_right, w, curK, tree_left, u, curM) 140 ## else: 141 ## def MFunc((m, k)): 142 ## return M[tree_left, u, m] + M[tree_right, w, k] + matrix[m, k] 143 ## m, k = min([(m, k) for m in other(u, Vll, Vlr) for k in other(w, Vrl, Vrr)], key=MFunc) 144 ## M[tree, u, w] = M[tree, w, u] = MFunc((m, k)) 145 ## ordering[tree, u, w] = (tree_left, u, m, tree_right, w, k) 146 ## ordering[tree, w, u] = (tree_right, w, k, tree_left, u, m) 147 # 148 # if progressCallback: 149 # progressCallback(100.0 * len(visitedClusters) / len(tree.mapping)) 150 # visitedClusters.add(tree) 151 # 152 # with recursion_limit(sys.getrecursionlimit() + len(tree)): 153 # _optOrderingRecursive(tree) 155 154 156 155 def _optOrderingIterative(tree): … … 244 243 if right.branches and k not in right.left: 245 244 right.swap() 246 247 # if len(tree) == 1:248 # return249 # left, u, m, right, w, k = ordering[tree, u, w]250 # if len(left) > 1 and m not in left.right:251 # left.swap()252 # _orderIterative(left, u, m)253 #254 # if len(right) > 1 and k not in right.left:255 # right.swap()256 # _orderIterative(right, k, w)257 245 258 246 u, w = min([(u, w) for u in tree.left for w in tree.right], key=lambda (u, w): M[tree, u, w]) … … 260 248 ## print "M(v) =", M[tree, u, w] 261 249 262 if False: 263 with recursion_limit(sys.getrecursionlimit() + len(tree)): 264 _orderRecursive(tree, u, w) 250 # with recursion_limit(sys.getrecursionlimit() + len(tree)): 251 # _orderRecursive(tree, u, w) 265 252 266 253 _orderIterative(tree, u, w)
Note: See TracChangeset
for help on using the changeset viewer.