01204453 – Web IR & Mining

เนื้อหาทั้งหมดต่อจากนี้ถูกเขียนโดยนิสิตภาควิชาวิศวกรรมคอมพิวเตอร์

คณะวิศวกรรมศาสตร์ มหาวิทยาลัยเกษตรศาสตร์ รุ่นที่ 23

โดยเป็นเนื้อหาจากบทเรียนทีเกิดจากการจดบันทึกในห้องเรียนและศึกษาเพิ่มเติมจากนอกห้องเรียน

โดย มีจุดประสงค์เพื่อเป็นแนวทางในการเรียนรู้ของผู้ที่สนใจหรือรุ่นน้องรุ่น ถัดๆไป โดยมีการคงสภาพของเนื้อหาทั้งหมดไว้ทุกประการ รวมถึง คอมเมนท์ ส่วนที่ไม่ใช่เนื้อหาอื่นๆ เป็นต้น

อย่างไรก็ตาม

ในกรณีที่ถูก นำไปใช้หรือนำไปอ้างอิงด้วยวิธีใดวิธีหนึ่งก็ตาม ในกรณีที่เนื้อหาไม่ถูกต้อง ไม่เหมาะสม ผู้เขียนจะไม่ขอรับผิดชอบใดๆทั้งสิ้น ขอให้อ่านด้วยวิจารณญาณของผู้อ่านเอง

ท่านสามารถอ่านเลคเชอร์ฉบับ Document ได้ที่นี่

========================================

204453 Web IR & Mining

Web IR & Mining

Course Information

See http://mike.cpe.ku.ac.th/204453/

Lecture 1: Introduction

IR หรือ Indexing and Retrieval มีวัตถุประสงค์หลักๆ คือ เพื่อให้เราสามารถเอาข้อมูลที่เกี่ยวข้อง (relevant) ออกมาจากข้อมูลปริมาณมากๆ ได้ โดยระบบอาจขยายได้ (scalable) และทำงานได้อย่างมีประสิทธิภาพ (efficient)

งานหลักของ IR คือ มีข้อมูลเป็นข้อความมากๆ ที่เป็นภาษาธรรมชาติ (natural language) เมื่อเราใส่ query string ลงไป จะได้รายการเอกสารกลับมา โดยเรียงลำดับตามความเกี่ยวข้องกับ query ของเรา

Relevance?

Relevance เป็นเรื่องที่ subjective โดยอาจเกิดจาก

  1. ความเกี่ยวข้องในเนื้อหานั้นๆ (belongs to subject)
  2. เวลา ความทันสมัยของเนื้อหา (timeliness)
  3. ความน่าเชื่อถือของแหล่งข้อมูล (authoritative)
  4. ตอบสนองความต้องการส่วนบุคคล (satisfies need)

ดังนั้น จากนิยามนี้เราจึงบอกไม่ได้ว่า relevance หมายถึงอะไร เพราะส่วนใหญ่ก็ขึ้นกับแต่ละคนด้วย

Keyword Search

มีสองลักษณะ

  1. แบบแรก คือการหาตรงๆ ก็จับตามสตริงที่เราใส่ลงไปเลย
  2. อีกแบบจะหลวมกว่า คือใช้ bag of words (คือ การนับความถี่คำ) โดยจะเห็นความสำคัญของแต่ละคำว่ามากน้อยเท่าไหร่ได้ด้วย

ปัญหาของ Keyword Search

Keyword Search จะเกิดปัญหาใหญ่ๆ อยู่สองลักษณะ

  1. คำคล้าย หรือ Synonym จะไม่ถูกค้นหาไปด้วย เช่น
  1. ร้านอาหาร มีทั้ง diner restaurant cafe ฯลฯ การใช้คำใดคำหนึ่งจะไม่เจอร้านแบบอื่น
  2. ประเทศจีน อาจใช้คำว่า China หรือ PRC หรือ People’s Republic of China ก็ได้ ถ้าใช้แบบใดแบบหนึ่งก็จะไม่เจอแบบที่เหลือเช่นกัน
  1. ไม่สามารถแก้ความกำกวมได้ เวลาค้นคำใดคำหนึ่งจะเจอหมด เช่น
  1. bat ที่เป็นค้างคาว กับ bat ที่เป็นไม้ตีๆ (และ bat ที่เป็น verb แปลว่าฟาดด้วย bat)
  2. Apple ที่เป็นบริษัท และผลไม้
  3. หิว อยากกินไอติม พิมพ์ ice cream ลงไปเจอแต่รอม Android ICS

แต่ Keyword search ทำไม่ยาก เราจึงยกมาพูดในวิชานี้ และจะไปต่ออีกเล็กน้อยด้วย

Intelligent IR

IR ที่ฉลาดจะ

  1. เข้าใจความหมายของคำ (แก้ปัญหาคำคล้ายและความกำกวม)
  2. จัดลำดับคำ
  3. ปรับตาม feedback จากผู้ใช้
  4. เลือกหาแหล่งที่น่าเชื่อถือ

