001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.ml.clustering.incremental;
031
032import gnu.trove.map.hash.TIntIntHashMap;
033import gnu.trove.set.TIntSet;
034
035import java.util.List;
036import java.util.Map;
037import java.util.Map.Entry;
038
039import org.openimaj.ml.clustering.IndexClusters;
040import org.openimaj.ml.clustering.SparseMatrixClusterer;
041import org.openimaj.util.pair.IntDoublePair;
042
043/**
044 *
045 * An {@link IncrementalSparseClusterer} which also has a notion of a lifetime.
046 * A lifetime is the number of windows which a given item is allowed to live before it
047 * must be clustered. 
048 * 
049 * By default this value is 3, meaning if 3 windows pass and a given row was not in a valid cluster,
050 * it is classified as noise and removed from clustering. More specifically it is added to a cluster
051 * of its own in isolation
052 * 
053 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
054 */
055public class IncrementalLifetimeSparseClusterer extends IncrementalSparseClusterer{
056        
057        
058
059        private int lifetime;
060        private TIntIntHashMap seenCount;
061
062        /**
063         * @param clusterer the underlying clusterer
064         * @param window 
065         */
066        public IncrementalLifetimeSparseClusterer(SparseMatrixClusterer<? extends IndexClusters> clusterer, int window) {
067                super(clusterer, window);
068                this.lifetime = 3;
069                this.seenCount = new TIntIntHashMap();
070        }
071        
072        /**
073         * @param clusterer the underlying clusterer
074         * @param window 
075         * @param lifetime 
076         */
077        public IncrementalLifetimeSparseClusterer(SparseMatrixClusterer<? extends IndexClusters> clusterer, int window, int lifetime) {
078                super(clusterer, window);
079                this.lifetime = lifetime;
080                this.seenCount = new TIntIntHashMap();
081        }
082        
083        /**
084         * @param clusterer the underlying clusterer
085         * @param window 
086         * @param threshold 
087         * @param lifetime 
088         */
089        public IncrementalLifetimeSparseClusterer(SparseMatrixClusterer<? extends IndexClusters> clusterer, int window, double threshold, int lifetime) {
090                super(clusterer, window, threshold);
091                this.lifetime = lifetime;
092                this.seenCount = new TIntIntHashMap();
093        }
094        
095        @Override
096        protected void detectInactive(IndexClusters oldClusters, IndexClusters newClusters, TIntSet inactiveRows, List<int[]> completedClusters) {
097                Map<Integer, IntDoublePair> stability = calculateStability(oldClusters,newClusters, inactiveRows);
098                for (Entry<Integer, IntDoublePair> e : stability.entrySet()) {
099                        int[] completedCluster = oldClusters.clusters()[e.getKey()];
100                        if(e.getValue().second >= threshold){
101                                for (int i = 0; i < completedCluster.length; i++) {
102                                        int index = completedCluster[i];
103                                        inactiveRows.add(index);
104                                        this.seenCount.remove(index);
105                                }
106                                completedClusters.add(completedCluster);
107                        }
108                        else{
109                                for (int i = 0; i < completedCluster.length; i++) {
110                                        int index = completedCluster[i];
111                                        int newCount = this.seenCount.adjustOrPutValue(index, 1, 1);
112                                        if(newCount>= this.lifetime){
113                                                this.seenCount.remove(index);
114                                                inactiveRows.add(index);
115                                                completedClusters.add(new int[]{index});
116                                        }
117                                }
118                        }
119                }
120        }
121        
122
123        
124}