partition.java

一个很好的LIBSVM的JAVA源码。对于要研究和改进SVM算法的学者。可以参考。来自数据挖掘工具YALE工具包。

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2001-2004
 *      Simon Fischer, Ralf Klinkenberg, Ingo Mierswa, 
 *          Katharina Morik, Oliver Ritthoff
 *      Artificial Intelligence Unit
 *      Computer Science Department
 *      University of Dortmund
 *      44221 Dortmund,  Germany
 *  email: [e-mail]
 *  web:   http://yale.cs.uni-dortmund.de/
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as 
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version. 
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 *  USA.
 */
package edu.udo.cs.yale.example;

import edu.udo.cs.yale.tools.RandomGenerator;

/** Implements a partition.
 *
 *  @author Simon, Ingo
 *  @version $Id: Partition.java,v 2.5 2004/08/27 11:57:32 ingomierswa Exp $
 */
public class Partition implements Cloneable {

    /** Mask for the selected partitions. */
    private boolean[] mask;

    /** Size of the individual partitions. */
    private int[] partitionSize;

    /** Maps every example to its partition index. */
    private int[] splitPartition;

    /** Creates a new partition of a given size consisting of <tt>ratio.length</tt> sets.
     *  The set <i>i</i> will be of size of <i>size x ratio[i]</i>, i.e. the sum of all 
     *  <i>ratio[i]</i> must be 1.
     *  Initially all partitions are selected. */
    public Partition(double ratio[], int size, boolean shuffle) {
	init(ratio, size, shuffle);
    }

    /** Creates a new partition of a given size consisting of <i>noPartitions</i> 
     *  equally sized sets. Initially all partitions are selected. */
    public Partition(int noPartitions, int size, boolean shuffle) {
	double[] ratio = new double[noPartitions];
	for (int i = 0; i < ratio.length; i++) {
	    ratio[i] = 1 / (double)noPartitions;
	}
	init(ratio, size, shuffle);
    }

    /** Creates a partition. */
    public Partition(int[] splitPartition, int numberOfPartitions) {
	init(splitPartition, numberOfPartitions);
    }

    /** Clone constructor. */
    private Partition(Partition p) {
	this.partitionSize  = (int[])p.partitionSize.clone();
	this.mask           = (boolean[])p.mask.clone();
	this.splitPartition = (int[])p.splitPartition.clone();
    }

    private void init(double[] ratio, int size, boolean shuffle) {
	partitionSize = new int[ratio.length];

	splitPartition = createIntPartition(ratio, size, shuffle);
	for (int i = 0; i < splitPartition.length; i++)
	    if (splitPartition[i] >= 0)
		partitionSize[splitPartition[i]]++;
	
	mask = new boolean[ratio.length];
	for (int i = 0; i < mask.length; i++)
	    mask[i] = true;
    }

    private void init(int[] elements, int noOfPartitions) {
	partitionSize = new int[noOfPartitions];

	splitPartition = elements;
	for (int i = 0; i < splitPartition.length; i++)
	    if (splitPartition[i] >= 0)
		partitionSize[splitPartition[i]]++;

	mask = new boolean[noOfPartitions];
	for (int i = 0; i < mask.length; i++)
	    mask[i] = true;

    }

    /** Clears the selection, i.e. deselects all subsets. */
    public void clearSelection() {
	this.mask = new boolean[mask.length];
    }

    /** Marks the given subset as selected. */
    public void selectSubset(int i) {
	this.mask[i] = true;
    }

    /** Marks the given subset as deselected. */
    public void deselectSubset(int i) {
	this.mask[i] = false;
    }

    /** Returns the number of subsets. */
    public int getNumberOfSubsets() {
	return partitionSize.length;
    }

    /** Randomly creates an array of size ints in the range of 0 to ratio.length where i
     *  appears exactly (except of rounding errors) size*ratio[i] times. 
     *  The sum of all ratio[i] must be 1. */
    private static int[] createIntPartition(double[] ratio, int size, boolean shuffle) {
	int[] part = new int[size];

	int[] startNewP = new int[ratio.length+1];
	startNewP[0] = 0;
	double ratioSum = 0;
	for (int i = 1; i < startNewP.length; i++) {
	    ratioSum += ratio[i-1];
	    startNewP[i] = (int)Math.round(((double)size)*ratioSum);
	}

	// create a simple partition
	int p = 0;
	for (int i = 0; i < part.length; i++) {
	    if (i >= startNewP[p+1]) p++;
	    part[i] = p;
	}

	// Create a random permutation of the generated array by swapping elements
	if (shuffle) {
	    for (int i = 0; i < size; i++) {
		int swap = RandomGenerator.getGlobalRandomGenerator().nextInt(part.length);
		int dummy = part[i];
		part[i] = part[swap];
		part[swap] = dummy;
	    }
	}
	return part;
    }

    /** Returns the number of selected elements. */
    public int getSelectionSize() {
	int s = 0;
	for (int i = 0; i < partitionSize.length; i++)
	    if (mask[i]) s += partitionSize[i];
	return s;
    }

    /** Returns the total number of examples. */
    public int getTotalSize() {
	return splitPartition.length;
    }

    /** Returns true iff the example with the given index is selected according to the current mask. */
    public boolean isSelected(int index) {
	return mask[splitPartition[index]];
    }

    public String toString() {
	String str ="(";
	for (int i = 0; i < partitionSize.length; i++)
	    str += (i!=0?"/":"") + partitionSize[i];
	str += ")";
	return str;
    }

    public Object clone() {
	return new Partition(this);
    }
}