องค์ประกอบของ IR

  1. การดำเนินการกับข้อความ
  1. ตัด stopword ออก (เช่น particles และ prepositions)
  2. stemming (แปลงคำให้มีรูปเดียวกัน)
  1. Indexing
  1. ทำดัชนี เช่น บอกว่าเอกสาร A มีคำ a b c d เอกสาร B มีคำ a b d เอกสาร C มีคำ a c
  2. จากนั้นแปลงเป็นดัชนีย้อนกลับ (inverted index) เช่น คำ a เจอในเอกสาร A B C
  1. Searching ค้นหาสิ่งที่ต้องการ โดยใช้ Inverted Index
  2. Ranking จัดอันดับเอกสารต่างๆ ตามความเกี่ยวข้อง
  3. UI ก็เป็นส่วนที่รับ query และ feedback แล้วก็ส่งผลลัพธ์ด้วย
  4. การดำเนินการกับ query เพื่อให้การสืบค้นคืนดีขึ้น

Web Search

Web Search หลักๆ ก็คือทำงานบน HTML หรือไฟล์บนเว็บด้วย มีบางสิ่งที่แตกต่างจาก text search เช่น

  1. การหาเอกสารทำโดยใช้ spidering
  2. อาศัยโครงสร้าง HTML/XML ในการจัดการเอกสารได้ (อาจง่ายกว่า text)
  3. เอกสารอาจเปลี่ยนแปลงได้ทุกเมื่อ
  4. อาศัยโครงสร้างลิงค์ระหว่างไฟล์

ศาสตร์อื่นๆ ที่เกี่ยวข้อง

  1. DB
  1. SQL, XML
  1. Information Sci.
  1. HCI, เรื่องเกี่ยวกับมนุษย์ทั้งหลาย
  2. การวิเคราะห์การอ้างอิงเอกสาร
  3. digital library
  1. AI
  1. การแทนความรู้และ query ด้วย FOL, Predicate, Bayes net
  2. Web ontology
  1. NLP
  1. Syntax, semantic, ฯลฯ
  2. ช่วยให้ IR สามารถทำงานกับความหมายของคำได้
  3. ดึงข้อมูลบางส่วนออกมาได้ (extraction)
  4. ตอบคำถามได้
  1. ML
  1. ทำให้ IR ของเราเรียนรู้และเพิ่มประสิทธิภาพได้
  2. Supervised learning ใช้ในการแยก category (เช่น spam, not spam)
  3. Unsupervised learning ใช้ในการจัด clustering
  4. Text mining

สั่งงาน

  1. จับกลุ่ม ลงชื่อบน fb อาจารย์ เลือก 1 หัวข้อ (ดูสไลด์)

Lecture 2

Common Preprocessing step

  1. เอาพวก unwanted character/ markup language ออกไป เช่นพวก tag html <title>
  2. break text ทั้งหลายให้เป็นชิ้นเล็กๆ (ภาษาอังกฤษ break ด้วย white space ต่างๆ: space bar, enter)
  3. stem หารากศัพท์ของคำต่างๆ (ภาษาอังกฤษ) [ตัวอย่างเครื่องมือ: lovin stemmer]
  4.  เอาพวก artricle a an the it ออกไป
  5. detect เป็น phrase (ต้องใช้พวก nlp) ต้องทำก่อนที่จะ stem
  6. inverted index   (เปลี่ยนว่าในเอกสารประกอบไปด้วยคำ ไปเป็นมองว่าคำๆนี้ อยู่ในเอกสารใดบ้าง)

Boolean model

  1. มองเป็นเซทของ Keyword
  2. Query ต่างๆก็เป็น Boolean expression of keyword ที่เชื่อมกันด้วย  and, or, not [[Rio & Brazil] | [Hilo  & Hawaii]] & Hotel & !Hilton]
  3. เป็นที่นิยม เพราะ เข้าใจง่าย , clean formalism

Boolean model : Problem

  1. ยากที่จะควบคุม่จำนวนผลลัพธ์ เพราะจะออกมาหมด
  2. ยากที่จะจัดลำดับ เพราะเป็นการ match ทาง logic (true, false)
  3. ยากที่จะให้ Relevance feedback

Statistical model

  1. document represented by bag of word (ดูว่าแต่ละคำมีปรากฏอยู่บน page กี่ครั้ง)
  2. สามารถ weight query term ได้ ว่า อยากได้เป็น text, database

Statistical retrival

  1. base on similarity ระหว่าง query กับ documents
  2. ranked โดยความเหมือน
  3. similarity ขึ้นอยู่กับความถี่ของ keyword
  4. Relevance feedback ทำได้ง่าย

