Carrot²

Carrot² Document Clustering Workbench is a standalone GUI application you can use to experiment with Carrot² clustering on data from common search engines or your own data.

You can use Carrot² Document Clustering Workbench to:

Carrot² Document Clustering Workbench features include:

Figure 3.1 Carrot² Document Clustering Workbench screenshot

The Carrot² Java API package contains Carrot² JAR files along with all dependencies, JavaDoc API reference and Java code examples. You can use this package to integrate Carrot² clustering into your Java software. Please see Section 4.3.1 and Section 4.3.3 for instructions.

The Carrot² C# API package contains all DLL libraries required to run Carrot², C# API reference and code examples. You can use this package to integrate Carrot² clustering into your C# / .NET software. Please see Section 4.3.5 for instructions.

Carrot² Document Clustering Server (DCS) exposes Carrot² clustering as a REST service. It can cluster documents from an external source (e.g. a search engine) or documents provided directly as an XML stream and returns results in XML or JSON formats.

You can use Carrot² Document Clustering Server to:

Carrot² Document Clustering Server features include:

Figure 3.2 Carrot² Document Clustering Server quick start screen

dcs -port 9090

Carrot² Web Application exposes Carrot² clustering as a web application for end users. It allows users to browse clusters using a conventional tree view, but also in an attractive visualization.

Carrot² Document Clustering Server features include:

Figure 3.3 Carrot² Web Application results screen

Carrot² Command Line Interface (CLI) is a set of applications that allow invoking Carrot² clustering from the command line. Currently, the only available CLI application is Carrot² Batch Processor, which performs Carrot² clustering on one or more files in the Carrot² XML format and saves the results as XML or JSON. Apart from clustering large number of documents sets at one time, you can use the Carrot² Batch Processor to integrate Carrot² with your non-Java applications.

Carrot² clustering can be performed directly within Solr by means of the Solr Clustering Component contrib extension.

A whitepaper discussing several integration strategies between Solr and Carrot² clustering algorithms can be found at a separate GitHub repository.

Carrot² search results clustering can be performed directly in ElasticSearch by installing a dedicated elasticsearch-carrot2 plugin. Generic plugin's installation instructions are described in detail at the plugin's GitHub web site. The API's documentation is dynamically rendered once installed (see installation instructions).

All Carrot² applications require Java Runtime Environment version 1.8 or later. The Carrot² Document Clustering Workbench is distributed for Windows, Linux and MacOSX.

The Carrot² C# API package requires the .NET Framework version 3.5 or later; it does not require a Java Runtime Environment.

This section shows how to apply Carrot² clustering on documents from various sources.

4.2.2 Clustering documents from XML files

To try Carrot² clustering on documents or search results stored in a single XML file you can use the Carrot² Document Clustering Workbench.

1. In the Search view of Carrot² Document Clustering Workbench, choose XML source.

2. Set path to your XML file in the XML Resource field.

3. (Optional) If your file is not in Carrot² format, create an XSLT style sheet that transforms your data into Carrot² format, see Section 4.2.3 for an example. Provide a path to your style sheet in the XSLT Stylesheet field in the Medium section.

4. If you know the query that generated the documents in your XML file, you can provide it in the Query field, which may improve the clustering results. Press the Process button to see the results.

Figure 4.1 Carrot² Document Clustering Workbench XML search view

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0"
     xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
     xmlns:media="http://search.yahoo.com/mrss">

  <xsl:output indent="yes" omit-xml-declaration="no"
       media-type="application/xml" encoding="UTF-8" />

  <xsl:template match="/">
    <searchresult>
      <xsl:apply-templates select="/rss/channel/item" />
    </searchresult>
  </xsl:template>

  <xsl:template match="item">
    <document>
      <title><xsl:value-of select="title" /></title>
      <snippet>
        <xsl:value-of select="description" />
      </snippet>
      <url><xsl:value-of select="link" /></url>
      <xsl:if test="media:thumbnail">
        <field key="thumbnail-url">
           <value type="java.lang.String"
                  value="{media:thumbnail/@url}"/>
        </field>
      </xsl:if>
    </document>
  </xsl:template>
</xsl:stylesheet>

<field key="key">
  <value><wrapper class="org.carrot2.util.simplexml.ListSimpleXmlWrapper">
    <list>
      <value value="value1"/>
      <value value="value2"/>
    </list>
  </wrapper></value>
