source: trunk/CrossPare/src/de/ugoe/cs/cpdp/training/QuadTree.java @ 28

Last change on this file since 28 was 23, checked in by sherbold, 10 years ago
  • renamed new training classes
File size: 12.7 KB
Line 
1package de.ugoe.cs.cpdp.training;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.Comparator;
6import java.util.HashMap;
7
8import weka.core.Instance;
9import de.ugoe.cs.cpdp.training.WekaLocalFQTraining.QuadTreePayload;
10
11/**
12 * QuadTree implementation
13 *
14 * QuadTree gets a list of instances and then recursively split them into 4 childs
15 * For this it uses the median of the 2 values x,y
16 */
17public class QuadTree {
18       
19        /* 1 parent or null */
20        private QuadTree parent = null;
21       
22        /* 4 childs, 1 per quadrant */
23        private QuadTree child_nw;
24        private QuadTree child_ne;
25        private QuadTree child_se;
26        private QuadTree child_sw;
27       
28        /* list (only helps with generation of list of childs!) */
29        private ArrayList<QuadTree> l = new ArrayList<QuadTree>();
30       
31        /* level only used for debugging */
32        public int level = 0;
33       
34        /* size of the quadrant */
35        private double[] x;
36        private double[] y;
37       
38        public static boolean verbose = false;
39        public static int size = 0;
40        public static double alpha = 0;
41       
42        /* cluster payloads */
43        public static ArrayList<ArrayList<QuadTreePayload<Instance>>> ccluster = new ArrayList<ArrayList<QuadTreePayload<Instance>>>();
44       
45        /* cluster sizes (index is cluster number, arraylist is list of boxes (x0,y0,x1,y1) */
46        public static HashMap<Integer, ArrayList<Double[][]>> csize = new HashMap<Integer, ArrayList<Double[][]>>();
47       
48        /* payload of this instance */
49        private ArrayList<QuadTreePayload<Instance>> payload;
50
51       
52        public QuadTree(QuadTree parent, ArrayList<QuadTreePayload<Instance>> payload) {
53                this.parent = parent;
54                this.payload = payload;
55        }
56       
57       
58        public String toString() {
59                String n = "";
60                if(this.parent == null) {
61                        n += "rootnode ";
62                }
63                String level = new String(new char[this.level]).replace("\0", "-");
64                n += level + " instances: " + this.getNumbers();
65                return n;
66        }
67       
68        /**
69         * Returns the payload, used for clustering
70         * in the clustering list we only have children with paylod
71         *
72         * @return payload
73         */
74        public ArrayList<QuadTreePayload<Instance>> getPayload() {
75                return this.payload;
76        }
77       
78        /**
79         * Calculate the density of this quadrant
80         *
81         * density = number of instances / global size (all instances)
82         *
83         * @return density
84         */
85        public double getDensity() {
86                double dens = 0;
87                dens = (double)this.getNumbers() / QuadTree.size;
88                return dens;
89        }
90       
91        public void setSize(double[] x, double[] y){
92                this.x = x;
93                this.y = y;
94        }
95       
96        public double[][] getSize() {
97                return new double[][] {this.x, this.y};
98        }
99       
100        public Double[][] getSizeDouble() {
101                Double[] tmpX = new Double[2];
102                Double[] tmpY = new Double[2];
103               
104                tmpX[0] = this.x[0];
105                tmpX[1] = this.x[1];
106               
107                tmpY[0] = this.y[0];
108                tmpY[1] = this.y[1];
109               
110                return new Double[][] {tmpX, tmpY};
111        }
112       
113        /**
114         * TODO: DRY, median ist immer dasselbe
115         * 
116         * @return median for x
117         */
118        private double getMedianForX() {
119                double med_x =0 ;
120               
121                Collections.sort(this.payload, new Comparator<QuadTreePayload<Instance>>() {
122                @Override
123                public int compare(QuadTreePayload<Instance> x1, QuadTreePayload<Instance> x2) {
124                    return Double.compare(x1.x, x2.x);
125                }
126            });
127
128                if(this.payload.size() % 2 == 0) {
129                        int mid = this.payload.size() / 2;
130                        med_x = (this.payload.get(mid).x + this.payload.get(mid+1).x) / 2;
131                }else {
132                        int mid = this.payload.size() / 2;
133                        med_x = this.payload.get(mid).x;
134                }
135               
136                if(QuadTree.verbose) {
137                        System.out.println("sorted:");
138                        for(int i = 0; i < this.payload.size(); i++) {
139                                System.out.print(""+this.payload.get(i).x+",");
140                        }
141                        System.out.println("median x: " + med_x);
142                }
143                return med_x;
144        }
145       
146        private double getMedianForY() {
147                double med_y =0 ;
148               
149                Collections.sort(this.payload, new Comparator<QuadTreePayload<Instance>>() {
150                @Override
151                public int compare(QuadTreePayload<Instance> y1, QuadTreePayload<Instance> y2) {
152                    return Double.compare(y1.y, y2.y);
153                }
154            });
155               
156                if(this.payload.size() % 2 == 0) {
157                        int mid = this.payload.size() / 2;
158                        med_y = (this.payload.get(mid).y + this.payload.get(mid+1).y) / 2;
159                }else {
160                        int mid = this.payload.size() / 2;
161                        med_y = this.payload.get(mid).y;
162                }
163               
164                if(QuadTree.verbose) {
165                        System.out.println("sorted:");
166                        for(int i = 0; i < this.payload.size(); i++) {
167                                System.out.print(""+this.payload.get(i).y+",");
168                        }
169                        System.out.println("median y: " + med_y);
170                }
171                return med_y;
172        }
173       
174        /**
175         * Reurns the number of instances in the payload
176         *
177         * @return int number of instances
178         */
179        public int getNumbers() {
180                int number = 0;
181                if(this.payload != null) {
182                        number = this.payload.size();
183                }
184                return number;
185        }
186       
187        /**
188         * Calculate median values of payload for x, y and split into 4 sectors
189         *
190         * @return Array of QuadTree nodes (4 childs)
191         * @throws Exception if we would run into an recursive loop
192         */
193        public QuadTree[] split() throws Exception {
194                               
195                double medx = this.getMedianForX();
196                double medy = this.getMedianForY();
197               
198                // Payload lists for each child
199                ArrayList<QuadTreePayload<Instance>> nw = new ArrayList<QuadTreePayload<Instance>>();
200                ArrayList<QuadTreePayload<Instance>> sw = new ArrayList<QuadTreePayload<Instance>>();
201                ArrayList<QuadTreePayload<Instance>> ne = new ArrayList<QuadTreePayload<Instance>>();
202                ArrayList<QuadTreePayload<Instance>> se = new ArrayList<QuadTreePayload<Instance>>();
203               
204                // sort the payloads to new payloads
205                // here we have the problem that payloads with the same values are sorted
206                // into the same slots and it could happen that medx and medy = size_x[1] and size_y[1]
207                // in that case we would have an endless loop
208                for(int i=0; i < this.payload.size(); i++) {
209                       
210                        QuadTreePayload<Instance> item = this.payload.get(i);
211                       
212                        // north west
213                        if(item.x <= medx && item.y >= medy) {
214                                nw.add(item);
215                        }
216                       
217                        // south west
218                        else if(item.x <= medx && item.y <= medy) {
219                                sw.add(item);
220                        }
221
222                        // north east
223                        else if(item.x >= medx && item.y >= medy) {
224                                ne.add(item);
225                        }
226                       
227                        // south east
228                        else if(item.x >= medx && item.y <= medy) {
229                                se.add(item);
230                        }
231                }
232               
233                // if we assign one child a payload equal to our own (see problem above)
234                // we throw an exceptions which stops the recursion on this node
235                if(nw.equals(this.payload)) {
236                        throw new Exception("payload equal");
237                }
238                if(sw.equals(this.payload)) {
239                        throw new Exception("payload equal");
240                }
241                if(ne.equals(this.payload)) {
242                        throw new Exception("payload equal");
243                }
244                if(se.equals(this.payload)) {
245                        throw new Exception("payload equal");
246                }
247
248                this.child_nw = new QuadTree(this, nw);
249                this.child_nw.setSize(new double[] {this.x[0], medx}, new double[] {medy, this.y[1]});
250                this.child_nw.level = this.level + 1;
251               
252                this.child_sw = new QuadTree(this, sw);
253                this.child_sw.setSize(new double[] {this.x[0], medx}, new double[] {this.y[0], medy});
254                this.child_sw.level = this.level + 1;
255               
256                this.child_ne = new QuadTree(this, ne);
257                this.child_ne.setSize(new double[] {medx, this.x[1]}, new double[] {medy, this.y[1]});
258                this.child_ne.level = this.level + 1;
259               
260                this.child_se = new QuadTree(this, se);
261                this.child_se.setSize(new double[] {medx, this.x[1]}, new double[] {this.y[0], medy});
262                this.child_se.level = this.level + 1;   
263               
264                this.payload = null;
265                return new QuadTree[] {this.child_nw, this.child_ne, this.child_se, this.child_sw};
266        }
267       
268        /**
269         * TODO: static method
270         *
271         * @param q
272         */
273        public void recursiveSplit(QuadTree q) {
274                if(QuadTree.verbose) {
275                        System.out.println("splitting: "+ q);
276                }
277                if(q.getNumbers() < QuadTree.alpha) {
278                        return;
279                }else{
280                        // exception is thrown if we would run into an endless loop (see comments in split())
281                        try {
282                                QuadTree[] childs = q.split();                 
283                                this.recursiveSplit(childs[0]);
284                                this.recursiveSplit(childs[1]);
285                                this.recursiveSplit(childs[2]);
286                                this.recursiveSplit(childs[3]);
287                        }catch(Exception e) {
288                                return;
289                        }
290                }
291        }
292       
293        /**
294         * returns an list of childs sorted by density
295         *
296         * @param q QuadTree
297         * @return list of QuadTrees
298         */
299        private void generateList(QuadTree q) {
300               
301                // we only have all childs or none at all
302                if(q.child_ne == null) {
303                        this.l.add(q);
304                }
305               
306                if(q.child_ne != null) {
307                        this.generateList(q.child_ne);
308                }
309                if(q.child_nw != null) {
310                        this.generateList(q.child_nw);
311                }
312                if(q.child_se != null) {
313                        this.generateList(q.child_se);
314                }
315                if(q.child_sw != null) {
316                        this.generateList(q.child_sw);
317                }
318        }
319       
320        /**
321         * Checks if passed QuadTree is neighboring to us
322         *
323         * @param q QuadTree
324         * @return true if passed QuadTree is a neighbor
325         */
326        public boolean isNeighbour(QuadTree q) {
327                boolean is_neighbour = false;
328               
329                double[][] our_size = this.getSize();
330                double[][] new_size = q.getSize();
331               
332                // X is i=0, Y is i=1
333                for(int i =0; i < 2; i++) {
334                        // we are smaller than q
335                        // -------------- q
336                        //    ------- we
337                        if(our_size[i][0] >= new_size[i][0] && our_size[i][1] <= new_size[i][1]) {
338                                is_neighbour = true;
339                        }
340                        // we overlap with q at some point
341                        //a) ---------------q
342                        //         ----------- we
343                        //b)     --------- q
344                        // --------- we
345                        if((our_size[i][0] >= new_size[i][0] && our_size[i][0] <= new_size[i][1]) ||
346                           (our_size[i][1] >= new_size[i][0] && our_size[i][1] <= new_size[i][1])) {
347                                is_neighbour = true;
348                        }
349                        // we are larger than q
350                        //    ---- q
351                        // ---------- we
352                        if(our_size[i][1] >= new_size[i][1] && our_size[i][0] <= new_size[i][0]) {
353                                is_neighbour = true;
354                        }
355                }
356               
357                if(is_neighbour && QuadTree.verbose) {
358                        System.out.println(this + " neighbour of: " + q);
359                }
360               
361                return is_neighbour;
362        }
363       
364        /**
365         * Perform pruning and clustering of the quadtree
366         *
367         * Pruning according to:
368         * Tim Menzies, Andrew Butcher, David Cok, Andrian Marcus, Lucas Layman,
369         * Forrest Shull, Burak Turhan, Thomas Zimmermann,
370         * "Local versus Global Lessons for Defect Prediction and Effort Estimation,"
371         * IEEE Transactions on Software Engineering, vol. 39, no. 6, pp. 822-834, June, 2013 
372         * 
373         * 1) get list of leaf quadrants
374         * 2) sort by their density
375         * 3) set stop_rule to 0.5 * highest Density in the list
376         * 4) merge all nodes with a density > stop_rule to the new cluster and remove all from list
377         * 5) repeat
378         *
379         * @param q List of QuadTree (children only)
380         */
381        public void gridClustering(ArrayList<QuadTree> list) {
382               
383                if(list.size() == 0) {
384                        return;
385                }
386               
387                double stop_rule;
388                QuadTree biggest;
389                QuadTree current;
390               
391                // current clusterlist
392                ArrayList<QuadTreePayload<Instance>> current_cluster;
393
394                // remove list (for removal of items after scanning of the list)
395            ArrayList<Integer> remove = new ArrayList<Integer>();
396               
397                // 1. find biggest, and add it
398            biggest = list.get(list.size()-1);
399            stop_rule = biggest.getDensity() * 0.5;
400           
401            current_cluster = new ArrayList<QuadTreePayload<Instance>>();
402            current_cluster.addAll(biggest.getPayload());
403
404            // remove the biggest because we are starting with it
405            remove.add(list.size()-1);
406           
407            ArrayList<Double[][]> tmpSize = new ArrayList<Double[][]>();
408            tmpSize.add(biggest.getSizeDouble());
409           
410                // check the items for their density
411            for(int i=list.size()-1; i >= 0; i--) {
412                current = list.get(i);
413               
414                        // 2. find neighbors with correct density
415                // if density > stop_rule and is_neighbour add to cluster and remove from list
416                if(current.getDensity() > stop_rule && !current.equals(biggest) && current.isNeighbour(biggest)) {
417                        current_cluster.addAll(current.getPayload());
418                       
419                        // add it to remove list (we cannot remove it inside the loop because it would move the index)
420                        remove.add(i);
421                       
422                        // get the size
423                        tmpSize.add(current.getSizeDouble());
424                }
425                }
426           
427                // 3. remove our removal candidates from the list
428            for(Integer item: remove) {
429                list.remove((int)item);
430            }
431           
432                // 4. add to cluster
433            QuadTree.ccluster.add(current_cluster);
434               
435            // 5. add sizes of our current (biggest) this adds a number of sizes (all QuadTree Instances belonging to this cluster)
436            // we need that to classify test instances to a cluster later
437            Integer cnumber = new Integer(QuadTree.ccluster.size()-1);
438            if(QuadTree.csize.containsKey(cnumber) == false) {
439                QuadTree.csize.put(cnumber, tmpSize);
440            }
441
442                // repeat
443            this.gridClustering(list);
444        }
445       
446        public void printInfo() {
447            System.out.println("we have " + ccluster.size() + " clusters");
448           
449            for(int i=0; i < ccluster.size(); i++) {
450                System.out.println("cluster: "+i+ " size: "+ ccluster.get(i).size());
451            }
452        }
453       
454        /**
455         * Helper Method to get a sorted list (by density) for all
456         * children
457         *
458         * @param q QuadTree
459         * @return Sorted ArrayList of quadtrees
460         */
461        public ArrayList<QuadTree> getList(QuadTree q) {
462                this.generateList(q);
463               
464                Collections.sort(this.l, new Comparator<QuadTree>() {
465                @Override
466                public int compare(QuadTree x1, QuadTree x2) {
467                    return Double.compare(x1.getDensity(), x2.getDensity());
468                }
469            });
470               
471                return this.l;
472        }
473}
Note: See TracBrowser for help on using the repository browser.