Vector-space model

  1. t คือ เซทของคำต่างๆที่ทำการ preprocess แล้ว (ไม่ซ้ำกันด้วย)
  2. ทุก term ใน t เป็น orthogonal กัน (มี t มิติ ซึ่งตั้งฉากกันหมด -> แต่ละ term ไม่เกี่ยวเนื่องกันเลย)
  3. term i ในเอกสาร j  มี weight เป็น wij

Document Collection

  1. แทนเป็น matrix ของ document * term

Term weights: term frequency

  1. แทนเป็น fij
  2. อาจจะแทนเป็น term frequency tfij = fij / max i{fij}

Term weights: inverse document frequeny

  1. dfi บอกว่า มี term i อยู่ในกี่ document
  2. inverse document frequncy term  idfi  = log2(N/dfi)
  3. เอาไว้ใช้บ่งบอก discrimination power[a] ของ document เช่น ถ้ามี dfi ของคำว่า the เยอะ แสดงว่า discrimination power ของ the ต้องต่ำมากๆ
  4. ยิ่ง dfi น้อย แสดงว่าเฉพาะเจาะจงมาก เพราะหาคำนี้ใน document เป็นล้านๆ

TF-IDF Weighting

  1. term ที่ปรากฏใน document หนึ่งเยอะๆ แต่ปรากฏอยู่ใน document อื่นน้อยๆ -> high weight

Query Vector

Similarity measuer

Cosine คือดูเฉพาะมุม ของเวกเตอร์หนึ่งหน่วย cos 0 -> 1, cos 90 -> 0 นั่นคือ ถ้าข้อมูลเหมือนกันเลย นั่นคือ cos 0 แสดงว่าข้อมูลสองชุดนี้เกี่ยวข้องกัน


Lecture 3

Java VSR[b] Implementation

Simple Tokenizing

  1. เริ่มต้นต้องจัดการพวก tag ทั้งหลาย เอาให้เหลือเป็นเนื้อความล้วนๆ
  2. แบ่งคำเป็น token เล็กๆ
  3. บางทีพวก punctuation ที่อยู่ในพวก email, ตัวเลขที่อยู่ในปี, คำตัวเล็ก/ตัวใหญ่ (Republican[c], republican[d] ) พวกนี้อาจจะต้องเก็บไว้

Tokenizing HTML

  1. พวกส่วนที่ผู้ใช้อาจจะมองไม่เห็น เช่น url, meta text ส่วนใหญ่ search engine จะเก็บไว้ด้วย

Stopwords

  1. พวก a, the , in, to จะเอาออกไป
  2. ทั่วไปจะมีประมาณ 500 คำในภาษาอังกฤษ

Stemming

  1. แปลงพวก token ให้อยู่ในรูปของ root (รากศัพท์) (Morphological variation)
  1. เช่นพวก computer, computational, computation ทั้งหมดแปลงให้เป็น compute
  1. ส่วนใหญ่จะเป็นการตัดพวก prefix, suffix แต่ก็ต้องมีข้อยกเว้นบางอย่างด้วย

Porter Stemmer

  1. เป็นผู้เสอนวิธีการจัดการพวก affix (prefix, suffix) ออก ในปี 1980 แต่ว่าผลลัพธ์ที่ได้ยังไม่ค่อยสมบูรณ์ คือจะไม่ได้รากศัพท์จริงๆออกมา
  2. Error of commission
  1. organization, organ->organ  (polysemy[e])
  2. police, polocy->polic

Sparse Vector

  1. พวก matrix document by term จะมี document ที่มี word เป็น 0 อยู่เยอะมาก ดังนั้นจะเรียกเวกเตอร์นี้ว่าเป็น sparse

Sparse Vectors as Lists

  1. เก็บพวก vector นี้เป็น linked list

Implementation Based on Inverted Files

  1. ประเด็นสำคัญของระบบสืบค้นคือ เวลา ต้องสั้น
  2. มอง doc by term ให้เป็น term by doc คือเก็บว่า term นี้เก็บอยู่ใน doc ไหนบ้าง แทนที่จะเก็บเป็น doc นี้เก็บ term อะไรบ้าง

การส่งงาน ir.jar

  1. ใส่ 00README ใส่ไว้ใน directory เดียวกับ ir
  2. เสร็จแล้วให้ jar uvf ir.jar 00README ir
  3. upload ไว้ที่ mikegrid.cpe.ku.ac.th/cpe204453/upload_upload_form.php
  1. id,pass เป็นรหัสนิสิต

Lecture 4

Performance evaluation of information retrieval system

Why System Evaluation?

  1. มีหลายๆวิธี หลายๆ Algorithm จะเปรียบเทียบว่าอะไรดีกว่ายังไง
  2. การทำ preprocess อันไหนดีกว่า
  1. Ranking function (dot-product)
  2. Term selection (stopword removal, stemming)

