Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

This is a solution from the CodeSprint 2012 coding competition. Any suggestions on ways to improve the object orientation or general style would be much appreciated. The code takes several text documents, encodes them into feature vectors using TF-IDF, and then applies k-means clustering to group documents with similar topics/themes.

/**
 * Class containing an individual document
 */
private class Document implements Comparable<Document> {

  // document title, contents and ID
  private final String title;
  private final String contents;
  private final long id;
  // whether document has been allocated to a cluster
  private boolean allocated;
  // document word histogram
  private Vector histogram;
  // encoded document vector (TF-IDF)
  private Vector vector;
  // precalculated document vector norms
  private double norm;

  public Document(long id, String title, String contents) {
    this.id = id;
    this.title = title;
    this.contents = contents;
  }

  public void setVector(Vector vector) {
    this.vector = vector;
  }

  public boolean isAllocated() {
    return allocated;
  }

  /**
   * Mark document as having been allocated to a cluster
   */
  public void setIsAllocated() {
    allocated = true;
  }

  /**
   * Mark document as not being allocated to a cluster
   */
  public void clearIsAllocated() {
    allocated = false;
  }

  public long getId() {
    return id;
  }

  public String getContents() {
    return contents;
  }

  public Vector getVector() {
    return vector;
  }

  public Vector getHistogram() {
    return histogram;
  }

  public void setHistogram(Vector histogram) {
    this.histogram = histogram;
  }

  public void setNorm(double norm) {
    this.norm = norm;
  }

  public double getNorm() {
    return norm;
  }

  /**
   * Allow documents to be sorted by ID
   */
  public int compareTo(Document document) {
    if (id > document.getId()) {
      return 1;
    } else if (id < document.getId()) {
      return -1;
    } else {
      return 0;
    }
  }

}

/**
 * Class storing a collection of documents to be clustered
 */
private class DocumentList extends ArrayList<Document> {

  /**
   * Parse input string into document ID, document title and contents then
   * encode into feature vector using encoder
   *
   * @param input
   *          String containing document fields
   * @param encoder
   *          Encoder to use for encoding document into feature vector
   */
  public DocumentList(String input) {
    StringTokenizer st = new StringTokenizer(input, "{");
    int numDocuments = st.countTokens() - 1;
    String record = st.nextToken(); // skip empty split to left of {
    Pattern pattern =
        Pattern
        .compile("\"content\": \"(.*)\", \"id\": (.*), \"title\": \"(.*)\"");
    for (int i = 0; i < numDocuments; i++) {
      record = st.nextToken();
      Matcher matcher = pattern.matcher(record);
      if (matcher.find()) {
        long documentID = Long.parseLong(matcher.group(2));
        String title = matcher.group(3);
        String contents = matcher.group(1);
        add(new Document(documentID, title, contents));
      }
    }
  }

  /**
   * Mark all documents as not being allocated to a cluster
   */
  public void clearIsAllocated() {
    for (Document document : this) {
      document.clearIsAllocated();
    }
  }

}

/**
 * Interface for encoders which encode documents into feature vectors
 */
private interface Encoder {

  public void encode(DocumentList documentList);

}

/**
 * Implementation of Encoder which uses Term Frequency - Inverse Document
 * Frequency (TF-IDF) encoding
 */
private class TfIdfEncoder implements Encoder {

  // number of features to be used in feature vector
  private final int numFeatures;
  // inverse document frequency used for normalization of feature vectors
  private Vector inverseDocumentFrequency = null;

  public TfIdfEncoder(int numFeatures) {
    this.numFeatures = numFeatures;
  }

  /**
   * Calculate word histogram for document and store in histogram field
   */
  private void calcHistogram(Document document) {

    // Calculate word histogram for document
    String[] words = document.getContents().split("[^\\w]+");
    Vector histogram = new Vector(numFeatures);
    for (int i = 0; i < words.length; i++) {
      int hashCode = hashWord(words[i]);
      histogram.increment(hashCode);
    }
    document.setHistogram(histogram);
  }