</field>

4.2.4 Clustering documents from a Lucene index

To try Carrot² clustering on documents from a local Lucene index, you can use Carrot² Document Clustering Workbench:

1. In the Search view of Carrot² Document Clustering Workbench, choose Lucene source.

2. Choose the path to your Lucene index in the Index directory field.

3. In the Medium section, choose fields from your Lucene index in at least one of Document title field and Document content field combo boxes.

4. Type a query and press the Process button to see the results.

Figure 4.4 Carrot² Document Clustering Workbench Lucene search view

4.2.5 Clustering documents from a Solr index

To try Carrot² clustering on documents from an instance of Apache Solr, you can use Carrot² Document Clustering Workbench:

1. In the Search view of Carrot² Document Clustering Workbench, choose Solr source.

2. In the Advanced section, provide the URL at which your Solr instance is available in the Service URL field.

3. In the Medium section, provide fields that should be used as document title, content and URL (optional) in the Title field name, Summary field name and URL field name field, respectively.

4. Type a query and press the Process button to see the results.

Tip

Carrot² clustering can also be performed directly within Solr by means of Solr's Carrot² Clustering Component.

Figure 4.5 Carrot² Document Clustering Workbench Solr search view

The quality of clusters and their labels largely depends on the characteristics of documents provided on the input. Although there is no general rule for optimum document content, below are some tips worth considering.

Let us once again stress that there are no definite generic guidelines for the best content for clustering, it is always worth experimenting with different combinations. You can also describe your specific application on Carrot² mailing list and ask for advice.

Currently, Carrot² offers two specialized search results clustering algorithms: Lingo and STC as well as an implementation of the bisecting k-means clustering. The algorithms differ in terms of the main clustering principle and hence have different quality and performance characteristics. This section describes briefly the algorithms and provides some recommendations for choosing the most suitable one.

The key characteristic of the Lingo algorithm is that it reverses the traditional clustering pipeline: it first identifies cluster labels and only then assigns documents to the labels to form final clusters. To find the labels, Lingo builds a term-document matrix for all input documents and decomposes the matrix to obtain a number of base vectors that well approximate the matrix in a low-dimensional space. Each such vector gives rise to one cluster label. To complete the clustering process, each label is assigned documents that contain the label's words.

The key data structure used in the Suffix Tree Clustering (STC) algorithm is a Generalized Suffix Tree (GST) built for all input documents. The algorithm traverses the GST to identify words and phrases that occurred more than once in the input documents. Each such word or phrase gives rise to one base cluster. The last stage of the clustering process is merging base clusters to form the final clusters.

The two algorithms have two features in common. They both create overlapping clusterings, in which one document can be assigned to more than one cluster. Also, in case of both algorithms a certain number of documents can remain unclustered and fall in the .

Bisecting k-means is a generic clustering algorithm that can also be applied to clustering textual data. As opposed to Lingo and STC, bisecting k-means creates non-overlapping clusters and does not produce the Other Topics group. Its current limitation is that it labels clusters using individual words and not all cluster's documents may correspond to the words included in the cluster label.

Table 5.1 compares the characteristics of Lingo, STC and k-means under their default settings and Figure 5.1 shows clusters generated by Lingo and STC for data mining search results.

Figure 5.1 Lingo and STC clusters for the 'data mining' search results

It is difficult to give one clear recommendation as to which algorithm is "better". Many people feel Lingo delivers better-formed and more diverse clusters at the cost of lower performance and scalability. The ultimate judgment, however, should based on the evaluation with the specific document collection. Table 5.2 highlights the scenarios for which the algorithms are best suited.

Table 5.2 Optimum usage scenarios for Lingo and STC

Feature	Use Lingo	Use STC	Use k-means
Well-formed longer labels required
Highlighting of small (outlier) clusters required
High clustering performance or large document set processing required
Need non-overlapping clusters

The bottom line is: use Lingo, unless you need high-performance clustering of document sets larger than 1000 documents or need non-overlapping clusters.

The best tool for experimenting and tuning Carrot² clustering is the Carrot² Document Clustering Workbench. Figure 5.2 shows the main components involved in the tuning process.

Figure 5.2 Tuning clustering in Carrot² Document Clustering Workbench

	The results editor presents documents and clusters. Changes made in the Attributes view will affect the currently active results editor.
	The Attributes view, where you can see and change values of clustering algorithm's attributes.
	The Attribute Info view, which shows documentation for specific attributes. Hold the mouse pointer over an attribute's label to see its documentation.

