Text Processing

MODULE-04
COB4 : To compare the relevance of query languages for text and multimedia data.
CO4 : Evaluate text processing techniques and operations in the information retrieval
system.
Introduction
• The document
• denotes a single unit of information has a syntax and structure.
• has a semantics, specified by the author.
• may have a presentation style.
• given by its syntax and structure.
• related to a specific application.
• specifies how to display or print document.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Syntax

• The document syntax

• expresses structure, presentation style, semantics.
• one or more of elements might be implicit or given together.
• structural element (e.g., a section) can have fixed formatting style.
Module-04(Text Processing) - INFORMATION RETRIEVAL
SYSTEM (ITDO7024)
Document Syntax
• The document syntax can be
• implicit in its content
• expressed in a simple declarative language
• expressed in a programming language
• the language syntax might be proprietary and specific
• open and generic languages are more flexible
• Text can also be written in natural language
• hard to process using a computer
• Current trend: use document languages that
• provide information on structure, format, and semantics
• are readable by humans and computers.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Style
• Defines how a document is visualized or
printed.
• can be embedded in the document: TeX
and RTF.
• can be complemented by macros: LaTeX.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Queries in search engines
• Can be considered as short pieces of text.
• Differ from normal text.
• Understanding them is very important.
• Semantics often ambiguous due to polysemy.
• Not simple to infer user intent behind a query.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Metadata
• Metadata is information on the organization of the data, the
various data domains, and their relationship.
• Metadata is data about the data.
• In a database, names of relations and attributes constitute metadata.
• Metadata is associated with most documents and text collections.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Metadata
• Descriptive Metadata:
• Common forms of metadata for documents.
• author of the text
• date of publication
• source of the publication
• document length
• Dublin Core Metadata Element Set proposes 15 fields to describe a
document.
• Marchionini refers to this type of information as Descriptive Metadata.
• Descriptive metadata are external to the meaning of the document and pertain
more to how it was created.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Metadata
• Semantic Metadata:
• Characterizes the subject matter within the document contents.
• Is associated with a wide number of documents.
• Its availability is increasing.
• An important metadata format is MARC(Machine Readable Cataloging
Record)
• most used format for library records.
• includes fields for distinct attributes of a bibliographic entry such as title, author,
publication venue.
• In the U.S.A., a particular version of MARC is used: USMARC.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Metadata
• Metadata in Web Documents:
• The increase in Web data has led to many initiatives to add metadata
information to Web pages for various purposes such as
• Cataloging and content rating
• Intellectual property rights and digital signatures
• Applications to electronic commerce
• RDF (Resource Description Framework)
• New standard for Web metadata
• Allows describing Web resources to facilitate automated processing.
• RDF does not assume any particular application or semantic domain.
• It consists of a description of nodes and attached attribute/value pairs

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Metadata
• Metadata in Web Documents:
• RDF (Resource Description Framework)
• It consists of a description of nodes and attached attribute/value pairs
• Nodes can be any Web resource, that is, any Uniform Resource Identifier (URI)
including Uniform Resource Locators (URLs)
• Attributes are properties of nodes and their values are text strings or other nodes
(Web resources or metadata instances)

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Formats
• Text:
• With the advent of the computer, it became necessary to represent code
characters in binary digits, which is done through coding schemes.
• EBCDIC (7 bits), ASCII (8 bits) and UNICODE (16 bits)
• All these coding schemes are based on characters.
• An IR system should be able to retrieve information from many text
formats (doc, pdf, html, txt)
• IR systems have filters to handle most popular documents
• But, good filters might not be possible with proprietary formats.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Formats
• Text:
• Other text formats:
• Rich Text Format (RTF): for document interchange.
• Portable Document Format (PDF): for printing and displaying.
• Postscript: for printing and displaying.
• Other interchange formats are used to encode electronic mail
• Multipurpose Internet Mail Exchange (MIME): for encoding email.
• Compress (Unix), ARJ (PCs): for compressing text.
• ZIP (Unix) (gzip in Unix and Winzip in Windows): for compressing text.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Multimedia Formats
• Multimedia usually stands for applications that handle different
types of digital data.
• Most common types of media: text, sound, images, and video.
• Different types of formats are necessary for storing each media.
• Most formats for multimedia can only be processed by a computer.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Multimedia Formats
• Image Formats:
• The simplest image formats are direct representations of a bit-mapped
display such as XBM, BMP or PCX.
• Images of these formats have a lot of redundancy and can be
compressed efficiently.
• Example of format that incorporates compression:
• Compuserve’s Graphic Interchange Format (GIF)
• To improve compression ratios, lossy compression was developed.
• Uncompressing a compressed image does not yield exactly the original image.
• This is done by the Joint Photographic Experts Group (JPEG) format.
• JPEG tries to eliminate parts of the image that have less impact in the human eye.
• This format is parametric, in the sense that the loss can be tuned.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Multimedia Formats
• Image Formats:
• Another common image format is the Tagged Image File Format (TIFF)
• exchange of documents between different applications and computers.
• TIFF provides for metadata, compression, and varying number of colors.
• Yet another format is Truevision Targa image file (TGA), which is
associated with video game boards.
• In 1996, a new image format was proposed for use in the Internet:
Portable Network Graphics (PNG)
• Standard de facto for images in the Web
• Further, various other image formats are associated with particular
applications ranging from fax to fingerprints.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Multimedia Formats
• Audio Formats:
• Audio must be digitalized to be stored properly.
• Most common formats for audio: AU, MIDI and WAVE
• MIDI: standard format to interchange music between electronic instruments and
computers.
• For audio libraries other formats are used such as
• RealAudio or CD formats

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Video / Movie Formats
• Main format for animations is Moving Pictures Expert Group
(MPEG):
• works by coding the changes in consecutive frames.
• profits from the temporal image redundancy that any video has includes
the audio signal associated with the video.
• specific cases for audio (MP3), video (MP4), etc.
• Other video formats are AVI, FLI and QuickTime
• AVI may include compression (CinePac).
• QuickTime, developed by Apple, also includes compression.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Graphics & Virtual Reality formats
• There are many formats for three dimensional graphics:
• Computer Graphics Metafile (CGM) and Virtual Reality Modeling Language
(VRML)
• VRML, intended to be a universal interchange format for 3D graphics
and multimedia, may be used in a variety of application areas such as
• engineering and scientific visualization
• multimedia presentations
• entertainment and educational titles
• web pages and shared virtual worlds
• VRML has become the de facto standard Modeling Language for the
Web.
Module-04(Text Processing) - INFORMATION RETRIEVAL
SYSTEM (ITDO7024)
Markup Languages
• Markup is defined as extra syntax used to describe formatting
actions, structure information, text semantics, attributes.
• Examples of Markup Languages:
• SGML: Standard Generalized Markup Language
• XML: eXtensible Markup Language
• HTML: Hyper Text Markup Language

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• SGML :
• SGML (ISO 8879) stands for Standard Generalized Markup Language, i.e.,
a meta-language for tagging text.
• It provides rules for defining a markup language based on tags.
• Includes a description of the document structure called document type definition.

