1 
  2 ////////////////////////////////////////////////////////////////////////////////
  3 /**
  4  * @fileOverview Copyright (C) 2009 www.webis.de
  5  * @author Christof Braeutigam christof.braeutigam@uni-weimar.de
  6  * @author Christian Fricke christian.fricke@uni-weimar.de
  7  * @version 0.1
  8  */
  9 
 10 /**
 11  * ExpectedDensity is a internal cluster validity measure, computing a measure
 12  * by comparing a clustering and the original similarity graph the clustering
 13  * was created from
 14  * @author Christof Bräutigam christof.braeutigam@uni-weimar.de
 15  * @constructor
 16  * @class ExpectedDensity cluster validity measure
 17  */
 18 de.aitools.js.ExpectedDensity = (function () {
 19   
 20   /* private */
 21   var voc = new de.aitools.js.Vocabulary();
 22   var stemming = false;
 23   var removeStopwords = false;
 24   var name = "Expected Density";
 25   
 26   /* public */
 27   return {
 28     measure : function (clustering, graph) {
 29       CHECK_NOT_UNDEFINED(clustering, "ExpectedDensity.measure: " +
 30                           "clustering to validate not defined");
 31       CHECK_NOT_UNDEFINED(graph, "ExpectedDensity.measure: reference " +
 32                           "(graph, reference clustering, ...) not defined");
 33       if (!(clustering instanceof de.aitools.js.Clustering)) {
 34         throw new Error("first argument must be a clustering");
 35       }
 36       if (!(graph instanceof de.aitools.js.Graph)) {
 37         throw new Error("second argument must be a graph");
 38       }
 39       var ed = 0;
 40       var n = graph.getNodeCount();
 41       var graphWeight = graph.getMass() + n;
 42       var theta = Math.log(graphWeight) / Math.log(n);
 43       for(var i = 0; i < clustering.getClusterCount(); ++i) {
 44         var curClusterItems = clustering.getItemsOfCluster(i);
 45         var clusterWeight = graph.getMass(curClusterItems);
 46         var nodesInCurrentCluster = curClusterItems.length;
 47         clusterWeight += nodesInCurrentCluster;
 48         var vitheta = Math.pow(nodesInCurrentCluster, theta);
 49         var clusterScore = clusterWeight / vitheta;
 50         var percentage = nodesInCurrentCluster / n;
 51         ed += percentage * clusterScore;
 52       }
 53       return ed;
 54     },
 55     getName : function () {
 56       return name;
 57     }
 58   };
 59 });
 60 
 61 ////////////////////////////////////////////////////////////////////////////////
 62 
 63 ////////////////////////////////////////////////////////////////////////////////
 64 
 65 // TODO: den namen uebergeben zu muessen ist mist, allerdings kommt man nicht
 66 //       an teile von ExpectedDensity heran, wenn man nur die measure-funktion
 67 //       uebergibt
 68 
 69 /**
 70  * ClusterValidityMeasure is a generic class for a cluster validity measure
 71  * @author Christof Bräutigam christof.braeutigam@uni-weimar.de
 72  * @param {Function} measureFunction The concrete validity measure to use (e.g.
 73  * {@link de.aitools.js.ExpectedDensity})
 74  * @param {String} name The name of the validity measure
 75  * @constructor
 76  * @class Generic cluster validity measure
 77  */
 78 de.aitools.js.ClusterValidityMeasure = function (measureFunction, name) {
 79   
 80   CHECK_TYPE(measureFunction, "function", "no validity measure function given");
 81   var n = (name !== undefined) ? name : "ClusterValidityMeasure: undefined";
 82   this.getName = function () { return n; };
 83   this.measure = function (clustering, reference) {
 84     return measureFunction(clustering, reference);
 85   };
 86 };
 87 
 88 ////////////////////////////////////////////////////////////////////////////////
 89