01 Intro - Chunk 02 (s.31-48)

Overview

This part finishes Concept - Feature Selection (pruning too frequent / too infrequent words, filtering tokens by POS tags; s.31-32) and then covers stage 5 of the Concept - Text Mining Process, Concept - Pattern Discovery (s.33). Pattern discovery has three methods: cluster analysis, classification and association analysis. The slides detail document clustering with the similarity measures Concept - Jaccard Coefficient, Concept - Cosine Similarity (with Concept - TF-IDF) and embedding-based similarity (s.34-40), then document classification with Concept - Sentiment Analysis as running example (s.41-45). The lecture ends with why text mining is hard, a summary and references (s.46-48).

Detailed notes

1. Finishing feature selection (s.31-32)

Pruning document vectors (s.31)

• Prune methods specify if and how too frequent or too infrequent words should be ignored (s.31).
• Two options (s.31):
  • Percentual: ignore words that appear in less / more than this percentage of all documents.
  • Absolute: ignore words that appear in less / more than that many documents.
• RapidMiner (s.31): operator Process Documents from Files, parameters prune method = absolute, prune below absolute = 30, prune above absolute = 250 (words in fewer than 30 or more than 250 documents are dropped).
• Python (s.31):
  • TfidfVectorizer(min_df=0.1, max_df=0.3) # Percentual
  • TfidfVectorizer(min_df=5, max_df=20) # Absolute
  • (a float is a share of documents, an integer is an absolute document count.) See Concept - Pruning.

Filter tokens by POS tags (s.32)

• Concept - POS Tagging may be helpful for feature selection: sometimes you want to focus on certain classes of words (s.32):
  • Adjectives (JJ.) for sentiment analysis: good, bad, great.
  • Nouns (N.) for text clustering: red and blue cars are similar; red and blue trousers are similar (the nouns carry the topic; colours do not).
• RapidMiner supports the PENN tag system for English and the STTS tag system for German; filtering conditions are expressed as regular expressions; operator Filter Tokens (by POS Tags) (s.32).
• Python: the NLTK library supports the PENN tag system for English (s.32).

2. Pattern discovery (s.33)

Methods: 1. Cluster Analysis, 2. Classification, 3. Association Analysis (s.33). The process diagram is shown again with the Data Mining / Pattern Discovery stage circled in red.

3. Document clustering (s.34-40)

• Goal (s.34): given a set of documents and a similarity measure among documents, find clusters such that documents in one cluster are more similar to one another and documents in separate clusters are less similar, using some clustering algorithm.
• Applications (s.34): topical clustering of news stories; email message thread identification; grouping of document versions.
• Question (s.34): which similarity measures are a good choice for comparing document vectors? The answer is developed on s.35-40.

Jaccard coefficient (s.35-36)

• Popular similarity measure for vectors of asymmetric binary attributes; used together with the binary term occurrence vector (1 = word occurs, 0 = word absent) (s.35).
• Formula (s.35, printed as $dist$ on the slide but used as similarity): $\text{sim}({\mathbf{x}}_i,{\mathbf{x}}_j)=\frac{M_{11}}{M_{01}+M_{10}+M_{11}}$ = number of 11 matches / number of not-both-zero attribute values.
• Example (s.36): d1 = “Saturn is the gas planet with rings.” d2 = “Jupiter is the largest gas planet.” d3 = “Saturn is the Roman god of sowing.”

	Saturn	is	the	gas	planet	with	rings	Jupiter	largest	Roman	god	of	sowing
d1	1	1	1	1	1	1	1	0	0	0	0	0	0
d2	0	1	1	1	1	0	0	1	1	0	0	0	0
d3	1	1	1	0	0	0	0	0	0	1	1	1	1

Results (s.36): sim(d1,d2) = 0.44 (highlighted), sim(d1,d3) = 0.27, sim(d2,d3) = 0.18. The red 0s on the slide mark the positions where both documents have 0 (not counted).

Added context

Check of s.36: d1 has 7 terms, d2 has 6, they share 4 (is, the, gas, planet) so $4/(7+6-4)=4/9=0.44$. d1/d3 share 3 (Saturn, is, the): $3/11=0.27$. d2/d3 share 2: $2/11=0.18$.

Cosine similarity (s.37)

