มีอะไรอยู่ใน Google (PageRank)


อัปเดท : 8 มกราคม พ.ศ.2547 , แสดง : 18,938 , ความคิดเห็น : 6

ถ้าคุณคิดที่จะหาอะไรสักอย่างคุณคงต้องนึกถึง เวบเสิร์ชเอ็นจิ้น และคุณคงปฏิเสธไม่ได้ว่าเวบเสิร์ชเอ็นจิ้นที่อยู่ในใจคุณอันดับแรกคือ Google™ อาจเป็นเพราะ Google™ ค้นหาข้อมูลได้รวดเร็วตรงใจ และตัว Google™ เองมีคลังข้อมูลมหาศาลซึ่งเป็นจุดแข็งหนึ่งของ Google™ , Google™ ก่อตั้งโดย Larry Page, Sergey Brin ซึ่งทั้ง 2 ได้ร่วมกันสร้างระหว่างกำลังศึกษา ระบบใช้หลักการ Information Retrieval เทคนิค หลักการที่ใช้ในการจัดอันดับคือ เพจแรงค์ อัลกอริธึ่ม (PageRank algorithm)

 

หลักการของการคำนวณหาค่าเพจแรงค์ คือเวบเพจจะมีค่าเพจแรงค์สูง ถ้ามีเวบเพจอื่นที่อ้างอิง(Link)ถึงมันจำนวนมากๆ เช่น
ตัวอย่าง ผมใช้ Keyword คือ "java" ระหว่างค้นหาตัว Google™ เองมันก็จะค้นหาข้อมูลที่มันมีอยู่และต้องมีคำว่า "java" เป็นส่วนประกอบ ข้อมูลที่เพจแรงค์เจอจะเยอะมาก มันจะรู้ว่าอันไหนสำคัญที่สุด โดยพิจารณาจากลิงค์ภายในเวบเพจที่ค้นพบ โดยดูว่าเวบเพจไหนถูกอ้างถึงมากที่สุด จะถูกจัดอันดับเพื่อแสดงผล ซึ่งจากตัวอย่างผลที่ได้ลำดับแรกคือ "java.sun.com" ซึ่งถูกเวบเพจอื่นๆ อ้างถึงมากที่สุด เป็นต้น ในกรณีที่ผลการค้นหาเวบเพจที่ได้มีจำนวนน้อยมันก็ทำเช่นกัน

Notes. ถ้าเปรียบเทียบกับเวบเสิร์ชเอ็นจิ้น อื่นๆ ผลที่ได้ส่วนใหญ่มาจากการสุ่มแสดงผลซึ่งไม่ค่อยตรงใจหรือไม่ค่อยเกี่ยวข้องกัน

  
 

อย่างไรก็ตามเพจแรงค์ก็ยังคงมีข้อผิดผลาด เนื่องจากเวบเพจ บางคู่เกิดการอ้างอิงไปมาทำให้ค่าเพจแรงค์เพิ่มขึ้นเรื่อย ๆ ไม่สิ้นสุด(infinity) เรียกปัญหานี้ว่า Rank Sink การแก้ไขปัญหานี้จะใช้ฟังก์ชัน Rank Source โดยมันจะกำหนดค่าเริ่มต้นของเพจแรงค์(จากการคำนวณก่อนหน้า) และเมื่อการคำนวณของค่าเพจแรงค์ของเวบเพจใด ๆ แล้วพบว่าค่าที่ได้ มีค่ามากกว่าค่าเริ่มต้นของเพจแรงค์ มันก็ข้ามไปคำนวณเพจแรงค์ หน้าอื่นๆที่เหลือ และสิ้นสุดที่เวบเพจหน้าใดหน้าหนึ่ง (Converge)

จากข้อมูลอ้างอิง(ลิงค์ด้านล่าง) มีผลการเปรียบเทียบเพจแรงค์ เค้าบอกว่าระหว่างการคำนวณลิงค์ 332 ล้านลิงค์กับ 161 ล้าน ของผลที่ได้ ข้อมูลที่มี 332 ล้านลิงค์ คำนวณเสร็จภายใน 52 รอบของการคำนวณ และที่มี 161 ล้าน ลิงค์จะคำนวณเสร็จภายใน 45 รอบของการคำนวณ