Difficulties in Evaluation IR System

  1. ประสิทธิภาพของความเกี่ยวข้องของ relevancy of retrieved item
  2. * Relevancy เป็น continuous ไม่ใช่ binary (ไม่ได้มีแค่ ใช่ กับ ไม่ใช่)

Human Labeled Corpora (gold standard)

  1. เริ่มที่ชุดของเอกสารชุดหนึ่ง
  2. หา Human expert (เช่น ในห้องสมุดจะเป็นบรรณารักษ์) มาศึกษาเอกสาร
  3. สร้าง set ของคำถาม
  4. mark set ของคำตอบ เอาคำตอบมาเทียบกันระหว่างเอกสารว่า เอกสารไหนได้คำตอบที่ดีกว่ากัน
  5. ต้องใช้ความพยายามมาก

Precision and Recall

  1. Recall คือ เปอร์เซนของ ข้อมูลที่ retrieve มาแล้ว relevant เทียบกับ relevant document ที่มีทั้งหมด
  2. Precisionl คือ เปอร์เซนของข้อมูลที่ retrieve มาแล้ว relevant เทียบกับ document ที่ retrieve มา
  1. ค่า Recall หาได้ยาก เพราะไม่รู้จำนวนของ relevant document ทั้งหมด

Computing Recall/Precision Point

  1. สำหรับแต่ละคำถาม เราจะพิจารณาเป็น list rank
  2. จากนั้นก็ไล่ดูเลยว่า แต่ละอันเป็นคำตอบหรือเปล่า ถ้าเป็นก็ติ๊กถูกไป หรือไม่เป็นก็ติ๊กผิด
  3. นั่นก็จะรู้ค่า P,R ของแต่ละอันได้เลย

ออกข้อสอบ slide หน้า 14 1 ข้อ

R-Precision: ค่า precision ที่ตำแหน่งใดๆ

F Measure: F = 2PR / P+R

        เอาค่า Precision กับ Recall มารวมกันให้เป็นค่าๆหนึ่ง (แต่ละค่ามีความสำคัญเท่ากัน)

Precision สูงๆ คือสิ่งที่ user ต้องการ -> หน้าแรกๆมีคำตอบเยอะที่สุด

Recall สูงๆ คือสิ่งที่ server ต้องการ -> ให้ได้ผลการค้นหาที่ได้ doc ที่ relevant ครบภายในหน้าที่น้อยที่สุด

Non-Binary Relevance

  1. ตอนแรกเป็น Binary นั่นคือ มีแค่ relevant กับ non-relevant
  2. อันนี้อาจจะเป็น % ได้

Lecture5

E-measure

  1. ต่างกับ F ตรงที่เราใส่ weight ให้กับ P,R ด้วย เนื่องจากเรามองว่าสองค่านี้มีความสำคัญไม่เท่ากัน

Mean average precision (MAP)

  1. ถ้า retrieve relevant ได้อยู่บนๆ จะได้ค่า MAP สูงๆ
  2. ในทางปฏิบัติจริงๆ จะหา MAR ไมไ่ด้ เพราะเราไม่สามารถหาค่า recall ได้ก่อนเลย

Non-binary relevant

  1. บอกค่าความ relevant เป็นเปอร์เซนท์ ทำให้จัดลำดับได้

Cumulative Gain

  1. ค่า cg มีข้อเสียคือยังไม่สนใจตำแหน่งของเอกสารที่ relevant

Discounting Based on Position

  1. คล้ายๆ cg แต่มีการสนใจตำแหน่งของเอสารที่ relevant ด้วย

Ideal discounted comulative gain (IDCG)

  1. คือเป็นค่า ideal โดยที่ทุกเอกสารที่ relevant จะอยู่บนสุดทั้งหมด โดยเรียงลำดับใหม่ตามค่า gain แล้วค่อยคิด DCG ใหม่

Normailized DCG

  1. คือเอา DCG / IDCG โดยี่เรียงเอกสารตามเดิม

Issues with Relevance

Other factors to consider

  1. user effort
  1. ผู้ใช้พยายามใส่ query ให้ชัดเจนเองขนาดไหน

A/B Testing

  1. เช่นการเช็ค Clickthrough นั่นคือดูว่าผู้ใช้คลิก link ที่โชว์ขึ้นมามากน้อยแค่ไหน

Experimental setup for benchmarking

  1. คือเราจะกำหนด  set ของ doc ทีเหมือนๆกัน ให้แต่ละระบบก็จะทำงานเหมือนกัน แล้วใช้คนในการตัดสินว่าอันไหนดีกว่ากัน

Benchmarks

  1. ประกอบไปด้วย
  1. Set of standard document, query
  2. list ของ relevant document ของแต่ละ query
  1. Standard collection

Lecture 6

Relevance Feedback

  1. เมื่อก่อนจะมีการอนุญาตให้มีการทำ feedback กลับไปให้ระบบ ซึ่งปัจจุบันไม่ค่อยมีแล้ว
  2. ใช้ feedback เพื่อใช้ reformulate query ใหม่

