12
$\begingroup$

I'm going to classify unstructured text documents, namely web sites of unknown structure. The number of classes to which I am classifying is limited (at this point, I believe there is no more than three). Does anyone have a suggested for how I might get started?

Is the "bag of words" approach feasible here? Later, I could add another classification stage based on document structure (perhaps decision trees).

I am somewhat familiar with Mahout and Hadoop, so I prefer Java-based solutions. If needed, I can switch to Scala and/or Spark engine (the ML library).

$\endgroup$
13
$\begingroup$

Let's work it out from the ground up. Classification (also known as categorization) is an example of supervised learning. In supervised learning you have:

  • model - something that approximates internal structure in your data, enabling you to reason about it and make useful predictions (e.g. predict class of an object); normally model has parameters that you want to "learn"
  • training and testing datasets - sets of objects that you use for training your model (finding good values for parameters) and further evaluating
  • training and classification algorithms - first describes how to learn model from training dataset, second shows how to derive class of a new object given trained model

Now let's take a simple case of spam classification. Your training dataset is a corpus of emails + corresponding labels - "spam" or "not spam". Testing dataset has the same structure, but made from some independent emails (normally one just splits his dataset and makes, say, 9/10 of it to be used for training and 1/10 - for testing). One way to model emails is to represent each of them as a set (bag) of words. If we assume that words are independent of each other, we can use Naive Bayes classifier, that is, calculate prior probabilities for each word and each class (training algorithm) and then apply Bayes theorem to find posterior probability of a new document to belong to particular class.

So, basically we have:

raw model + training set + training algorithm -> trained model
trained model + classification algorithm + new object -> object label

Now note that we represented our objects (documents) as a bag of words. But is the only way? In fact, we can extract much more from raw text. For example, instead of words as is we can use their stems or lemmas, throw out noisy stop words, add POS tags of words, extract named entities or even explore HTML structure of the document. In fact, more general representation of a document (and, in general, any object) is a feature vector. E.g. for text:

actor, analogue, bad, burn, ..., NOUN, VERB, ADJ, ..., in_bold, ... | label
    0,        0,   1,    1, ...,    5,    7,   2, ...,       2, ... | not spam
    0,        1,   0,    0, ...,    3,   12,  10, ...,       0, ... | spam

Here first row is a list of possible features and subsequent rows show how many times that feature occurs in a document. E.g. in first document there's no occurrences of word "actor", 1 occurrence of word "burn", 5 nouns, 2 adjectives and 2 pieces of text in bold. Last column corresponds to a resulting class label.

Using feature vector you can incorporate any properties of your texts. Though finding good set of features may take some time.

And what about model and algorithms? Are we bound to Naive Bayes. Not at all. logistic regression, SVM, decision trees - just to mention few popular classifiers. (Note, that we say "classifier" in most cases we mean model + corresponding algorithms for training and classification).

As for implementation, you can divide task into 2 parts:

  1. Features extraction - transforming raw texts into feature vectors.
  2. Object classification - building and applying model.

First point is well worked out in many NLP libraries. Second is about machine learning, so, depending on your dataset, you can use either Weka, or MLlib.

$\endgroup$
  • $\begingroup$ Original Poster used the word "classify" but "cluster" is a more accurate description of his problem because he has no a priori definitions of categories. Therefore, this is not necessarily a supervised learning problem. $\endgroup$ – MrMeritology Sep 8 '14 at 2:28
  • $\begingroup$ @MrMeritology: hmm, from context I would say that author is just not sure about concrete classes he's going to use, but still wants classification, not clustering. Anyway, he's the only person who knows the truth :) $\endgroup$ – ffriend Sep 8 '14 at 5:31
  • $\begingroup$ Maybe i was not clear at the point. The categories are going to be selected in advice, so it is rather classification than clustering problem. The idea of creating a complex features vector seems to be quite reasonable - especially, that there are some particular tags, that are most likely probably to quickly classify some of samples. I'm not sure if SVM are going to fit the problem, as I predict high nonlinearities, but decision trees and Bayes seem to be applicable. I'm starting also to think about application of a hybrid algorithm (SVM based decision trees). $\endgroup$ – Grzegorz E. Sep 8 '14 at 5:46
  • $\begingroup$ @GrzegorzE. -- If your categories are defined in advance, then please list these three categories in your question. In my opinion, you are too focused on ML algorithms and not enough on the nature of your problem and the nature of your data. For example, you predict "nonlinearies" in features for web sites of unknown structure. Why? Also, you are mixing tags with web page text with who-knows-what-else, and they have different semantic significance. $\endgroup$ – MrMeritology Sep 8 '14 at 6:07
  • $\begingroup$ @GrzegorzE. -- I strongly suggest that your classification method should be primarily driven by the nature of your a priori categories and the nature of the data. There are an infinite number of ways to categorize arbitrary web sites into 3 categories. Each way of categorizing will suggest salient features in the data or salient patterns. There's no substitute for manual analysis of individual data elements (web pages) and their context. $\endgroup$ – MrMeritology Sep 8 '14 at 6:17
5
$\begingroup$

Topic Modeling would be a very appropriate method for your problem. Topic Models are a form of unsupervised learning/discovery, where a specified (or discovered) number of topics are defined by a list of words that have a high probability of appearing together. In a separate step, you can label each topic using subject matter experts, but for your purposes this isn't necessary since you are only interested in getting to three clusters.

You treat each document as a bag of words, and pre-process to remove stop words, etc. With the simplest methods, you pre-specify the number of topics. In your case, you could either specify "3", which is your fixed limit on categories, or pick a larger number of topics (between 10 and 100), and then in a separate step, form three clusters for documents with common emphasis on topics. K-means or other clustering methods could be used. (I'd recommend the latter approach)

You don't need to code topic modeling software from scratch. Here's a web page with many resources, including software libraries/packages.

None are in Java, but there are ways to run C++ and Python under Java.

$\endgroup$
4
$\begingroup$

Here are a couple of really great open source software packages for text classification that should help get you started:

  • MALLET is a CPL-licensed Java-based machine learning toolkit built by UMass for working with text data. It includes implementations of several classification algorithms (e.g., naïve Bayes, maximum entropy, decision trees).
  • The Stanford Classifier from the Stanford NLP Group is a GPL-licensed Java implementation of a maximum entropy classifier designed to work with text data.
$\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.