Changes between Version 1 and Version 2 of Clustering

Timestamp:

Apr 24, 2013, 9:22:34 AM (12 years ago)

Author:

manualwiki

Comment:

--

Clustering

@@ -6 +6 @@
 
 Before using the clustering functionality of the tool, the source files have to be loaded to the database. The clustering algorithm will cluster all the modules and functions which are in the database. In the clustering options the user can choose the modules and functions that should be ignored during the clustering.
+{{{#!comment 
+The clustering module can also provide a decomposition of the modules base on a module clustering. This option takes the library modules and header files in the database, and distributes their functions, records and macros among the clusters. Parts used by more than one cluster stay in their place.
+}}} 
 
 == Types of clustering ==
@@ -20 +23 @@
 === Genetic clustering ===
 
-Genetic algorithms simulate the evolution of species. There are iterations of populations in which every entity figths for survival or for the survival of its genes. A fitness function is defined to determine the value of an entity. The fitter an entity is, the more likely it survives. The algorithm is expected to converge to the fittest possible entity, like evolution does.
+Genetic algorithms simulate the evolution of species. There are iterations of populations in which every entity fights for survival or for the survival of its genes. A fitness function is defined to determine the value of an entity. The fitter an entity is, the more likely it survives. The algorithm is expected to converge to the fittest possible entity, like evolution does.
 
 = Using the clustering functionality =
 
-The clustering functionality is available from Emacs and the console interface.
+The clustering functionality is available from Emacs, the console interface and the scriptable interface.
 
 == Parameters for agglomerative clustering ==
@@ -51 +54 @@
 * '''''Maximum cluster size:''''' Maximum number of clusters allowed.
 * '''''Maximum start cluster size:''''' Maximum number of clusters allowed at startup.
+
+{{{#!comment
+== Parameters for decomposition ==
+
+* '''''Decomposition:''''' It shows whether the user wants a possible decomposition
+ of the modules or not. Only available with module clustering.
+* '''''Library limit:''''' The minimum number of function calls for library modules. If a module is called by at least this many other modules, it is considered a library modules.
+* '''''Headers:''''' The format of header files. It is a string which is matched to the end of the file names.
+
+== Parameters for clustering ==
+
+* '''''Algorithm:''''' The used clustering algorithm.
+* '''''Entities:''''' The entities of the clustering. Modules and functions available for both algorithms.
+* '''''Show Goodness:''''' Yes/No question. If enabled, the tool shows the goodness values for each of the clusterings.
+* '''''Only best:''''' Yes/No question. If enabled, the tool shows the best clustering result only.
+* '''''Store results:''''' Yes/No question. If enabled, the tool stores the results in 3 different format describes bellow.
+
+== Output formats ==
+
+As mentioned above, the tool can store clustering results in 3 different formats:
+* '''''Dets table:''''' It is used by the tool itself.
+* '''''Scriptable file:''''' It is format which can easily be used by other programs. It is a list of pairs, every pair contains a keyword and a result. ([{clusterings, [[cluster1],[cluster2],...,[clusterN]]},{goodnesses,[goodness1,...,goodnessN]},...])
+* '''''Readable file:''''' It creates a report "readable to the human eye". It shows the resulting clusterings and the decomposition offered by the tool. 
+
+== Important notes about the module ==
+
+There are some things which are important to know, when using the clustering module of the tool. 
+
+=== Distance functions for agglomerative algorithm ===
+
+Currently, there are two distance functions available for the agglomerative clustering module. (Weight and Call Sum)
+The weight distance function recognizes two entities similar, if they use the same functions. It uses the idea, that the modules' behavior is largely dependent on the functions they call. It means that if two modules call the same functions, they must be similar in behavior. 
+The call sum distance function considers two modules similar if they call each others' functions. The idea here is that these modules must work similarly, because use each other more. 
+It is very important to choose the distance function wisely, because the two distance function can generate very different results, so the goal of the clustering must be considered before running the algorithm. The call sum distance function can be better, if the user wants to discover connections between the modules, and unite modules, while weight distance function can show, which modules have the same behavior.
+
+=== Choosing the parameters of the genetic algorithm ===
+
+As mentioned above, the genetic algorithm starts from a randomly generated population. This makes the algorithm very non-deterministic. This makes choosing the parameters very important.
+We don't have proven method for choosing the parameters right, but we have some results which can make this decision easier. We examined the effect of population size and iteration number on the precision and run time of the algorithm.
+The results are the following:
+
+|| Iterations / Population size || 10 || 20 || 30 || 40 || 50 ||
+|| 10 || {,} || {,} || {,} || {,} || {,} ||
+|| 20 || {,} || {,} || {,} || {,} || {,} ||
+|| 30 || {,} || {,} || {,} || {,} || {,} ||
+|| 40 || {,} || {,} || {,} || {,} || {,} ||
+|| 50 || {,} || {,} || {,} || {,} || {,} ||
+
+Every cell shows the results' average weighted fitness and the run time of the algorithms, with parameters {iterations,X}, {population_size,Y} for cell {X,Y}. The fitness of the best clustering of this database is 2.404, so this is the maximum fitness achievable. The algorithm is run 500 times with every pair of parameters on this database. The run time is shown in seconds.
+}}}