Query reformulation

  1. Query expansion: เพิ่มคำเข้าไปใน relevant doc
  2. Term reweighting: ให้น้ำหนักเพิ่มเข้าไปให้กับเทอม

Query reformulation for VSR

  1. เพิ่ม vector ของ relevant เพิ่มเข้าไป
  2. หรือลด vector ของ irrelevant ออก

Optimal Query

  1. เช่นในฐานข้อมูลเราไม่สามารถทราบได้ว่า relevant set ของเราคืออะไร
  2. แต่ถ้าสมมติว่าเรารู้ว่า relevant documents เป็น C จะมีสูตรอยู่

Evaluating feedback

Residual collection: รอบแรกติ๊กอะไรออกไป รอบสองเอาอันนั้นออกไป (user ตัดสินไปแล้ว)

เมื่อตัดข้อมูลที่ทำ feedback ออกไปแล้ว อาจจะทำให้ recall/precision ลดลงเมื่อเทียบกับตอนที่ยังไม่ได้ทำ feedback เพราะ relevant documents จะถูกเอาออกไป

Why is feedback not widely used

  1. ในพวก ไฟฟ้า/Mechanic จะทำกันเยอะ เพราะจะช่วยปรับปรุงระบบให้ stable มากขึ้น
  2. แต่ทางด้าน search engine นี้จะไม่ทำ เพราะสร้างความยุ่งยากให้กับผู้ใช้

Pseudo feedback

  1. user ไม่ต้องทำ แต่ระบบจะ assume ว่า top K rank จะเป็น relevant เลย แล้วก็เอาไป reformulate

Thesaurus

  1. คือรวมพวก คำ synnonym
  2. เอามาใช้ประกอบได้
  3. เพิ่ม พำแฟสส
  4. อาจจะทำให้ ค่า precision ลดลง เพราะจะมีพวกคำกำกวม ambiguous terms

Wordnet

  1. เก็บรวบรวมความหมายของความสัมพันธ์ระหว่างคำ
  2. เช่น         Antonym: font – back

Attribute: benevolence – good

Statistical Thesaurus

  1. จากปัญหา thesaurus จำกัดอยู่ที่บางภาษาใช้ไม่ได้ง่าย
  2. เลยใช้การค้นหาคำที่พบคู่กันในแต่ละ document  เช่นอยากหา thesaurus ของคำว่า computer  ก็จะกวาดหาไปทุก document (Global analysis) เลยว่าคำไหนปรากฏพร้อมกับ computer บ่อยที่สุด
  3. ถ้าเป็น Local analysis ก็จะเอามาหาเฉพาะ document rank แรกๆ

Metric correlation matrix

  1. คือนอกจากจะหาคำที่พบพร้อมกันในแต่ละ  Document แล้ว ยังใช้ระยะห่างของคู่ที่เจอมาคำนวณด้วย เพราะถ้าอยู่ไกลก็จะยิ่งมีความสำคัญน้อยลง

Problem of Global analysis

  1. มีปัญหาของคำกำกวม (คำที่มีหลายความหมายในแต่ละบริบท)

Automatic local analysis

  1. จะพิจารณาเฉพาะ top-rank document เท่านั้น
  2. ลดความกำกวม โดยพิจารณาเฉพาะ relevant document

Global VS Local

  1. Global ทำที่ system development time คือทำเตรียมไว้ล่วงหน้าได้: user ใช้เวลาน้อย
  2. Local ทำที่ run time: user ใช้เวลามาก
  3. แต่ Local มักจะให้ผลที่ดีกว่า

สรุปแล้ว

  1. การทำ Expansion conclusion จะเพิ่ม recall แต่มักจะลด precision

Lecture 7

Web Search:

Tim Berners-Lee

        ผู้คิดค้นและเขียน Proposal เกี่ยวกับ WWW

Challanges for IR

  1. Volatile[f] data: มีการเปลี่ยนแปลงตลอดเวลา
  2. Unstructured and Redundant Data: ไม่มีโครงสร้างที่แน่นอน + ข้อมูลซ้ำซ้อนเยอะ จากการ copy + paste

Midterm Test

- เครื่องคิดเลข ไม่โปรแกรม

- A4 1 แผ่น 2 หน้า เขียนด้วยลายมือตัวเอง

Lecture 8

Restricting Spidering

        Robot exclusion: ข้อตกลงที่จะให้ Robot เข้ามาเก็บข้อมูล เพราะถ้าเข้ามาบ่อยเกินไปจะทำให้เว็ปนั้นๆเสีย Bandwidth ไป(เพิ่ม cost)

Breadth-first search

  1. ทำ Thread ได้ แต่จะต้องเปลือง memory * ปกติใช้วิธีนี้

Dept-first search

  1. แบ่งเป็น Thread ไม่ได้ แต่ไม่เปลือง memory ละก็เร็วกว่า

