Machine Learning and Data Mining: 19 Mining Text And Web Data

Text and Web MiningMachine Learning and Data Mining (Unit 19)Prof. Pier Luca LanziReferences2Jiawei Han and Micheline Kamber, "Data Mining: Concepts and Techniques", The Morgan Kaufmann Series in Data Management Systems (Second Edition)Chapter 10, part 2Web Mining Course by Gregory-Platesky Shapiro available atwww.kdnuggets.comProf. Pier Luca LanziMining Text Data: An Introduction3Data Mining / Knowledge DiscoveryStructured Data Multimedia Free TextHypertextHomeLoan (Frank Rizzo bought<a href>Frank RizzoLoanee: Frank Rizzohis home from Lake</a> BoughtLender: MWFView Real Estate in<a hef>this home</a>Agency: Lake View1992.from <a href>LakeAmount: $200,000He paid $200,000View Real Estate</a>Term:15 yearsunder a15-year loanIn <b>1992</b>.)Loans($200K,[map],...)from MW Financial.<p>...Prof. Pier Luca LanziBag-of-Tokens Approaches4DocumentsToken SetsFour score and seven nation – 5years ago our fathers brought civil - 1forth on this continent, a new war – 2nation, conceived in Liberty, Featuremen – 2and dedicated to the Extractiondied – 4proposition that all men are people – 5created equal.Liberty – 1Now we are engaged in a God – 1great civil war, testing …whether that nation, or …Loses all order-specific information!Severely limits context!Prof. Pier Luca LanziNatural Language Processing5A dog is chasing a boy on the playground LexicalDetNoun AuxVerbDet Noun Prep DetNounanalysis(part-of-speechtagging)Noun PhraseNoun PhraseComplex VerbNoun PhrasePrep PhraseSemantic analysisVerb PhraseSyntactic analysisDog(d1).(Parsing)Boy(b1).Verb PhrasePlayground(p1).Chasing(d1,b1,p1).Sentence+Scared(x) if Chasing(_,x,_).A person saying this maybe reminding another person toget the dog back…Scared(b1)InferencePragmatic analysis(speech act)(Taken from ChengXiang ZhaProf. Pier Luca Lanzi, CS 397cxz – Fall 2003) iGeneral NLP—Too Difficult!6Word-level ambiguity “design” can be a noun or a verb (Ambiguous POS) “root” has multiple meanings (Ambiguous sense)Syntactic ambiguity“natural language processing” (Modification)“A man saw a boy with a telescope.” (PP Attachment)Anaphora resolution“John persuaded Bill to buy a TV for himself.”(himself = John or Bill?)Presupposition“He has quit smoking.” implies that he smoked before.Humans rely on context to interpret (when possible).This context may extend beyond a given document!(Taken from ChengXiang Zhai, CS 397cxz – Fall 2003)Prof. Pier Luca LanziShallow Linguistics7English LexiconPart-of-Speech TaggingWord Sense DisambiguationPhrase Detection / ParsingProf. Pier Luca LanziWordNet8An extensive lexical network for the English languageContains over 138,838 words.Several graphs, one for each part-of-speech.Synsets (synonym sets), each defining a semantic sense.Relationship information (antonym, hyponym, meronym …)Downloadable for free (UNIX, Windows)Expanding to other languages (Global WordNet Association)Funded >$3 million, mainly government (translation interest)Founder George Miller, National Medal of Science, 1991.wateryparchedmoistwetdryaridsynonymantonymdampanhydrousProf. Pier Luca LanziPart-of-Speech Tagging9Training data (Annotated text)This sentence serves as an example of annotated text…DetN V1 P DetN P V2 NThis is a new sentence.“This is a new sentence.”POS TaggerDet Aux Det AdjNPick the (p w ,..., w ,most likely t ,...,t )tag sequence.1k1k⎧ (p t | w )... (p t | w ) (p w )... (p w )11kk1k⎪p(w ,..., w ,t ,...,t )k= ⎨1k1k∏ (pw |t ) (pt |t )⎪Independent assignment−⎧iiii 1p(t | w )...p(t | w ) p(⎩ wMost common tagi 1= )...p(w )11kk1k⎪ k= ⎨∏p(w |t ) (pt |t )⎪iiii 1−⎩Partial dependencyi 1=(HMM)Prof. Pier Luca LanziWord Sense Disambiguation10?“The difficulties of computational linguistics are rooted in ambiguity.”N Aux V P NSupervised LearningFeatures:Neighboring POS tags (N Aux V P N)Neighboring words (linguistics are rooted in ambiguity)Stemmed form (root)Dictionary/Thesaurus entries of neighboring wordsHigh co-occurrence words (plant, tree, origin,…)Other senses of word within discourseAlgorithms:Rule-based Learning (e.g. IG guided)Statistical Learning (i.e. Naïve Bayes)Unsupervised Learning (i.e. Nearest Neighbor)(Adapted from ChengXiang Zhai, CS 397cxz – Fall 2003)Prof. Pier Luca LanziDocument Outline

• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