อย่างไรก็ตาม ณ.เวลานี้เทคนิคนี้ดี,เร็วและคนยอมรับมากที่สุด ทางผู้พัฒนาเองก็ยังไม่หยุดนิ่ง ยังมีปัญหาอื่นๆให้แก้ เช่น ผลจากเพจแรงค์อัลกอริธึ่มพบว่าเวบเพจที่ลิงค์ไปเพจอื่นๆ ส่วนใหญ่มาจากเวบเพจเดิมๆ ผลการค้นหาที่ได้ไม่หลากหลายไม่ตรงใจเท่าที่ควร ผู้พัฒนาก็กำลังพัฒนา บล็อคแรงค์ (BlockRank) ว่ากันว่าเร็วกว่าเพจแรงค์ถึง 3 เท่า (ถ้ามีข้อมูลผมค่อยเขียนบทความเพิ่มเติมภายหลัง)

ด้วย Google™ สนับสนุน หรือทำงานได้เต็มที่กับภาษาอังกฤษเป็นหลัก ออกแบบโดยใช้หลักการ Information Retrieval เช่น ใน Keyword เจอคำว่า "is","am","are" หรือคำอื่น ๆที่ใช้บ่อย ๆ ในประโยคค้นหา มันจะไม่สนใจเลยจะตัดทิ้ง ตัวอย่าง Keyword "what is Java" มันจะไม่สนใจ "what" กับ "is" มันจะสนใจ "Java" เท่านั้น ผลที่ได้ จึงเหมือนกับป้อน Keyword "Java" คำเดียว เป็นต้น นอกจากนี้ยังมีเทคนิค Information Retrieval อื่น ๆ ที่ใช้ร่วมกัน ด้วยเหตผลนี้เมื่อนำมาใช้กับภาษาอื่น เช่นภาษาไทย ซึ่งมันไม่เข้าใจตัวภาษาทำผลที่ได้ไม่ค่อยจะตรงตามความต้องการ เช่นผมป้อน keyword ว่า "Java คือ" มันไม่เข้าใจคำว่า "คือ" มันจึงค้นหาทุกเวบเพจที่มีคำว่า "คือ" และ "Java" หรือมี "คือ","Java" อย่างใดอย่างหนึ่ง ต่อให้คุณเลือก "หน้าของ ประเทศไทย " ซึ่งคุณคงนึกออกว่าเวบเพจที่มีคำว่า "คือ" มีมากขนาดไหน และคงพอเดาออกว่าผลที่ได้เป็นอย่างไร แต่ผลการค้นหาจริงมันก็จำกัดเช่นจะค้นหามาแค่ 75 หน้าเป็นต้น

ทำใจเถอะครับ เราคนไทยไม่ได้สร้างเทคโนโลยีนี้เองก็ต้องยอมรับตรงนี้ หวังว่าสักวัน Google™ คงจะมาเรียนภาษาไทย เพื่อรู้จัก เข้าใจภาษาไทยมากขึ้น

ปล. ตอนแรกคิดว่าจะไม่ลงรายละเอียด แต่ก็ลงสักหน่อยดีกว่าเผื่อเห็นสูตร จะช่วยให้เข้าใจอะไรๆได้ดีขึ้น

PageRank Algorithm
เพจแรงค์เป็น อัลกอริธึ่ม ที่
Google™ ใช้ในการนับจำนวนของ เวบเพจ ที่เชื่อมไปยัง เวบเพจหนึ่งๆ และให้ค่าความสำคัญ (Score) ในรูป Scale ระหว่าง 0-10 ซึ่งไม่ได้เป็นการเพิ่มความสำคัญ แบบเชิงเส้น (Linear) แต่เป็นการเพิ่มแบบ Logarithm (Log N)

PageRank Algorithm
เพจแรงค์ อัลกอริธึ่ม ที่ใช้ในการคำนวณใน Google ที่อธิบายโดย Lawrence เวบเพจและ Sergey Brin คือ