Query Strategy

  1. Heuristic: การทำแบบมีทิศทาง คือไปหาลิ้งที่เกี่ยวข้องกันก่อน

Link Extraction

  1. เก็บ Link ต่างๆ โดยอาจจะเป็น Relative path ด้วย

URL Syntax

การจัดการ URL

  1. พวก Slash (/) หลังสุดจะตัดออก
  2. พวก #abc (Anchor) ก็ต้องเอาออกด้วย

Anchor

  1. บาง search engine จะทำ ดรรชนีสำหรับ Anchor ไว้เลย เพราะคิดว่าเป็นส่วนที่สำคัญ
  2. เพิ่ม recall

Robot Exclusion

  1. คือข้อตกลงระหว่างผู้สร้างเว็ปและเจ้าของ Robot
  2. - Robot Exclusion Protocol
  3. - Robots META tag

Robot Exclusion Protocol

  1. ผู้สร้างเว็ปจะใส่ไฟล์ robots.txt ไว้ที่ root directory เพื่อบอกว่า Robot ตัวไหน สามารถไปเก็บข้อมูลที่ directory ไหนได้

Robot Exclusion Issue

  1. Meta tag จะใช้น้อยกว่า robots.txt
  2. Robot ต้องทำตามมาตรฐานต่างๆ

Multi-Threaded Spidering

  1. เว็ปเพจบนโลกมีอยู่มหาศาล ถ้าอยากให้ Spider ไปเก็บข้อมูลมาได้ทุกๆเว็ป ต้องมีการแบ่ง Spider หลายๆตัวและคอมพิวเตอร์หลายๆเครื่องช่วยกัน

Topic-Directed Spider

  1. การจะ search เว็ปที่ปรากฏคำหรือหัวข้อที่ป้อนให้ ต้องดูว่า page นั้นๆมีคำนี้ปรากฏหรือไม่ แล้ว link ที่ต่อจาก page นั้นมีหรือไม่ ถ้าไม่มีก็ต้องรีบตัดทั้ง page นั้นรวมถึง link หลังจากนั้นออกไป

Link-Directed Spidering

  1. Hub score คือ เช่น สนามบินสุวรรณภูมิ เป็น hub ที่ทำให้เราสามารถไปประเทศต่างๆได้ ในทางเว็ป ถ้ามี hub score มากๆ แสดงว่าเว็ปนี้สามารถนำพาเราไปหาข้อมูลที่น่าเชื่อถือได้
  2. Authorities คือต้องดูความ popular ของ page ว่าเพจนั้นๆน่าเชื่อถือแค่ไหน

Keep Spidered Page Up To Date

  1. เว็ปทั่วไปจะเปลี่ยนไปมาตลอดเวลา แต่บางเว็ปก็จะนานๆอัพเดทที หรือบางเว็ปอัพเดททุกๆวัน
  2. ต้องมีการเก็บข้อมูลเป็นรอบๆ
  1. อาจจะมีการใส่ tag ไปใน header เพื่อบอกว่า page นี้มีอัพเดทล่าสุดเมื่อไหร่
  2. อาจใช้วิธีการที่ ปีแรก เก็บทุกๆเว็ปเดือนละครั้ง แล้วดูความเปลี่ยนแปลง
  3. ในปีต่อๆไปอาจจะเอาผลที่ได้จากการเรียนรู้ในปีก่อนมาคำนวนใหม่ เพื่อเพิ่ม หรือลดช่วงเวลาที่จะเก็บเว็ปนั้นๆ

Lecture 9

Web graph

  1. ใช้กราฟเพราะกราฟเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพมาก

Web graph considerations

  1. ปกติเราจะมองเป็น Directed graph แต่ จะมองให้เป็น undirected ก็ได้
  2. กราฟจะเป็น Dynamic มากๆ

Why web graph

  1. เป็นตัวอย่างที่ดีของโครงสร้างข้อมูลขนาดใหญ่
  2. เป็น Dynamic สูง
  3. ช่วยแก้ปัญหาอื่นๆที่สามารถใช้กราฟแก้ปัญหาได้
  4. ทำให้รู้ความสำคัญของ web page นั้นๆ ว่ามีการเชื่อมโยงอย่างไรบ้าง
  5. ช่วยเพิ่มประสิทธิภาพให้กับการสืบค้น
  6. สามารถเรียนรู้การเดินทางภายในกราฟของผู้ใช้ เอามาวิเคราะห์ได้

Statistic of Interest (ข้อมูลที่น่าสนใจ)

  1. ขนาดและการเชื่อมโยงของกราฟ
  2. แต่ละเว็ปไซต์มีเว็ปเพจกี่เพจ
  3. จำนวน link เชื่อมโยงเข้าออกของแต่ละไซต์
  4. โดยเฉลี่ยแล้ว ในกราฟมี shortest paht เท่าไหร่

