http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/OrderedIntDoubleMapping.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/OrderedIntDoubleMapping.java b/core/src/main/java/org/apache/mahout/math/OrderedIntDoubleMapping.java deleted file mode 100644 index 7c6ad11..0000000 --- a/core/src/main/java/org/apache/mahout/math/OrderedIntDoubleMapping.java +++ /dev/null @@ -1,265 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.mahout.math; - -import java.io.Serializable; - -public final class OrderedIntDoubleMapping implements Serializable, Cloneable { - - static final double DEFAULT_VALUE = 0.0; - - private int[] indices; - private double[] values; - private int numMappings; - - // If true, doesn't allow DEFAULT_VALUEs in the mapping (adding a zero discards it). Otherwise, a DEFAULT_VALUE is - // treated like any other value. - private boolean noDefault = true; - - OrderedIntDoubleMapping(boolean noDefault) { - this(); - this.noDefault = noDefault; - } - - OrderedIntDoubleMapping() { - // no-arg constructor for deserializer - this(11); - } - - OrderedIntDoubleMapping(int capacity) { - indices = new int[capacity]; - values = new double[capacity]; - numMappings = 0; - } - - OrderedIntDoubleMapping(int[] indices, double[] values, int numMappings) { - this.indices = indices; - this.values = values; - this.numMappings = numMappings; - } - - public int[] getIndices() { - return indices; - } - - public int indexAt(int offset) { - return indices[offset]; - } - - public void setIndexAt(int offset, int index) { - indices[offset] = index; - } - - public double[] getValues() { - return values; - } - - public void setValueAt(int offset, double value) { - values[offset] = value; - } - - - public int getNumMappings() { - return numMappings; - } - - private void growTo(int newCapacity) { - if (newCapacity > indices.length) { - int[] newIndices = new int[newCapacity]; - System.arraycopy(indices, 0, newIndices, 0, numMappings); - indices = newIndices; - double[] newValues = new double[newCapacity]; - System.arraycopy(values, 0, newValues, 0, numMappings); - values = newValues; - } - } - - private int find(int index) { - int low = 0; - int high = numMappings - 1; - while (low <= high) { - int mid = low + (high - low >>> 1); - int midVal = indices[mid]; - if (midVal < index) { - low = mid + 1; - } else if (midVal > index) { - high = mid - 1; - } else { - return mid; - } - } - return -(low + 1); - } - - public double get(int index) { - int offset = find(index); - return offset >= 0 ? values[offset] : DEFAULT_VALUE; - } - - public void set(int index, double value) { - if (numMappings == 0 || index > indices[numMappings - 1]) { - if (!noDefault || value != DEFAULT_VALUE) { - if (numMappings >= indices.length) { - growTo(Math.max((int) (1.2 * numMappings), numMappings + 1)); - } - indices[numMappings] = index; - values[numMappings] = value; - ++numMappings; - } - } else { - int offset = find(index); - if (offset >= 0) { - insertOrUpdateValueIfPresent(offset, value); - } else { - insertValueIfNotDefault(index, offset, value); - } - } - } - - /** - * Merges the updates in linear time by allocating new arrays and iterating through the existing indices and values - * and the updates' indices and values at the same time while selecting the minimum index to set at each step. - * @param updates another list of mappings to be merged in. - */ - public void merge(OrderedIntDoubleMapping updates) { - int[] updateIndices = updates.getIndices(); - double[] updateValues = updates.getValues(); - - int newNumMappings = numMappings + updates.getNumMappings(); - int newCapacity = Math.max((int) (1.2 * newNumMappings), newNumMappings + 1); - int[] newIndices = new int[newCapacity]; - double[] newValues = new double[newCapacity]; - - int k = 0; - int i = 0, j = 0; - for (; i < numMappings && j < updates.getNumMappings(); ++k) { - if (indices[i] < updateIndices[j]) { - newIndices[k] = indices[i]; - newValues[k] = values[i]; - ++i; - } else if (indices[i] > updateIndices[j]) { - newIndices[k] = updateIndices[j]; - newValues[k] = updateValues[j]; - ++j; - } else { - newIndices[k] = updateIndices[j]; - newValues[k] = updateValues[j]; - ++i; - ++j; - } - } - - for (; i < numMappings; ++i, ++k) { - newIndices[k] = indices[i]; - newValues[k] = values[i]; - } - for (; j < updates.getNumMappings(); ++j, ++k) { - newIndices[k] = updateIndices[j]; - newValues[k] = updateValues[j]; - } - - indices = newIndices; - values = newValues; - numMappings = k; - } - - @Override - public int hashCode() { - int result = 0; - for (int i = 0; i < numMappings; i++) { - result = 31 * result + indices[i]; - result = 31 * result + (int) Double.doubleToRawLongBits(values[i]); - } - return result; - } - - @Override - public boolean equals(Object o) { - if (o instanceof OrderedIntDoubleMapping) { - OrderedIntDoubleMapping other = (OrderedIntDoubleMapping) o; - if (numMappings == other.numMappings) { - for (int i = 0; i < numMappings; i++) { - if (indices[i] != other.indices[i] || values[i] != other.values[i]) { - return false; - } - } - return true; - } - } - return false; - } - - @Override - public String toString() { - StringBuilder result = new StringBuilder(10 * numMappings); - for (int i = 0; i < numMappings; i++) { - result.append('('); - result.append(indices[i]); - result.append(','); - result.append(values[i]); - result.append(')'); - } - return result.toString(); - } - - @SuppressWarnings("CloneDoesntCallSuperClone") - @Override - public OrderedIntDoubleMapping clone() { - return new OrderedIntDoubleMapping(indices.clone(), values.clone(), numMappings); - } - - public void increment(int index, double increment) { - int offset = find(index); - if (offset >= 0) { - double newValue = values[offset] + increment; - insertOrUpdateValueIfPresent(offset, newValue); - } else { - insertValueIfNotDefault(index, offset, increment); - } - } - - private void insertValueIfNotDefault(int index, int offset, double value) { - if (!noDefault || value != DEFAULT_VALUE) { - if (numMappings >= indices.length) { - growTo(Math.max((int) (1.2 * numMappings), numMappings + 1)); - } - int at = -offset - 1; - if (numMappings > at) { - for (int i = numMappings - 1, j = numMappings; i >= at; i--, j--) { - indices[j] = indices[i]; - values[j] = values[i]; - } - } - indices[at] = index; - values[at] = value; - numMappings++; - } - } - - private void insertOrUpdateValueIfPresent(int offset, double newValue) { - if (noDefault && newValue == DEFAULT_VALUE) { - for (int i = offset + 1, j = offset; i < numMappings; i++, j++) { - indices[j] = indices[i]; - values[j] = values[i]; - } - numMappings--; - } else { - values[offset] = newValue; - } - } -}
http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/OrthonormalityVerifier.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/OrthonormalityVerifier.java b/core/src/main/java/org/apache/mahout/math/OrthonormalityVerifier.java deleted file mode 100644 index e8dd2b1..0000000 --- a/core/src/main/java/org/apache/mahout/math/OrthonormalityVerifier.java +++ /dev/null @@ -1,46 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.mahout.math; - -import com.google.common.collect.Lists; - -import java.util.List; - -public final class OrthonormalityVerifier { - - private OrthonormalityVerifier() { - } - - public static VectorIterable pairwiseInnerProducts(Iterable<MatrixSlice> basis) { - DenseMatrix out = null; - for (MatrixSlice slice1 : basis) { - List<Double> dots = Lists.newArrayList(); - for (MatrixSlice slice2 : basis) { - dots.add(slice1.vector().dot(slice2.vector())); - } - if (out == null) { - out = new DenseMatrix(dots.size(), dots.size()); - } - for (int i = 0; i < dots.size(); i++) { - out.set(slice1.index(), i, dots.get(i)); - } - } - return out; - } - -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/PermutedVectorView.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/PermutedVectorView.java b/core/src/main/java/org/apache/mahout/math/PermutedVectorView.java deleted file mode 100644 index 4659f03..0000000 --- a/core/src/main/java/org/apache/mahout/math/PermutedVectorView.java +++ /dev/null @@ -1,250 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.mahout.math; - -import java.util.Iterator; - -import com.google.common.collect.AbstractIterator; - -/** - * Provides a permuted view of a vector. - */ -public class PermutedVectorView extends AbstractVector { - private final Vector vector; // the vector containing the data - private final int[] pivot; // convert from external index to internal - private final int[] unpivot; // convert from internal index to external - - public PermutedVectorView(Vector vector, int[] pivot, int[] unpivot) { - super(vector.size()); - this.vector = vector; - this.pivot = pivot; - this.unpivot = unpivot; - } - - public PermutedVectorView(Vector vector, int[] pivot) { - this(vector, pivot, reversePivotPermutation(pivot)); - } - - private static int[] reversePivotPermutation(int[] pivot) { - int[] unpivot1 = new int[pivot.length]; - for (int i = 0; i < pivot.length; i++) { - unpivot1[pivot[i]] = i; - } - return unpivot1; - } - - /** - * Subclasses must override to return an appropriately sparse or dense result - * - * @param rows the row cardinality - * @param columns the column cardinality - * @return a Matrix - */ - @Override - protected Matrix matrixLike(int rows, int columns) { - if (vector.isDense()) { - return new DenseMatrix(rows, columns); - } else { - return new SparseRowMatrix(rows, columns); - } - } - - /** - * Used internally by assign() to update multiple indices and values at once. - * Only really useful for sparse vectors (especially SequentialAccessSparseVector). - * <p> - * If someone ever adds a new type of sparse vectors, this method must merge (index, value) pairs into the vector. - * - * @param updates a mapping of indices to values to merge in the vector. - */ - @Override - public void mergeUpdates(OrderedIntDoubleMapping updates) { - for (int i = 0; i < updates.getNumMappings(); ++i) { - updates.setIndexAt(i, pivot[updates.indexAt(i)]); - } - vector.mergeUpdates(updates); - } - - /** - * @return true iff this implementation should be considered dense -- that it explicitly - * represents every value - */ - @Override - public boolean isDense() { - return vector.isDense(); - } - - /** - * If the view is permuted, the elements cannot be accessed in the same order. - * - * @return true iff this implementation should be considered to be iterable in index order in an - * efficient way. In particular this implies that {@link #iterator()} and {@link - * #iterateNonZero()} return elements in ascending order by index. - */ - @Override - public boolean isSequentialAccess() { - return false; - } - - /** - * Iterates over all elements <p> * NOTE: Implementations may choose to reuse the Element - * returned for performance reasons, so if you need a copy of it, you should call {@link - * #getElement(int)} for the given index - * - * @return An {@link Iterator} over all elements - */ - @Override - public Iterator<Element> iterator() { - return new AbstractIterator<Element>() { - private final Iterator<Element> i = vector.all().iterator(); - - @Override - protected Vector.Element computeNext() { - if (i.hasNext()) { - final Element x = i.next(); - return new Element() { - private final int index = unpivot[x.index()]; - - @Override - public double get() { - return x.get(); - } - - @Override - public int index() { - return index; - } - - @Override - public void set(double value) { - x.set(value); - } - }; - } else { - return endOfData(); - } - } - }; - } - - /** - * Iterates over all non-zero elements. <p> NOTE: Implementations may choose to reuse the Element - * returned for performance reasons, so if you need a copy of it, you should call {@link - * #getElement(int)} for the given index - * - * @return An {@link Iterator} over all non-zero elements - */ - @Override - public Iterator<Element> iterateNonZero() { - return new AbstractIterator<Element>() { - private final Iterator<Element> i = vector.nonZeroes().iterator(); - - @Override - protected Vector.Element computeNext() { - if (i.hasNext()) { - final Element x = i.next(); - return new Element() { - private final int index = unpivot[x.index()]; - - @Override - public double get() { - return x.get(); - } - - @Override - public int index() { - return index; - } - - @Override - public void set(double value) { - x.set(value); - } - }; - } else { - return endOfData(); - } - } - }; - } - - /** - * Return the value at the given index, without checking bounds - * - * @param index an int index - * @return the double at the index - */ - @Override - public double getQuick(int index) { - return vector.getQuick(pivot[index]); - } - - /** - * Return an empty vector of the same underlying class as the receiver - * - * @return a Vector - */ - @Override - public Vector like() { - return vector.like(); - } - - @Override - public Vector like(int cardinality) { - return vector.like(cardinality); - } - - /** - * Set the value at the given index, without checking bounds - * - * @param index an int index into the receiver - * @param value a double value to set - */ - @Override - public void setQuick(int index, double value) { - vector.setQuick(pivot[index], value); - } - - /** Return the number of values in the recipient */ - @Override - public int getNumNondefaultElements() { - return vector.getNumNondefaultElements(); - } - - @Override - public int getNumNonZeroElements() { - // Return the number of nonzeros in the recipient, - // so potentially don't have to go through our iterator - return vector.getNumNonZeroElements(); - } - - @Override - public double getLookupCost() { - return vector.getLookupCost(); - } - - @Override - public double getIteratorAdvanceCost() { - return vector.getIteratorAdvanceCost(); - } - - @Override - public boolean isAddConstantTime() { - return vector.isAddConstantTime(); - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/PersistentObject.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/PersistentObject.java b/core/src/main/java/org/apache/mahout/math/PersistentObject.java deleted file mode 100644 index f1d4293..0000000 --- a/core/src/main/java/org/apache/mahout/math/PersistentObject.java +++ /dev/null @@ -1,58 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ -/* -Copyright 1999 CERN - European Organization for Nuclear Research. -Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose -is hereby granted without fee, provided that the above copyright notice appear in all copies and -that both that copyright notice and this permission notice appear in supporting documentation. -CERN makes no representations about the suitability of this software for any purpose. -It is provided "as is" without expressed or implied warranty. -*/ -package org.apache.mahout.math; - -/** - * This empty class is the common root for all persistent capable classes. - * If this class inherits from <tt>java.lang.Object</tt> then all subclasses are serializable with - * the standard Java serialization mechanism. - * If this class inherits from <tt>com.objy.db.app.ooObj</tt> then all subclasses are - * <i>additionally</i> serializable with the Objectivity ODBMS persistance mechanism. - * Thus, by modifying the inheritance of this class the entire tree of subclasses can - * be switched to Objectivity compatibility (and back) with minimum effort. - */ -public abstract class PersistentObject implements java.io.Serializable, Cloneable { - - /** Not yet commented. */ - protected PersistentObject() { - } - - /** - * Returns a copy of the receiver. This default implementation does not nothing except making the otherwise - * <tt>protected</tt> clone method <tt>public</tt>. - * - * @return a copy of the receiver. - */ - @Override - public Object clone() { - try { - return super.clone(); - } catch (CloneNotSupportedException exc) { - throw new InternalError(); //should never happen since we are cloneable - } - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/PivotedMatrix.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/PivotedMatrix.java b/core/src/main/java/org/apache/mahout/math/PivotedMatrix.java deleted file mode 100644 index 9be8abf..0000000 --- a/core/src/main/java/org/apache/mahout/math/PivotedMatrix.java +++ /dev/null @@ -1,288 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.mahout.math; - -import com.google.common.base.Preconditions; - -/** - * Matrix that allows transparent row and column permutation. - */ -public class PivotedMatrix extends AbstractMatrix { - - private Matrix base; - private int[] rowPivot; - private int[] rowUnpivot; - private int[] columnPivot; - private int[] columnUnpivot; - - public PivotedMatrix(Matrix base, int[] pivot) { - this(base, pivot, java.util.Arrays.copyOf(pivot, pivot.length)); - } - public PivotedMatrix(Matrix base, int[] rowPivot, int[] columnPivot) { - super(base.rowSize(), base.columnSize()); - - this.base = base; - this.rowPivot = rowPivot; - rowUnpivot = invert(rowPivot); - - this.columnPivot = columnPivot; - columnUnpivot = invert(columnPivot); - } - - public PivotedMatrix(Matrix base) { - this(base, identityPivot(base.rowSize()),identityPivot(base.columnSize())); - } - - /** - * Swaps indexes i and j. This does both row and column permutation. - * - * @param i First index to swap. - * @param j Second index to swap. - */ - public void swap(int i, int j) { - swapRows(i, j); - swapColumns(i, j); - } - - /** - * Swaps indexes i and j. This does just row permutation. - * - * @param i First index to swap. - * @param j Second index to swap. - */ - public void swapRows(int i, int j) { - swap(rowPivot, rowUnpivot, i, j); - } - - - /** - * Swaps indexes i and j. This does just row permutation. - * - * @param i First index to swap. - * @param j Second index to swap. - */ - public void swapColumns(int i, int j) { - swap(columnPivot, columnUnpivot, i, j); - } - - private static void swap(int[] pivot, int[] unpivot, int i, int j) { - Preconditions.checkPositionIndex(i, pivot.length); - Preconditions.checkPositionIndex(j, pivot.length); - if (i != j) { - int tmp = pivot[i]; - pivot[i] = pivot[j]; - pivot[j] = tmp; - - unpivot[pivot[i]] = i; - unpivot[pivot[j]] = j; - } - } - - /** - * Assign the other vector values to the column of the receiver - * - * @param column the int row to assign - * @param other a Vector - * @return the modified receiver - * @throws CardinalityException - * if the cardinalities differ - */ - @Override - public Matrix assignColumn(int column, Vector other) { - // note the reversed pivoting for other - return base.assignColumn(columnPivot[column], new PermutedVectorView(other, rowUnpivot, rowPivot)); - } - - /** - * Assign the other vector values to the row of the receiver - * - * @param row the int row to assign - * @param other a Vector - * @return the modified receiver - * @throws CardinalityException - * if the cardinalities differ - */ - @Override - public Matrix assignRow(int row, Vector other) { - // note the reversed pivoting for other - return base.assignRow(rowPivot[row], new PermutedVectorView(other, columnUnpivot, columnPivot)); - } - - /** - * Return the column at the given index - * - * @param column an int column index - * @return a Vector at the index - * @throws IndexException - * if the index is out of bounds - */ - @Override - public Vector viewColumn(int column) { - if (column < 0 || column >= columnSize()) { - throw new IndexException(column, columnSize()); - } - return new PermutedVectorView(base.viewColumn(columnPivot[column]), rowPivot, rowUnpivot); - } - - /** - * Return the row at the given index - * - * @param row an int row index - * @return a Vector at the index - * @throws IndexException - * if the index is out of bounds - */ - @Override - public Vector viewRow(int row) { - if (row < 0 || row >= rowSize()) { - throw new IndexException(row, rowSize()); - } - return new PermutedVectorView(base.viewRow(rowPivot[row]), columnPivot, columnUnpivot); - } - - /** - * Return the value at the given indexes, without checking bounds - * - * @param row an int row index - * @param column an int column index - * @return the double at the index - */ - @Override - public double getQuick(int row, int column) { - return base.getQuick(rowPivot[row], columnPivot[column]); - } - - /** - * Return an empty matrix of the same underlying class as the receiver - * - * @return a Matrix - */ - @Override - public Matrix like() { - return new PivotedMatrix(base.like()); - } - - - @Override - public Matrix clone() { - PivotedMatrix clone = (PivotedMatrix) super.clone(); - - base = base.clone(); - rowPivot = rowPivot.clone(); - rowUnpivot = rowUnpivot.clone(); - columnPivot = columnPivot.clone(); - columnUnpivot = columnUnpivot.clone(); - - return clone; - } - - - /** - * Returns an empty matrix of the same underlying class as the receiver and of the specified - * size. - * - * @param rows the int number of rows - * @param columns the int number of columns - */ - @Override - public Matrix like(int rows, int columns) { - return new PivotedMatrix(base.like(rows, columns)); - } - - /** - * Set the value at the given index, without checking bounds - * - * @param row an int row index into the receiver - * @param column an int column index into the receiver - * @param value a double value to set - */ - @Override - public void setQuick(int row, int column, double value) { - base.setQuick(rowPivot[row], columnPivot[column], value); - } - - /** - * Return the number of values in the recipient - * - * @return an int[2] containing [row, column] count - */ - @Override - public int[] getNumNondefaultElements() { - return base.getNumNondefaultElements(); - } - - /** - * Return a new matrix containing the subset of the recipient - * - * @param offset an int[2] offset into the receiver - * @param size the int[2] size of the desired result - * @return a new Matrix that is a view of the original - * @throws CardinalityException - * if the length is greater than the cardinality of the receiver - * @throws IndexException - * if the offset is negative or the offset+length is outside of the receiver - */ - @Override - public Matrix viewPart(int[] offset, int[] size) { - return new MatrixView(this, offset, size); - } - - public int rowUnpivot(int k) { - return rowUnpivot[k]; - } - - public int columnUnpivot(int k) { - return columnUnpivot[k]; - } - - public int[] getRowPivot() { - return rowPivot; - } - - public int[] getInverseRowPivot() { - return rowUnpivot; - } - - public int[] getColumnPivot() { - return columnPivot; - } - - public int[] getInverseColumnPivot() { - return columnUnpivot; - } - - public Matrix getBase() { - return base; - } - - private static int[] identityPivot(int n) { - int[] pivot = new int[n]; - for (int i = 0; i < n; i++) { - pivot[i] = i; - } - return pivot; - } - - private static int[] invert(int[] pivot) { - int[] x = new int[pivot.length]; - for (int i = 0; i < pivot.length; i++) { - x[pivot[i]] = i; - } - return x; - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/QR.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/QR.java b/core/src/main/java/org/apache/mahout/math/QR.java deleted file mode 100644 index 5992224..0000000 --- a/core/src/main/java/org/apache/mahout/math/QR.java +++ /dev/null @@ -1,27 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License.package org.apache.mahout.math; - */ -package org.apache.mahout.math; - -public interface QR { - Matrix getQ(); - - Matrix getR(); - - boolean hasFullRank(); - - Matrix solve(Matrix B); -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/QRDecomposition.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/QRDecomposition.java b/core/src/main/java/org/apache/mahout/math/QRDecomposition.java deleted file mode 100644 index ab5b3d2..0000000 --- a/core/src/main/java/org/apache/mahout/math/QRDecomposition.java +++ /dev/null @@ -1,181 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Copyright 1999 CERN - European Organization for Nuclear Research. - * Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose - * is hereby granted without fee, provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear in supporting documentation. - * CERN makes no representations about the suitability of this software for any purpose. - * It is provided "as is" without expressed or implied warranty. - */ -package org.apache.mahout.math; - -import org.apache.mahout.math.function.Functions; - -import java.util.Locale; - -/** - For an <tt>m x n</tt> matrix <tt>A</tt> with {@code m >= n}, the QR decomposition is an <tt>m x n</tt> - orthogonal matrix <tt>Q</tt> and an <tt>n x n</tt> upper triangular matrix <tt>R</tt> so that - <tt>A = Q*R</tt>. - <P> - The QR decomposition always exists, even if the matrix does not have - full rank, so the constructor will never fail. The primary use of the - QR decomposition is in the least squares solution of non-square systems - of simultaneous linear equations. This will fail if <tt>isFullRank()</tt> - returns <tt>false</tt>. - */ - -public class QRDecomposition implements QR { - private final Matrix q; - private final Matrix r; - private final Matrix mType; - private final boolean fullRank; - private final int rows; - private final int columns; - - /** - * Constructs and returns a new QR decomposition object; computed by Householder reflections; The - * decomposed matrices can be retrieved via instance methods of the returned decomposition - * object. - * - * @param a A rectangular matrix. - * @throws IllegalArgumentException if {@code A.rows() < A.columns()}. - */ - public QRDecomposition(Matrix a) { - - rows = a.rowSize(); - int min = Math.min(a.rowSize(), a.columnSize()); - columns = a.columnSize(); - mType = a.like(1,1); - - Matrix qTmp = a.clone(); - - boolean fullRank = true; - - r = new DenseMatrix(min, columns); - - for (int i = 0; i < min; i++) { - Vector qi = qTmp.viewColumn(i); - double alpha = qi.norm(2); - if (Math.abs(alpha) > Double.MIN_VALUE) { - qi.assign(Functions.div(alpha)); - } else { - if (Double.isInfinite(alpha) || Double.isNaN(alpha)) { - throw new ArithmeticException("Invalid intermediate result"); - } - fullRank = false; - } - r.set(i, i, alpha); - - for (int j = i + 1; j < columns; j++) { - Vector qj = qTmp.viewColumn(j); - double norm = qj.norm(2); - if (Math.abs(norm) > Double.MIN_VALUE) { - double beta = qi.dot(qj); - r.set(i, j, beta); - if (j < min) { - qj.assign(qi, Functions.plusMult(-beta)); - } - } else { - if (Double.isInfinite(norm) || Double.isNaN(norm)) { - throw new ArithmeticException("Invalid intermediate result"); - } - } - } - } - if (columns > min) { - q = qTmp.viewPart(0, rows, 0, min).clone(); - } else { - q = qTmp; - } - this.fullRank = fullRank; - } - - /** - * Generates and returns the (economy-sized) orthogonal factor <tt>Q</tt>. - * - * @return <tt>Q</tt> - */ - @Override - public Matrix getQ() { - return q; - } - - /** - * Returns the upper triangular factor, <tt>R</tt>. - * - * @return <tt>R</tt> - */ - @Override - public Matrix getR() { - return r; - } - - /** - * Returns whether the matrix <tt>A</tt> has full rank. - * - * @return true if <tt>R</tt>, and hence <tt>A</tt>, has full rank. - */ - @Override - public boolean hasFullRank() { - return fullRank; - } - - /** - * Least squares solution of <tt>A*X = B</tt>; <tt>returns X</tt>. - * - * @param B A matrix with as many rows as <tt>A</tt> and any number of columns. - * @return <tt>X</tt> that minimizes the two norm of <tt>Q*R*X - B</tt>. - * @throws IllegalArgumentException if <tt>B.rows() != A.rows()</tt>. - */ - @Override - public Matrix solve(Matrix B) { - if (B.numRows() != rows) { - throw new IllegalArgumentException("Matrix row dimensions must agree."); - } - - int cols = B.numCols(); - Matrix x = mType.like(columns, cols); - - // this can all be done a bit more efficiently if we don't actually - // form explicit versions of Q^T and R but this code isn't so bad - // and it is much easier to understand - Matrix qt = getQ().transpose(); - Matrix y = qt.times(B); - - Matrix r = getR(); - for (int k = Math.min(columns, rows) - 1; k >= 0; k--) { - // X[k,] = Y[k,] / R[k,k], note that X[k,] starts with 0 so += is same as = - x.viewRow(k).assign(y.viewRow(k), Functions.plusMult(1 / r.get(k, k))); - - // Y[0:(k-1),] -= R[0:(k-1),k] * X[k,] - Vector rColumn = r.viewColumn(k).viewPart(0, k); - for (int c = 0; c < cols; c++) { - y.viewColumn(c).viewPart(0, k).assign(rColumn, Functions.plusMult(-x.get(k, c))); - } - } - return x; - } - - /** - * Returns a rough string rendition of a QR. - */ - @Override - public String toString() { - return String.format(Locale.ENGLISH, "QR(%d x %d,fullRank=%s)", rows, columns, hasFullRank()); - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/RandomAccessSparseVector.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/RandomAccessSparseVector.java b/core/src/main/java/org/apache/mahout/math/RandomAccessSparseVector.java deleted file mode 100644 index c325078..0000000 --- a/core/src/main/java/org/apache/mahout/math/RandomAccessSparseVector.java +++ /dev/null @@ -1,303 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.mahout.math; - -import it.unimi.dsi.fastutil.doubles.DoubleIterator; -import it.unimi.dsi.fastutil.ints.Int2DoubleMap; -import it.unimi.dsi.fastutil.ints.Int2DoubleMap.Entry; -import it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap; -import it.unimi.dsi.fastutil.objects.ObjectIterator; - -import java.util.Iterator; -import java.util.NoSuchElementException; - -import org.apache.mahout.math.set.AbstractSet; - -/** Implements vector that only stores non-zero doubles */ -public class RandomAccessSparseVector extends AbstractVector { - - private static final int INITIAL_CAPACITY = 11; - - private Int2DoubleOpenHashMap values; - - /** For serialization purposes only. */ - public RandomAccessSparseVector() { - super(0); - } - - public RandomAccessSparseVector(int cardinality) { - this(cardinality, Math.min(cardinality, INITIAL_CAPACITY)); // arbitrary estimate of 'sparseness' - } - - public RandomAccessSparseVector(int cardinality, int initialCapacity) { - super(cardinality); - values = new Int2DoubleOpenHashMap(initialCapacity, .5f); - } - - public RandomAccessSparseVector(Vector other) { - this(other.size(), other.getNumNondefaultElements()); - for (Element e : other.nonZeroes()) { - values.put(e.index(), e.get()); - } - } - - private RandomAccessSparseVector(int cardinality, Int2DoubleOpenHashMap values) { - super(cardinality); - this.values = values; - } - - public RandomAccessSparseVector(RandomAccessSparseVector other, boolean shallowCopy) { - super(other.size()); - values = shallowCopy ? other.values : other.values.clone(); - } - - @Override - protected Matrix matrixLike(int rows, int columns) { - return new SparseMatrix(rows, columns); - } - - @Override - public RandomAccessSparseVector clone() { - return new RandomAccessSparseVector(size(), values.clone()); - } - - @Override - public String toString() { - return sparseVectorToString(); - } - - @Override - public Vector assign(Vector other) { - if (size() != other.size()) { - throw new CardinalityException(size(), other.size()); - } - values.clear(); - for (Element e : other.nonZeroes()) { - setQuick(e.index(), e.get()); - } - return this; - } - - @Override - public void mergeUpdates(OrderedIntDoubleMapping updates) { - for (int i = 0; i < updates.getNumMappings(); ++i) { - values.put(updates.getIndices()[i], updates.getValues()[i]); - } - } - - /** - * @return false - */ - @Override - public boolean isDense() { - return false; - } - - /** - * @return false - */ - @Override - public boolean isSequentialAccess() { - return false; - } - - @Override - public double getQuick(int index) { - return values.get(index); - } - - @Override - public void setQuick(int index, double value) { - invalidateCachedLength(); - if (value == 0.0) { - values.remove(index); - } else { - values.put(index, value); - } - } - - @Override - public void incrementQuick(int index, double increment) { - invalidateCachedLength(); - values.addTo( index, increment); - } - - - @Override - public RandomAccessSparseVector like() { - return new RandomAccessSparseVector(size(), values.size()); - } - - @Override - public Vector like(int cardinality) { - return new RandomAccessSparseVector(cardinality, values.size()); - } - - @Override - public int getNumNondefaultElements() { - return values.size(); - } - - @Override - public int getNumNonZeroElements() { - final DoubleIterator iterator = values.values().iterator(); - int numNonZeros = 0; - for( int i = values.size(); i-- != 0; ) if ( iterator.nextDouble() != 0 ) numNonZeros++; - return numNonZeros; - } - - @Override - public double getLookupCost() { - return 1; - } - - @Override - public double getIteratorAdvanceCost() { - return 1 + (AbstractSet.DEFAULT_MAX_LOAD_FACTOR + AbstractSet.DEFAULT_MIN_LOAD_FACTOR) / 2; - } - - /** - * This is "sort of" constant, but really it might resize the array. - */ - @Override - public boolean isAddConstantTime() { - return true; - } - - /* - @Override - public Element getElement(int index) { - // TODO: this should return a MapElement so as to avoid hashing for both getQuick and setQuick. - return super.getElement(index); - } - */ - - private final class NonZeroIterator implements Iterator<Element> { - final ObjectIterator<Int2DoubleMap.Entry> fastIterator = values.int2DoubleEntrySet().fastIterator(); - final RandomAccessElement element = new RandomAccessElement( fastIterator ); - - @Override - public boolean hasNext() { - return fastIterator.hasNext(); - } - - @Override - public Element next() { - if ( ! hasNext() ) throw new NoSuchElementException(); - element.entry = fastIterator.next(); - return element; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - final class RandomAccessElement implements Element { - Int2DoubleMap.Entry entry; - final ObjectIterator<Int2DoubleMap.Entry> fastIterator; - - public RandomAccessElement( ObjectIterator<Entry> fastIterator ) { - super(); - this.fastIterator = fastIterator; - } - - @Override - public double get() { - return entry.getDoubleValue(); - } - - @Override - public int index() { - return entry.getIntKey(); - } - - @Override - public void set( double value ) { - invalidateCachedLength(); - if (value == 0.0) fastIterator.remove(); - else entry.setValue( value ); - } - } - /** - * NOTE: this implementation reuses the Vector.Element instance for each call of next(). If you need to preserve the - * instance, you need to make a copy of it - * - * @return an {@link Iterator} over the Elements. - * @see #getElement(int) - */ - @Override - public Iterator<Element> iterateNonZero() { - return new NonZeroIterator(); - } - - @Override - public Iterator<Element> iterator() { - return new AllIterator(); - } - - final class GeneralElement implements Element { - int index; - double value; - - @Override - public double get() { - return value; - } - - @Override - public int index() { - return index; - } - - @Override - public void set( double value ) { - invalidateCachedLength(); - if (value == 0.0) values.remove( index ); - else values.put( index, value ); - } -} - - private final class AllIterator implements Iterator<Element> { - private final GeneralElement element = new GeneralElement(); - - private AllIterator() { - element.index = -1; - } - - @Override - public boolean hasNext() { - return element.index + 1 < size(); - } - - @Override - public Element next() { - if (!hasNext()) { - throw new NoSuchElementException(); - } - element.value = values.get( ++element.index ); - return element; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/RandomTrinaryMatrix.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/RandomTrinaryMatrix.java b/core/src/main/java/org/apache/mahout/math/RandomTrinaryMatrix.java deleted file mode 100644 index ae1a1a3..0000000 --- a/core/src/main/java/org/apache/mahout/math/RandomTrinaryMatrix.java +++ /dev/null @@ -1,146 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.mahout.math; - -import java.nio.ByteBuffer; -import java.util.concurrent.atomic.AtomicInteger; - -/** - * Random matrix. Each value is taken from {-1,0,1} with roughly equal probability. Note - * that by default, the value is determined by a relatively simple hash of the coordinates. - * Such a hash is not usable where real randomness is required, but suffices nicely for - * random projection methods. - * - * If the simple hash method is not satisfactory, an optional high quality mode is available - * which uses a murmur hash of the coordinates. - */ -public class RandomTrinaryMatrix extends AbstractMatrix { - private static final AtomicInteger ID = new AtomicInteger(); - private static final int PRIME1 = 104047; - private static final int PRIME2 = 101377; - private static final int PRIME3 = 64661; - private static final long SCALE = 1L << 32; - - private final int seed; - - // set this to true to use a high quality hash - private boolean highQuality = false; - - public RandomTrinaryMatrix(int seed, int rows, int columns, boolean highQuality) { - super(rows, columns); - - this.highQuality = highQuality; - this.seed = seed; - } - - public RandomTrinaryMatrix(int rows, int columns) { - this(ID.incrementAndGet(), rows, columns, false); - } - - @Override - public Matrix assignColumn(int column, Vector other) { - throw new UnsupportedOperationException("Can't assign to read-only matrix"); - } - - @Override - public Matrix assignRow(int row, Vector other) { - throw new UnsupportedOperationException("Can't assign to read-only matrix"); - } - - /** - * Return the value at the given indexes, without checking bounds - * - * @param row an int row index - * @param column an int column index - * @return the double at the index - */ - @Override - public double getQuick(int row, int column) { - if (highQuality) { - ByteBuffer buf = ByteBuffer.allocate(8); - buf.putInt(row); - buf.putInt(column); - buf.flip(); - return (MurmurHash.hash64A(buf, seed) & (SCALE - 1)) / (double) SCALE; - } else { - // this isn't a fantastic random number generator, but it is just fine for random projections - return ((((row * PRIME1) + column * PRIME2 + row * column * PRIME3) & 8) * 0.25) - 1; - } - } - - - /** - * Return an empty matrix of the same underlying class as the receiver - * - * @return a Matrix - */ - @Override - public Matrix like() { - return new DenseMatrix(rowSize(), columnSize()); - } - - /** - * Returns an empty matrix of the same underlying class as the receiver and of the specified - * size. - * - * @param rows the int number of rows - * @param columns the int number of columns - */ - @Override - public Matrix like(int rows, int columns) { - return new DenseMatrix(rows, columns); - } - - /** - * Set the value at the given index, without checking bounds - * - * @param row an int row index into the receiver - * @param column an int column index into the receiver - * @param value a double value to set - */ - @Override - public void setQuick(int row, int column, double value) { - throw new UnsupportedOperationException("Can't assign to read-only matrix"); - } - - /** - * Return the number of values in the recipient - * - * @return an int[2] containing [row, column] count - */ - @Override - public int[] getNumNondefaultElements() { - throw new UnsupportedOperationException("Can't assign to read-only matrix"); - } - - /** - * Return a new matrix containing the subset of the recipient - * - * @param offset an int[2] offset into the receiver - * @param size the int[2] size of the desired result - * @return a new Matrix that is a view of the original - * @throws CardinalityException - * if the length is greater than the cardinality of the receiver - * @throws IndexException - * if the offset is negative or the offset+length is outside of the receiver - */ - @Override - public Matrix viewPart(int[] offset, int[] size) { - return new MatrixView(this, offset, size); - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/SequentialAccessSparseVector.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/SequentialAccessSparseVector.java b/core/src/main/java/org/apache/mahout/math/SequentialAccessSparseVector.java deleted file mode 100644 index 82b38b6..0000000 --- a/core/src/main/java/org/apache/mahout/math/SequentialAccessSparseVector.java +++ /dev/null @@ -1,379 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.mahout.math; - -import java.util.Arrays; -import java.util.Iterator; -import java.util.NoSuchElementException; - -import com.google.common.primitives.Doubles; -import org.apache.mahout.math.function.Functions; - -/** - * <p> - * Implements vector that only stores non-zero doubles as a pair of parallel arrays (OrderedIntDoubleMapping), - * one int[], one double[]. If there are <b>k</b> non-zero elements in the vector, this implementation has - * O(log(k)) random-access read performance, and O(k) random-access write performance, which is far below that - * of the hashmap based {@link RandomAccessSparseVector RandomAccessSparseVector}. This - * class is primarily used for operations where the all the elements will be accessed in a read-only fashion - * sequentially: methods which operate not via get() or set(), but via iterateNonZero(), such as (but not limited - * to) :</p> - * <ul> - * <li>dot(Vector)</li> - * <li>addTo(Vector)</li> - * </ul> - * - * See {@link OrderedIntDoubleMapping} - */ -public class SequentialAccessSparseVector extends AbstractVector { - - private OrderedIntDoubleMapping values; - - /** For serialization purposes only. */ - public SequentialAccessSparseVector() { - super(0); - } - - public SequentialAccessSparseVector(int cardinality) { - this(cardinality, Math.min(100, cardinality / 1000 < 10 ? 10 : cardinality / 1000)); // arbitrary estimate of - // 'sparseness' - } - - public SequentialAccessSparseVector(int cardinality, int size) { - super(cardinality); - values = new OrderedIntDoubleMapping(size); - } - - public SequentialAccessSparseVector(Vector other) { - this(other.size(), other.getNumNondefaultElements()); - - if (other.isSequentialAccess()) { - for (Element e : other.nonZeroes()) { - set(e.index(), e.get()); - } - } else { - // If the incoming Vector to copy is random, then adding items - // from the Iterator can degrade performance dramatically if - // the number of elements is large as this Vector tries to stay - // in order as items are added, so it's better to sort the other - // Vector's elements by index and then add them to this - copySortedRandomAccessSparseVector(other); - } - } - - // Sorts a RandomAccessSparseVectors Elements before adding them to this - private int copySortedRandomAccessSparseVector(Vector other) { - int elementCount = other.getNumNondefaultElements(); - OrderedElement[] sortableElements = new OrderedElement[elementCount]; - int s = 0; - for (Element e : other.nonZeroes()) { - sortableElements[s++] = new OrderedElement(e.index(), e.get()); - } - Arrays.sort(sortableElements); - for (int i = 0; i < sortableElements.length; i++) { - values.setIndexAt(i, sortableElements[i].index); - values.setValueAt(i, sortableElements[i].value); - } - values = new OrderedIntDoubleMapping(values.getIndices(), values.getValues(), elementCount); - return elementCount; - } - - public SequentialAccessSparseVector(SequentialAccessSparseVector other, boolean shallowCopy) { - super(other.size()); - values = shallowCopy ? other.values : other.values.clone(); - } - - public SequentialAccessSparseVector(SequentialAccessSparseVector other) { - this(other.size(), other.getNumNondefaultElements()); - values = other.values.clone(); - } - - private SequentialAccessSparseVector(int cardinality, OrderedIntDoubleMapping values) { - super(cardinality); - this.values = values; - } - - @Override - protected Matrix matrixLike(int rows, int columns) { - //return new SparseRowMatrix(rows, columns); - return new SparseMatrix(rows, columns); - } - - @SuppressWarnings("CloneDoesntCallSuperClone") - @Override - public SequentialAccessSparseVector clone() { - return new SequentialAccessSparseVector(size(), values.clone()); - } - - @Override - public void mergeUpdates(OrderedIntDoubleMapping updates) { - values.merge(updates); - } - - @Override - public String toString() { - return sparseVectorToString(); - } - - /** - * @return false - */ - @Override - public boolean isDense() { - return false; - } - - /** - * @return true - */ - @Override - public boolean isSequentialAccess() { - return true; - } - - /** - * Warning! This takes O(log n) time as it does a binary search behind the scenes! - * Only use it when STRICTLY necessary. - * @param index an int index. - * @return the value at that position in the vector. - */ - @Override - public double getQuick(int index) { - return values.get(index); - } - - /** - * Warning! This takes O(log n) time as it does a binary search behind the scenes! - * Only use it when STRICTLY necessary. - * @param index an int index. - */ - @Override - public void setQuick(int index, double value) { - invalidateCachedLength(); - values.set(index, value); - } - - @Override - public void incrementQuick(int index, double increment) { - invalidateCachedLength(); - values.increment(index, increment); - } - - @Override - public SequentialAccessSparseVector like() { - return new SequentialAccessSparseVector(size(), values.getNumMappings()); - } - - @Override - public Vector like(int cardinality) { - return new SequentialAccessSparseVector(cardinality); - } - - @Override - public int getNumNondefaultElements() { - return values.getNumMappings(); - } - - @Override - public int getNumNonZeroElements() { - double[] elementValues = values.getValues(); - int numMappedElements = values.getNumMappings(); - int numNonZeros = 0; - for (int index = 0; index < numMappedElements; index++) { - if (elementValues[index] != 0) { - numNonZeros++; - } - } - return numNonZeros; - } - - @Override - public double getLookupCost() { - return Math.max(1, Math.round(Functions.LOG2.apply(getNumNondefaultElements()))); - } - - @Override - public double getIteratorAdvanceCost() { - return 1; - } - - @Override - public boolean isAddConstantTime() { - return false; - } - - @Override - public Iterator<Element> iterateNonZero() { - - // TODO: this is a bug, since nonDefaultIterator doesn't hold to non-zero contract. - return new NonDefaultIterator(); - } - - @Override - public Iterator<Element> iterator() { - return new AllIterator(); - } - - private final class NonDefaultIterator implements Iterator<Element> { - private final NonDefaultElement element = new NonDefaultElement(); - - @Override - public boolean hasNext() { - return element.getNextOffset() < values.getNumMappings(); - } - - @Override - public Element next() { - if (!hasNext()) { - throw new NoSuchElementException(); - } - element.advanceOffset(); - return element; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - private final class AllIterator implements Iterator<Element> { - private final AllElement element = new AllElement(); - - @Override - public boolean hasNext() { - return element.getNextIndex() < SequentialAccessSparseVector.this.size(); - } - - @Override - public Element next() { - if (!hasNext()) { - throw new NoSuchElementException(); - } - - element.advanceIndex(); - return element; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - private final class NonDefaultElement implements Element { - private int offset = -1; - - void advanceOffset() { - offset++; - } - - int getNextOffset() { - return offset + 1; - } - - @Override - public double get() { - return values.getValues()[offset]; - } - - @Override - public int index() { - return values.getIndices()[offset]; - } - - @Override - public void set(double value) { - invalidateCachedLength(); - values.setValueAt(offset, value); - } - } - - private final class AllElement implements Element { - private int index = -1; - private int nextOffset; - - void advanceIndex() { - index++; - if (nextOffset < values.getNumMappings() && index > values.getIndices()[nextOffset]) { - nextOffset++; - } - } - - int getNextIndex() { - return index + 1; - } - - @Override - public double get() { - if (nextOffset < values.getNumMappings() && index == values.getIndices()[nextOffset]) { - return values.getValues()[nextOffset]; - } else { - return OrderedIntDoubleMapping.DEFAULT_VALUE; - } - } - - @Override - public int index() { - return index; - } - - @Override - public void set(double value) { - invalidateCachedLength(); - if (nextOffset < values.getNumMappings() && index == values.indexAt(nextOffset)) { - values.setValueAt(nextOffset, value); - } else { - // Yes, this works; the offset into indices of the new value's index will still be nextOffset - values.set(index, value); - } - } - } - - // Comparable Element for sorting Elements by index - private static final class OrderedElement implements Comparable<OrderedElement> { - private final int index; - private final double value; - - OrderedElement(int index, double value) { - this.index = index; - this.value = value; - } - - @Override - public int compareTo(OrderedElement that) { - // both indexes are positive, and neither can be Integer.MAX_VALUE (otherwise there would be - // an array somewhere with Integer.MAX_VALUE + 1 elements) - return this.index - that.index; - } - - @Override - public int hashCode() { - return index ^ Doubles.hashCode(value); - } - - @Override - public boolean equals(Object o) { - if (!(o instanceof OrderedElement)) { - return false; - } - OrderedElement other = (OrderedElement) o; - return index == other.index && value == other.value; - } - } -} http://git-wip-us.apache.org/repos/asf/mahout/blob/49ad8cb4/core/src/main/java/org/apache/mahout/math/SingularValueDecomposition.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/mahout/math/SingularValueDecomposition.java b/core/src/main/java/org/apache/mahout/math/SingularValueDecomposition.java deleted file mode 100644 index 2abff10..0000000 --- a/core/src/main/java/org/apache/mahout/math/SingularValueDecomposition.java +++ /dev/null @@ -1,669 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Copyright 1999 CERN - European Organization for Nuclear Research. - * Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose - * is hereby granted without fee, provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear in supporting documentation. - * CERN makes no representations about the suitability of this software for any purpose. - * It is provided "as is" without expressed or implied warranty. - */ -package org.apache.mahout.math; - -public class SingularValueDecomposition implements java.io.Serializable { - - /** Arrays for internal storage of U and V. */ - private final double[][] u; - private final double[][] v; - - /** Array for internal storage of singular values. */ - private final double[] s; - - /** Row and column dimensions. */ - private final int m; - private final int n; - - /**To handle the case where numRows() < numCols() and to use the fact that SVD(A')=VSU'=> SVD(A')'=SVD(A)**/ - private boolean transpositionNeeded; - - /** - * Constructs and returns a new singular value decomposition object; The - * decomposed matrices can be retrieved via instance methods of the returned - * decomposition object. - * - * @param arg - * A rectangular matrix. - */ - public SingularValueDecomposition(Matrix arg) { - if (arg.numRows() < arg.numCols()) { - transpositionNeeded = true; - } - - // Derived from LINPACK code. - // Initialize. - double[][] a; - if (transpositionNeeded) { - //use the transpose Matrix - m = arg.numCols(); - n = arg.numRows(); - a = new double[m][n]; - for (int i = 0; i < m; i++) { - for (int j = 0; j < n; j++) { - a[i][j] = arg.get(j, i); - } - } - } else { - m = arg.numRows(); - n = arg.numCols(); - a = new double[m][n]; - for (int i = 0; i < m; i++) { - for (int j = 0; j < n; j++) { - a[i][j] = arg.get(i, j); - } - } - } - - - int nu = Math.min(m, n); - s = new double[Math.min(m + 1, n)]; - u = new double[m][nu]; - v = new double[n][n]; - double[] e = new double[n]; - double[] work = new double[m]; - boolean wantu = true; - boolean wantv = true; - - // Reduce A to bidiagonal form, storing the diagonal elements - // in s and the super-diagonal elements in e. - - int nct = Math.min(m - 1, n); - int nrt = Math.max(0, Math.min(n - 2, m)); - for (int k = 0; k < Math.max(nct, nrt); k++) { - if (k < nct) { - - // Compute the transformation for the k-th column and - // place the k-th diagonal in s[k]. - // Compute 2-norm of k-th column without under/overflow. - s[k] = 0; - for (int i = k; i < m; i++) { - s[k] = Algebra.hypot(s[k], a[i][k]); - } - if (s[k] != 0.0) { - if (a[k][k] < 0.0) { - s[k] = -s[k]; - } - for (int i = k; i < m; i++) { - a[i][k] /= s[k]; - } - a[k][k] += 1.0; - } - s[k] = -s[k]; - } - for (int j = k + 1; j < n; j++) { - if (k < nct && s[k] != 0.0) { - - // Apply the transformation. - - double t = 0; - for (int i = k; i < m; i++) { - t += a[i][k] * a[i][j]; - } - t = -t / a[k][k]; - for (int i = k; i < m; i++) { - a[i][j] += t * a[i][k]; - } - } - - // Place the k-th row of A into e for the - // subsequent calculation of the row transformation. - - e[j] = a[k][j]; - } - if (wantu && k < nct) { - - // Place the transformation in U for subsequent back - // multiplication. - - for (int i = k; i < m; i++) { - u[i][k] = a[i][k]; - } - } - if (k < nrt) { - - // Compute the k-th row transformation and place the - // k-th super-diagonal in e[k]. - // Compute 2-norm without under/overflow. - e[k] = 0; - for (int i = k + 1; i < n; i++) { - e[k] = Algebra.hypot(e[k], e[i]); - } - if (e[k] != 0.0) { - if (e[k + 1] < 0.0) { - e[k] = -e[k]; - } - for (int i = k + 1; i < n; i++) { - e[i] /= e[k]; - } - e[k + 1] += 1.0; - } - e[k] = -e[k]; - if (k + 1 < m && e[k] != 0.0) { - - // Apply the transformation. - - for (int i = k + 1; i < m; i++) { - work[i] = 0.0; - } - for (int j = k + 1; j < n; j++) { - for (int i = k + 1; i < m; i++) { - work[i] += e[j] * a[i][j]; - } - } - for (int j = k + 1; j < n; j++) { - double t = -e[j] / e[k + 1]; - for (int i = k + 1; i < m; i++) { - a[i][j] += t * work[i]; - } - } - } - if (wantv) { - - // Place the transformation in V for subsequent - // back multiplication. - - for (int i = k + 1; i < n; i++) { - v[i][k] = e[i]; - } - } - } - } - - // Set up the final bidiagonal matrix or order p. - - int p = Math.min(n, m + 1); - if (nct < n) { - s[nct] = a[nct][nct]; - } - if (m < p) { - s[p - 1] = 0.0; - } - if (nrt + 1 < p) { - e[nrt] = a[nrt][p - 1]; - } - e[p - 1] = 0.0; - - // If required, generate U. - - if (wantu) { - for (int j = nct; j < nu; j++) { - for (int i = 0; i < m; i++) { - u[i][j] = 0.0; - } - u[j][j] = 1.0; - } - for (int k = nct - 1; k >= 0; k--) { - if (s[k] != 0.0) { - for (int j = k + 1; j < nu; j++) { - double t = 0; - for (int i = k; i < m; i++) { - t += u[i][k] * u[i][j]; - } - t = -t / u[k][k]; - for (int i = k; i < m; i++) { - u[i][j] += t * u[i][k]; - } - } - for (int i = k; i < m; i++) { - u[i][k] = -u[i][k]; - } - u[k][k] = 1.0 + u[k][k]; - for (int i = 0; i < k - 1; i++) { - u[i][k] = 0.0; - } - } else { - for (int i = 0; i < m; i++) { - u[i][k] = 0.0; - } - u[k][k] = 1.0; - } - } - } - - // If required, generate V. - - if (wantv) { - for (int k = n - 1; k >= 0; k--) { - if (k < nrt && e[k] != 0.0) { - for (int j = k + 1; j < nu; j++) { - double t = 0; - for (int i = k + 1; i < n; i++) { - t += v[i][k] * v[i][j]; - } - t = -t / v[k + 1][k]; - for (int i = k + 1; i < n; i++) { - v[i][j] += t * v[i][k]; - } - } - } - for (int i = 0; i < n; i++) { - v[i][k] = 0.0; - } - v[k][k] = 1.0; - } - } - - // Main iteration loop for the singular values. - - int pp = p - 1; - int iter = 0; - double eps = Math.pow(2.0, -52.0); - double tiny = Math.pow(2.0,-966.0); - while (p > 0) { - int k; - - // Here is where a test for too many iterations would go. - - // This section of the program inspects for - // negligible elements in the s and e arrays. On - // completion the variables kase and k are set as follows. - - // kase = 1 if s(p) and e[k-1] are negligible and k<p - // kase = 2 if s(k) is negligible and k<p - // kase = 3 if e[k-1] is negligible, k<p, and - // s(k), ..., s(p) are not negligible (qr step). - // kase = 4 if e(p-1) is negligible (convergence). - - for (k = p - 2; k >= -1; k--) { - if (k == -1) { - break; - } - if (Math.abs(e[k]) <= tiny +eps * (Math.abs(s[k]) + Math.abs(s[k + 1]))) { - e[k] = 0.0; - break; - } - } - int kase; - if (k == p - 2) { - kase = 4; - } else { - int ks; - for (ks = p - 1; ks >= k; ks--) { - if (ks == k) { - break; - } - double t = - (ks != p ? Math.abs(e[ks]) : 0.) + - (ks != k + 1 ? Math.abs(e[ks-1]) : 0.); - if (Math.abs(s[ks]) <= tiny + eps * t) { - s[ks] = 0.0; - break; - } - } - if (ks == k) { - kase = 3; - } else if (ks == p - 1) { - kase = 1; - } else { - kase = 2; - k = ks; - } - } - k++; - - // Perform the task indicated by kase. - - switch (kase) { - - // Deflate negligible s(p). - - case 1: { - double f = e[p - 2]; - e[p - 2] = 0.0; - for (int j = p - 2; j >= k; j--) { - double t = Algebra.hypot(s[j], f); - double cs = s[j] / t; - double sn = f / t; - s[j] = t; - if (j != k) { - f = -sn * e[j - 1]; - e[j - 1] = cs * e[j - 1]; - } - if (wantv) { - for (int i = 0; i < n; i++) { - t = cs * v[i][j] + sn * v[i][p - 1]; - v[i][p - 1] = -sn * v[i][j] + cs * v[i][p - 1]; - v[i][j] = t; - } - } - } - } - break; - - // Split at negligible s(k). - - case 2: { - double f = e[k - 1]; - e[k - 1] = 0.0; - for (int j = k; j < p; j++) { - double t = Algebra.hypot(s[j], f); - double cs = s[j] / t; - double sn = f / t; - s[j] = t; - f = -sn * e[j]; - e[j] = cs * e[j]; - if (wantu) { - for (int i = 0; i < m; i++) { - t = cs * u[i][j] + sn * u[i][k - 1]; - u[i][k - 1] = -sn * u[i][j] + cs * u[i][k - 1]; - u[i][j] = t; - } - } - } - } - break; - - // Perform one qr step. - - case 3: { - - // Calculate the shift. - - double scale = Math.max(Math.max(Math.max(Math.max( - Math.abs(s[p - 1]), Math.abs(s[p - 2])), Math.abs(e[p - 2])), - Math.abs(s[k])), Math.abs(e[k])); - double sp = s[p - 1] / scale; - double spm1 = s[p - 2] / scale; - double epm1 = e[p - 2] / scale; - double sk = s[k] / scale; - double ek = e[k] / scale; - double b = ((spm1 + sp) * (spm1 - sp) + epm1 * epm1) / 2.0; - double c = sp * epm1 * sp * epm1; - double shift = 0.0; - if (b != 0.0 || c != 0.0) { - shift = Math.sqrt(b * b + c); - if (b < 0.0) { - shift = -shift; - } - shift = c / (b + shift); - } - double f = (sk + sp) * (sk - sp) + shift; - double g = sk * ek; - - // Chase zeros. - - for (int j = k; j < p - 1; j++) { - double t = Algebra.hypot(f, g); - double cs = f / t; - double sn = g / t; - if (j != k) { - e[j - 1] = t; - } - f = cs * s[j] + sn * e[j]; - e[j] = cs * e[j] - sn * s[j]; - g = sn * s[j + 1]; - s[j + 1] = cs * s[j + 1]; - if (wantv) { - for (int i = 0; i < n; i++) { - t = cs * v[i][j] + sn * v[i][j + 1]; - v[i][j + 1] = -sn * v[i][j] + cs * v[i][j + 1]; - v[i][j] = t; - } - } - t = Algebra.hypot(f, g); - cs = f / t; - sn = g / t; - s[j] = t; - f = cs * e[j] + sn * s[j + 1]; - s[j + 1] = -sn * e[j] + cs * s[j + 1]; - g = sn * e[j + 1]; - e[j + 1] = cs * e[j + 1]; - if (wantu && j < m - 1) { - for (int i = 0; i < m; i++) { - t = cs * u[i][j] + sn * u[i][j + 1]; - u[i][j + 1] = -sn * u[i][j] + cs * u[i][j + 1]; - u[i][j] = t; - } - } - } - e[p - 2] = f; - iter = iter + 1; - } - break; - - // Convergence. - - case 4: { - - // Make the singular values positive. - - if (s[k] <= 0.0) { - s[k] = s[k] < 0.0 ? -s[k] : 0.0; - if (wantv) { - for (int i = 0; i <= pp; i++) { - v[i][k] = -v[i][k]; - } - } - } - - // Order the singular values. - - while (k < pp) { - if (s[k] >= s[k + 1]) { - break; - } - double t = s[k]; - s[k] = s[k + 1]; - s[k + 1] = t; - if (wantv && k < n - 1) { - for (int i = 0; i < n; i++) { - t = v[i][k + 1]; - v[i][k + 1] = v[i][k]; - v[i][k] = t; - } - } - if (wantu && k < m - 1) { - for (int i = 0; i < m; i++) { - t = u[i][k + 1]; - u[i][k + 1] = u[i][k]; - u[i][k] = t; - } - } - k++; - } - iter = 0; - p--; - } - break; - default: - throw new IllegalStateException(); - } - } - } - - /** - * Returns the two norm condition number, which is <tt>max(S) / min(S)</tt>. - */ - public double cond() { - return s[0] / s[Math.min(m, n) - 1]; - } - - /** - * @return the diagonal matrix of singular values. - */ - public Matrix getS() { - double[][] s = new double[n][n]; - for (int i = 0; i < n; i++) { - for (int j = 0; j < n; j++) { - s[i][j] = 0.0; - } - s[i][i] = this.s[i]; - } - - return new DenseMatrix(s); - } - - /** - * Returns the diagonal of <tt>S</tt>, which is a one-dimensional array of - * singular values - * - * @return diagonal of <tt>S</tt>. - */ - public double[] getSingularValues() { - return s; - } - - /** - * Returns the left singular vectors <tt>U</tt>. - * - * @return <tt>U</tt> - */ - public Matrix getU() { - if (transpositionNeeded) { //case numRows() < numCols() - return new DenseMatrix(v); - } else { - int numCols = Math.min(m + 1, n); - Matrix r = new DenseMatrix(m, numCols); - for (int i = 0; i < m; i++) { - for (int j = 0; j < numCols; j++) { - r.set(i, j, u[i][j]); - } - } - - return r; - } - } - - /** - * Returns the right singular vectors <tt>V</tt>. - * - * @return <tt>V</tt> - */ - public Matrix getV() { - if (transpositionNeeded) { //case numRows() < numCols() - int numCols = Math.min(m + 1, n); - Matrix r = new DenseMatrix(m, numCols); - for (int i = 0; i < m; i++) { - for (int j = 0; j < numCols; j++) { - r.set(i, j, u[i][j]); - } - } - - return r; - } else { - return new DenseMatrix(v); - } - } - - /** Returns the two norm, which is <tt>max(S)</tt>. */ - public double norm2() { - return s[0]; - } - - /** - * Returns the effective numerical matrix rank, which is the number of - * nonnegligible singular values. - */ - public int rank() { - double eps = Math.pow(2.0, -52.0); - double tol = Math.max(m, n) * s[0] * eps; - int r = 0; - for (double value : s) { - if (value > tol) { - r++; - } - } - return r; - } - - /** - * @param minSingularValue - * minSingularValue - value below which singular values are ignored (a 0 or negative - * value implies all singular value will be used) - * @return Returns the n à n covariance matrix. - * The covariance matrix is V à J à Vt where J is the diagonal matrix of the inverse - * of the squares of the singular values. - */ - Matrix getCovariance(double minSingularValue) { - Matrix j = new DenseMatrix(s.length,s.length); - Matrix vMat = new DenseMatrix(this.v); - for (int i = 0; i < s.length; i++) { - j.set(i, i, s[i] >= minSingularValue ? 1 / (s[i] * s[i]) : 0.0); - } - return vMat.times(j).times(vMat.transpose()); - } - - /** - * Returns a String with (propertyName, propertyValue) pairs. Useful for - * debugging or to quickly get the rough picture. For example, - * - * <pre> - * rank : 3 - * trace : 0 - * </pre> - */ - @Override - public String toString() { - StringBuilder buf = new StringBuilder(); - buf.append("---------------------------------------------------------------------\n"); - buf.append("SingularValueDecomposition(A) --> cond(A), rank(A), norm2(A), U, S, V\n"); - buf.append("---------------------------------------------------------------------\n"); - - buf.append("cond = "); - String unknown = "Illegal operation or error: "; - try { - buf.append(String.valueOf(this.cond())); - } catch (IllegalArgumentException exc) { - buf.append(unknown).append(exc.getMessage()); - } - - buf.append("\nrank = "); - try { - buf.append(String.valueOf(this.rank())); - } catch (IllegalArgumentException exc) { - buf.append(unknown).append(exc.getMessage()); - } - - buf.append("\nnorm2 = "); - try { - buf.append(String.valueOf(this.norm2())); - } catch (IllegalArgumentException exc) { - buf.append(unknown).append(exc.getMessage()); - } - - buf.append("\n\nU = "); - try { - buf.append(String.valueOf(this.getU())); - } catch (IllegalArgumentException exc) { - buf.append(unknown).append(exc.getMessage()); - } - - buf.append("\n\nS = "); - try { - buf.append(String.valueOf(this.getS())); - } catch (IllegalArgumentException exc) { - buf.append(unknown).append(exc.getMessage()); - } - - buf.append("\n\nV = "); - try { - buf.append(String.valueOf(this.getV())); - } catch (IllegalArgumentException exc) { - buf.append(unknown).append(exc.getMessage()); - } - - return buf.toString(); - } -}