PR(A) = (1-d) + d(PR(T1/C(T1) + … + PR(Tn)/C(Tn))

โดยที่
PR(A) คือเพจแรงค์ ของ เวบเพจ A
PR(Ti) คือเพจแรงค์ ของ Ti ที่ลิงค์มายังเวบเพจ A
C(Ti) คือ จำนวนของ Outbound ลิงค์ ของ Ti
d คือ Damping Factor มีค่า ระหว่าง 0-1

Note :
1. ค่าเฉลี่ยของเพจแรงค์ ของ เวบเพจทั้งหมด จะมีค่าเท่ากับ 1
2. เพจแรงค์ หรือ PR(A) จะคำนวณ โดยการใช้ Iterative Algorithm ซึ่งโดยทั่วไปจะประมาณ 100 ครั้ง

Example

กำหนดค่าเป็น d = 0.85
PR(A) = 0.15 + 0.85 PR(C)
PR(B) = 0.15 + 0.85 (PR(A)/2)
PR(C) = 0.15 + 0.85 (PR(A)/2 + PR(B) + PR(D))

หลังจากใช้เพจแรงค์ อัลกอริธึ่มจะได้ค่า PR ของแต่ละ เวบเพจดังนี้ (วนรอบเดียว)

PR(A) = 1.49
PR(B) = 0.78
PR(C) = 1.58
PR(D) = 0.15

The Iterative Calculation

กำหนดให้แต่ละ Page เริ่มต้นที่ค่า 1 ยกเว้น Page D มีค่า 0.15 เนื่องจากไม่มี Page อื่น Link มา

Iterative

PR(A)

PR(B)

PR(C)

PR(D)

0

1

1

1

0.15

1

1

0.575

1.225

0.15

2

1.19125

0.65628125

1.34162031

0.15

3

1.29037726

0.69841034

1.41955912

0.15

4

1.35662528

0.72656574

1.47164662

0.15

5

1.40089963

0.74538234

1.50649983

0.15

6

1.43052486

0.75797307

1.52975018

0.15

7

1.45028765

0.76637225

1.54528866

0.15

8

1.46349536

0.77198553

1.55571573

0.15

9

1.47235837

0.77575231

1.56264175

0.15

10

1.47824549

0.77285433

1.56727051

0.15

11

1.48217993

0.77992647

1.57036397

0.15

12

1.48480937

0.78104398

1.57243136

0.15

13

1.48656666

0.78179083

1.57381304

0.15

14

1.48774108

0.78228996

1.57473643

0.15

15

1.48852597

0.78262353

1.57535353

0.15

16

1.4890505

0.78284646

1.58001595

0.15

17

1.49301356

0.78453076

1.57888318

0.15

  
 

Effects on PageRank


1. The Effect Of Inbound Links
จำนวน Inbound ลิงค์มีผลต่อค่าเพจแรงค์สำหรับเวบเพจที่มี Inbound ลิงค์จากเวบเพจอื่นๆ จะมีค่า PageRank เพิ่มขึ้น

2. The Influence of Damping Factor
ถ้ากำหนดค่า Damping Factor สูงในขณะที่จำนวนของ Inbound ลิงค์เท่าเดิมจะทำให้ค่าเพจแรงค์ สูงขึ้น

3. The Effect of Outbound Links
สำหรับ เวบไซต์ หนึ่งๆ หากมี Outbound ลิงค์ไปยัง เวบไซต์ อื่นๆ จะทำให้ค่าเพจแรงค์ของเวบเพจต่างๆ ในเวบไซต์นั้นๆ เพิ่มขึ้น แต่ผลรวมของเพจแรงค์ ของทุกเวบเพจในเวบไซต์ทั้งหมดจะยังมีค่าเท่าเดิม

4. Dangling Links
คือ เวบเพจที่ไม่มี Outbound ลิ้งค์ไปยัง เวบเพจอื่นๆ ตัวอย่างเช่น เวบเพจที่เป็น PDF หรือ Word files ในการคำนวณ PageRank จะแบ่งการคำนวณเป็น 2 ครั้ง โดยตัด Web เวบเพจที่เป็น Dangling ลิงค์ออกไปก่อน ซึ่งจะไม่มีผลกระทบต่อผลรวมของค่า เพจแรงค์ ของเวบเพจทั้งหมด

5. The Effect of the Number of Pages
ถ้าจำนวน Pages ภายใน 1 เวบไซต์ (ที่ไม่มี Outbound ลิงค์ไปยัง เวบไซต์ อื่น) เพิ่มขึ้น 1 เวบเพจผลรวมของค่า PageRank ของทั้ง เวบไซต์ จะเพิ่มขึ้นอีก 1 สำหรับค่าเพจแรงค์ ของ เวบเพจภายใน เวบไซต์ ส่วนใหญ่จะลดลง แต่บางตัวอาจเพิ่มขึ้น ทั้งนี้ขึ้นอยู่กับโครงสร้างของ เวบไซต์

6. The Distribution of PageRank
การเพิ่ม Internal ลิงค์ของ เวบเพจหนึ่งๆ จะทำให้ค่าเพจแรงค์ ของแต่ละ เวบเพจนั้นๆ เพิ่มขึ้น

จบแค่นี้ก่อนนะครับ..ผมนำความรู้ความเข้าใจที่พอจะมีบ้าง หาเอกสารอ้างอิงพยายามกลั่นกรองเป็นตัวอักษร สำหรับเรื่องนี้ผมบอกตรงๆว่าเขียนยาก เพราะมีเรื่องเกี่ยวข้องเยอะ เช่น Information Retrieval, การเก็บข้อมูล,Caching ฯลฯ ผมเขียนแค่เบื้องต้น คิดว่าอ่านแล้วคงได้ประโยชน์ได้แนวความคิดไปบ้าง อย่างน้อยก็ได้คุยกับเพื่อนๆ ได้ ถ้าสนใจข้อมูลเพิ่มเติมก็ดูตามลิงค์ด้านล่างเลยครับ

ข้อมูลเพิ่มเติม

http://pr.efactory.de/e-pagerank-algorithm.shtml
http://www.seorank.com/Google-pagerank.htm
http://www.markhorrell.com/seo/pagerank.html

เขียนเพิ่มเติม : 08-01-2005

บังเอิญอ่านเจอข้อมูลของ Google อีกอย่างที่เรียกว่า PigeonRank (http://www.google.com/technology/pigeonrank.html) ซึ่งอ้างว่าเป็บเบื่องหลังความสำเร็จของ Google ผมเลยลองหาข้อมูลของ PigeonRank และอ่าน Forum จากหลายๆที่เข้าใจว่า PigeonRank เป็น Joke ในวัน April Fool's Day - 2002.(วันที่ฝรั่งโกหกกันได้โดยไม่ถือสากัน) ผมลองหาข้อมูลสนับสนุนว่าใช่หรือเปล่า ก็พบว่า ตอนที่ Larry Page, Sergey Brin ก่อตั้ง Google ไม่เคยกล่าวถึง PigeonRank เลยและในหน้า http://www.google.com/technology/pigeonrank.html ถ้าลองเปลี่ยนคำว่า "PigeonRank" เป็น "PageRank" ทั้งหมด แล้วลองอ่านดู มันก็คือ PageRank นี่เอง


ผู้เขียน/อ้างอิง : จักรกฤษณ์ แร่ทอง

เวบ/อินเตอร์เน็ตเทคโนโลยี

ความคิดเห็น/แนะนำ/ติชม/อื่นๆ

  • Bow [29 Oct 2004 , 08:51 PM]

    ช่วยเขียนเรื่อง PageRank ต่อด้วยนะครับ ท่าทางจะน่าสนใจ

  • pin [21 Jan 2005 , 05:19 PM]

    เรื่องนี้อ่านแล้วงง ความจริงแล้วมันเก่งทุกภาษามันอ่านได้ทั่วโลกนะ

  • deoinbox [28 Jan 2005 , 01:01 PM]

    ถึง K.pin ครับ ขอบคุณสำหรับ comment ครับ ที่ว่า Google เก่งทุกภาษามันอ่านก็ใช่ครับ (ไม่ใช่เพราะ Google เก่ง แต่เพราะ IE,OS และ เทคโนโลยีที่เกี่ยวข้องรองรับทุกภาษา) แต่ที่พูดถึงไม่ได้หมายความถึงการอ่านครับ ผมหมายถึงความเข้าใจ ของ Google ที่มีต่อตัวภาษานั้น ๆ

  • Joe [15 Mar 2005 , 02:41 PM]

    แล้วมีวิธีอะไรบ้างที่เราจะทำการโปรโมท website ของเราให้เวลา ค้นหาจาก Keyword แล้วขึ้นมาอยู่บน Top 10 ของ Google เพราะทำการค้นหาที่ไรก็เป็น website ดังๆ ขึ้นก่อนทุกที่ meta keyword ก็ใส่แล้ว จะทำอย่างไรครับ...ช่วยหน่อย

  • KT [10 Oct 2005 , 08:57 PM]

    เห็นด้วยกับคุณ bow ตอนนี้งานผมต้องการมากเลย เรื่อง PageRank

  • jjj [07 ธ.ค. 2553 , 12:13 AM]

    รูปผิดรึเปล่าอะคับ จากตัวอย่างของรูปกับตัวอย่างของสมการที่ยกมา เพจ d น่าจะลิ้งไปยัง เพจ c นะครับ