Math: Power law

  1. รูปแบบการกระจายตัวที่เกิดขึ้นทั่วไป
  2. ข้อมูลนึง เป็นจำนวนเท่า ของอีกอย่างนึง
  3. เช่น คนรายได้น้อยมีปริมาณเป็น….เท่า ของคนที่มีรายได้เยอะ

Scale-free property

  1. คุณลักษณะเด่นของ Power law
  2. ไม่สนใจขนาด
  3. เป็นการอนุมานว่า ถ้ามีข้อมูลอยู่ชุดนึง ถ้าพบว่าชุดนี้มีการกระจายตัวแบบ Power law เราจะอนุมาว่าข้อมูลขนาดใหญ่กว่า หรือขนาดใดๆก็ตามจะเปป็น Power law ด้วย

Family of power law

  1. Parento
  1. 20% แรก จะเป็น 80% ของทั้งหมด (ตามกราฟ)
  1. Zifpf
  1. ความถี่ของคำแต่ละคำ จะเป็นส่วนกลับของ Rank ในตารางความถี่

Example of Networks with Power Law DIstribution

  1. Citation Network: จำนวน reference อ้างอิง ในแต่ละบทความ

Implication for web

  1. 10 fold… ถ้ากราฟใหญ๋ขึ้น 10 เท่า จะต้องกระโดดเพิ่มขึ้นเฉลี่ย 2 hop

Lecture10

Link Analysis

  1. เกิดปัญหาเพราะ Text ธรรมดาสามารถโกงได้ง่าย

Hyperlinks and algorithm

  1. การที่มีลิ้งชี้ไปที่ปลายทาง หมายความว่าต้องมีความสัมพันธ์อะไรบางอย่าง
  2. เว็ปเพจที่ถูกลิ้งถึงมาก น่าจะเป็นเว็ปที่ให้ข้อมูลได้ดี

The web as a directed graph

  1. เขียนแทนเว็ปเพจต่างๆด้วย directed graph
  2. การที่ A มีการเชื่อมโยงไปที่ B แสดงว่า A และ B มีความเกี่ยวข้องกัน
  3. Anchor ที่เป็น Text ก็ควรจะมีความเกี่ยวข้องกับเว็ปเพจปลายทางนั้นๆด้วย

Bibliometrics: Citation Analysis

  1. บทความต่างๆมักมีการอ้างอิงถึงบทความอื่นๆ เหมือนเป็นกราฟอย่างหนึ่ง
  2. กราฟที่ได้สามารถเอามาวิเคราะห์ similarity ต่อได้

Bibliometrics

  1. การวัด similarity ของบทความ
  2. Bibliographic coupling  เป็นมาตรวัดความเหมือนของบทความ โดยวัดว่ามีการอ้างถึงบทความอื่นอะไรบ้าง <-ถ้า2บทความอ้างถึงบทความเดียวกัน แสดงว่า 2บทความนี้น่าจะมีความใกล้เคียงกัน
  3. Co-citation บทความ 2 บทความที่ถูกอ้างถึงโดยบทความเดียวกัน
  4. Impact factor เป็นมาตรในการวัดความสำคัญ โดยพิจารณาว่าบทความนี้ถูกอ้างอิงถึงมากน้อยแค่ไหน

Citation VS Hyperlinks

  1. ลิ้งส่วนใหญ่จะเป็น navigational เช่น home, about us, contact us ในบทความไม่เป็นแบบนั้น
  2. ลิ้งจะไม่มีใครมาพิจารณาว่าดีไม่ดี แต่บทความจะมีการพิจารณาก่อนแล้ว
  3. ปกติแล้วเว็ปต่างๆจะไม่ลิ้งต่อไปยังเว็ปคู่แข่ง
  4. บทความก่อนที่จะถูกตีพิมพ์จะต้องถูกพิจารณาก่อน โดยกลุ่มคนกลุ่มหนึ่ง (peer-review)

Ranking the web

  1. Query dependence เป็นการคำนวนโดยดูจาก query ของผู้สช้ (Online analyais) เช่น HIT
  2. Query Independence ไม่สนใจว่า query ของผู้ใช้เป็นอะไร แต่จำคำนวนค่าความสำคัญของเพจก่อนได้ (Offline analysis) เช่น PageRank algorithm

HITS

  1. วิเคราะห์ web graph บางส่วน โดนสนใจเฉพาะส่วนที่มีความเกี่ยวข้องกันโดยเนื้อหา จะคำนวนอยู่ 2 ค่า คือ hubs และ authorities
  2. Hub page: เว็ปเพจที่มีลิ้งชี้ออกไป
  3. Authorities page: เว็ปเพจที่มีลิ้งชี้เข้าหา
  4. Hub ที่ดี มักจะมีลิ้งชี้ไปยัง authorities ที่ดี
  5. authorities ที่ดี ต้องถูกชี้ด้วย hub ที่ดี
  6. Hub ที่ดี เหมือนกับสนามบิน ที่มีเส้นทางไปประเทศดังๆในโลก
  7. Hub ที่ดีน้อย เหมือนกับสนามบิินที่มีเส้นทางไปประเทศไม่ดัง
  8. เป็น Online analysis ดังนั้นต้องสร้าง sub graph ตอนที่ผู้ใช้ใส่ query เลย

