gentreeutils.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

/*
 *    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., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/**
 * Title: XELOPES Data Mining Library
 * Description: The XELOPES library is an open platform-independent and data-source-independent library for Embedded Data Mining.
 * Copyright: Copyright (c) 2002 Prudential Systems Software GmbH
 * Company: ZSoft (www.zsoft.ru), Prudsys (www.prudsys.com)
 * @author Valentine Stepanenko ([e-mail])
 * @author Sascha Trautzsch
 * @author Michael Thess
 * @version 1.0
 */

package com.prudsys.pdm.Models.Classification.DecisionTree.Algorithms.GenTree;

import com.prudsys.pdm.Core.CategoricalAttribute;
import com.prudsys.pdm.Core.MiningAttribute;
import com.prudsys.pdm.Core.MiningException;
import com.prudsys.pdm.Core.NumericAttribute;
import com.prudsys.pdm.Input.MiningStoredData;
import com.prudsys.pdm.Input.MiningVector;
import com.prudsys.pdm.Utils.IntVector;

/**
 * Class implementing some usefull methods for decision tree classifier.
 */
public class GenTreeUtils
{
    /** The small deviation allowed in double comparisons */
    public static double SMALL = 1e-6;

    /** For Quicksort. Use Selectsort if set is lower this number. */
    static final int SORT_SMALL_SET = 15;

    public GenTreeUtils()
    {
    }

    /*****************************************************************************
    *  Funktion: SelectionSort                                                   *
    *                                                                            *
    *  Aufrufparameter:   double F[]: Array von double-Werten                    *
    *                     int C[]:    Klassenvektor                              *
    *                     int l,r:   linke bzw. rechte Bereichsgrenzen           *
    *  R點kgabeparameter: keiner                                                 *
    *                                                                            *
    *  Beschreibung                                                              *
    *  ============                                                              *
    *  Sortiert den Attributvektor F und den Klassenvektor C mit dem Selection-  *
    *  sort-Verfahren. Sortierreihenfolge ist aufsteigend. Es wird jeweils das   *
    *  kleinste Element gesucht und getauscht.                                   *
    ******************************************************************************/

    public static void SelectionSort(double F[], int C[], int l, int r){

      for (int i = l; i < r; i++)
      {
        int min = i;
        for (int j=i+1; j <= r; j++)
          if (F[j] < F[min]) min = j;
        double tempd=F[min];
        F[min]=F[i];
        F[i]=tempd;
        int tempi=C[min];
        C[min] = C[i];
        C[i] = tempi;
      }
    }

    /*****************************************************************************
    *  Funktion: Partition                                                       *
    *                                                                            *
    *  Aufrufparameter:   double F[]: Array von double-Werten, die sortiert      *
    *                                 werden sollen                              *
    *                     int C[]:    Klassenvektor                              *
    *                     int l,r:    linke bzw. rechte Bereichsgrenzen          *
    *  R點kgabeparameter: int:        liefert die Grenze zwischen den Teilmengen *
    *                                                                            *
    *  Beschreibung                                                              *
    *  ============                                                              *
    *  Partioniert die Gesamtmenge zwischen l und r in zwei Teilmengen. Die      *
    *  Elemente der ersten H鋖fte sind dabei kleiner oder gleich den Elementen   *
    *  der zweiten H鋖fte. Diese Funktion wird f黵 die Sortierung mit dem Quick- *
    *  sort-Algorithmus verwendet.                                               *
    ******************************************************************************/

    protected static int Partition(double F[], int C[], int l, int r)
    {
      double val =F[l];
      int lm = l-1;
      int rm = r+1;
      for(;;)
      {
        do rm--;while (F[rm] > val);
        do lm++;while( F[lm] < val);
        if(lm < rm)
        {
          double tempd=F[rm];F[rm]=F[lm];F[lm]=tempd; //Attributwert vertauschen
          int tempi = C[rm];                //Klasseattribut vertauschen
          C[rm] = C[lm];
          C[lm] = tempi;
        }
        else return rm;
      }
    }

    /*****************************************************************************
    *  Funktion: Quicksort                                                       *
    *                                                                            *
    *  Aufrufparameter:   double F[]: Array von double-Werten, die sortiert      *
    *                                 werden soll                                *
    *                     int *C:     Klassenvektor                              *
    *                     int l,r:    linke bzw. rechte Bereichsgrenzen          *
    *  R點kgabeparameter: keiner                                                 *
    *                                                                            *
    *  Beschreibung                                                              *
    *  ============                                                              *
    *  Sortiert den Attributvektor F und den Klassenvektor C mit dem Quicksort-  *
    *  Verfahren. Ist die Differenz r-l klein, wird mit Selection-Sort-Verfahren *
    *  weiter sortiert.                                                          *
    ******************************************************************************/

    public static void Quicksort(double F[], int C[], int l, int r)
    {
      if(l < (r-SORT_SMALL_SET))
      {
        int split_pt = Partition(F, C, l, r); //Pivot-Element suchen
        Quicksort(F, C, l, split_pt);         //rechts Teilmenge sortieren
        Quicksort(F, C, split_pt+1, r);       //linke Teilmenge sortieren
      }else SelectionSort(F, C, l, r);        //kleine Datenmengen werden mit
                                              //Selectionsort sortiert
    }

    /**
     * Returns index of maximum element in a given
     * array of doubles. First maximum is returned.
     *
     * @param doubles the array of doubles
     * @return the index of the maximum element
     */
    public static int maxIndex(double [] doubles)
    {
        double maximum = 0;
        int maxIndex = 0;
        for(int i = 0; i < doubles.length; i++)
        {
            if((i == 0) || (doubles[i] > maximum))
            {
                maxIndex = i;
                maximum = doubles[i];
            }
        }
        return maxIndex;
    }

    /**
     * Returns index of maximum element in a given
     * array of integers. First maximum is returned.
     *
     * @param ints the array of integers
     * @return the index of the maximum element
     */
    public static int maxIndex(int [] ints)
    {
        int maximum = 0;
        int maxIndex = 0;
        for(int i = 0; i < ints.length; i++)
        {
            if((i == 0) || (ints[i] > maximum))
            {
                maxIndex = i;
                maximum = ints[i];
            }
        }
        return maxIndex;
    }

    /**
     * Tests if a is equal to b.
     *
     * @param a a double
     * @param b a double
     */
    public static boolean eq(double a, double b)
    {
        return (a - b < SMALL) && (b - a < SMALL);
    }

    /**
    * Normalizes the doubles in the array by their sum.
    *
    * @param doubles the array of double
    * @exception IllegalArgumentException if sum is Zero or NaN
    */
    public static void normalize(double[] doubles)
    {
        double sum = 0;