klinkage.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 Michael Thess
 * @version 1.1
 */

package com.prudsys.pdm.Models.Clustering.Partitioning.Algorithms;

import java.util.Vector;

import com.prudsys.pdm.Core.MiningException;
import com.prudsys.pdm.Input.MiningVector;
import com.prudsys.pdm.Models.Clustering.Cluster;
import com.prudsys.pdm.Models.Clustering.Partitioning.PartitioningClusteringAlgorithm;

/**
 * Class for k-linkage clustering.
 */
public class KLinkage extends PartitioningClusteringAlgorithm
{
  /** Matrix of threshold distances. */
  private boolean[][] distMat;

  /**
   * Runs k-linkage clustering algorithm.
   *
   * @exception MiningException could not run algorithm
   */
  protected void runAlgorithm() throws MiningException {

    // Number of attributes and vectors:
    int numbAtt = metaData.getAttributesNumber();
    int numbVec = 0;

    // Get minimum and maximum of attributes, used if normalization:
    double[] minArr = new double[ numbAtt ];
    double[] maxArr = new double[ numbAtt ];
    for (int i = 0; i < numbAtt; i++) {
      minArr[i] = 0.0;
      maxArr[i] = 0.0;
    };
    while (miningInputStream.next()) {
      MiningVector vec = miningInputStream.read();
      for (int i = 0; i < numbAtt; i++) {
        if (vec.getValue(i) < minArr[i])
          minArr[i] = vec.getValue(i);
        if (vec.getValue(i) > maxArr[i])
          maxArr[i] = vec.getValue(i);
      };
      numbVec = numbVec + 1;
    };
    distance.setMinAtt( minArr );
    distance.setMaxAtt( maxArr );

    // Calculate distance matrix:
    distMat = new boolean[numbVec][numbVec];
    for (int i = 0; i < numbVec; i++)
      for (int j = i+1; j < numbVec; j++)
         if (distance.distance( miningInputStream.read(i),
                                miningInputStream.read(j) ) < threshold) {
           distMat[i][j] = true;
           distMat[j][i] = true;
         };

    // Find clusters:
    Vector pclust  = new Vector();
    MiningLinkNode[] mln = new MiningLinkNode[numbVec];
    for (int i = 0; i < numbVec; i++) {
      mln[i] = new MiningLinkNode();
      mln[i].setIndex(i);
    }
    for (int i = 0; i < numbVec; i++)
      for (int j = i+1; j < numbVec; j++)
        if (distMat[i][j]) {
          mln[i].addNeighbNode(mln[j]);
          mln[j].addNeighbNode(mln[i]);
        };

    for (int i = 0; i < numbVec; i++) {
      if (mln[i].getStatus() != 0) continue;

      // Build graph of all 1-links:
      mln[i].setStatus(1);
      buildNeighbGraph(mln[i], mln);

      // Prune graph to k-links:
      pruneNeighbGraph(mln[i], mln);

      // Create current cluster:
      Cluster clust           = new Cluster();
      Vector containedVectors = new Vector();
      for (int j = 0; j < numbVec; j++) {
        if (mln[j].getStatus() == 1) {
          containedVectors.addElement( miningInputStream.read(j) );
          mln[j].setStatus(-1);
        };
      };
      clust.setContainedVectors(containedVectors);
      pclust.addElement(clust);
    };

    // Create array of clusters:
    int nclust = pclust.size();
    clusters   = new Cluster[nclust];
    for (int i = 0; i < nclust; i++)
      clusters[i] = (Cluster) pclust.elementAt(i);
  };

  /**
  * Build 1-link cluster using a loop.
  *
  * @param node node to look for neighbours
  * @param all all nodes
  */
  private void buildNeighbGraph(MiningLinkNode node, MiningLinkNode[] all) {

    boolean newLink = true;
    while (newLink) {
      newLink = false;
      for (int i = 0; i < all.length; i++) {
        MiningLinkNode cnode = all[i];
        if (cnode.getStatus() != 1)
          continue;
        for (int j = 0; j < cnode.getNeighbCount(); j++) {
          MiningLinkNode nnode = (MiningLinkNode) cnode.getNeighbAt(j);
          if (nnode.getStatus() == 0) {
            nnode.setStatus(1);
            newLink = true;
          };
        };
      };
    };
  }

  /**
  * Build 1-link cluster recursively. No more used because of
  * stack overflow problems.
  *
  * @param node node to look for neighbours
  * @param all all nodes
  */
  private void buildNeighbGraphRec(MiningLinkNode node, MiningLinkNode[] all) {

    int ind = node.getIndex();
    for (int i = 0; i < all.length; i++) {
      MiningLinkNode neighb = all[i];
      if ( i == ind || !distMat[ind][i] || node.getNeighbIndex(neighb) > -1 )
        continue;
      node.addNeighbNode(neighb);
      neighb.addNeighbNode(node);
      neighb.setStatus(1);

      buildNeighbGraphRec(neighb, all);
    };
  }

  /**
  * Prune cluster recursively according to linkage parameter.
  *
  * @param node node to look for neighbours
  * @param all all nodes
  */
  private void pruneNeighbGraph(MiningLinkNode node, MiningLinkNode[] all) {

    int nclust    = 0;
    int ncold     = Integer.MAX_VALUE;
    boolean first = true;
    while (nclust < ncold) {
      if (! first) ncold  = nclust;
      if (first)    first = false;
      nclust = 0;
      for (int i = 0; i < all.length; i++) {
        MiningLinkNode cnode = all[i];
        int nn = cnode.getNeighbCount();
        if (cnode == node || (cnode.getStatus() == 1 && nn >= linkage) )
          nclust = nclust + 1;
        else if (cnode.getStatus() == 1) {
          for (int j = 0; j < nn; j++) {
            MiningLinkNode nei = (MiningLinkNode) cnode.getNeighbAt(0);
            cnode.removeNeighbNode(nei);
            nei.removeNeighbNode(cnode);
            cnode.setStatus(0);
          };
        };
      };

      // There exists another isolated cluster that must be removed:
      if (node.getNeighbCount() == 0 && nclust > 1) {
        for (int i = 0; i < all.length; i++)
          if (all[i].getStatus() == 1 && all[i] != node)
            all[i].setStatus(0);
      };
    };
  }
}