  /**
   * Calculate word histogram for all documents in a DocumentList
   */
  private void calcHistogram(DocumentList documentList) {
    for (Document document : documentList) {
      calcHistogram(document);
    }
  }

  /**
   * Calculate inverse document frequency for DocumentList. Assumes word
   * histograms for constituent documents have already been calculated
   */
  private void calcInverseDocumentFrequency(DocumentList documentList) {

    inverseDocumentFrequency = new Vector(numFeatures);
    for (Document document : documentList) {
      for (int i = 0; i < numFeatures; i++) {
        if (document.getHistogram().get(i) > 0) {
          inverseDocumentFrequency.increment(i);
        }
      }
    }
    inverseDocumentFrequency.invert();
    inverseDocumentFrequency.multiply(documentList.size());
    inverseDocumentFrequency.log();
  }

  /**
   * Encode document using Term Frequency - Inverse Document Frequency
   */
  private void encode(Document document) {

    // Normalize word histogram by maximum word frequency
    Vector vector = document.getHistogram().clone();
    // Allow histogram to be deallocated as it is no longer needed
    document.setHistogram(null);
    vector.divide(vector.max());
    // Normalize by inverseDocumentFrequency
    vector.multiply(inverseDocumentFrequency);
    // Store feature vecotr in document
    document.setVector(vector);
    // Precalculate norm for use in distance calculations
    document.setNorm(vector.norm());

  }

  /**
   * Hash word into integer between 0 and numFeatures-1. Used to form document
   * feature vector
   *
   * @param word
   *          String to be hashed
   * @return hashed integer
   */
  private int hashWord(String word) {
    return Math.abs(word.hashCode()) % numFeatures;
  }

  /**
   * Encode all documents within a DocumentList
   */
  public void encode(DocumentList documentList) {

    calcHistogram(documentList);
    calcInverseDocumentFrequency(documentList);
    for (Document document : documentList) {
      encode(document);
    }

  }

}

/**
 * Class representing a cluster of Documents
 */
private class Cluster extends ArrayList<Document> implements
Comparable<Cluster> {

  // cluster centroid
  private Vector centroid;
  // norm of cluster centroid
  private double centroidNorm;

  /**
   * Instantiate a cluster with a single member document
   */
  public Cluster(Document document) {
    super();
    add(document);
    centroid = document.getVector().clone();
    centroidNorm = centroid.norm();
  }

  /**
   * Allows sorting of Clusters by comparing ID of first document
   */
  public int compareTo(Cluster cluster) {
    return get(0).compareTo(cluster.get(0));
  }

  /**
   * Add document to cluster and mark document as allocated
   */
  public boolean add(Document document) {
    super.add(document);
    document.setIsAllocated();
    return true;
  }

  /**
   * Update centroids and centroidNorms for a specific cluster
   *
   * @param clusterIndex
   *          cluster to update
   */
  private void updateCentroid() {
    centroid = null;
    for (Document document : this) {
      if (centroid == null) {
        centroid = document.getVector().clone();
      } else {
        centroid.add(document.getVector());
      }
    }
    centroid.divide(size());
    centroidNorm = centroid.norm();
  }

  public Vector getCentroid() {
    return centroid;
  }

  public double getCentroidNorm() {
    return centroidNorm;
  }

  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    for (int i = 0; i < this.size(); i++) {
      sb.append(this.get(i).getId());
      if (i < this.size() - 1) {
        sb.append(", ");
      }
    }
    sb.append("]");
    return sb.toString();
  }

}

/**
 * Class representing a list of clusters. This is the output of the clustering
 * process
 */

private class ClusterList extends ArrayList<Cluster> {

  /**
   * Instantiate a list of clusters with a given initial capacity
   *
   * @param initialCapacity
   */
  public ClusterList(int initialCapacity) {
    super(initialCapacity);
  }