Opening the Attributes view.  By default, the Attributes view shows on the right hand side of the Carrot² Document Clustering Workbench. You can open the view at any time by choosing Window > Show view > Attributes.

Setting modified attributes as default for new queries.  If you modified a number of attributes for an algorithm and would like to use the modified values for new queries, choose the Set as defaults for new queries from the Attributes view's context menu (Figure 5.3).

Figure 5.3 Attributes view's context menu

Restoring default attribute values.  To reset the attributes to their default values, choose the Reset to defaults option from the Attributes view's context menu (Figure 5.3). To bring the attributes back to their factory defaults, choose the Reset to factory defaults option.

Loading and saving attribute values to XML.  To load or save attribute values to an XML file, use the Open and Save as... options available under the icon on the Attributes view's menu bar.

Accessing attribute documentation.  To see the documentation for a specific attribute, hold the mouse pointer over the attribute's label and its documentation will show in the Attribute Info view.

Please see Section 6.3 and Section 6.2 of Chapter 6 for details.

Please see Section 6.4 and Section 6.2 of Chapter 6 for details.

The Other Topics cluster contains documents that do not belong to any other cluster generated by the algorithm. Depending on the input documents, the size of this cluster may vary from a few to tens of documents.

By tuning parameters of the clustering algorithm, you can reduce the number of unclustered documents, however bringing the number down to 0 is unachievable in most cases. Please note that minimizing the Other Topics cluster size is usually achieved by forcing the algorithm to create more clusters, which may degrade the perceived clustering quality.

Further performance tuning tips are specific for each clustering algorithm.

You can use the Carrot² Document Clustering Workbench to run simple performance benchmarks of Carrot². The benchmarks repeatedly cluster the content of the currently opened editor and report the average clustering time. You can use the benchmarking results to measure the impact of different algorithm's attribute settings on its performance and estimate the the maximum number of clustering requests that the algorithm can process per second.

To perform a performance benchmark:

The user-define Carrot² lexical resources are placed at the following application-specific locations:

The easiest way to tune the lexical resources is to use the Carrot² Document Clustering Workbench which will allow observing the effect of the changes in real time. To tune the lexical resources in Carrot² Document Clustering Workbench:

Stop word files are UTF-8 encoded plain text files with a single word in each line. Lines starting with # are omitted (considered to be comments). Files must follow a naming convention and be named stopwords.lang, where lang is a two-letter language suffix defined in LanguageCode class.

# stop word file for English
ain't
thanks
need
needs
needed
vs
hit

The Lingo clustering algorithm, in addition to stop words editing, offers more precise control over cluster labels by means of "stop label" regular expressions. If a cluster's label matches one of the stop labels, the label will not appear on the list of clusters produced by Lingo.

Label filtering files are UTF-8 encoded plain text files with a single regular expression pattern in each line. Lines starting with # are omitted (considered to be comments). Files must follow a naming convention and be named stoplabels.lang, where lang is a two-letter language suffix defined in LanguageCode class.

Each line of a stop labels file corresponds to one stop label and is a Java regular expression. Please note that in order to be removed, a label as a whole must match at least one of the stop label expressions. A number of example stop label expressions are shown below.

# stop label patterns for English
(?i)new
(?i)information (about|on).*
(?i)(index|list) of.*
(?i)(information|list|skip|join|cheap|access(es)?|corp(oration)?s?)
(?i).*(page|part|copyright) \d+.*
(?i)(official|offer(ing)?s?|lists|uses?).*
(?i).*(known|information|offer(ing)?s?|a range)

All stop labels shown above start with the (?i) prefix, which enables case-insensitive matching for them. The stop label in the first line suppresses labels consisting solely of the word new. The stop label in the second line removes labels that start in information about or information on, and the stop label in the third line removes labels that start with index of or list of.

Key concepts in customizing and tuning Carrot² applications are component suites and component attributes described in the following sections.

