Sea Sand Song

คราวก่อนที่เขียนเรื่อง Recommendation Systems ไป ไม่ได้เน้นถึงหลักการทำงานของมันซักเท่าไหร่ พอดีเดือนนี้มีงานของวิชา Decision Support Systems และผมเลือกเรื่องนี้มาทำเป็นรายงาน ก็เลยเป็นโอกาสดี มาเขียนลง blog ซะ

หนังสือเกี่ยวกับเรื่องระบบ 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 ก็แนะนำให้หาหนังสือเล่มนี้มาอ่าน