  /**
   * Update centroids of all clusters within ClusterList
   */
  public void updateCentroids() {
    for (Cluster cluster : this) {
      cluster.updateCentroid();
    }
  }

  /**
   * Find document with maximum distance to clusters in ClusterList. Distance
   * to ClusterList is defined as the minimum of the distances to each
   * constituent Cluster's centroid. This method is used during the cluster
   * initialization in k means clustering
   *
   * @param distance
   *          distance measure to use
   * @param documentList
   *          list of documents to search
   * @return furthest document
   */
  public Document findFurthestDocument(Distance distance,
      DocumentList documentList) {
    double furthestDistance = Double.MIN_VALUE;
    Document furthestDocument = null;
    for (Document document : documentList) {
      if (!document.isAllocated()) {
        double documentDistance = distance.calcDistance(document, this);
        if (documentDistance > furthestDistance) {
          furthestDistance = documentDistance;
          furthestDocument = document;
        }
      }
    }
    return furthestDocument;
  }

  /**
   * Clear out documents from within each cluster. Used to cleanup at the end
   * of each iteration of k means
   */
  private void emptyClusters() {
    for (Cluster cluster : this) {
      cluster.clear();
    }
  }

  /**
   * Find cluster whose centroid is closest to a document
   *
   * @param distance
   *          distance measure to use
   * @param document
   * @return Cluster closest to document
   */
  private Cluster findNearestCluster(Distance distance, Document document) {
    Cluster nearestCluster = null;
    double nearestDistance = Double.MAX_VALUE;
    for (Cluster cluster : this) {
      double clusterDistance = distance.calcDistance(document, cluster);
      if (clusterDistance < nearestDistance) {
        nearestDistance = clusterDistance;
        nearestCluster = cluster;
      }
    }
    return nearestCluster;
  }

  /**
   * Calculate ratio of average intracluster distance to average intercluster
   * distance. Used to optimize number of clusters k
   *
   * @return ratio of average intracluster distance to average intercluster
   *         distance
   */
  private double calcIntraInterDistanceRatio(Distance distance) {
    if (this.size() > 1) {
      double interDist = calcInterClusterDistance(distance);
      if (interDist > 0.0) {
        return calcIntraClusterDistance(distance) / interDist;
      } else {
        return Double.MAX_VALUE;
      }
    } else {
      return Double.MAX_VALUE;
    }
  }

  /**
   * Calculate average intracluster distance, which is the average distance
   * between the constituent documents in a cluster and the cluster centroid
   *
   * @param distance
   *          distance measure to use
   */
  private double calcIntraClusterDistance(Distance distance) {
    double avgIntraDist = 0.0;
    int numDocuments = 0;
    for (Cluster cluster : this) {
      double clusterIntraDist = 0.0;
      for (Document document : cluster) {
        clusterIntraDist += distance.calcDistance(document, cluster);
      }
      numDocuments += cluster.size();
      avgIntraDist += clusterIntraDist;
    }
    return avgIntraDist / numDocuments;
  }

  /**
   * Calculate average intercluster distance, which is the distance between
   * cluster centroids
   *
   * @param distance
   *          distance measure to use
   */
  private double calcInterClusterDistance(Distance distance) {

    if (this.size() > 1) {
      double avgInterDist = 0.0;
      for (Cluster cluster1 : this) {
        for (Cluster cluster2 : this) {
          if (cluster1 != cluster2) {
            avgInterDist += distance.calcDistance(cluster1, cluster2);
          }
        }
      }
      // there are N*N-1 unique pairs of clusters
      avgInterDist /= (this.size() * (this.size() - 1));
      return avgInterDist;
    } else {
      return 0.0;
    }
  }

  /**
   * Sort order of documents within each cluster, then sort order of clusters
   * within ClusterList
   */
  public void sort() {
    for (Cluster cluster : this) {
      Collections.sort(cluster);
    }
    Collections.sort(this);
  }

