001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/machine-learning/clustering/src/main/jtemp/org/openimaj/ml/clustering/kmeans/Hierarchical#T#KMeansResult.jtemp
004*/
005/**
006 * Copyright (c) 2011, The University of Southampton and the individual contributors.
007 * All rights reserved.
008 *
009 * Redistribution and use in source and binary forms, with or without modification,
010 * are permitted provided that the following conditions are met:
011 *
012 *   *  Redistributions of source code must retain the above copyright notice,
013 *      this list of conditions and the following disclaimer.
014 *
015 *   *  Redistributions in binary form must reproduce the above copyright notice,
016 *      this list of conditions and the following disclaimer in the documentation
017 *      and/or other materials provided with the distribution.
018 *
019 *   *  Neither the name of the University of Southampton nor the names of its
020 *      contributors may be used to endorse or promote products derived from this
021 *      software without specific prior written permission.
022 *
023 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
024 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
025 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
026 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
027 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
028 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
029 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
030 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
031 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
032 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
033 */
034package org.openimaj.ml.clustering.kmeans;
035
036import java.io.DataInput;
037import java.io.DataOutput;
038import java.io.IOException;
039import java.io.PrintWriter;
040import java.util.Scanner;
041
042import org.openimaj.ml.clustering.ShortCentroidsResult;
043import org.openimaj.ml.clustering.SpatialClusters;
044import org.openimaj.ml.clustering.assignment.hard.HierarchicalShortHardAssigner;
045
046/** 
047 * The result of a {@link HierarchicalShortKMeans} clustering operation.
048 *
049 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
050 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
051 */
052public class HierarchicalShortKMeansResult implements SpatialClusters<short[]> {
053        /**
054         * HierarchicalShortKMeans tree node
055         *
056         * The number of children is not bigger than the HierarchicalShortKMeans K parameter
057         **/
058        public static class Node {
059                /** {@link ShortCentroidsResult} for this node */
060                public ShortCentroidsResult result;
061
062                /** Node children (if any) */
063                public Node[] children;
064        }
065        
066        private static final String HEADER = SpatialClusters.CLUSTER_HEADER + "H" +"Short".charAt(0) + "KM";
067        
068        /** Data dimensionality */
069        int M;
070
071        /** K clusters per node */
072        int K;
073        
074        /** Depth of the tree */
075        int depth;
076        
077        /** Tree root node */
078        Node root;
079
080        protected HierarchicalShortKMeansResult() {}
081
082        @Override
083        public int numDimensions() {
084                return M;
085        }
086        
087        /**
088         * Get the number of clusters per node
089         * @return number of clusters per node
090         */
091        public int getK() {
092                return K;
093        }
094
095        /**
096         * Get the depth of the cluster tree
097         * @return the depth of the cluster tree
098         */
099        public int getDepth() {
100                return depth;
101        }
102
103        /**
104         * Get the root node of the tree
105         * @return the root node of the tree
106         */
107        public Node getRoot() {
108                return root;
109        }
110
111        private static int ipow(int x, int y) {
112                int sum = 1;
113                for (int i=0; i<y; i++) 
114                        sum *= x;
115                return sum;
116        }
117
118        /**
119         * Translates a path down the KDTree as a cluster index. This allows the specification of K and the depth
120         * @param path
121         * @param depth
122         * @param K
123         * @return cluster index
124         */
125        public static int getIndex(int [] path, int depth, int K) {
126                int idx = 0;
127
128                for (int i=0; i<depth; i++) 
129                        idx += path[i] * ipow(K, depth-1-i);
130
131                return idx;
132        }
133
134        /**
135         * Translates a path down the KDTree as a cluster index. 
136         * @param path
137         * @return cluster index
138         */
139        public int getIndex(int [] path) {
140                return getIndex(path, depth, K);
141        }
142
143        /**
144         * Given an index, what was the path down the hierarchy that lead to it. Allows the specification of
145         * depth and number of clusters. 
146         * @param index
147         * @param depth
148         * @param K
149         * @return a hierarchy path
150         */
151        public static int [] getPath(int index, int depth, int K) {
152                int [] path = new int[depth];
153
154                for (int i=0; i<depth; i++) {
155                        int v = ipow(K, depth-1-i);
156
157                        for (int j=0; j<K; j++) {       
158                                int vp = v * j;
159                                int vpn = v * (j+1);
160
161                                if (index < vpn) {
162                                        path[i] = j;
163                                        index -= vp;
164                                        break;
165                                }
166                        }
167                }
168
169                return path;
170        }
171
172        /**
173         * Given an index, what was the path down the hierarchy that lead to it. Assumes the class depth and K.
174         * @param index
175         * @return a hierarchy path
176         */
177        public int [] getPath(int index) {
178                return getPath(index, depth, K);
179        }
180
181        private int countLeaves(Node node) {
182                int count = 0;
183                if (node.children == null) {
184                        count = node.result.numClusters();
185                } else {
186                        for (int i=0; i<node.result.numClusters(); i++) {
187                                count += countLeaves(node.children[i]);
188                        }
189                }
190                return count;
191        }
192
193        /**
194         * Count number of active leaf nodes.
195         * @return number of nodes.
196         */
197        public int countActiveLeafNodes() {
198                return countLeaves(root);
199        }
200        
201        @Override
202        public String toString() {
203                String s = "";
204                s += String.format("Number of dimensions:               %d\n", M);
205                s += String.format("Number of clusters:                 %d\n", K);
206                s += String.format("Number of levels:                   %d\n", depth);
207                s += String.format("Maximum number of leaf nodes:       %d\n", ipow(K, depth));
208                s += String.format("Number of leaf active nodes:        %d", countActiveLeafNodes());
209                return s;
210        }
211
212        /**
213         * Total number of leaves assuming leaves = K^depth
214         * @return number of leaves
215         */
216        public int countLeafs() {
217                return ipow(K, depth);
218        }
219
220        @Override
221        public int numClusters() {
222                return this.countLeafs();
223        }
224        
225        @Override
226        public boolean equals(Object o) {
227                if(!(o instanceof HierarchicalShortKMeansResult)) return false;
228                
229                HierarchicalShortKMeansResult other = (HierarchicalShortKMeansResult) o;
230                
231                return other.countActiveLeafNodes() == this.countActiveLeafNodes() && 
232                                other.getDepth() == this.getDepth() &&
233                                other.getK() == this.getK() &&
234                                other.numDimensions() == this.numDimensions();
235        }
236        
237        /**
238         * Given a path, get the cluster centroid associated with the cluster index of the path.  
239         * @param path
240         * @return the centroid of a given path
241         */
242        public short [] getClusterCentroid(int [] path) {
243                Node node = root;
244                
245                for (int i=0; i<path.length-1; i++) {
246                        node = node.children[path[i]];
247                }
248                
249                return node.result.getCentroids()[path[path.length-1]];
250        }
251        
252        @Override
253        public String asciiHeader() {
254                return "ASCII"+HEADER;
255        }
256
257        @Override
258        public byte[] binaryHeader() {
259                return HEADER.getBytes();
260        }
261
262        @Override
263        public void readASCII(Scanner reader) throws IOException {
264                M = Integer.parseInt(reader.nextLine());
265                K = Integer.parseInt(reader.nextLine());
266                depth = Integer.parseInt(reader.nextLine());
267
268                root = readNode(this,reader);
269        }
270        
271        private Node readNode(HierarchicalShortKMeansResult hShortkm, Scanner reader) throws IOException {
272                String line;
273                
274                while ((line = reader.nextLine()).length()==0) {/*do nothing*/}
275                
276                char type = line.charAt(0);
277
278                //read result data
279                Node node = new Node();
280                node.result = new ShortCentroidsResult();
281                node.result.readASCII(reader);
282                
283                if (type == 'I') {
284                        node.children = new Node[node.result.numClusters()];
285
286                        for (int i=0; i<node.result.numClusters(); i++) {
287                                node.children[i] = readNode(hShortkm,reader);
288                        }
289                } else {
290                        node.children = null;
291                }
292
293                return node ;
294        }
295        
296        @Override
297        public void readBinary(DataInput dis) throws IOException {
298                M = dis.readInt();
299                K = dis.readInt();
300                depth = dis.readInt();
301
302                root = readNodeB(this,dis);
303        }
304        
305        private Node readNodeB(HierarchicalShortKMeansResult hShortkm, DataInput dis) throws IOException {
306                Node node = new Node();
307                char type = (char) dis.readByte();
308
309                //read result data
310                node.result = new ShortCentroidsResult();
311                node.result.readBinary(dis);
312                
313                if (type == 'I') {
314                        node.children = new Node[node.result.numClusters()];
315
316                        for (int i=0; i<node.result.numClusters(); i++) {
317                                node.children[i] = readNodeB(hShortkm, dis);
318                        }
319                } else {
320                        node.children = null;
321                }
322
323                return node ;
324        }
325        
326        @Override
327        public void writeASCII(PrintWriter writer) throws IOException {
328                writer.format("%d\n", this.M);
329                writer.format("%d\n", this.K);
330                writer.format("%d\n", this.depth);
331
332                writeNodeASCII(writer, this.root);
333        }
334        
335        private void writeNodeASCII(PrintWriter writer, final Node node) throws IOException {
336                //write node type
337                if (node.children == null) 
338                        writer.write("L\n"); //intermediate
339                else
340                        writer.write("I\n"); //leaf
341
342                //write result data
343                node.result.writeASCII(writer); // node.result.writeASCII(writer, false);
344                writer.flush();
345                //write children
346                if (node.children != null) {
347                        for (int i=0; i<node.result.numClusters(); i++) {
348                                writeNodeASCII(writer, node.children[i]);
349                        }
350                }
351        }
352        
353        @Override
354        public void writeBinary(DataOutput dos) throws IOException {    
355                dos.writeInt(this.M);
356                dos.writeInt(this.K);
357                dos.writeInt(this.depth);
358        
359                writeNodeB(dos, this.root);
360        }
361        
362        private void writeNodeB(DataOutput dos, Node node) throws IOException {
363                //write node type
364                char type;
365                if (node.children == null) 
366                        type='L'; //intermediate
367                else
368                        type='I'; //leaf
369                dos.writeByte(type);
370
371                //write result data
372                node.result.writeBinary(dos);
373
374                //write children
375                if (node.children != null) {
376                        for (int i=0; i<node.result.numClusters(); i++) {
377                                writeNodeB(dos, node.children[i]);
378                        }
379                }
380        }
381        
382        @Override
383        public HierarchicalShortHardAssigner defaultHardAssigner() {
384                return new HierarchicalShortHardAssigner(this);
385        }
386}