0
$\begingroup$

I built an inverted index to represent the following sample documents:

String[] docs = {"hot chocolate cocoa beans",
                 "cocoa ghana africa",
                 "beans harvest ghana",
                 "cocoa butter",
                 "butter truffles",
                 "sweet chocolate can",
                 "brazil sweet sugar can",
                 "suger can brazil",
                 "sweet cake icing",
                 "cake black forest",
                 "cake black forest forest"
                };

The inverted index looks like this:

hot            0: 2.3978952727983707    
chocolate      0: 1.7047480922384253    5: 1.7047480922384253   
cocoa          0: 1.2992829841302609    1: 1.2992829841302609   3: 1.2992829841302609   
beans          0: 1.7047480922384253    2: 1.7047480922384253   
ghana          1: 1.7047480922384253    2: 1.7047480922384253   
africa         1: 2.3978952727983707    
harvest        2: 2.3978952727983707    
butter         3: 1.7047480922384253    4: 1.7047480922384253   
truffles       4: 2.3978952727983707    
sweet          5: 1.2992829841302609    6: 1.2992829841302609   8: 1.2992829841302609   
can            5: 1.2992829841302609    6: 1.2992829841302609   7: 1.2992829841302609   
brazil         6: 1.7047480922384253    7: 1.7047480922384253   
sugar          6: 2.3978952727983707    
suger          7: 2.3978952727983707    
cake           8: 1.2992829841302609    9: 1.2992829841302609   10: 1.2992829841302609  
icing          8: 2.3978952727983707    
black          9: 1.7047480922384253    10: 1.7047480922384253  
forest         9: 1.7047480922384253    10: 2.8863894259384355  

Each term has a tf-idf weight that corresponds to the document it's found in.

My class assignment would like me to next compute k-means on these documents using this inverted index and the tf-idf values. I've been struggling to do this. I read that k-means requires document vectors that are normalized to be of the same length, but this inverted index seems not to have that. How do I compute k-means with this data structure? What exactly do I set the centroid seeds as?

Code (with cluster method incomplete):

import java.util.*;

/**
 * Document clustering
 */
public class Clustering {
    // Declare attributes
    int k; // num of clusters
    ArrayList<String> vocabulary; // termList
    ArrayList<ArrayList<Doc>> docLists;
    double[] docLength;


    /**
     * Constructor for attribute initialization
     * @param numC number of clusters
     */
    public Clustering(int numC)
    {
        k = numC;
    }

    /**
     * Load the documents to build the vector representations
     * @param docs
     */
    public void preprocess(String[] docs){
        vocabulary = new ArrayList<String>();
        docLists = new ArrayList<ArrayList<Doc>>();
        ArrayList<Doc> docList; // reusable variable

        // For each document,
        for (int i = 0; i < docs.length; i++) {
            // Tokenize document, removing punctuation
            String[] tokens = docs[i].split("[ _\".,?!/:;$%&*+()\\-\\^]+");

            // For each token,
            for (String token : tokens) {
                // If new, 
                if (!vocabulary.contains(token)) {
                    // Add to vocabulary
                    vocabulary.add(token);
                    // Set corresponding postings
                    docList = new ArrayList<Doc>();
                    Doc doc = new Doc(i, 1); // Initial weight is raw word frequency, starting with 1
                    docList.add(doc);
                    docLists.add(docList);
                } else {
                // If not new,
                    // Retrieve postings
                    int index = vocabulary.indexOf(token);
                    docList = docLists.get(index);
                    boolean match = false;

                    // Search postings for matching document id
                    for (Doc d : docList) {
                        if (d.id == i) {
                            d.tw++; // Increase word frequency 
                            match = true;
                            break;
                        }
                    }

                    // If postings did not contain matching document id, 
                    // add a new posting for the document 
                    if (!match) {
                        Doc d = new Doc(i, 1);
                        docList.add(d);
                    }
                }
            }
        } // End parsing documents

        // Calculate tf*idf of each document and set as weights
        int N = docs.length;
        docLength = new double[N];
        // For each term in the vocabulary
        for (int i = 0; i < vocabulary.size(); i++) {
            // Get its corresponding postings & document frequency 
            docList = docLists.get(i);
            int df = docList.size();
            Doc d;
            // For each document in the postings
            for (int j = 0; j < df; j++) {
                // Get its Doc object, calculate tf-idf
                d = docList.get(j);
                double tfidf = (1 + Math.log(d.tw)) * Math.log(N / (df * 1.0));
                docLength[d.id] += Math.pow(tfidf,  2);
                d.tw = tfidf;
                docList.set(j, d);
            }
        }

        // Update all lengths
        for (int i = 0; i < N; i++) {
            docLength[i] = Math.sqrt(docLength[i]);
        }
    }

    /**
     * Cluster the documents
     * For kmeans clustering, use the first and the ninth documents as the initial centroids
     */
    public void cluster(){

    }

    public String toString() {
        String matrixString = new String();
        ArrayList<Doc> docList;
        for (int i = 0; i < vocabulary.size(); i++) {
            matrixString += String.format("%-15s", vocabulary.get(i));
            docList = docLists.get(i);
            for (int j = 0; j < docList.size(); j++) {
                matrixString += docList.get(j) + "\t";
            }
            matrixString += "\n";
        }
        return matrixString;
    }

    public static void main(String[] args){
        String[] docs = {"hot chocolate cocoa beans",
                 "cocoa ghana africa",
                 "beans harvest ghana",
                 "cocoa butter",
                 "butter truffles",
                 "sweet chocolate can",
                 "brazil sweet sugar can",
                 "suger can brazil",
                 "sweet cake icing",
                 "cake black forest",
                 "cake black forest forest"
                };

        Clustering c = new Clustering(2);
        c.preprocess(docs);
        System.out.println(c);
        c.cluster();

        /*
         * Expected result:
         * Cluster: 0
            0   1   2   3   4   
           Cluster: 1
            5   6   7   8   9   
         */
    }
}

/**
 * Document class for the vector representation of a document
 */
class Doc{
    int id; 
    double tw;

    public Doc(int id, double tw) {
        this.id = id;
        this.tw = tw;
    }

    public String toString() {
        String docRepr = id + ": " + tw;
        return docRepr;
    }
}
$\endgroup$
-1
$\begingroup$

Using an index in k-means is not trivial, the default algorithm will not benefit much from this. You need some advanced versions of it instead. Some may only build an index on the centers.

Then you'll of course need to build the index on the normalized vectors, to be able to efficiently query.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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