  /**
   * Display clusters in sorted order
   */
  public String toString() {
    sort();
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    for (int i = 0; i < this.size(); i++) {
      sb.append(this.get(i));
      if (i < this.size() - 1) {
        sb.append(", ");
      }
    }
    sb.append("]");
    return sb.toString();
  }

}

/**
 * Class for measuring the distance between documents, clusters and
 * clusterLists
 */
private abstract class Distance {

  public double calcDistance(Document document, Cluster cluster) {

    return calcDistance(document.getVector(), cluster.getCentroid(),
        document.getNorm(), cluster.getCentroidNorm());

  }

  /**
   * Calculate minimum of the distances between a document and the centroids
   * of the clusters within a clusterList
   */
  public double calcDistance(Document document, ClusterList clusterList) {
    double distance = Double.MAX_VALUE;
    for (Cluster cluster : clusterList) {
      distance = Math.min(distance, calcDistance(document, cluster));
    }
    return distance;
  }

  public double calcDistance(Cluster cluster1, Cluster cluster2) {
    return calcDistance(cluster1.getCentroid(), cluster2.getCentroid(),
        cluster1.getCentroidNorm(), cluster2.getCentroidNorm());
  }

  public abstract double calcDistance(Vector vector1, Vector vector2,
      double norm1, double norm2);

}

/**
 * Class for calculating cosine distance between two vectors
 */
private class CosineDistance extends Distance {

  public double calcDistance(Vector vector1, Vector vector2, double norm1,
      double norm2) {
    return 1.0 - vector1.innerProduct(vector2) / norm1 / norm2;
  }

}

/**
 * Class for caculating Jaccard distance between vectors
 */
@SuppressWarnings("unused")
private class JaccardDistance extends Distance {

  public double calcDistance(Vector vector1, Vector vector2, double norm1,
      double norm2) {
    double innerProduct = vector1.innerProduct(vector2);
    return Math.abs(1.0 - innerProduct / (norm1 + norm2 - innerProduct));
  }

}

/**
 * Class for a clusterer which clusters the documents within a DocumentList
 * into a ClusterList
 */
private abstract class Clusterer {

  // distance measure to use when evaluating distance between documents
  Distance distance;

  public abstract ClusterList cluster(DocumentList documentList);

}

/**
 * An k means clustering implementation of the Clusterer class
 */
private class KMeansClusterer extends Clusterer {

  // threshold used to determine number of clusters k
  private final double clusteringThreshold;
  // number of iterations to use in k means clustering
  private final int clusteringIterations;

  public KMeansClusterer(Distance distance, double clusteringThreshold,
      int clusteringIterations) {
    this.distance = distance;
    this.clusteringThreshold = clusteringThreshold;
    this.clusteringIterations = clusteringIterations;
  }

  /**
   * Run k means clustering on documentList. Number of clusters k is set to
   * the lowest value that ensures the intracluster to intercluster distance
   * ratio is above clusteringThreshold
   *
   * @return ClusterList containing the clusters
   */
  public ClusterList cluster(DocumentList documentList) {
    ClusterList clusterList = null;
    for (int k = 1; k <= documentList.size(); k++) {
      clusterList = runKMeansClustering(documentList, k);
      if (clusterList.calcIntraInterDistanceRatio(distance) < clusteringThreshold) {
        break;
      }
    }
    return clusterList;
  }