<component-suite>
  <sources>
    <source id="lucene"
        component-class="org.carrot2.source.lucene.LuceneDocumentSource"
        attribute-sets-resource="lucene.attributes.xml">
      <label>Lucene</label>
      <title>Apache Lucene</title>
      <mnemonic>L</mnemonic>
      <description>
        Apache Lucene index (local index access).
      </description>
      <icon-path>icons/lucene.png</icon-path>
      <example-queries>
        <example-query>data mining</example-query>
        <example-query>london</example-query>
        <example-query>clustering</example-query>
      </example-queries>
    </source>
  </sources>
  
  <algorithms>
    <algorithm id="lingo" 
        component-class="org.carrot2.clustering.lingo.LingoClusteringAlgorithm" 
        attribute-sets-resource="lingo.attributes.xml">
      <label>Lingo</label>
      <title>Lingo Clustering</title>
    </algorithm>
  </algorithms>
  
  <include suite="source-bing.xml" />
  <include suite="algorithm-stc.xml" />
</component-suite>

<attribute-sets>
  <attribute-set id="lucene">
    <value-set>
      <label>Lucene</label>
      <attribute key="LuceneDocumentSource.directory">
        <value>
           <wrapper class="org.carrot2.source.lucene.FSDirectoryWrapper">
              <indexPath>/path/to/lucene/index/directory</indexPath>
           </wrapper>
        </value>
      </attribute>
      <attribute key="org.carrot2.source.lucene.SimpleFieldMapper.contentField">
        <value type="java.lang.String" value="summary" />
      </attribute>
      <attribute key="org.carrot2.source.lucene.SimpleFieldMapper.titleField">
        <value type="java.lang.String" value="title" />
      </attribute>
      <attribute key="org.carrot2.source.lucene.SimpleFieldMapper.urlField">
        <value type="java.lang.String" value="url" />
      </attribute>
    </value-set>
  </attribute-set>
</attribute-sets>

To add a document source tab to the Carrot² Web Application:

To add a document source tab to the Carrot² Document Clustering Server:

To run the Carrot² Web Application with custom attributes of the Lingo clustering algorithm:

You can use the same procedure to customize other algorithms, e.g. STC.

To run the Carrot² Document Clustering Server with custom attributes of the Lingo clustering algorithm:

You can use the same procedure to customize other algorithms, e.g. STC.

To run the Carrot² Command Line Interface with custom attributes of the Lingo clustering algorithm:

You can use the same procedure to customize other algorithms, e.g. STC.

The Java API distribution package contains examples showing how to customize attributes of the clustering algorithms. Please see the org.carrot2.examples.clustering.UsingAttributes class or the JavaDoc overview page.

Not yet covered, please contact us if you need this section.

To build Carrot² applications from source code, you will need Java Software Development Kit (Java SDK) version 1.8 or higher and Apache Ant version 1.9.3 or higher. You can chcek out the latest Carrot² source code using git:

git clone git://github.com/carrot2/carrot2.git

You can use curl to post requests to the Carrot² Document Clustering Server Figure 8.2 shows how to use curl to query an external document source and cluster the results using the DCS. Figure 8.3 shows how to cluster documents from an XML file in Carrot² format using the DCS. Please see the examples/curl directory of the Carrot² Document Clustering Server distribution archive for more curl DCS invocation examples.

curl http://localhost/dcs/rest \
     -F "dcs.source=etools" \
     -F "query=test" \
     -o result.xml

curl http://localhost/dcs/rest \
     -F "dcs.c2stream=@documents-in-carrot2-format.xml" \
     -o result.xml

If your server or development machine connects to HTTP servers via a HTTP proxy, you can most of Carrot² document source implementations to take this information into account by defining the following global system properties:

Two sources that currently do not support the above properties are: Bing7DocumentSource and OpenSearchDocumentSource.

If your document source initiates HTTP connections to a server protected with BASIC or DIGEST HTTP authentication, you will have to pass the username and password to the application so that such connections can be established. Define the following global system properties (they are picked up once, when the Controller is created):

Note that, in general, it's better not to have any HTTP authentication at all since it's a very weak form of protection anyway and only increases network traffic (two HTTP requests may have to be made in order to fetch the remote resource).

This section provides a very brief overview of Carrot² architecture. If you would like us to cover some specific topic in more detail, please let us know on the mailing list.

This section shows examples of Carrot² input and output XML formats, used consistently by all Carrot² applications, including Carrot² Document Clustering Workbench, Carrot² Document Clustering Server and Carrot² Web Application.

