Flat clustering in information retrieval

flat clustering and hierarchical clustering and flat vs. hierarchical clustering
WilliamsMcmahon Profile Pic
WilliamsMcmahon,United States,Professional
Published Date:20-07-2017
Your Website URL(Optional)
Introduction to Information Retrieval Introduction to Information Retrieval : Flat Clustering 1Introduction to Information Retrieval MI example for poultry/ EXPORT in Reuters 4 4Introduction to Information Retrieval Linear classifiers  Linear classifiers compute a linear combination or weighted sum of the feature values.  Classification decision:  Geometrically, the equation defines a line (2D), a plane (3D) or a hyperplane (higher dimensionalities).  Assumption: The classes are linearly separable.  Methods for finding a linear separator: Perceptron, Rocchio, Naive Bayes, linear support vector machines, many others 5 5Introduction to Information Retrieval A linear classifier in 1D  A linear classifier in 1D is a point described by the equation w d = θ 1 1  The point at θ/w 1  Points (d ) with w d ≥ 1 1 1 are in the class c.  Points (d ) with w d θ 1 1 1 are in the complement class 6 6Introduction to Information Retrieval A linear classifier in 2D  A linear classifier in 2D is a line described by the equation w d +w d = θ 1 1 2 2  Example for a 2D linear classifier  Points (d d ) with w d + 1 2 1 1 w d ≥ θ are in the class c. 2 2  Points (d d ) with w d + 1 2 1 1 w d θ are in the 2 2 complement class 7 7Introduction to Information Retrieval A linear classifier in 3D  A linear classifier in 3D is a plane described by the equation w1d1 + w2d2 + w3d3 = θ  Example for a 3D linear classifier  Points (d1 d2 d3) with w1d1 + w2d2 + w3d3 ≥ θ are in the class c.  Points (d1 d2 d3) with w1d1 + w2d2 + w3d3 θ are in the complement class 8 8Introduction to Information Retrieval Rocchio as a linear classifier  Rocchio is a linear classifier defined by:  where is the normal vector and 9 9Introduction to Information Retrieval Naive Bayes as a linear classifier Naive Bayes is a linear classifier (in log space) defined by: where , d = number of occurrences of t i i in d, and . Here, the index i , 1 ≤ i ≤ M, refers to terms of the vocabulary (not to positions in d as k did in our original definition of Naive Bayes) 10 10Introduction to Information Retrieval kNN is not a linear classifier  The decision boundaries between classes are piecewise linear . . .  . . . but they are in general not linear classifiers that can be described as 11 11Introduction to Information Retrieval Take-away today  What is clustering?  Applications of clustering in information retrieval  K-means algorithm  Evaluation of clustering  How many clusters? 12 12Introduction to Information Retrieval Clustering: Definition  (Document) clustering is the process of grouping a set of documents into clusters of similar documents.  Documents within a cluster should be similar.  Documents from different clusters should be dissimilar.  Clustering is the most common form of unsupervised learning.  Unsupervised = there are no labeled or annotated data. 14 14Introduction to Information Retrieval Data set with clear cluster structure Propose algorithm for finding the cluster structure in this example 15 15Introduction to Information Retrieval Classification vs. Clustering  Classification: supervised learning  Clustering: unsupervised learning  Classification: Classes are human-defined and part of the input to the learning algorithm.  Clustering: Clusters are inferred from the data without human input.  However, there are many ways of influencing the outcome of clustering: number of clusters, similarity measure, representation of documents, . . . 16 16Introduction to Information Retrieval The cluster hypothesis Cluster hypothesis. Documents in the same cluster behave similarly with respect to relevance to information needs. All applications of clustering in IR are based (directly or indirectly) on the cluster hypothesis. Van Rijsbergen’s original wording: “closely associated documents tend to be relevant to the same requests”. 18 18Introduction to Information Retrieval Applications of clustering in IR Application What is Benefit clustered? Search result clustering search more effective results information presentation to user Scatter-Gather (subsets alternative user of) collection interface: “search without typing” Collection clustering collection effective information presentation for exploratory browsing Cluster-based retrieval collection higher efficiency: faster search 19 19Introduction to Information Retrieval Search result clustering for better navigation 20 20Introduction to Information Retrieval Navigational hierarchies: Manual vs. automatic creation  Note: Yahoo/MESH are not examples of clustering.  But they are well known examples for using a global hierarchy for navigation.  Some examples for global navigation/exploration based on clustering:  Cartia  Themescapes  Google News 25 25Introduction to Information Retrieval Clustering for improving recall  To improve search recall:  Cluster docs in collection a priori  When a query matches a doc d, also return other docs in the cluster containing d  Hope: if we do this: the query “car” will also return docs containing “automobile”  Because the clustering algorithm groups together docs containing “car” with those containing “automobile”.  Both types of documents contain words like “parts”, “dealer”, “mercedes”, “road trip”. 29 29Introduction to Information Retrieval Data set with clear cluster structure Propose algorithm for finding the cluster structure in this example 30 30Introduction to Information Retrieval Desiderata for clustering  General goal: put related docs in the same cluster, put unrelated docs in different clusters.  How do we formalize this?  The number of clusters should be appropriate for the data set we are clustering.  Initially, we will assume the number of clusters K is given.  Later: Semiautomatic methods for determining K  Secondary goals in clustering  Avoid very small and very large clusters  Define clusters that are easy to explain to the user  Many others . . . 31 31