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

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.

All Carrot² applications require Java Runtime Environment version 1.5.0 or higher (1.6.0 recommended). The Carrot² Document Clustering Workbench is distributed for Windows, Linux 32-bit and 64-bit versions and Mac OS x86. All other Carrot² applications will run on any platform supporting Java Runtime Environment version 1.5.0 or higher.

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

4.2.3 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.4 for an example. Provide a path to your style sheet in the XSLT Stylesheet field, which is an optional field. You can show optional fields by clicking the button on the Search view toolbar (Figure 4.2).

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.2 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.5 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. Click the button on the view's toolbar (Figure 4.5) to show optional attributes.

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

3. 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.5 Carrot² Document Clustering Workbench Lucene search view

4.2.6 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. Click the button on the view's toolbar (Figure 4.6) to show optional attributes.

2. Provide the URL at which your Solr instance is available in the Service URL field.

3. 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. Please see Section 7.1 for more details.

Figure 4.6 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. The algorithms differ in terms of the main clustering principle and hence have different quality and performance characteristics. This section describes briefly the two 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 Other Topics group.

Table 5.1 compares the characteristics of Lingo and STC 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
Well-formed longer labels required
Highlighting of small (outlier) clusters required
High clustering performance or large document set processing required

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

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.

Stop words are the common meaningless words, such as the, to, for in English, that should be ignored while clustering. The Lingo algorithm, for example, will not create clusters whose labels start or end in a stop word.

To fine-tune the stop words list you can use the Carrot² Document Clustering Workbench in the following way:

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.

The procedure for tuning stop labels and transferring them to other Carrot² applications is similar to stop word tuning. The difference is that this time you need to edit the stoplabels.* files. 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.

(?i)new
(?i)information
(?i)information (about|on).*
(?i)(index|list) of.*

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. Similarly, the stop label in the second line removes labels consisting of the word information. The stop label in the third line removes labels that start in information about or information on, and the stop label in the fourth line removes labels that start with index of or list of.

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:

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-yahoo-boss.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.

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

As of version 1.4 of Apache Solr, Carrot² clustering can be performed directly within Solr by means of the Carrot² Clustering Component

To build Carrot² applications from source code, you will need Java Softwade Development Kit (Java SDK) version 1.6 or higher and Apache Ant version 1.7.1 or higher. You can chcek out the latest Carrot² source code from the following SVN location:

https://carrot2.svn.sourceforge.net/svnroot/carrot2/trunk

You can use curl to post requests to the Carrot² Document Clustering Server Figure 7.3 shows how to use curl to query an external document source and cluster the results using the DCS. Figure 7.4 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: MicrosoftLiveDocumentSource and OpenSearchDocumentSource.

To speed up clustering performed by the Lingo algorithm, you can configure Carrot² to use a native platform-specific matrix computation library. Depending on the platform, you may see up to a 400% speed-up compared to the Java-only mode.

To enable native matrix computations for Carrot²:

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">
    <title>
      <phrase>com</phrase>
    </title>
    <group id="1" size="2">
      <title>
        <phrase>amazon.com</phrase>
      </title>
      <document refid="43"/>
      <document refid="77"/>
    </group>
    <group id="2" size="2">
      <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">
    <title>
      <phrase>org</phrase>
    </title>
    <group id="9" size="2">
      <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:

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.

Open Search document source retrieves search results from search engines supporting the OpenSearch standard.