  /**
   * Run k means clustering on documentList for a fixed number of clusters k
   *
   * @param documentList
   *          documents to be clustered
   * @param k
   *          target number of clusters
   * @return ClusterList containing the clusters
   */
  private ClusterList runKMeansClustering(DocumentList documentList, int k) {
    ClusterList clusterList = new ClusterList(k);
    documentList.clearIsAllocated();
    // create 1st cluster using a random document
    Random rnd = new Random();
    int rndDocIndex = rnd.nextInt(k);
    Cluster initialCluster = new Cluster(documentList.get(rndDocIndex));
    clusterList.add(initialCluster);
    // create k-1 more clusters
    while (clusterList.size() < k) {
      // create new cluster containing furthest doc from existing clusters
      Document furthestDocument =
          clusterList.findFurthestDocument(distance, documentList);
      Cluster nextCluster = new Cluster(furthestDocument);
      clusterList.add(nextCluster);
    }

    // add remaining documents to one of the k existing clusters
    for (int iter = 0; iter < clusteringIterations; iter++) {
      for (Document document : documentList) {
        if (!document.isAllocated()) {
          Cluster nearestCluster =
              clusterList.findNearestCluster(distance, document);
          nearestCluster.add(document);
        }
      }
      // update centroids and centroidNorms
      clusterList.updateCentroids();
      // prepare for reallocation in next iteration
      if (iter < clusteringIterations - 1) {
        documentList.clearIsAllocated();
        clusterList.emptyClusters();
      }
    }
    return clusterList;
  }

}

Here's an example of a typical clustering:

public static void main(String[] args) throws IOException {
  String input;
  if (args.length > 0) {
    BufferedReader in = new BufferedReader(new FileReader(new File(args[0])));
    input = in.readLine();
  } else {
    Scanner sc = new Scanner(System.in);
    input = sc.nextLine();
  }
  DocumentList documentList = new DocumentList(input);
  Encoder encoder = new TfIdfEncoder(10000);
  encoder.encode(documentList);
  Distance distance = new CosineDistance();
  Clusterer clusterer = new KMeansClusterer(distance, 0.4, 3);
  ClusterList clusterList = clusterer.cluster(documentList);
  System.out.println(clusterList.toString());
}
share|improve this question
    
    
This may look similar at the top due to the Vector class but it's very much a different program and I think that different issues come into play. –  padawan Jan 19 '12 at 7:22
2  
@cendrillon Maybe you should factor Vector out into its own class (which you could ask about separately) to avoid duplication between the questions. As far as I can tell it shouldn't be a nested class anyway (style tip 1: classes that don't need to share state, should not be defined as (non-static) nested classes). –  sepp2k Jan 19 '12 at 7:40
    
Thanks Sepp. The single class is a bit of a quirk of the competition (CodeSprint). They require you to cut and paste a single class which contains the solution into their site which then goes off and runs unit tests to see if the code is valid. Anyway, I'll take the Vector class out here to avoid the duplication. –  padawan Jan 19 '12 at 16:56
add comment

1 Answer 1

up vote 1 down vote accepted
+50

Some notes:

  1. This comment is unnecessary:

    // document title, contents and ID
    private final String title;
    private final String contents;
    private final long id;
    

    Since they are inside the Document class, it's obvious that the title is a title of a document, and so on.

  2. // whether document has been allocated to a cluster
    private boolean allocated;
    

    Here I'd rename the variable to allocatedToCluster and remove the comment. It would make the code more readable since you don't have to check the declaration to figure out what it is allocated to.

  3. For the same reason as above,

    • histogram should be wordHistogram,
    • vector should be encodedDocumentVector,

    etc.

  4. Input check is missing in the constructor:

    public Document(long id, String title, String contents) {
        this.id = id;
        this.title = title;
        this.contents = contents;
    }
    

    Does it make sense to have a Document with null or empty String title or contents? If not, check it and throw an IllegalArgumentException. (Effective Java, Second Edition, Item 38: Check parameters for validity)

  5. if (id > document.getId()) {
        return 1;
    } else if (id < document.getId()) {
        return -1;
    } else {
        return 0;
    }
    

    Instead of this code I'd use ObjectUtils.compare from Apache Commons Lang.

  6. class DocumentList extends ArrayList<Document> 
    

    Check Effective Java, Second Edition, Item 16: Favor composition over inheritance.

  7. Sometimes comments should be method names:

    // add remaining documents to one of the k existing clusters
    for (int iter = 0; iter < clusteringIterations; iter++) {
    

    Create an addRemainingDocuments... method and move the for loop in it instead of the comment.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.