Context Navigation

source: trunk/CrossPare/src/de/ugoe/cs/cpdp/training/WekaLocalFQTraining.java @ 23

Last change on this file since 23 was 23, checked in by sherbold, 10 years ago
renamed new training classes
File size: 23.7 KB

Line
1	package de.ugoe.cs.cpdp.training;
2
3	import java.io.PrintStream;
4	import java.util.ArrayList;
5	import java.util.HashMap;
6	import java.util.HashSet;
7	import java.util.Iterator;
8	import java.util.Random;
9	import java.util.Set;
10	import java.util.logging.Level;
11
12	import org.apache.commons.io.output.NullOutputStream;
13
14	import de.ugoe.cs.cpdp.training.QuadTree;
15	import de.ugoe.cs.util.console.Console;
16	import weka.classifiers.AbstractClassifier;
17	import weka.classifiers.Classifier;
18	import weka.core.DenseInstance;
19	import weka.core.EuclideanDistance;
20	import weka.core.Instance;
21	import weka.core.Instances;
22	import weka.filters.Filter;
23	import weka.filters.unsupervised.attribute.Remove;
24
25	/**
26	* Trainer with reimplementation of WHERE clustering algorithm from:
27	* Tim Menzies, Andrew Butcher, David Cok, Andrian Marcus, Lucas Layman,
28	* Forrest Shull, Burak Turhan, Thomas Zimmermann,
29	* "Local versus Global Lessons for Defect Prediction and Effort Estimation,"
30	* IEEE Transactions on Software Engineering, vol. 39, no. 6, pp. 822-834, June, 2013
31	*
32	* With WekaLocalTraining2 we do the following:
33	* 1) Run the Fastmap algorithm on all training data, let it calculate the 2 most significant
34	* dimensions and projections of each instance to these dimensions
35	* 2) With these 2 dimensions we span a QuadTree which gets recursively split on median(x) and median(y) values.
36	* 3) We cluster the QuadTree nodes together if they have similar density (50%)
37	* 4) We save the clusters and their training data
38	* 5) We only use clusters with > ALPHA instances (currently Math.sqrt(SIZE)), rest is discarded with the training data of this cluster
39	* 6) We train a Weka classifier for each cluster with the clusters training data
40	* 7) We recalculate Fastmap distances for a single instance with the old pivots and then try to find a cluster containing the coords of the instance.
41	* 7.1.) If we can not find a cluster (due to coords outside of all clusters) we find the nearest cluster.
42	* 8) We classify the Instance with the classifier and traindata from the Cluster we found in 7.
43	*/
44	public class WekaLocalFQTraining extends WekaBaseTraining implements ITrainingStrategy {
45
46	private final TraindatasetCluster classifier = new TraindatasetCluster();
47
48	@Override
49	public Classifier getClassifier() {
50	return classifier;
51	}
52
53	@Override
54	public void apply(Instances traindata) {
55	PrintStream errStr = System.err;
56	System.setErr(new PrintStream(new NullOutputStream()));
57	try {
58	classifier.buildClassifier(traindata);
59	} catch (Exception e) {
60	throw new RuntimeException(e);
61	} finally {
62	System.setErr(errStr);
63	}
64	}
65
66
67	public class TraindatasetCluster extends AbstractClassifier {
68
69	private static final long serialVersionUID = 1L;
70
71	/* classifier per cluster */
72	private HashMap<Integer, Classifier> cclassifier;
73
74	/* instances per cluster */
75	private HashMap<Integer, Instances> ctraindata;
76
77	/* holds the instances and indices of the pivot objects of the Fastmap calculation in buildClassifier*/
78	private HashMap<Integer, Instance> cpivots;
79
80	/* holds the indices of the pivot objects for x,y and the dimension [x,y][dimension]*/
81	private int[][] cpivotindices;
82
83	/* holds the sizes of the cluster multiple "boxes" per cluster */
84	private HashMap<Integer, ArrayList<Double[][]>> csize;
85
86	/* debug vars */
87	@SuppressWarnings("unused")
88	private boolean show_biggest = true;
89
90	@SuppressWarnings("unused")
91	private int CFOUND = 0;
92	@SuppressWarnings("unused")
93	private int CNOTFOUND = 0;
94
95
96	private Instance createInstance(Instances instances, Instance instance) {
97	// attributes for feeding instance to classifier
98	Set<String> attributeNames = new HashSet<>();
99	for( int j=0; j<instances.numAttributes(); j++ ) {
100	attributeNames.add(instances.attribute(j).name());
101	}
102
103	double[] values = new double[instances.numAttributes()];
104	int index = 0;
105	for( int j=0; j<instance.numAttributes(); j++ ) {
106	if( attributeNames.contains(instance.attribute(j).name())) {
107	values[index] = instance.value(j);
108	index++;
109	}
110	}
111
112	Instances tmp = new Instances(instances);
113	tmp.clear();
114	Instance instCopy = new DenseInstance(instance.weight(), values);
115	instCopy.setDataset(tmp);
116
117	return instCopy;
118	}
119
120	/**
121	* Because Fastmap saves only the image not the values of the attributes it used
122	* we can not use the old data directly to classify single instances to clusters.
123	*
124	* To classify a single instance we do a new fastmap computation with only the instance and
125	* the old pivot elements.
126	*
127	* After that we find the cluster with our fastmap result for x and y.
128	*/
129	@Override
130	public double classifyInstance(Instance instance) {
131
132	double ret = 0;
133	try {
134	// classinstance gets passed to classifier
135	Instances traindata = ctraindata.get(0);
136	Instance classInstance = createInstance(traindata, instance);
137
138	// this one keeps the class attribute
139	Instances traindata2 = ctraindata.get(1);
140
141	// remove class attribute before clustering
142	Remove filter = new Remove();
143	filter.setAttributeIndices("" + (traindata.classIndex() + 1));
144	filter.setInputFormat(traindata);
145	traindata = Filter.useFilter(traindata, filter);
146	Instance clusterInstance = createInstance(traindata, instance);
147
148	Fastmap FMAP = new Fastmap(2);
149	EuclideanDistance dist = new EuclideanDistance(traindata);
150
151	// we set our pivot indices [x=0,y=1][dimension]
152	int[][] npivotindices = new int[2][2];
153	npivotindices[0][0] = 1;
154	npivotindices[1][0] = 2;
155	npivotindices[0][1] = 3;
156	npivotindices[1][1] = 4;
157
158	// build temp dist matrix (2 pivots per dimension + 1 instance we want to classify)
159	// the instance we want to classify comes first after that the pivot elements in the order defined above
160	double[][] distmat = new double[2FMAP.target_dims+1][2FMAP.target_dims+1];
161	distmat[0][0] = 0;
162	distmat[0][1] = dist.distance(clusterInstance, this.cpivots.get((Integer)this.cpivotindices[0][0]));
163	distmat[0][2] = dist.distance(clusterInstance, this.cpivots.get((Integer)this.cpivotindices[1][0]));
164	distmat[0][3] = dist.distance(clusterInstance, this.cpivots.get((Integer)this.cpivotindices[0][1]));
165	distmat[0][4] = dist.distance(clusterInstance, this.cpivots.get((Integer)this.cpivotindices[1][1]));
166
167	distmat[1][0] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][0]), clusterInstance);
168	distmat[1][1] = 0;
169	distmat[1][2] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][0]), this.cpivots.get((Integer)this.cpivotindices[1][0]));
170	distmat[1][3] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][0]), this.cpivots.get((Integer)this.cpivotindices[0][1]));
171	distmat[1][4] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][0]), this.cpivots.get((Integer)this.cpivotindices[1][1]));
172
173	distmat[2][0] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][0]), clusterInstance);
174	distmat[2][1] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][0]), this.cpivots.get((Integer)this.cpivotindices[0][0]));
175	distmat[2][2] = 0;
176	distmat[2][3] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][0]), this.cpivots.get((Integer)this.cpivotindices[0][1]));
177	distmat[2][4] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][0]), this.cpivots.get((Integer)this.cpivotindices[1][1]));
178
179	distmat[3][0] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][1]), clusterInstance);
180	distmat[3][1] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][1]), this.cpivots.get((Integer)this.cpivotindices[0][0]));
181	distmat[3][2] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][1]), this.cpivots.get((Integer)this.cpivotindices[1][0]));
182	distmat[3][3] = 0;
183	distmat[3][4] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[0][1]), this.cpivots.get((Integer)this.cpivotindices[1][1]));
184
185	distmat[4][0] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][1]), clusterInstance);
186	distmat[4][1] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][1]), this.cpivots.get((Integer)this.cpivotindices[0][0]));
187	distmat[4][2] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][1]), this.cpivots.get((Integer)this.cpivotindices[1][0]));
188	distmat[4][3] = dist.distance(this.cpivots.get((Integer)this.cpivotindices[1][1]), this.cpivots.get((Integer)this.cpivotindices[0][1]));
189	distmat[4][4] = 0;
190
191
192	/* debug output: show biggest distance found within the new distance matrix
193	double biggest = 0;
194	for(int i=0; i < distmat.length; i++) {
195	for(int j=0; j < distmat[0].length; j++) {
196	if(biggest < distmat[i][j]) {
197	biggest = distmat[i][j];
198	}
199	}
200	}
201	if(this.show_biggest) {
202	Console.traceln(Level.INFO, String.format(""+clusterInstance));
203	Console.traceln(Level.INFO, String.format("biggest distances: "+ biggest));
204	this.show_biggest = false;
205	}
206	*/
207
208	FMAP.setDistmat(distmat);
209	FMAP.setPivots(npivotindices);
210	FMAP.calculate();
211	double[][] x = FMAP.getX();
212	double[] proj = x[0];
213
214	// debug output: show the calculated distance matrix, our result vektor for the instance and the complete result matrix
215	/*
216	Console.traceln(Level.INFO, "distmat:");
217	for(int i=0; i<distmat.length; i++){
218	for(int j=0; j<distmat[0].length; j++){
219	Console.trace(Level.INFO, String.format("%20s", distmat[i][j]));
220	}
221	Console.traceln(Level.INFO, "");
222	}
223
224	Console.traceln(Level.INFO, "vector:");
225	for(int i=0; i < proj.length; i++) {
226	Console.trace(Level.INFO, String.format("%20s", proj[i]));
227	}
228	Console.traceln(Level.INFO, "");
229
230	Console.traceln(Level.INFO, "resultmat:");
231	for(int i=0; i<x.length; i++){
232	for(int j=0; j<x[0].length; j++){
233	Console.trace(Level.INFO, String.format("%20s", x[i][j]));
234	}
235	Console.traceln(Level.INFO, "");
236	}
237	*/
238
239	// now we iterate over all clusters (well, boxes of sizes per cluster really) and save the number of the
240	// cluster in which we are
241	int cnumber;
242	int found_cnumber = -1;
243	Iterator<Integer> clusternumber = this.csize.keySet().iterator();
244	while ( clusternumber.hasNext() && found_cnumber == -1) {
245	cnumber = clusternumber.next();
246
247	// now iterate over the boxes of the cluster and hope we find one (cluster could have been removed)
248	// or we are too far away from any cluster because of the fastmap calculation with the initial pivot objects
249	for ( int box=0; box < this.csize.get(cnumber).size(); box++ ) {
250	Double[][] current = this.csize.get(cnumber).get(box);
251
252	if(proj[0] >= current[0][0] && proj[0] <= current[0][1] && // x
253	proj[1] >= current[1][0] && proj[1] <= current[1][1]) { // y
254	found_cnumber = cnumber;
255	}
256	}
257	}
258
259	// we want to count how often we are really inside a cluster
260	//if ( found_cnumber == -1 ) {
261	// CNOTFOUND += 1;
262	//}else {
263	// CFOUND += 1;
264	//}
265
266	// now it can happen that we do not find a cluster because we deleted it previously (too few instances)
267	// or we get bigger distance measures from weka so that we are completely outside of our clusters.
268	// in these cases we just find the nearest cluster to our instance and use it for classification.
269	// to do that we use the EuclideanDistance again to compare our distance to all other Instances
270	// then we take the cluster of the closest weka instance
271	dist = new EuclideanDistance(traindata2);
272	if( !this.ctraindata.containsKey(found_cnumber) ) {
273	double min_distance = Double.MAX_VALUE;
274	clusternumber = ctraindata.keySet().iterator();
275	while ( clusternumber.hasNext() ) {
276	cnumber = clusternumber.next();
277	for(int i=0; i < ctraindata.get(cnumber).size(); i++) {
278	if(dist.distance(instance, ctraindata.get(cnumber).get(i)) <= min_distance) {
279	found_cnumber = cnumber;
280	min_distance = dist.distance(instance, ctraindata.get(cnumber).get(i));
281	}
282	}
283	}
284	}
285
286	// here we have the cluster where an instance has the minimum distance between itself and the
287	// instance we want to classify
288	// if we still have not found a cluster we exit because something is really wrong
289	if( found_cnumber == -1 ) {
290	Console.traceln(Level.INFO, String.format("ERROR matching instance to cluster with full search!"));
291	throw new RuntimeException("cluster not found with full search");
292	}
293
294	// classify the passed instance with the cluster we found and its training data
295	ret = cclassifier.get(found_cnumber).classifyInstance(classInstance);
296
297	}catch( Exception e ) {
298	Console.traceln(Level.INFO, String.format("ERROR matching instance to cluster!"));
299	throw new RuntimeException(e);
300	}
301	return ret;
302	}
303
304	@Override
305	public void buildClassifier(Instances traindata) throws Exception {
306
307	//Console.traceln(Level.INFO, String.format("found: "+ CFOUND + ", notfound: " + CNOTFOUND));
308	this.show_biggest = true;
309
310	cclassifier = new HashMap<Integer, Classifier>();
311	ctraindata = new HashMap<Integer, Instances>();
312	cpivots = new HashMap<Integer, Instance>();
313	cpivotindices = new int[2][2];
314
315	// 1. copy traindata
316	Instances train = new Instances(traindata);
317	Instances train2 = new Instances(traindata); // this one keeps the class attribute
318
319	// 2. remove class attribute for clustering
320	Remove filter = new Remove();
321	filter.setAttributeIndices("" + (train.classIndex() + 1));
322	filter.setInputFormat(train);
323	train = Filter.useFilter(train, filter);
324
325	// 3. calculate distance matrix (needed for Fastmap because it starts at dimension 1)
326	double biggest = 0;
327	EuclideanDistance dist = new EuclideanDistance(train);
328	double[][] distmat = new double[train.size()][train.size()];
329	for( int i=0; i < train.size(); i++ ) {
330	for( int j=0; j < train.size(); j++ ) {
331	distmat[i][j] = dist.distance(train.get(i), train.get(j));
332	if( distmat[i][j] > biggest ) {
333	biggest = distmat[i][j];
334	}
335	}
336	}
337	//Console.traceln(Level.INFO, String.format("biggest distances: "+ biggest));
338
339	// 4. run fastmap for 2 dimensions on the distance matrix
340	Fastmap FMAP = new Fastmap(2);
341	FMAP.setDistmat(distmat);
342	FMAP.calculate();
343
344	cpivotindices = FMAP.getPivots();
345
346	double[][] X = FMAP.getX();
347	distmat = new double[0][0];
348	System.gc();
349
350	// quadtree payload generation
351	ArrayList<QuadTreePayload<Instance>> qtp = new ArrayList<QuadTreePayload<Instance>>();
352
353	// we need these for the sizes of the quadrants
354	double[] big = {0,0};
355	double[] small = {Double.MAX_VALUE,Double.MAX_VALUE};
356
357	// set quadtree payload values and get max and min x and y values for size
358	for( int i=0; i<X.length; i++ ){
359	if(X[i][0] >= big[0]) {
360	big[0] = X[i][0];
361	}
362	if(X[i][1] >= big[1]) {
363	big[1] = X[i][1];
364	}
365	if(X[i][0] <= small[0]) {
366	small[0] = X[i][0];
367	}
368	if(X[i][1] <= small[1]) {
369	small[1] = X[i][1];
370	}
371	QuadTreePayload<Instance> tmp = new QuadTreePayload<Instance>(X[i][0], X[i][1], train2.get(i));
372	qtp.add(tmp);
373	}
374
375	//Console.traceln(Level.INFO, String.format("size for cluster ("+small[0]+","+small[1]+") - ("+big[0]+","+big[1]+")"));
376
377	// 5. generate quadtree
378	QuadTree TREE = new QuadTree(null, qtp);
379	QuadTree.size = train.size();
380	QuadTree.alpha = Math.sqrt(train.size());
381	QuadTree.ccluster = new ArrayList<ArrayList<QuadTreePayload<Instance>>>();
382	QuadTree.csize = new HashMap<Integer, ArrayList<Double[][]>>();
383
384	//Console.traceln(Level.INFO, String.format("Generate QuadTree with "+ QuadTree.size + " size, Alpha: "+ QuadTree.alpha+ ""));
385
386	// set the size and then split the tree recursively at the median value for x, y
387	TREE.setSize(new double[] {small[0], big[0]}, new double[] {small[1], big[1]});
388
389	// recursive split und grid clustering eher static
390	TREE.recursiveSplit(TREE);
391
392	// generate list of nodes sorted by density (childs only)
393	ArrayList<QuadTree> l = new ArrayList<QuadTree>(TREE.getList(TREE));
394
395	// recursive grid clustering (tree pruning), the values are stored in ccluster
396	TREE.gridClustering(l);
397
398	// wir iterieren durch die cluster und sammeln uns die instanzen daraus
399	//ctraindata.clear();
400	for( int i=0; i < QuadTree.ccluster.size(); i++ ) {
401	ArrayList<QuadTreePayload<Instance>> current = QuadTree.ccluster.get(i);
402
403	// i is the clusternumber
404	// we only allow clusters with Instances > ALPHA, other clusters are not considered!
405	//if(current.size() > QuadTree.alpha) {
406	if( current.size() > 4 ) {
407	for( int j=0; j < current.size(); j++ ) {
408	if( !ctraindata.containsKey(i) ) {
409	ctraindata.put(i, new Instances(train2));
410	ctraindata.get(i).delete();
411	}
412	ctraindata.get(i).add(current.get(j).getInst());
413	}
414	}else{
415	Console.traceln(Level.INFO, String.format("drop cluster, only: " + current.size() + " instances"));
416	}
417	}
418
419	// here we keep things we need later on
420	// QuadTree sizes for later use (matching new instances)
421	this.csize = new HashMap<Integer, ArrayList<Double[][]>>(QuadTree.csize);
422
423	// pivot elements
424	//this.cpivots.clear();
425	for( int i=0; i < FMAP.PA[0].length; i++ ) {
426	this.cpivots.put(FMAP.PA[0][i], (Instance)train.get(FMAP.PA[0][i]).copy());
427	}
428	for( int j=0; j < FMAP.PA[0].length; j++ ) {
429	this.cpivots.put(FMAP.PA[1][j], (Instance)train.get(FMAP.PA[1][j]).copy());
430	}
431
432
433	/* debug output
434	int pnumber;
435	Iterator<Integer> pivotnumber = cpivots.keySet().iterator();
436	while ( pivotnumber.hasNext() ) {
437	pnumber = pivotnumber.next();
438	Console.traceln(Level.INFO, String.format("pivot: "+pnumber+ " inst: "+cpivots.get(pnumber)));
439	}
440	*/
441
442	// train one classifier per cluster, we get the cluster number from the traindata
443	int cnumber;
444	Iterator<Integer> clusternumber = ctraindata.keySet().iterator();
445	//cclassifier.clear();
446
447	//int traindata_count = 0;
448	while ( clusternumber.hasNext() ) {
449	cnumber = clusternumber.next();
450	cclassifier.put(cnumber,setupClassifier()); // this is the classifier used for the cluster
451	cclassifier.get(cnumber).buildClassifier(ctraindata.get(cnumber));
452	//Console.traceln(Level.INFO, String.format("classifier in cluster "+cnumber));
453	//traindata_count += ctraindata.get(cnumber).size();
454	//Console.traceln(Level.INFO, String.format("building classifier in cluster "+cnumber +" with "+ ctraindata.get(cnumber).size() +" traindata instances"));
455	}
456
457	// add all traindata
458	//Console.traceln(Level.INFO, String.format("traindata in all clusters: " + traindata_count));
459	}
460	}
461
462
463	/**
464	* Payload for the QuadTree.
465	* x and y are the calculated Fastmap values.
466	* T is a weka instance.
467	*/
468	public class QuadTreePayload<T> {
469
470	public double x;
471	public double y;
472	private T inst;
473
474	public QuadTreePayload(double x, double y, T value) {
475	this.x = x;
476	this.y = y;
477	this.inst = value;
478	}
479
480	public T getInst() {
481	return this.inst;
482	}
483	}
484
485
486	/**
487	* Fastmap implementation
488	*
489	* Faloutsos, C., & Lin, K. I. (1995).
490	* FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets
491	* (Vol. 24, No. 2, pp. 163-174). ACM.
492	*/
493	public class Fastmap {
494
495	/N x k Array, at the end, the i-th row will be the image of the i-th object/
496	private double[][] X;
497
498	/2 x k pivot Array one pair per recursive call/
499	private int[][] PA;
500
501	/Objects we got (distance matrix)/
502	private double[][] O;
503
504	/column of X currently updated (also the dimension)/
505	private int col = 0;
506
507	/number of dimensions we want/
508	private int target_dims = 0;
509
510	// if we already have the pivot elements
511	private boolean pivot_set = false;
512
513
514	public Fastmap(int k) {
515	this.target_dims = k;
516	}
517
518	/**
519	* Sets the distance matrix
520	* and params that depend on this
521	* @param O
522	*/
523	public void setDistmat(double[][] O) {
524	this.O = O;
525	int N = O.length;
526	this.X = new double[N][this.target_dims];
527	this.PA = new int[2][this.target_dims];
528	}
529
530	/**
531	* Set pivot elements, we need that to classify instances
532	* after the calculation is complete (because we then want to reuse
533	* only the pivot elements).
534	*
535	* @param pi
536	*/
537	public void setPivots(int[][] pi) {
538	this.pivot_set = true;
539	this.PA = pi;
540	}
541
542	/**
543	* Return the pivot elements that were chosen during the calculation
544	*
545	* @return
546	*/
547	public int[][] getPivots() {
548	return this.PA;
549	}
550
551	/**
552	* The distance function for euclidean distance
553	*
554	* Acts according to equation 4 of the fastmap paper
555	*
556	* @param x x index of x image (if k==0 x object)
557	* @param y y index of y image (if k==0 y object)
558	* @param kdimensionality
559	* @return distance
560	*/
561	private double dist(int x, int y, int k) {
562
563	// basis is object distance, we get this from our distance matrix
564	double tmp = this.O[x][y] * this.O[x][y];
565
566	// decrease by projections
567	for( int i=0; i < k; i++ ) {
568	double tmp2 = (this.X[x][i] - this.X[y][i]);
569	tmp -= tmp2 * tmp2;
570	}
571
572	return Math.abs(tmp);
573	}
574
575	/**
576	* Find the object farthest from the given index
577	* This method is a helper Method for findDistandObjects
578	*
579	* @param index of the object
580	* @return index of the farthest object from the given index
581	*/
582	private int findFarthest(int index) {
583	double furthest = Double.MIN_VALUE;
584	int ret = 0;
585
586	for( int i=0; i < O.length; i++ ) {
587	double dist = this.dist(i, index, this.col);
588	if( i != index && dist > furthest ) {
589	furthest = dist;
590	ret = i;
591	}
592	}
593	return ret;
594	}
595
596	/**
597	* Finds the pivot objects
598	*
599	* This method is basically algorithm 1 of the fastmap paper.
600	*
601	* @return 2 indexes of the choosen pivot objects
602	*/
603	private int[] findDistantObjects() {
604	// 1. choose object randomly
605	Random r = new Random();
606	int obj = r.nextInt(this.O.length);
607
608	// 2. find farthest object from randomly chosen object
609	int idx1 = this.findFarthest(obj);
610
611	// 3. find farthest object from previously farthest object
612	int idx2 = this.findFarthest(idx1);
613
614	return new int[] {idx1, idx2};
615	}
616
617	/**
618	* Calculates the new k-vector values (projections)
619	*
620	* This is basically algorithm 2 of the fastmap paper.
621	* We just added the possibility to pre-set the pivot elements because
622	* we need to classify single instances after the computation is already done.
623	*
624	* @param dims dimensionality
625	*/
626	public void calculate() {
627
628	for( int k=0; k < this.target_dims; k++ ) {
629	// 2) choose pivot objects
630	if ( !this.pivot_set ) {
631	int[] pivots = this.findDistantObjects();
632
633	// 3) record ids of pivot objects
634	this.PA[0][this.col] = pivots[0];
635	this.PA[1][this.col] = pivots[1];
636	}
637
638	// 4) inter object distances are zero (this.X is initialized with 0 so we just continue)
639	if( this.dist(this.PA[0][this.col], this.PA[1][this.col], this.col) == 0 ) {
640	continue;
641	}
642
643	// 5) project the objects on the line between the pivots
644	double dxy = this.dist(this.PA[0][this.col], this.PA[1][this.col], this.col);
645	for( int i=0; i < this.O.length; i++ ) {
646
647	double dix = this.dist(i, this.PA[0][this.col], this.col);
648	double diy = this.dist(i, this.PA[1][this.col], this.col);
649
650	double tmp = (dix + dxy - diy) / (2 * Math.sqrt(dxy));
651
652	// save the projection
653	this.X[i][this.col] = tmp;
654	}
655
656	this.col += 1;
657	}
658	}
659
660	/**
661	* returns the result matrix of the projections
662	*
663	* @return calculated result
664	*/
665	public double[][] getX() {
666	return this.X;
667	}
668	}
669	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: