วันพุธที่ 23 กันยายน พ.ศ. 2552

Collaborative filtering

หนังสือเกี่ยวกับเรื่องระบบ recommendation systems ที่ค่อนข้างดังคือ Programming Collective Intelligence ของ Toby Segaran และนอกจากนั้นก็ยังมี paper อีกมากมายบนอินเทอร์เนต

ระบบนี้มีหลักการทำงานพื้นฐานคือการใช้ Collaborative filtering (เป็นการกั่นกรองที่อาศัยความร่วมมือกัน) ซึ่งเป็นหลักการที่ไม่ยาก สมมุติว่าระบบต้องการแนะนำหนังให้นายเอก ระบบก็จะเริ่มจากการดึงข้อมูลคะแนนเก่าๆที่นายเอกให้คะแนนหนังเอาไว้ มาเปรียบเทียบกับคนอื่นๆในระบบเพื่อหาคนที่มีความชอบคล้ายคลึงกับนายเอก เมื่อได้กลุ่มคนที่มีความชอบคล้ายคลึงกันแล้ว ก็ดูว่าคนกลุ่มนั้นชอบหนังอะไรที่นายเอกยังไม่ได้ดู และเลือกเอาหนังเหล่านั้นมาแนะนำให้นายเอก

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

การหาคนที่มีความคล้ายคลึงกับเรานั้นสามารถทำได้หลายวิธี แต่ในหนังสือกล่าวเอาไว้อยู่ 2 วิธีคือ Euclidean Distance Score กับ Pearson Correlation Score

วิธี Euclidean Distance Score นั่นคือการเอาหนังแต่ละเรื่องมาวาดเป็นแกนของกราฟ จากนั้นก็ลงจุดของผู้ใช้แต่ละคนลงไปตามคะแนนที่แต่ละคนให้ไว้ และวัดระยะห่างระหว่างจุดของผู้ใช้เหล่านั้น ภาพข้างล่างคือตัวอย่างของการใช้วิธี Euclidean Distance ในการหาความเหมือนโดยอ้างอิงจากข้อมูลด้านบน กราฟนี้วาดแค่ในระนาบ 2 มิติ ซึ่งจริงๆแล้วถ้ามีหนังที่คนสองคนให้คะแนน n เรื่อง กราฟก็จะต้องมี n มิติ (ในระบบอาจมีหนัง 1000 เรื่อง แต่ถ้ามีหนังแค่ 100 เรื่องที่คนสองคนนี้ให้คะแนนแล้ว กราฟก็จะมีแค่ 100 มิติ)

จะเห็นว่าระหว่างจุดของ Mike กับ John จะใกล้กันมากกว่า Mike กับ Anna ซึ่งก็หมายความว่า Mike กับ John นั้นมีความเหมือนกันมากกว่า Mike กับ Anna ค่าตัวเลขความเหมือนที่ได้ก็คือค่าระยะห่างจริงๆในกราฟนี้ ระหว่าง Mike กับ John นั่นคือ 1 และระหว่าง Mike กับ Anna นั่นคือ 3.61 (รากที่สองของ 2^2 + 3^2 — การหาความยาวด้านของสามเหลี่ยมด้านเท่า)

สูตรที่ใช้คือ

p และ q จะแทนคนสองคนที่ต้องการหาค่าความเหมือน ค่าที่ได้ยิ่งมากแสดงว่ายิ่งไม่เหมือน เวลาใช้งานจริง ส่วนใหญ่แล้วเค้าจะกลับค่านิดหน่อยเพื่อให้ค่ายิ่งมากแสดงว่ายิ่งเหมือนแทน วิธีกลับค่าก็ใช้สูตรนี้ โดย similarity คือผลลัพธ์ที่ได้จากสูตรที่แล้ว

โดยผลลัพธ์สุดท้ายที่ได้มาคือค่าระหว่าง เกือบๆ 0 กับ 1 ซึ่งถ้าได้ค่า 1 แสดงว่าคะแนนของคนสองคนเหมือนกันทุกประการ (ที่เขียนว่าค่าเกือบๆ 0 นั้นก็เพราะไม่ว่าจะหารยังไงมันก็ไม่ได้ค่า 0 ยกเว้นเป็นค่า infinity)

วิธี Pearson Correlation Score จะต่างออกไปโดยที่จะหาค่าความเหมือนโดยใช้ค่า Correlation Coefficient ถ้าใครที่เรียนสถิติมาก็คงจะคุ้นเคยกับการหาค่านี้ ซึ่งเป็นการหาค่าความสัมพันธ์ระหว่างตัวแปร (ว่าเวลาตัวแปร 2 ตัวนั้นจะแปรผันตามกันหรือแปรผันตรงกันข้ามกันแค่ไหน หรือจะไม่เกี่ยวข้องกันเลย)

จากรูปจะเห็นเส้นประที่เรียกกันว่า trend line ซึ่งเป็นเส้นตรงที่จะให้ค่าใกล้เคียงกับทุกๆค่าบนกราฟมากที่สุด ยิ่งจุดแต่ละจุดเข้าใกล้เส้นประมากเท่าไหร่ ก็ยิ่งแสดงว่าคนสองคนมีความเหมือนกันมากขึ้นเท่านั้น ค่า Correlation Coefficient จะคำนวณออกมาได้จากสมการนี้

ซึ่งเป็นสมการการหาค่า Correlation Coefficient ทั่วๆไปตามหลักสถิติ ค่า่ที่ได้จะอยู่ในช่วง (-1) ถึง 1 ซึ่งถ้าได้ 1 แสดงว่าคนสองคนเหมือนกันทุกประการ (มันต้องเป็นคนๆเดียวกันแน่นอน ไม่ก็เป็นคู่ลิขิตแต่ชาติปางก่อน)

เมื่อเราได้รู้แล้วว่าคนสองคนมีความเหมือนกันแค่ไหน เราก็สามารถแนะนำหนังโดยอ้างอิงจากคนที่เหมือนกันได้ ตารางด้านล่างเป็นตัวอย่างการหาหนังแนะนำให้ Mike ซึ่งยังไม่ได้ดูเรื่อง Spiderman และ Babel

จะเห็นว่าเราจะเอาค่าความเหมือนของคนอื่นๆ มาคูณกับคะแนนที่คนนั้นให้ไว้ ยิ่งมีค่าความเหมือนมากเท่าไหร่ คะแนนที่คนๆนั้นให้ไว้ก็ยิ่งมีความสำคัญมากขึ้นเท่านั้น ผลลัพธ์ที่ได้ (4.601522843 และ 2.800761421) คือคะแนนที่ Mike น่าจะให้กับหนังเรื่องนั้น โดยคำนวณจากคนอื่น

ดูจากคะแนนก็เป็นที่แน่นอนว่าระบบต้องตัดสินใจแนะนำหนังเรื่อง Spiderman ให้ Mike แทนที่จะเป็นหนังเครียดๆอย่าง Babel

นี่เป็นแค่หลักพื้นฐานคร่าวๆเท่านั้น ในหนังสือเขียนไว้ได้ละเอียดกว่าและดีกว่า ใครที่สนใจเรื่อง Recommendation System ก็แนะนำให้หาหนังสือเล่มนี้มาอ่าน

ไม่มีความคิดเห็น:

แสดงความคิดเห็น

แสดงความคิดเห็น