• An SGML document is defined by:

• A document type definition.
• The text itself marked with tags which describe the structure.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• SGML :
• The document type definition is used to
• Describe and name the pieces that a document is composed of.
• Define how those pieces relate to each other.
• part of the definition can be specified by an SGML document type declaration
(DTD)
• Other parts, such as the semantics of elements and attributes, or
application conventions, cannot be expressed formally in SGML
• Comments can be used, however, to express them informally.
• More complete information is usually present in separate documentation.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• SGML :
• Example of a SGML DTD for electronic messages:

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• SGML :
• Example of use of previous DTD

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• SGML :
• Document description does not specify how a document is printed.
• Output specifications are often added to SGML documents, such as:
• DSSSL: Document Style Semantic Specification Language
• FOSI: Formatted Output Specification Instance
• These standards define mechanisms for associating style information with SGML
document instances.
• They allow defining that the data identified by a tag should be typeset in some
particular font.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• SGML :
• One important use of SGML is in the Text Encoding Initiative (TEI)
• Includes several USA associations related to the humanities and linguistics.
• Provides several document formats through SGML DTDs.
• Main goal is to generate guidelines for the preparation and interchange of
electronic texts for scholarly research, as well as the industry.
• one of the most used formats is TEI Lite

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HTML :
• HTML stands for HyperText Markup Language and is an instance of SGML.
• It was created in 1992 and has evolved during the last years, being 5.0
the latest version.
• Most documents on the Web are stored and transmitted in HTML
• Although there is an HTML DTD, most HTML instances do not explicitly
make reference to the DTD.
• The HTML tags follow all the SGML conventions and also include
formatting directives.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HTML :
• HTML documents can have other media embedded within them, such as
images or audios.
• HTML also has fields for metadata, which can be used for different
applications and purposes.
• If we also add programs (for example, using Javascript) inside a page
some people call it dynamic HTML.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HTML :
• Example of an HTML document

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HTML :
• How to HTML document is seen on browser

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HTML :
• Because HTML does not fix a presentation style, the Cascade Style
Sheets (CSS) were introduced in 1997.
• powerful and manageable way for authors to improve the aesthetics of HTML
pages.
• Separate information about presentation from document content
• Support (for CSS) in current browsers is still modest.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HTML :
• The evolution of HTML implies support for backward compatibility and also for
forward compatibility.
• HTML 4.0 has been specified in three flavors: strict, transitional, and frameset
• Strict HTML only worries about non-presentational markup, leaving all the displaying
information to CSS.
• Transitional HTML uses all the presentational features for pages that should be read for
old browsers that do not understand CSS.
• Frameset HTML is used when you want to partition the browser window in two or more
frames.
• HTML 4.0 includes support for style sheets, internationalization, frames, richer
tables and forms, and accessibility options for people with disabilities.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HTML :
• Typical HTML applications use a fixed small set of tags
• Makes the language specification much easier to build applications.
• Comes at the cost of severely limiting HTML in several important aspects.
• In particular, HTML does not
• Allow users to specify their own tags.
• support the specification of nested structures needed to represent database schemas.
• support the kind of language specification that allows consuming applications to
check data for structural validity on importation.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• XML:
• XML stands for the eXtensible Markup Language.
• Is a simplified subset of SGML.
• Is not a markup language, as HTML, but a meta-language, as SGML.
• Allows to have human-readable semantic markup, which is also
machine-readable.
• Makes it easier to develop and deploy new specific markup languages.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• XML:
• XML does not have many of the restrictions of HTML
• On the other hand, imposes a more rigid syntax on the markup:
• In XML, ending tags cannot be omitted.
• XML also distinguishes upper and lower case .
• All attribute values must be between quotes.
• Parsing XML without a DTD is easier.
• The tags can be obtained while the parsing is done.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• XML:
• XML allows any user to define new tags.
• Extensible Style sheet Language (XSL)
• The XML counterpart of Cascading Style Sheets (CSS).
• Syntax defined based on XML.
• Designed to transform and style highly-structured, data-rich documents written in
XML.
• For example, with XSL it would be possible to automatically extract a table of
contents from a document.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• XML:
• Extensible Linking Language (XLL)
• Another extension to XML, defined using XML.
• Defines different types of links (external and internal)
• Recent uses of XML include:
• Mathematical Markup Language (MathML).
• Synchronized Multimedia Integration Language (SMIL).
• Resource Description Format (RDF).

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• RDF (Resource Description Framework):
• Family of specifications originally designed as a metadata model
• Has become a general method for the conceptual description or
modeling of information.
• The de facto standard language of the Semantic Web.
• Similar to conceptual modeling approaches such as Entity-Relationship or
Class diagrams.
• More naturally suited to represent certain kinds of knowledge than other
traditional models.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• RDF (Resource Description Framework):
• The RDF Schema (RDFS) is an extensible knowledge representation
language.
• It provides basic elements for the description of ontologies, intended to structure
RDF resources.
• Many RDFS components are included in the more expressive language
Web Ontology Language (OWL)
• OWL is a family of knowledge representation languages for authoring ontologies,
also endorsed by the W3C.
• Ontologies defined with OWL are most commonly serialized using
RDF/XML syntax.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HyTime (Hypermedia/Time-based Structuring Language):
• An SGML architecture that specifies the generic hypermedia structure of
documents.
• Its hypermedia concepts include
• complex locating of document objects.
• Relationships (hyperlinks) between document objects.
• Numeric, measured associations between document objects.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Markup Languages
• HyTime (Hypermedia/Time-based Structuring Language):
• The HyTime architecture has three parts:
• The base linking and addressing architecture.
• The scheduling architecture (derived from the base architecture)
• The rendition architecture (which is an application of the scheduling architecture)
• HyTime does not directly specify graphical interfaces, user navigation or
user interaction.
• These aspects of document processing are rendered from the HyTime
constructs in a similar manner as style sheets in SGML documents.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Document preprocessing can be divided into five text operations:
• Lexical analysis of the text.
• Elimination of stopwords.
• Stemming of the remaining words.
• Selection of index terms or keywords.
• Construction of term categorization structures (thesaurus)

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Logical View of Documents

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Lexical Analysis of the Text :
• Process of converting stream of chars into stream of words.
• Major objective: identify words in the text
• Word separators:
• Space: most common separator.
• Numbers: inherently vague, need context for disambiguation.
• Hyphens: break up hyphenated words.
• Punctuation marks: allows distinguishing [Link] from xid in a program.
• Case of the letters: allows distinguishing Bank from bank.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Elimination of Stopwords :
• Stopwords
• Words that appear too frequently.
• Usually, not good discriminators
• Normally, filtered out as potential index terms
• Natural candidates: articles, prepositions, conjunctions
• Elimination of stopwords
• Reduces size of index by 40% or more
• At expense of reducing recall: not able to retrieve documents that contain “to be
or not to be”

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Stemming:
• User specifies query word but only a variant of it is present in a relevant
document.
• Plurals, gerund forms, and past tense suffixes
• Partially solved by the adoption of stems
• Stem
• portion of word left after removal of prefixes/suffixes
• connect: stem of connected, connecting, connection, connections
• Stemming reduces size of the index
• There is controversy about benefits of stemming for retrieval.
• Many search engines do not adopt any stemming.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Stemming:
• Stemming Strategies:
1. Affix removal: in which the most important part is suffix/prefix removal.
• The Porter algorithm is a suffix removal algorithm for English
2. Table lookup: look for the stem of a word in a table.
3. Successor variety: determine morpheme boundaries and use knowledge from
structural linguistics.
4. N-grams: Identify digrams and trigrams (term clustering)

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Keyword Selection:
• Full text representation
• All words in text used as index terms (or, keywords)
• Alternative to full text representation
• Not all words in text used as index terms.
• Case 1: use just nouns as index terms.
• Case 2: group nouns that appear nearby in text into a single indexing component
(a concept)
• Noun groups as index terms: computer science, los angeles.
• Logical view of documents as sets of non-elementary index terms.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Thesauri :
• Thesaurus
• Word has Greek and Latin origins
• Used as reference to a treasury of words
• In its simplest form, this treasury consists of :
• Precompiled list of important words in a knowledge domain.
• For each word in this list, a set of related words derived from a synonymy relationship.
• The main purposes of a thesaurus are to provide:
• A standard vocabulary for indexing and searching.
• A means to find terms for proper query formulation.
• Classified hierarchies to allow broadening/narrowing queries

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Thesauri :
• Thesaurus
• Motivation for building a thesaurus: A controlled vocabulary for indexing and
searching.
• A controlled vocabulary presents important advantages:
• Normalization of indexing concepts.
• Reduction of noise.
• Identification of indexing terms with a clear semantic meaning.
• Retrieval based on concepts rather than on words.
• Such advantages are particularly important in specific domains of knowledge.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Thesaurus Index Terms :
• Terms are the indexing components of a thesaurus
• A term can be composed of a word, a group of words, or a phrase
• It is normally a noun (most concrete part of speech)
• It usually denotes a concept.
• Can be expressed as a combination of an adjective with a noun: e.g. polar bear.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Thesaurus Term Relationships:
• Synonyms and near-synonyms
• Set of terms related to a given thesaurus term
• Relationships can be induced by patterns of co-occurrence within documents
• Such relationships are usually of a hierarchical nature
• Broader (represented by BT) related terms
• Narrower (represented by NT) related terms
• But, they can also be of a lateral or non-hierarchical nature
• We simply say that the terms are related (represented by RT)
• BT and NT relationships can be identified automatically
• Dealing with RT relationships is much harder

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Pre-processing
• Use of Thesauri in IR:
• Query formation process
• User forms a query
• Query terms might be erroneous and improper
• Solution: reformulate the original query
• Usually, this implies expanding original query with related terms
• Thus, it is natural to use a thesaurus for finding related terms
• Relationships captured in a thesaurus are frequently not valid for the
local context of a query
• To solve this context problem:
• Determine thesaurus-like relationships at query time
• But, not attractive for search engines
• Expensive in terms of time and resources
Module-04(Text Processing) - INFORMATION RETRIEVAL
SYSTEM (ITDO7024)
Document Clustering
• Clustering:
• Clustering is a division of data into groups of similar objects.
• Each group, called cluster, consists of objects that are similar between
themselves and dissimilar to objects of other groups.
• In other words, the goal of a good document clustering scheme is to
minimize intra-cluster distances between documents, while maximizing
inter-cluster distances.
• Clustering is the most common form of unsupervised learning and this is
the major difference between clustering and classification.
• No super-vision means that there is no human expert who has assigned
documents to classes.
• In clustering, it is the distribution and makeup of the data that will
determine cluster membership.
Module-04(Text Processing) - INFORMATION RETRIEVAL
SYSTEM (ITDO7024)
Document Clustering
• Document Clustering:
• Document clustering (or text clustering) is the application of cluster
analysis to textual documents.
• It has applications in automatic document organization, topic extraction
and fast information retrieval or filtering.
• Document clustering involves the use of descriptors and descriptor
extraction.
• Descriptors are sets of words that describe the contents within the cluster.
• Document clustering is generally considered to be a centralized process.
• Examples of document clustering include web document clustering for
search users.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Clustering
• Document Clustering:
• The application of document clustering can be categorized to two types,
online and offline.
• Online applications are usually constrained by efficiency problems when
compared to offline applications.
• Document clustering may be used for different tasks, such as:
• Grouping similar documents (news, tweets, etc.)
• Analysis of customer/employee feedback.
• Discovering meaningful implicit subjects across all documents.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Clustering
• Document Clustering:
• Algorithms:
• In general, there are two common algorithms.
• The first one is the hierarchical based algorithm, which includes single link,
complete linkage, group average and Ward's method.
• By aggregating or dividing, documents can be clustered into hierarchical structure,
which is suitable for browsing.
• However, such an algorithm usually suffers from efficiency problems.
• The other algorithm is developed using the K-means algorithm and its variants.
• Generally hierarchical algorithms produce more in-depth information for detailed
analyses, while algorithms based around variants of the K-means algorithm are
more efficient and provide sufficient information for most purposes.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Clustering
• Document Clustering:
• Algorithms:
• These algorithms can further be classified as hard or soft clustering algorithms.
• Hard clustering computes a hard assignment – each document is a member of
exactly one cluster.
• The assignment of soft clustering algorithms is soft – a document’s assignment is
a distribution over all clusters.
• In a soft assignment, a document has fractional membership in several clusters.
• Other algorithms involve graph based clustering, ontology supported clustering
and order sensitive clustering.
• Given a clustering, it can be beneficial to automatically derive human-readable
labels for the clusters. Various methods exist for this purpose.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Clustering
• Document Clustering Process:
• Tokenization:
• Tokenization is the process of parsing text data into smaller units (tokens) such as
words and phrases.
• Commonly used tokenization methods include Bag-of-words model and N-gram
model.
• Stemming and lemmatization:
• Different tokens might carry out similar information (e.g. tokenization and
tokenizing).
• We can avoid calculating similar information repeatedly by reducing all tokens to
its base form using various stemming and lemmatization dictionaries.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Clustering
• Document Clustering Process:
• Removing Stop Words and punctuation:
• Some tokens are less important than others.
• For instance, common words such as "the" might not be very helpful for revealing the
essential characteristics of a text.
• So usually it is a good idea to eliminate stop words and punctuation marks before doing
further analysis.
• Computing term frequencies:
• After pre-processing the text data, we can then proceed to generate features.
• For document clustering, one of the most common ways to generate features for a
document is to calculate the term frequencies of all its tokens.
• Although not perfect, these frequencies can usually provide some clues about the topic
of the document.
• Sometimes it is also useful to weight the term frequencies by the inverse document
frequencies.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Clustering
• Document Clustering Process:
• Clustering:
• We can then cluster different documents based on the features we have
generated.
• Number of standard clustering algorithms can be used for this purpose.
• Evaluation and Visualization:
• Finally, the clustering models can be assessed by various metrics.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)
Document Clustering
• Challenges in Document Clustering:
1. Selecting appropriate features of the documents that should be used for
clustering.
2. Selecting an appropriate similarity measure between documents.
3. Selecting an appropriate clustering method utilizing the above similarity
measure.
4. Implementing the clustering algorithm in an efficient way that makes it feasible
in terms of required memory and CPU resources.
5. Finding ways of assessing the quality of the performed clustering.

Module-04(Text Processing) - INFORMATION RETRIEVAL

SYSTEM (ITDO7024)