• Popular similarity measure for comparing weighted document vectors such as term-frequency or TF-IDF vectors (s.37).
• $\cos (d_1,d_2)=\frac{d_1\bullet d_2}{\Vert d_1\Vert \Vert d_2\Vert }$, where $\bullet$ is the vector dot product $\mathbf{a}\cdot \mathbf{b}={\sum }_i{a}_i{b}_i$ and $\Vert d\Vert =\sqrt{{\sum }_i{a}_i^2}$ is the vector length (s.37).
• Example (s.37): $d_1=(3,2,0,5,0,0,0,2,0,0)$, $d_2=(1,0,0,0,0,0,0,1,0,2)$.
  • $d_1\bullet d_2=3\cdot 1+2\cdot 1=5$ (only positions 1 and 8 are non-zero in both).
  • $\Vert d_1\Vert =\sqrt{42}=6.481$; slide gives $\Vert d_2\Vert =\sqrt{6}=2.245$.
  • $\cos (d_1,d_2)=0.3150$.

Added context

The slide prints $\sqrt{6}=2.245$, but $\sqrt{6}\approx 2.449$. With 2.449, $5/(6.481\cdot 2.449)=0.315$, which matches the slide’s final result, so the 2.245 is a typo on the slide (UNCLEAR (slide 37) which is intended; the final 0.3150 is correct).

Cosine similarity + TF-IDF (s.38-39)

• “A commonly used combination for text clustering”: each document is represented by a vector of TF-IDF weights (s.38). Formulas on slide: $w_{ij}=t{f}_{ij}\times id{f}_i$, $id{f}_i=\log \frac{N}{d{f}_i}$.
• First document as TF-IDF vector (s.38): $\left(\frac{1}{7}\log \frac{3}{2},\frac{1}{7}\log \frac{3}{3},\frac{1}{7}\log \frac{3}{3},\dots ,0,0,0,\dots \right)$ for Saturn, is, the, … ; $1/7$ = term frequency (7 words in d1); “Saturn” occurs in 2 of 3 docs, so $idf=\log (3/2)$; “is” and “the” occur in all 3 docs, so $idf=\log (3/3)=0$. Terms such as Jupiter, largest, Roman do not occur in d1 -> 0.
• TF-IDF vectors for the same three documents (s.39):

	Saturn	is	the	gas	planet	with	rings	Jupiter	largest	Roman	god	of	sowing
d1	0.03	0	0	0.03	0.03	0.07	0.07	0	0	0	0	0	0
d2	0	0	0	0.03	0.03	0	0	0.08	0.08	0	0	0	0
d3	0.03	0	0	0	0	0	0	0	0	0.07	0.07	0.07	0.07

• Cosine similarities (s.39): cos(d1,d2) = 0.13 (highlighted), cos(d1,d3) = 0.05, cos(d2,d3) = 0.00.
• Takeaway: is and the get weight 0 (red on slide), so stopword-like terms no longer create similarity. d2 and d3 share only “is, the”, which now have weight 0, hence cosine 0 (while Jaccard gave 0.18).

	Jaccard (s.36)	Cosine + TF-IDF (s.39)
sim(d1,d2)	0.44	0.13
sim(d1,d3)	0.27	0.05
sim(d2,d3)	0.18	0.00

Ranking of pairs is the same in both (d1-d2 most similar); Jaccard counts all shared terms equally, cosine + TF-IDF discounts common words.

Embedding-based similarity (s.40)

1. Translate documents into embedding vectors using e.g. doc2vec, or the average of the embeddings of all words in the document (Concept - Word Embeddings).
2. Calculate similarity of the document embedding vectors with: cosine similarity, word mover’s distance, or neural nets (RNNs, LSTMs) (slide spells “LTSMs”).