PageRank

  1. ไม่ได้คำนวณทั้ง Hub, Authorities
  2. สนในกราฟทั้งหมด ไม่ใช่แค่ subgraph
  3. ดูแต่ Authorities
  4. Row-sthochastic matrix -> ทุกแถวมีผลรวม= 1

Rank Leak

  1. เว็ปที่ไม่มีลิ้งออกไปข้างนอก -> “dangling node”
  2. ทำให้เกิดปัญหาว่าไม่ใช่ row-stochastic
  3. แก้ปัญหาโดยสร้างลิ้งกลับไปให้กับทุกๆ node เลย

Rank sink

  1. มีแต่ลิ้งไปมากันในเพจกลุ่มๆนึง โดยที่ไม่มีออกนอกเลย

Lecture 11

WEB Spam

Search engines direct traffic

  1. web referrals
  1. ตรงๆ หรือจาก bookmark
  2. จาก link อื่นในเว็ปต่างๆ
  3. SE referral (search engine) จาก search engine หรือ พวกโฆษณาเช่น adword, adsense
  1. 1ใน3 ของลูกค้าที่เข้ามาในเว็ปได้มาจาก SE referral

Ways to increase SE referrals

  1. แรกๆมีซื้อขาย Keyword / ขายโฆษณา
  2. เพิ่ม ranking ให้เว็ปตัวเองโดย ทำ content ให้ดี / GAME the system : ทำ SEO
  3. SEO
  1. some are ethical (White hat)
  2. some are not

Defining web spam

  1. Definition:
  1. เว็ปเพจที่ถูกสร้างขึ้นมาเพื่อที่จะทำ traffic บน search engine ให้มากๆ

Why web spam is bad

  1. Bad for user
  1. ผู้ใช้ไม่ได้ข้อมูลที่พอใจ
  2. ลำคาญจนเลิกใช้ search engine
  1. Bad for search engines
  1. burn crawling bandwidth: เสีย bandwidth ในการ crawling
  2. ranking result เพี้ยนไป

Detecting web spam

  1. Spam detection ทำให้เป็น classification problem
  1. ให้ความรู้กับ bot  โดยให้ feature ของ web spam
  1. ใช้ automatic classifier
  1. supervise learning : สอนโดยให้ตัวอย่าง
  1. salient features
  1. ต้องเข้าใจ spamming techniques ต่างๆก่อน
  2. แต่เรื่องพวกนี้เป็น Alchemy: เล่นแร่แปรธาตุ ไม่ใช่ science

Keyword stuffing

  1. Search engine อย่างน้อยต้อง return page ที่มีคำ query อยู่
  2. จะเพิ่ม SE referral ก็มีวิธีง่ายๆคือ ยัดคำเข้าไปให้เยอะๆ
  1. ทำด้วยมือ
  2. ทำด้วย machine: คือถ้ารู้ว่า มีคน search ด้วยคำว่าอะไรมากๆ ก็เอาพวกนั้นใส่ใน page ซะ

Features identifying synthetic content

  1. average word length
  1. ประมาณ 5 character        

Content repurposing

  1. ตัด content จากเว็ปเพจต่างๆมารวมๆกัน
  2. ตัด snippet มาแปะๆ

Link based ranking

  1. search engine ทั่วไปใช้ page rank

Link spam

  1. หาลิ้งไปหา เพจเราให้มากๆ
  1. ทำ link farm ในเว็ปอื่นๆ
  2. อาจจะมีการแลกเปลี่ยน link กับเพจ partner

Features identifying link spam

  1. มี link เยอะๆจากเพจที่มี rank ต่ำ

Cloaking

  1. หลอก bot

QUIZ next week

web crawling

  1. คืออะไร ทำยังไง มีอะไรบ้าง

web graph

  1. ให้กราฟมา หา page rank แต่ละ node
  2. หาค่า authority

link analysis

web spam

  1. ทำทำไม มีจุดประสงค์อะไร  detect ยังไง

[a]Nuttapoom Amornpashara:

ออกสอบด้วย

[b]Nuttapoom Amornpashara:

vector space retrieval

[c]Nuttapoom Amornpashara:

ชื่อพรรค

[d]Nuttapoom Amornpashara:

เป็น n, adj

[e]Nuttapoom Amornpashara:

หนึ่งคำมีหลายความหมาย

[f]Nuttapoom Amornpashara:

Dynamic

 

 

Comments are closed.