<?xml version="1.0" encoding="UTF-8"?>
<searchresult>
  <query>Globe</query>
  <document id="0">
    <title>default</title>
    <url>http://www.globe.com.ph/</url>
    <snippet>
      Provides mobile communications (GSM) including 
      GenTXT, handyphones, wireline services, an
      broadband Internet services.
    </snippet>
  </document>
  <document id="1">
    <title>Skate Shoes by Globe | Time For Change</title>
    <url>http://www.globeshoes.com/</url>
    <snippet>
      Skaters, surfers, and showboarders
      designing in their own style.
    </snippet>
  </document>

  ...

</searchresult>

<?xml version="1.0" encoding="UTF-8"?>
<searchresult>
  <query>Globe</query>
  <document id="0">
    <title>default</title>
    <url>http://www.globe.com.ph/</url>
    <snippet>
      Provides mobile communications (GSM) including 
      GenTXT, handyphones, wireline services, an
      broadband Internet services.
    </snippet>
  </document>
  <document id="1">
    <title>Skate Shoes by Globe | Time For Change</title>
    <url>http://www.globeshoes.com/</url>
    <snippet>
      Skaters, surfers, and showboarders
      designing in their own style.
    </snippet>
  </document>

  ...

  <group id="0" size="60" score="1.0">
    <title>
      <phrase>com</phrase>
    </title>
    <group id="1" size="2" score="1.0">
      <title>
        <phrase>amazon.com</phrase>
      </title>
      <document refid="43"/>
      <document refid="77"/>
    </group>
    <group id="2" size="2" score="0.8">
      <title>
        <phrase>boston.com</phrase>
      </title>
      <document refid="4"/>
      <document refid="7"/>
    </group>
    
    ...
    
    <group id="7" size="48">
      <title>
        <phrase>Other Sites</phrase>
      </title>
      <attribute key="other-topics">
        <value type="java.lang.Boolean" value="true"/>
      </attribute>
      <document refid="1"/>
      <document refid="2"/>
      ...
    </group>
  </group>
  <group id="8" size="12" score="0.72">
    <title>
      <phrase>org</phrase>
    </title>
    <group id="9" size="2" score="1.0">
      <title>
        <phrase>en.wikipedia.org</phrase>
      </title>
      <document refid="9"/>
      <document refid="14"/>
      ...
    </group>
  </group>
  ...


</searchresult>

This section shows examples of Carrot² output JSON format, used consistently by all Carrot² applications, including Carrot² Document Clustering Server and Carrot² Java API.

{
  "clusters": [
    {
      "attributes": {
        "score": 1.0
      }, 
      "documents": [
        0, 
        2
      ], 
      "id": 0, 
      "phrases": [
        "Cluster 1"
      ], 
      "score": 1.0, 
      "size": 2
    }, 
    {
      "attributes": {
        "score": 0.63
      }, 
      "clusters": [
        {
          "attributes": {
            "score": 0.3
          }, 
          "documents": [
            1
          ], 
          "id": 2, 
          "phrases": [
            "Cluster 2.1"
          ], 
          "score": 0.3, 
          "size": 1
        }, 
        {
          "attributes": {
            "score": 0.15
          }, 
          "documents": [
            2
          ], 
          "id": 3, 
          "phrases": [
            "Cluster 2.2"
          ], 
          "score": 0.15, 
          "size": 1
        }
      ], 
      "documents": [
        0
      ], 
      "id": 1, 
      "phrases": [
        "Cluster 2"
      ], 
      "score": 0.63, 
      "size": 3
    }
  ], 
  "documents": [
    {
      "id": 0, 
      "snippet": "Document 1 Content.", 
      "title": "Document 1 Title", 
      "url": "http://document.url/1"
    }, 
    {
      "id": 1, 
      "snippet": "Document 2 Content.", 
      "title": "Document 2 Title", 
      "url": "http://document.url/2"
    }, 
    {
      "id": 2, 
      "snippet": "Document 3 Content.", 
      "title": "Document 3 Title", 
      "url": "http://document.url/3"
    }
  ], 
  "query": "query (optional)"
}

Each Carrot² release should be performed according to the following procedure:

Carrot² uses version identifiers consisting of three, dot-separated numbers: product-line.major.minor. This scheme is modelled after Maven's POM versions and has the following interpretation:

The git repository is organized so that the master branch tracks the development of the next major revision. Bugfix branches track minor revisions of already shipped versions. A tag is created for each shipped version. Branch and tag names follow the naming conventions below.

This a very quick quality assurance check list to run through before stable releases. This list also serves as some guide line for further automation of acceptance tests.