• Libraries: Python gensim (doc2vec, word2vec); RapidMiner word2vec extension on the marketplace (s.40).
• Demo screenshot (s.40, http://bionlp-www.utu.fi/wv_demo/): “Similarity of two words”, value between 1 and -1: Restaurant vs Eatery = 0.723; Restaurant vs Resource = 0.146. Takeaway: semantically related words score high even though they share no letters or tokens, which bag-of-words cannot capture.

4. Document classification (s.41-45)

• Given: a collection of labeled documents (training set). Find: a model for the class as a function of the values of the features. Goal: previously unseen documents should be assigned a class as accurately as possible (s.41).
• Applications (s.41): topical classification of news stories or web pages; SPAM detection; sentiment analysis.
• Classification methods commonly used for text (s.41): 1. naive Bayes; 2. support vector machines (SVMs); 3. recurrent neural networks (RNNs), e.g. long short-term memory (LSTMs); 4. but KNN or random forests may also work. See Concept - Document Classification.

Example application: sentiment analysis (s.42-45)

• Given a text, goal: assign a sentiment class, e.g. positive / neutral / negative, or sad / happy / angry / surprised. Can be implemented as a supervised classification task, requiring training data of pairs <text; sentiment> (s.42).
• Labeling data for sentiment analysis is expensive, like every data labeling task. Web reviews may be used as labeled data (s.43): the star rating (red box on slide) is the label, the review text (blue box) is the document. Example screenshot: a 5-star review “Listen Closer” vs a 3-star review “Good, But Not Their Best” for a Nine Inch Nails album (173 of 213 resp. 19 of 21 people found them helpful).
• Large public review corpora (s.43): Amazon Product Data by Julian McAuley (142 million reviews); WebDataCommons (70 million reviews from 50,000 websites using RDFa or Microdata markup).
• Preprocessing for sentiment analysis (s.44): the standard simple syntactic steps (remove punctuation and HTML tags, normalize case) can destroy useful signals. Reasonable features: punctuation ”!”, ”?”, ”?!”; smileys encoded with punctuation (;-) :-( ); visual markup (red colour, bold face); amount of capitalization (“SCREAMING”). Practical approach: replace smileys / visual markup with sentiment words during preprocessing, e.g. smiley -> great; COOL -> cool cool (emphasis by repetition).
• Text classification tricks (s.45):
  • Finding selective words: weight words by their correlation with the label; select the top-k words with the highest correlation. RapidMiner screenshot: Weight by Correlation -> Select by Weights -> Naive Bayes (inside a Training subprocess).
  • Sentiment lexicons: use an external dictionary of opinion words - Bing Liu’s lexicon, AFINN lexicon; restrict the RapidMiner word list to these words or combine them with your learned sentiment words. Screenshot: operators Load Opinion … feeding Process Documents (word-list input). See Concept - Sentiment Lexicon.

5. Why is text mining difficult? (s.46)

Five reasons (s.46); see Concept - Text Mining Challenges:

1. Many ways to represent similar concepts - e.g. space ship, flying saucer, UFO.
2. “Countless” combinations of subtle, abstract relationships among concepts - e.g. relationship between drugs and diseases.
3. High dimensionality - tens of hundreds of thousands of features.
4. Data variation - we have ImageNet, but no such huge labelled text data volume.
5. Ambiguity of language - word level: bank; sentence level: “I heard his cell phone in my office” (the underlined “in my office” can attach to heard or to cell phone).

6. Summary and references (s.47-48)

• Summary (s.47): main challenge = preprocessing and vectorization, in order to apply well-known data mining algorithms. Lots of alternative techniques, so you must experiment to find what works for your use case; focus has shifted from bag-of-words approaches to embeddings. Text mining can be tricky, but “OK-ish” results are easily achieved.
• References (s.48): textbook Jurafsky & Martin, Speech and Language Processing, 2nd ed., Pearson 2008 (draft 3rd ed. online at web.stanford.edu/~jurafsky/slp3/); videos: Stanford lecture series NLP with Deep Learning, DWS screencast Text Mining with RapidMiner; tools: Stanza / Stanford CoreNLP (neural and classic NLP tools), Gensim (Python word2vec), GATE (General Architecture for Text Engineering).

Figures & diagrams

• s.31 RapidMiner parameter panel (prune method absolute, below 30, above 250, data management auto) and a Python box with min_df / max_df for percentual vs absolute pruning.
• s.32 RapidMiner operator Filter Tokens (by POS Tags) and a constituency parse tree: S -> NP (Det “that”, NOM Noun “man”) + VP (Verb “read”, NP (Det “this”, NOM Noun “book”)). Takeaway: POS/syntactic structure identifies which tokens are nouns, adjectives etc.
• s.33 Process pipeline (Text -> Preprocessing -> Feature Generation -> Feature Selection -> Data Mining / Pattern Discovery (circled) -> Interpretation / Evaluation, dotted feedback arrows).
• s.34 Two orange circles = clusters of documents; yellow document in each = representative document.
• s.35 Jaccard formula. s.36 binary term occurrence matrix, zeros in red where both are 0 / not counted.
• s.37 Dot-product and norm formulas plus numeric example. s.38 TF-IDF first-document vector with arrows labelling positions (Saturn, is, the, Jupiter, largest, Roman). s.39 TF-IDF matrix (zeros for is, the in red; highest weights 0.08 for Jupiter/largest).
• s.40 Word-similarity web demo (Restaurant/Eatery 0.723; Restaurant/Resource 0.146).
• s.42 Smiley vs sad face “or ?” illustration of sentiment. s.43 Two Amazon-style reviews (5 stars vs 3 stars; stars boxed red = label, text boxed blue = input).
• s.45 Two RapidMiner process screenshots (correlation weighting + Naive Bayes; loading opinion lexicon).
• s.46 Text-only slide (49 embedded decoration images; no diagram content). s.48 Book cover of Jurafsky & Martin.

flowchart TD
    PD[Pattern Discovery s.33] --> CL[Cluster Analysis]
    PD --> CF[Classification]
    PD --> AA[Association Analysis]
    CL --> SIM{Similarity measure}
    SIM --> J[Jaccard<br/>binary term occurrence]
    SIM --> C[Cosine<br/>TF / TF-IDF vectors]
    SIM --> E[Embedding-based<br/>doc2vec, avg word vectors]
    CF --> M[Naive Bayes, SVM, RNN/LSTM, KNN, RF]
    CF --> SA[Sentiment analysis<br/>labels from review stars]

Similarity measure	Vector type	Formula idea	Slide
Jaccard	binary term occurrence	$M_{11}/(M_{01}+M_{10}+M_{11})$	s.35-36
Cosine	TF or TF-IDF weights	$d_1\bullet d_2/(\Vert d_1\Vert \Vert d_2\Vert )$	s.37-39
Embedding-based	doc2vec / averaged word embeddings	cosine, word mover’s distance, neural nets	s.40

Key terms

• Concept - Feature Selection
• Concept - Pruning
• Concept - POS Tagging
• Concept - Pattern Discovery
• Concept - Document Clustering
• Concept - Jaccard Coefficient
• Concept - Cosine Similarity
• Concept - TF-IDF
• Concept - Word Embeddings
• Concept - Document Classification
• Concept - Sentiment Analysis
• Concept - Sentiment Lexicon
• Concept - Text Mining Challenges

Formulas

• Jaccard (s.35): $\text{sim}({\mathbf{x}}_i,{\mathbf{x}}_j)=\frac{M_{11}}{M_{01}+M_{10}+M_{11}}$
• Cosine (s.37): $\cos (d_1,d_2)=\frac{d_1\bullet d_2}{\Vert d_1\Vert \Vert d_2\Vert }$, $d_1\bullet d_2={\sum }_i{a}_i{b}_i$, $\Vert a\Vert =\sqrt{{\sum }_i{a}_i^2}$
• TF-IDF (s.38): $w_{ij}=t{f}_{ij}\times id{f}_i$, $id{f}_i=\log \frac{N}{d{f}_i}$
• Worked values: Jaccard 0.44/0.27/0.18 (s.36); cosine example 0.3150 (s.37); cosine+TF-IDF 0.13/0.05/0.00 (s.39).

Likely exam questions

Style follows Past Exam - Question Bank & Style Guide (short “discuss / describe / explain” answers).

1. Discuss the goal of document clustering and give applications. (s.34) Given documents and a similarity measure, find clusters where intra-cluster similarity is high and inter-cluster similarity low. Applications: topical news clustering, email thread identification, grouping of document versions.
2. Explain the Jaccard coefficient and for which vectors it is used. (s.35) $M_{11}/(M_{01}+M_{10}+M_{11})$; for asymmetric binary attributes, i.e. binary term occurrence vectors; joint absences (0-0) are ignored.
3. Compute the Jaccard similarity of “Saturn is the gas planet with rings” and “Jupiter is the largest gas planet”. (s.36) Shared = {is, the, gas, planet} = 4; union = 9; 0.44.
4. Write the cosine similarity formula and compute it for d1=(3,2,0,5,0,0,0,2,0,0), d2=(1,0,0,0,0,0,0,1,0,2). (s.37) dot = 5, $\Vert d_1\Vert =\sqrt{42}$, $\Vert d_2\Vert =\sqrt{6}$, cos ≈ 0.315.
5. Why combine cosine similarity with TF-IDF for clustering? (s.38-39) TF-IDF down-weights terms present in every document (idf = log(3/3) = 0, e.g. is, the), cosine normalizes for document length, so similarity reflects distinctive shared terms.
6. How can document similarity be computed with embeddings? (s.40) Embed documents (doc2vec or average of word vectors), then compare with cosine similarity, word mover’s distance or neural nets.
7. Define document classification. (s.41) Given a labeled training set, learn a model class = f(features) and assign classes to unseen documents as accurately as possible.
8. Name classification methods used for text. (s.41) Naive Bayes, SVMs, RNNs/LSTMs, also KNN and random forests.
9. Describe how sentiment analysis can be implemented and where training data comes from. (s.42-43) Supervised classification on pairs <text; sentiment>; labeling is expensive, so web reviews (star rating = label) are used, e.g. Amazon (142M) and WebDataCommons (70M).
10. Why must preprocessing be adapted for sentiment analysis? (s.44) Punctuation (!, ?!), smileys, visual markup and capitalization carry sentiment; replace them with sentiment words (smiley -> great, COOL -> cool cool).
11. Describe two tricks to improve text classification. (s.45) Select top-k words by correlation with the label; use sentiment lexicons (Bing Liu, AFINN).
12. Why is text mining considered difficult? (s.46) Many ways to express a concept, subtle relations, high dimensionality, little labelled data, language ambiguity.
13. Compare percentual and absolute pruning. (s.31) Percentage of documents vs number of documents as the min/max threshold for ignoring words (min_df/max_df as float vs int).

Common confusions

• Jaccard vs cosine: Jaccard needs binary vectors and ignores 0-0 matches; cosine works on weighted (TF, TF-IDF) vectors (s.35, s.37).
• Similarity vs distance: the Jaccard slide labels the formula “dist”, but it is a similarity (1 = identical sets) and the example calls it sim (s.35-36).
• Cosine of weight-0 terms: terms with idf = 0 (in all documents) contribute nothing, so d2 and d3 have cosine 0 although they share is and the (s.39).
• Pruning vs stopword removal: stopwords are removed by a fixed list; pruning removes words by document frequency thresholds (s.31, Concept - Stopword Removal).
• Adjectives vs nouns: adjectives are filtered for sentiment analysis, nouns for clustering (s.32).
• Clustering vs classification: clustering has no labels and needs a similarity measure; classification needs a labeled training set (s.34, s.41).

Slide coverage

Slide	Content	Covered in
31	Pruning document vectors (percentual / absolute; RapidMiner, Python)	Detailed notes 1; Figures
32	Filter tokens by POS tags (JJ for sentiment, N for clustering, PENN/STTS)	Detailed notes 1; Figures
33	Section 5 Pattern Discovery: clustering, classification, association	Detailed notes 2; Figures
34	5.1 Document clustering: goal, applications, question	Detailed notes 3; Figures
35	Jaccard coefficient definition	Detailed notes 3; Formulas
36	Jaccard example (0.44, 0.27, 0.18)	Detailed notes 3
37	Cosine similarity definition and numeric example	Detailed notes 3; Formulas
38	Cosine + TF-IDF: first document vector	Detailed notes 3
39	Cosine + TF-IDF example matrix and results	Detailed notes 3
40	Embedding-based similarity (doc2vec, word mover’s distance, demo)	Detailed notes 3; Figures
41	5.2 Document classification: setup, applications, methods	Detailed notes 4
42	Sentiment analysis as supervised classification	Detailed notes 4
43	Labeled review data and corpora	Detailed notes 4; Figures
44	Preprocessing for sentiment analysis	Detailed notes 4
45	Text classification tricks (correlation, lexicons)	Detailed notes 4; Figures
46	Why is text mining difficult?	Detailed notes 5
47	Summary	Detailed notes 6
48	References and tools	Detailed notes 6

Previous: 01 Intro - Chunk 01 (s.1-30) | Next: (none, last chunk of this deck) | Up: 01 Intro - Index