1/*! 2 * Figue v1.0.1 3 * 4 * Copyright 2010, Jean-Yves Delort 5 * Licensed under the MIT license. 6 * 7 */ 8var figue = function () { 9 10 11 function euclidianDistance (vec1 , vec2) { 12 var N = vec1.length ; 13 var d = 0 ; 14 for (var i = 0 ; i < N ; i++) 15 d += Math.pow (vec1[i] - vec2[i], 2) 16 d = Math.sqrt (d) ; 17 return d ; 18 } 19 20 function manhattanDistance (vec1 , vec2) { 21 var N = vec1.length ; 22 var d = 0 ; 23 for (var i = 0 ; i < N ; i++) 24 d += Math.abs (vec1[i] - vec2[i]) 25 return d ; 26 } 27 28 function maxDistance (vec1 , vec2) { 29 var N = vec1.length ; 30 var d = 0 ; 31 for (var i = 0 ; i < N ; i++) 32 d = Math.max (d , Math.abs (vec1[i] - vec2[i])) ; 33 return d ; 34 } 35 36 function addVectors (vec1 , vec2) { 37 var N = vec1.length ; 38 var vec = new Array(N) ; 39 for (var i = 0 ; i < N ; i++) 40 vec[i] = vec1[i] + vec2[i] ; 41 return vec ; 42 } 43 44 function multiplyVectorByValue (value , vec) { 45 var N = vec.length ; 46 var v = new Array(N) ; 47 for (var i = 0 ; i < N ; i++) 48 v[i] = value * vec[i] ; 49 return v ; 50 } 51 52 function vectorDotProduct (vec1, vec2) { 53 var N = vec1.length ; 54 var s = 0 ; 55 for (var i = 0 ; i < N ; i++) 56 s += vec1[i] * vec2[i] ; 57 return s ; 58 } 59 60 61 function repeatChar(c, n) { 62 var str = ""; 63 for (var i = 0 ; i < n ; i++) 64 str += c ; 65 return str ; 66 } 67 68 function calculateCentroid (c1Size , c1Centroid , c2Size , c2Centroid) { 69 var newCentroid = new Array(c1Centroid.length) ; 70 var newSize = c1Size + c2Size ; 71 for (var i = 0 ; i < c1Centroid.length ; i++) 72 newCentroid[i] = (c1Size * c1Centroid[i] + c2Size * c2Centroid[i]) / newSize ; 73 return newCentroid ; 74 } 75 76 77 function centerString(str, width) { 78 var diff = width - str.length ; 79 if (diff < 0) 80 return ; 81 82 var halfdiff = Math.floor(diff / 2) ; 83 return repeatChar (" " , halfdiff) + str + repeatChar (" " , diff - halfdiff) ; 84 } 85 86 function putString(str, width, index) { 87 var diff = width - str.length ; 88 if (diff < 0) 89 return ; 90 91 return repeatChar (" " , index) + str + repeatChar (" " , width - (str.length+index)) ; 92 } 93 94 function prettyVector(vector) { 95 var vals = new Array(vector.length) ; 96 var precision = Math.pow(10, figue.PRINT_VECTOR_VALUE_PRECISION) ; 97 for (var i = 0 ; i < vector.length ; i++) 98 vals[i] = Math.round(vector[i]*precision)/precision ; 99 return vals.join(",") 100 } 101 102 function prettyValue(value) { 103 var precision = Math.pow(10, figue.PRINT_VECTOR_VALUE_PRECISION) ; 104 return String (Math.round(value*precision)/precision) ; 105 } 106 107 function generateDendogram(tree, sep, balanced, withLabel, withCentroid, withDistance) { 108 var lines = new Array ; 109 var centroidstr = prettyVector(tree.centroid) ; 110 if (tree.isLeaf()) { 111 var labelstr = String(tree.label) ; 112 var len = 1; 113 if (withCentroid) 114 len = Math.max(centroidstr.length , len) ; 115 if (withLabel) 116 len = Math.max(labelstr.length , len) ; 117 118 lines.push (centerString ("|" , len)) ; 119 if (withCentroid) 120 lines.push (centerString (centroidstr , len)) ; 121 if (withLabel) 122 lines.push (centerString (labelstr , len)) ; 123 124 } else { 125 var distancestr = prettyValue(tree.dist) ; 126 var left_dendo = generateDendogram(tree.left ,sep, balanced,withLabel,withCentroid, withDistance) ; 127 var right_dendo = generateDendogram(tree.right, sep, balanced,withLabel,withCentroid,withDistance) ; 128 var left_bar_ix = left_dendo[0].indexOf("|") ; 129 var right_bar_ix = right_dendo[0].indexOf("|") ; 130 131 // calculate nb of chars of each line 132 var len = sep + right_dendo[0].length + left_dendo[0].length ; 133 if (withCentroid) 134 len = Math.max(centroidstr.length , len) ; 135 if (withDistance) 136 len = Math.max(distancestr.length , len) ; 137 138 139 // calculate position of new vertical bar 140 var bar_ix = left_bar_ix + Math.floor(( left_dendo[0].length - (left_bar_ix) + sep + (1+right_bar_ix)) / 2) ; 141 142 // add line with the new vertical bar 143 lines.push (putString ("|" , len , bar_ix)) ; 144 if (withCentroid) { 145 lines.push (putString (centroidstr , len , bar_ix - Math.floor (centroidstr.length / 2))) ; //centerString (centroidstr , len)) ; 146 } 147 if (withDistance) { 148 lines.push (putString (distancestr , len , bar_ix - Math.floor (distancestr.length / 2))) ; //centerString (centroidstr , len)) ; 149 } 150 151 // add horizontal line to connect the vertical bars of the lower level
152 var hlineLen = sep + (left_dendo[0].length -left_bar_ix) + right_bar_ix+1 ; 153 var hline = repeatChar ("_" , hlineLen) ; 154 lines.push (putString(hline, len, left_bar_ix)) ; 155 156 // IF: the user want the tree to be balanced: all the leaves have to be at the same level 157 // THEN: if the left and right subtrees have not the same depth, add extra vertical bars to the top of the smallest subtree 158 if (balanced && (left_dendo.length != right_dendo.length)) { 159 var shortest ; 160 var longest ; 161 if (left_dendo.length > right_dendo.length) { 162 longest = left_dendo ; 163 shortest = right_dendo ; 164 } else { 165 longest = right_dendo ; 166 shortest = left_dendo ; 167 } 168 // repeat the first line containing the vertical bar 169 header = shortest[0] ; 170 var toadd = longest.length - shortest.length ; 171 for (var i = 0 ; i < toadd ; i++) { 172 shortest.splice (0,0,header) ; 173 } 174 } 175 176 // merge the left and right subtrees 177 for (var i = 0 ; i < Math.max (left_dendo.length , right_dendo.length) ; i++) { 178 var left = "" ; 179 if (i < left_dendo.length) 180 left = left_dendo[i] ; 181 else 182 left = repeatChar (" " , left_dendo[0].length) ; 183 184 var right = "" ; 185 if (i < right_dendo.length) 186 right = right_dendo[i] ; 187 else 188 right = repeatChar (" " , right_dendo[0].length) ; 189 lines.push(left + repeatChar (" " , sep) + right) ; 190 var l = left + repeatChar (" " , sep) + right ; 191 } 192 } 193 194 return lines ; 195 } 196 197 198 199 function agglomerate (labels, vectors, distance, linkage) { 200 var N = vectors.length ; 201 var dMin = new Array(N) ; 202 var cSize = new Array(N) ; 203 var matrixObj = new figue.Matrix(N,N); 204 var distMatrix = matrixObj.mtx ; 205 var clusters = new Array(N) ; 206 207 var c1, c2, c1Cluster, c2Cluster, i, j, p, root , newCentroid ; 208 209 if (distance == figue.EUCLIDIAN_DISTANCE) 210 distance = euclidianDistance ; 211 else if (distance == figue.MANHATTAN_DISTANCE) 212 distance = manhattanDistance ; 213 else if (distance == figue.MAX_DISTANCE) 214 distance = maxDistance ; 215 216 // Initialize distance matrix and vector of closest clusters 217 for (i = 0 ; i < N ; i++) { 218 dMin[i] = 0 ; 219 for (j = 0 ; j < N ; j++) { 220 if (i == j) 221 distMatrix[i][j] = Infinity ; 222 else 223 distMatrix[i][j] = distance(vectors[i] , vectors[j]) ; 224 225 if (distMatrix[i][dMin[i]] > distMatrix[i][j] ) 226 dMin[i] = j ; 227 } 228 } 229 230 // create leaves of the tree 231 for (i = 0 ; i < N ; i++) { 232 clusters[i] = [] ; 233 clusters[i][0] = new Node (labels[i], null, null, 0, vectors[i]) ; 234 cSize[i] = 1 ; 235 } 236 237 // Main loop 238 for (p = 0 ; p < N-1 ; p++) { 239 // find the closest pair of clusters 240 c1 = 0 ; 241 for (i = 0 ; i < N ; i++) { 242 if (distMatrix[i][dMin[i]] < distMatrix[c1][dMin[c1]]) 243 c1 = i ; 244 } 245 c2 = dMin[c1] ; 246 247 // create node to store cluster info 248 c1Cluster = clusters[c1][0] ; 249 c2Cluster = clusters[c2][0] ; 250 251 newCentroid = calculateCentroid ( c1Cluster.size , c1Cluster.centroid , c2Cluster.size , c2Cluster.centroid ) ; 252 newCluster = new Node (-1, c1Cluster, c2Cluster , distMatrix[c1][c2] , newCentroid) ; 253 clusters[c1].splice(0,0, newCluster) ; 254 cSize[c1] += cSize[c2] ; 255 256 // overwrite row c1 with respect to the linkage type 257 for (j = 0 ; j < N ; j++) { 258 if (linkage == figue.SINGLE_LINKAGE) { 259 if (distMatrix[c1][j] > distMatrix[c2][j]) 260 distMatrix[j][c1] = distMatrix[c1][j] = distMatrix[c2][j] ; 261 } else if (linkage == figue.COMPLETE_LINKAGE) { 262 if (distMatrix[c1][j] < distMatrix[c2][j]) 263 distMatrix[j][c1] = distMatrix[c1][j] = distMatrix[c2][j] ; 264 } else if (linkage == figue.AVERAGE_LINKAGE) { 265 var avg = ( cSize[c1] * distMatrix[c1][j] + cSize[c2] * distMatrix[c2][j]) / (cSize[c1] + cSize[j]) 266 distMatrix[j][c1] = distMatrix[c1][j] = avg ; 267 } 268 } 269 distMatrix[c1][c1] = Infinity ; 270 271 // infinity Âout old row c2 and column c2 272 for (i = 0 ; i < N ; i++) 273 distMatrix[i][c2] = distMatrix[c2][i] = Infinity ; 274 275 // update dmin and replace ones that previous pointed to c2 to point to c1 276 for (j = 0; j < N ; j++) { 277 if (dMin[j] == c2) 278 dMin[j] = c1; 279 if (distMatrix[c1][j] < distMatrix[c1][dMin[c1]]) 280 dMin[c1] = j; 281 } 282 283 // keep track of the last added cluster 284 root = newCluster ; 285 } 286 287 return root ; 288 } 289 290 291 292 function getRandomVectors(k, vectors) { 293 /* Returns a array of k distinct vectors randomly selected from a the input array of vectors 294 Returns null if k > n or if there are less than k distinct objects in vectors */ 295 296 var n = vectors.length ; 297 if ( k > n ) 298 return null ; 299 300 var selected_vectors = new Array(k) ; 301 var selected_indices = new Array(k) ; 302 303 var tested_indices = new Object ; 304 var tested = 0 ; 305 var selected = 0 ; 306 var i , vector, select ; 307 while (selected < k) { 308 if (tested == n) 309 return null ; 310 311 var random_index = Math.floor(Math.random()*(n)) ; 312 if (random_index in tested_indices) 313 continue ; 314 315 tested_indices[random_index] = 1; 316 tested++ ; 317 vector = vectors[random_index] ; 318 select = true ; 319 for (i = 0 ; i < selected ; i++) { 320 if ( vector.compare (selected_vectors[i]) ) { 321 select = false ; 322 break ; 323 } 324 } 325 if (select) { 326 selected_vectors[selected] = vector ; 327 selected_indices[selected] = random_index ; 328 selected++ ; 329 } 330 } 331 return {'vectors': selected_vectors, 'indices': selected_indices} ; 332 } 333 334 function kmeans (k, vectors) { 335 var n = vectors.length ; 336 var assignments = new Array(n) ; 337 var clusterSizes = new Array(k) ; 338 var repeat = true ; 339 var nb_iters = 0 ; 340 var centroids = null ; 341 342 var t = getRandomVectors(k, vectors) ; 343 if (t == null) 344 return null ; 345 else 346 centroids = t.vectors ; 347 348 while (repeat) { 349 350 // assignment step 351 for (var j = 0 ; j < k ; j++) 352 clusterSizes[j] = 0 ; 353 354 for (var i = 0 ; i < n ; i++) { 355 var vector = vectors[i] ; 356 var mindist = Number.MAX_VALUE ; 357 var best ; 358 for (var j = 0 ; j < k ; j++) { 359 dist = euclidianDistance (centroids[j], vector) 360 if (dist < mindist) { 361 mindist = dist ; 362 best = j ; 363 } 364 } 365 clusterSizes[best]++ ; 366 assignments[i] = best ; 367 } 368 369 // update centroids step 370 var newCentroids = new Array(k) ; 371 for (var j = 0 ; j < k ; j++) 372 newCentroids[j] = null ; 373 374 for (var i = 0 ; i < n ; i++) { 375 cluster = assignments[i] ; 376 if (newCentroids[cluster] == null) 377 newCentroids[cluster] = vectors[i] ; 378 else 379 newCentroids[cluster] = addVectors (newCentroids[cluster] , vectors[i]) ; 380 } 381 382 for (var j = 0 ; j < k ; j++) { 383 newCentroids[j] = multiplyVectorByValue (1/clusterSizes[j] , newCentroids[j]) ; 384 } 385 386 // check convergence 387 repeat = false ; 388 for (var j = 0 ; j < k ; j++) { 389 if (! newCentroids[j].compare (centroids[j])) { 390 repeat = true ; 391 break ; 392 } 393 } 394 centroids = newCentroids ; 395 nb_iters++ ; 396 397 // check nb of iters 398 if (nb_iters > figue.KMEANS_MAX_ITERATIONS) 399 repeat = false ; 400 401 } 402 return { 'centroids': centroids , 'assignments': assignments} ; 403 404 } 405 406 function fcmeans (k, vectors, epsilon, fuzziness) { 407 var membershipMatrix = new Matrix (vectors.length, k) ; 408 var repeat = true ; 409 var nb_iters = 0 ; 410 411 var centroids = null ; 412 413 var i,j,l, tmp, norm, max, diff ; 414 while (repeat) { 415 // initialize or update centroids 416 if (centroids == null) { 417 418 tmp = getRandomVectors(k, vectors) ; 419 if (tmp == null) 420 return null ; 421 else 422 centroids = tmp.vectors ; 423 424 } else { 425 for (j = 0 ; j < k; j++) { 426 centroids[j] = [] ; 427 norm = 0 ; 428 for (i = 0 ; i < membershipMatrix.rows ; i++) { 429 norm += Math.pow(membershipMatrix.mtx[i][j], fuzziness) ; 430 tmp = multiplyVectorByValue( Math.pow(membershipMatrix.mtx[i][j], fuzziness) , vectors[i]) ; 431 432 if (i == 0) 433 centroids[j] = tmp ; 434 else 435 centroids[j] = addVectors (centroids[j] , tmp) ; 436 } 437 if (norm > 0) 438 centroids[j] = multiplyVectorByValue(1/norm, centroids[j]); 439 440 441 } 442 443 } 444 //alert(centroids); 445 446 // update the degree of membership of each vector 447 previousMembershipMatrix = membershipMatrix.copy() ; 448 for (i = 0 ; i < membershipMatrix.rows ; i++) { 449 for (j = 0 ; j < k ; j++) { 450 membershipMatrix.mtx[i][j] = 0; 451 for (l = 0 ; l < k ; l++) { 452 if (euclidianDistance(vectors[i] , centroids[l]) == 0) 453 tmp = 0 ; 454 else 455 tmp = euclidianDistance(vectors[i] , centroids[j]) / euclidianDistance(vectors[i] , centroids[l]) ; 456 tmp = Math.pow (tmp, 2/(fuzziness-1)) ; 457 membershipMatrix.mtx[i][j] += tmp ; 458 } 459 if (membershipMatrix.mtx[i][j] > 0) 460 membershipMatrix.mtx[i][j] = 1 / membershipMatrix.mtx[i][j] ; 461 } 462 } 463 464 //alert(membershipMatrix) ; 465 466 // check convergence 467 max = -1 ; 468 diff; 469 for (i = 0 ; i < membershipMatrix.rows ; i++) 470 for (j = 0 ; j < membershipMatrix.cols ; j++) { 471 diff = Math.abs(membershipMatrix.mtx[i][j] - previousMembershipMatrix.mtx[i][j]) ; 472 if (diff > max) 473 max = diff ; 474 } 475 476 if (max < epsilon) 477 repeat = false ; 478 479 nb_iters++ ; 480 481 // check nb of iters 482 if (nb_iters > figue.FCMEANS_MAX_ITERATIONS) 483 repeat = false ; 484 } 485 return { 'centroids': centroids , 'membershipMatrix': membershipMatrix} ; 486 487 } 488 489 490 function Matrix (rows,cols) 491 { 492 this.rows = rows ; 493 this.cols = cols ; 494 this.mtx = new Array(rows) ; 495 496 for (var i = 0 ; i < rows ; i++) 497 { 498 var row = new Array(cols) ; 499 for (var j = 0 ; j < cols ; j++) 500 row[j] = 0; 501 this.mtx[i] = row ; 502 } 503 } 504 505 function Node (label,left,right,dist, centroid) 506 { 507 this.label = label ; 508 this.left = left ; 509 this.right = right ; 510 this.dist = dist ; 511 this.centroid = centroid ; 512 if (left == null && right == null) { 513 this.size = 1 ; 514 this.depth = 0 ; 515 } else { 516 this.size = left.size + right.size ; 517 this.depth = 1 + Math.max (left.depth , right.depth ) ; 518 } 519 } 520 521 522 523 return { 524 SINGLE_LINKAGE: 0, 525 COMPLETE_LINKAGE: 1, 526 AVERAGE_LINKAGE:2 , 527 EUCLIDIAN_DISTANCE: 0, 528 MANHATTAN_DISTANCE: 1, 529 MAX_DISTANCE: 2, 530 PRINT_VECTOR_VALUE_PRECISION: 2, 531 KMEANS_MAX_ITERATIONS: 10, 532 FCMEANS_MAX_ITERATIONS: 3, 533 534 Matrix: Matrix, 535 Node: Node, 536 generateDendogram: generateDendogram, 537 agglomerate: agglomerate, 538 kmeans: kmeans, 539 fcmeans: fcmeans 540 } 541}() ; 542 543 544figue.Matrix.prototype.toString = function() 545{ 546 var lines = [] ; 547 for (var i = 0 ; i < this.rows ; i++) 548 lines.push (this.mtx[i].join("\t")) ; 549 return lines.join ("\n") ; 550} 551 552 553figue.Matrix.prototype.copy = function() 554{ 555 var duplicate = new figue.Matrix(this.rows, this.cols) ; 556 for (var i = 0 ; i < this.rows ; i++) 557 duplicate.mtx[i] = this.mtx[i].slice(0); 558 return duplicate ; 559} 560 561figue.Node.prototype.isLeaf = function() 562{ 563 if ((this.left == null) && (this.right == null)) 564 return true ; 565 else 566 return false ; 567} 568 569figue.Node.prototype.buildDendogram = function (sep, balanced,withLabel,withCentroid, withDistance) 570{ 571 lines = figue.generateDendogram(this, sep, balanced,withLabel,withCentroid, withDistance) ; 572 return lines.join ("\n") ; 573} 574 575 576Array.prototype.compare = function(testArr) { 577 if (this.length != testArr.length) return false;
578 for (var i = 0; i < testArr.length; i++) { 579 if (this[i].compare) { 580 if (!this[i].compare(testArr[i])) return false; 581 } 582 if (this[i] !== testArr[i]) return false; 583 } 584 return true; 585} 586 587
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.