Cluster hypothesis

In machine learning and information retrieval, the cluster hypothesis is an assumption about the nature of the data handled in those fields, which takes various forms. In information retrieval, it states that documents that are clustered together "behave similarly with respect to relevance to information needs". In terms of classification, it states that if points are in the same cluster, they are likely to be of the same class. There may be multiple clusters forming a single class.

Information retrieval

The cluster hypothesis was formulated first by van Rijsbergen: "closely associated documents
tend to be relevant to the same requests". Thus, theoretically, a search engine could try to locate only the appropriate cluster for a query, and then allow users to browse through this cluster. Although experiments showed that the cluster hypothesis as such holds, exploiting it for retrieval did not lead to satisfying results.

Machine learning

The cluster assumption is assumed in many machine learning algorithms such as the k-nearest neighbor classification algorithm and the k-means clustering algorithm. As the word "likely" appears in the definition, there is no clear border differentiating whether the assumption does hold or does not hold. In contrast the amount of adherence of data to this assumption can be quantitatively measured.

Properties

The cluster assumption is equivalent to the Low density separation assumption which states that the decision boundary should lie on a low-density region. To prove this, suppose the decision boundary crosses one of the clusters. Then this cluster will contain points from two different classes, therefore it is violated on this cluster.