001    /*
002     * Copyright (C) 2008-2010 by Holger Arndt
003     *
004     * This file is part of the Universal Java Matrix Package (UJMP).
005     * See the NOTICE file distributed with this work for additional
006     * information regarding copyright ownership and licensing.
007     *
008     * UJMP is free software; you can redistribute it and/or modify
009     * it under the terms of the GNU Lesser General Public License as
010     * published by the Free Software Foundation; either version 2
011     * of the License, or (at your option) any later version.
012     *
013     * UJMP is distributed in the hope that it will be useful,
014     * but WITHOUT ANY WARRANTY; without even the implied warranty of
015     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
016     * GNU Lesser General Public License for more details.
017     *
018     * You should have received a copy of the GNU Lesser General Public
019     * License along with UJMP; if not, write to the
020     * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
021     * Boston, MA  02110-1301  USA
022     */
023    
024    package org.ujmp.core.doublematrix.calculation.general.missingvalues;
025    
026    import java.util.ArrayList;
027    import java.util.Collections;
028    import java.util.List;
029    
030    import org.ujmp.core.Matrix;
031    import org.ujmp.core.doublematrix.calculation.AbstractDoubleCalculation;
032    import org.ujmp.core.exceptions.MatrixException;
033    import org.ujmp.core.util.MathUtil;
034    import org.ujmp.core.util.Sortable;
035    
036    public class ImputeKNN extends AbstractDoubleCalculation {
037            private static final long serialVersionUID = -4923873199518001578L;
038    
039            private Matrix distanceMatrix = null;
040    
041            private int k = 1;
042    
043            public ImputeKNN(Matrix matrix, Object... parameters) {
044                    super(matrix);
045                    if (parameters.length != 0) {
046                            k = MathUtil.getInt(parameters[0]);
047                    }
048            }
049    
050            private List<Integer> getCandidates(long... coordinates) {
051                    List<Integer> candidates = new ArrayList<Integer>();
052                    for (int r = 0; r < getSource().getRowCount(); r++) {
053                            if (coordinates[ROW] == r) {
054                                    continue;
055                            }
056                            if (!MathUtil.isNaNOrInfinite(getSource().getAsDouble(r, coordinates[COLUMN]))) {
057                                    candidates.add(r);
058                            }
059                    }
060                    return candidates;
061            }
062    
063            private Matrix getDistanceMatrix() {
064                    Matrix distanceMatrix = Matrix.factory.zeros(getSource().getRowCount(), getSource()
065                                    .getRowCount());
066                    for (int r = 0; r < getSource().getRowCount(); r++) {
067                            for (int c = 0; c < getSource().getRowCount(); c++) {
068                                    if (r != c) {
069                                            Matrix m1 = getSource().selectRows(Ret.LINK, r);
070                                            Matrix m2 = getSource().selectRows(Ret.LINK, c);
071                                            double dist = m1.euklideanDistanceTo(m2, true);
072                                            distanceMatrix.setAsDouble(dist, r, c);
073                                    }
074                            }
075                    }
076                    return distanceMatrix;
077            }
078    
079            private List<Sortable<Double, Matrix>> getSortedNeighbors(long... coordinates) {
080                    List<Sortable<Double, Matrix>> neighbors = new ArrayList<Sortable<Double, Matrix>>();
081                    List<Integer> candidates = getCandidates(coordinates);
082    
083                    for (int candidateRow : candidates) {
084                            double dist = distanceMatrix.getAsDouble(coordinates[ROW], candidateRow);
085                            Matrix candidate = getSource().selectRows(Ret.LINK, candidateRow);
086                            neighbors.add(new Sortable<Double, Matrix>(dist, candidate));
087                    }
088    
089                    Collections.sort(neighbors);
090                    return neighbors;
091            }
092    
093            public double getDouble(long... coordinates) throws MatrixException {
094                    if (distanceMatrix == null) {
095                            distanceMatrix = getDistanceMatrix();
096                    }
097                    double value = getSource().getAsDouble(coordinates);
098                    if (MathUtil.isNaNOrInfinite(value)) {
099                            List<Sortable<Double, Matrix>> sortedNeighbors = getSortedNeighbors(coordinates);
100                            double sum = 0;
101                            int count = 0;
102                            for (Sortable<Double, Matrix> s : sortedNeighbors) {
103                                    sum += s.getObject().getAsDouble(0, coordinates[COLUMN]);
104                                    if (++count == k) {
105                                            break;
106                                    }
107                            }
108                            return sum / count;
109                    } else {
110                            return value;
111                    }
112            }
113    
114    }