RBO กับ Kendall Tau เพื่อเปรียบเทียบรายการจัดอันดับ

ในขณะที่แก้ไขปัญหาการจัดอันดับ (การจัดอันดับฟีด การจัดอันดับการค้นหา ฯลฯ) ฉันมักจะพบกับสถานการณ์เมื่อต้องเปรียบเทียบรายการจัดอันดับที่สร้างขึ้นโดยระบบที่แยกจากกัน เช่น การผลิตกับการทดสอบ A/B ความจำเป็นในการเปรียบเทียบรายการจัดอันดับสองรายการขึ้นไปนั้นเป็นเรื่องปกติมากกว่าที่คุณคิด ลองพิจารณาตัวอย่างง่ายๆ: คุณและเพื่อนสองสามคนตัดสินใจแสดงรายการตอนที่คุณชื่นชอบ 5 ตอนของซีรีส์ทางโทรทัศน์ยอดนิยมเรื่อง "FRIENDS" ทุกคนเขียนชื่อตอนที่ชอบที่สุด 5 ตอน โดยรายการแรกหมายถึงตอนที่ชอบมากที่สุด และรายการสุดท้ายหมายถึงตอนที่ชอบน้อยที่สุด ตอนนี้คุณแต่ละคนอาจสงสัยว่ารายการของคุณเหมือนหรือแตกต่างกับเพื่อนอีกสองคนในห้องอย่างไร

เราจะเปรียบเทียบรายการเหล่านี้อย่างไร อย่างเป็นทางการ รายการจัดอันดับเหล่านี้เรียกว่าการจัดอันดับที่ ไม่สมบูรณ์ เนื่องจากไม่ได้จัดอันดับตอนทั้งหมดจาก "FRIENDS" และจะเลือกเฉพาะ 5 อันดับแรกแทน เราจะหารือเกี่ยวกับแนวทางบางประการที่เป็นที่นิยมและค่อนข้างธรรมดาใน การแก้ปัญหาเฉพาะนี้

วิธีที่ 1: เคนดัลล์เทา

การวัด Kendall Tau หรือที่เรียกว่า Kendall's Correlation เป็นวิธีการทั่วไปที่ใช้ในการตรวจสอบว่ารายการที่มีการจัดอันดับสองรายการสอดคล้องกันหรือไม่

ความสัมพันธ์ของเคนดัลล์ (𝛕) สามารถคำนวณได้โดยการนับจำนวนคู่ที่สอดคล้องกัน (C) และจำนวนคู่ที่ไม่ลงรอยกัน (D) ก่อน กล่าวกันว่าคู่จะสอดคล้องกันหากปรากฏอยู่ในลำดับเดียวกันในรายการจัดอันดับ

M = (C -D)

𝛕 = M / (C + D)

จำนวนคู่สูงสุดที่แตกต่างกันระหว่างสองรายการจัดอันดับที่เชื่อมต่อกันในตัวอย่างของเรา (รูปที่ 2) คือ = 5 เลือก 2 = ½ * (5 * (5–1)) = 10 หากทุกคู่สอดคล้องกัน C = 10 และ D = 0 นั่นหมายถึง max(𝛕) = (10–0) / (10+0) = 1 หากทุกคู่ไม่ลงรอยกัน ดังนั้น C = 0 และ D = 10 นั่นหมายถึง min(𝛕) = (0–10 ) / (0+10) = -1

มาคำนวณมูลค่าที่แท้จริงของ 𝛕 กัน

คู่ที่สอดคล้องกัน:

(S6E17, S2E10) (S6E17, S3E24) (S6E17, S3E25) (S6E17, S3E15) (S2E10, S3E24) (S2E10, S3E25) (S2E10, S3E15) (S3E24, S3E25)

คู่ที่ไม่ลงรอยกัน:

(S3E24, S3E15) (S3E25, S3E15)

𝛕 = (8–2) / (8 + 2) = 0.6

การตีความของ Kendall Tau

โปรดสังเกตว่าค่าสูงสุดและต่ำสุดที่ 𝛕 สามารถรับได้คือ +1 และ -1 ตามลำดับ +1 หมายถึงตกลงโดยสมบูรณ์ และ -1 หมายถึงไม่เห็นด้วยโดยสิ้นเชิง ค่า 0 หมายความว่าไม่มีความสัมพันธ์กันระหว่างการจัดอันดับ ค่า 0.6 ที่เราคำนวณสำหรับรูปที่ 2 แสดงให้เราเห็นว่าการจัดอันดับมีความสัมพันธ์กันในระดับปานกลาง

อีกวิธีในการตีความ 𝛕 ก็คือสถิติ M คือจำนวนการแลกเปลี่ยนคู่ที่อยู่ติดกัน ซึ่งจำเป็นในการจัดเรียงรายการจัดอันดับหนึ่งให้คล้ายคลึงกับอีกรายการหนึ่ง สิ่งนี้ทำให้คุณนึกถึงอัลกอริธึมการเรียงลำดับยอดนิยมหรือไม่? การเรียงลำดับฟองแน่นอน!

คุณยังสามารถทดสอบนัยสำคัญทางสถิติของเมตริก Kendall Tau [8] ได้

การนำไปปฏิบัติ

Kendall Tau ที่แก้ไขแล้วสามารถนำไปใช้กับการจัดอันดับที่มีความสัมพันธ์กัน เช่น หากบุคคลนั้นชอบตอนหนึ่งมากจนแสดงรายการตอนเดียวกันในช่องทั้ง 3 ช่องจาก 3 อันดับแรกในรายการ การเสมอกันในการจัดอันดับไม่ใช่เรื่องแปลก ฉันปรับใช้อัลกอริทึม O(NLogN) Kendall Tau แบบกำหนดเองที่จัดการความสัมพันธ์ที่ Netflix เมื่อเร็วๆ นี้ นี่คือการใช้งานอัลกอริธึมแบบโอเพ่นซอร์สบางส่วน:

• [Java] Apache คอมมอนส์ ไลบรารี่
• [Python] SciPy ไลบรารี่

ประเพณี

Kendall Tau เป็นวิธีการยอดนิยมที่ใช้ในงานเรียกค้นข้อมูล เช่น โปรแกรมค้นหา และระบบแนะนำ บริษัทต่างๆ เช่น Yahoo [1] และ Microsoft [3] ได้ใช้วิธีนี้กับกรณีการใช้งานต่างๆ

ข้อเสีย

แม้ว่า Kendall Tau จะเป็นตัวชี้วัดความสัมพันธ์ของอันดับยอดนิยม แต่ก็มีข้อเสีย:

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

เพื่อแสดงให้เห็นข้อเสียเหล่านี้ ให้พิจารณารายการจัดอันดับของบุคคลที่ 1 กับบุคคลที่ 2 จากรูปที่ 1 โปรดสังเกตว่ามีเพียงสองตอนที่เหมือนกันระหว่างสองรายการ: S2E10 และ S3E24 ไม่สามารถใช้ความสัมพันธ์ของ Kendall กับรายการเหล่านี้ได้เนื่องจากรายการเหล่านี้ไม่เหมือนกัน (ไม่มีรายการเดียวกันทุกประการ) วิธีหนึ่งที่เป็นไปได้ในการใช้ Kendall's Correlation กับทั้งสองรายการนี้คือการแทนที่รายการที่ไม่มีอยู่ในทั้งสองรายการด้วยอักขระพิเศษ '#' จากนั้น อันดับบุคคลที่ 1 จะกลายเป็น “# S2E10 # S3E24 #” และอันดับบุคคลที่ 2 จะกลายเป็น “# S2E10 # # S3E24” การคำนวณ 𝛕 สำหรับรายการที่แปลงแล้วเหล่านี้จะส่งผลให้มีค่า 1.0 แม้ว่า S3E24 จะอยู่ที่ตำแหน่ง 3 ในรายการของบุคคลที่ 1 และอยู่ที่ตำแหน่ง 4 ในรายการของบุคคลที่ 2 (ดัชนีตามศูนย์) ค่า 1.0 นี้แสดงถึงข้อตกลงที่สมบูรณ์แบบระหว่างสองรายการ ซึ่งเห็นได้ชัดว่าไม่เป็นความจริงในที่นี้

วิธีที่ 2: อันดับการทับซ้อนเอนเอียง (RBO)

ต่างจากการวัดระยะทาง Kendall Tau RBO เป็นการวัดความคล้ายคลึงกัน RBO แก้ปัญหา 3 ข้อเสียที่พบใน Kendall Tau โดยใช้น้ำหนักสำหรับแต่ละตำแหน่ง ตุ้มน้ำหนักได้มาจากอนุกรมแบบลู่เข้า สมการด้านล่างอธิบาย RBO ของสองรายการที่มีอันดับไม่สิ้นสุด S และ T:

พารามิเตอร์ p เป็นพารามิเตอร์ที่ปรับได้ในช่วง (0, 1) ที่สามารถใช้เพื่อกำหนดการมีส่วนร่วมของอันดับสูงสุด d ต่อค่าสุดท้ายของความคล้ายคลึงกันของ RBO วัด. โปรดทราบว่าพจน์การรวมของ SUM(p^(d-1)) จะมาบรรจบกันเนื่องจากเป็นอนุกรมเรขาคณิต ผลรวมกำหนดไว้ที่ 1/(1-p) และเนื่องจาก 0 ‹ p ‹ 1 ผลรวมจึงมีจำกัด

หากต้องการได้รับคะแนน RBO เดี่ยว เราสามารถคาดการณ์ได้จากข้อมูลที่มีอยู่ โดยสมมติว่าข้อตกลงที่เห็นในระดับลึก k ดำเนินต่อไปอย่างไม่มีกำหนดในสองรายการ คะแนน RBO เดี่ยวสามารถคำนวณได้โดยใช้:

นี่คือการใช้งานการวัด RBO คะแนนเดี่ยวที่คาดการณ์ใน Python 3 อย่างง่าย (ไม่ได้ทดสอบอย่างละเอียด):

จะเลือกค่าของ 'p' ได้อย่างไร?

ในการวัด RBO การเลือกค่า p จะกำหนดระดับการถ่วงน้ำหนักสูงสุดที่ผลลัพธ์ของการวัด RBO แสดง จากรายงาน RBO สามารถใช้สมการต่อไปนี้เพื่อคำนวณน้ำหนักโดยรวมที่อันดับ d บนสุดมีส่วนช่วยในการคำนวณ RBO:

นี่คือการใช้งานข้างต้นอย่างง่าย ๆ (ไม่ได้ทดสอบอย่างละเอียด):

สำหรับค่า p = 0.9 และ d = 10 (อันดับ 10 อันดับแรกที่กำลังตรวจสอบ) WRBO[1:d] คือ 0.8556 กล่าวคือ อันดับ 10 อันดับแรกมีส่วนช่วย 85.56% ในการวัด RBO สุดท้าย ดังนั้น ขึ้นอยู่กับปริมาณการมีส่วนร่วมที่คุณต้องการจากผลลัพธ์ d อันดับแรก คุณสามารถเลือกค่า p ตามลำดับได้โดยใช้สมการ WRBO[1:d] ด้านบน

การตีความ RBO

ดังที่ได้กล่าวไว้ข้างต้น RBO รับค่าในช่วง [0, 1] โดยที่ 0 หมายถึงความไม่ต่อเนื่องกัน และ 1 หมายถึงรายการที่มีอันดับเหมือนกัน

กลับไปที่ตัวอย่างที่ Kendall Tau ล้มเหลวในการรับรู้รายการอันดับที่ไม่คล้ายกันที่สร้างโดยบุคคลที่ 1 และบุคคลที่ 2 อย่างชัดเจน:

อันดับบุคคลที่ 1 คือ “# S2E10 # S3E24 #”

อันดับบุคคลที่ 2 คือ “# S2E10 # # S3E24”

ผมจะเลือก p = 0.6 เพราะอยากให้ 3 ตำแหน่งบนสุดรับน้ำหนักได้มากที่สุด ด้วย p = 0.6 ตำแหน่ง 3 อันดับแรกจะมีน้ำหนัก 91.26% ในการวัด RBO สุดท้าย เมื่อรวมค่าของบุคคลที่ 1 และบุคคลที่ 2 แล้ว เราจะได้ RBO(Person1, Person2, p, k) = 0.24144 กล่าวคือ ค่า RBO บ่งชี้ว่าทั้งสองรายการส่วนใหญ่แตกต่างกันโดยมีความคล้ายคลึงกันเล็กน้อยในตำแหน่ง 3 อันดับแรก การเพิ่มค่า p เป็น 0.9 ส่งผลให้ค่า RBO สูงขึ้นเป็น 0.352655 แต่ค่าดังกล่าวยังสามารถแสดงว่าทั้งสองรายการแตกต่างกัน

โดยสรุป RBO เป็นมาตรการที่แข็งแกร่งกว่าในการตัดสินความคล้ายคลึงกันของรายการการจัดอันดับแบบไม่แน่นอนซึ่งไม่จำเป็นต้องเชื่อมโยงกัน และสามารถปรับให้เข้ากับการถ่วงน้ำหนักสูงสุดได้ หากต้องการอ่านเพิ่มเติมเกี่ยวกับ RBO และทฤษฎีเบื้องหลัง โปรดดูเอกสารของ RBO [2]

อ่านเพิ่มเติม

เราได้ศึกษาวิธีการต่างๆ สองสามวิธีในการเปรียบเทียบการจัดอันดับสองชุดที่แตกต่างกัน ต่อไปนี้เป็นวิธีการอื่นๆ สำหรับการอ่านเพิ่มเติม:

• ความสัมพันธ์ของเพียร์สัน [5]
• บททดสอบของโคลโมโกรอฟ-สมีร์นอฟ [6]
• การเปรียบเทียบรายการยอดนิยม (7)

อาหารบางอย่างสำหรับความคิด

สุดท้ายนี้ ฉันอยากจะฝากอะไรไว้ให้คุณไตร่ตรอง:

ลองนึกภาพกรณีที่การเปรียบเทียบสองรายการใดๆ ในรายการไม่ใช่เรื่องง่าย สมมติว่าคุณจัดอันดับ กิจกรรม ที่คุณชื่นชอบจากฟุตบอลโลกด้วยการถ่ายภาพกิจกรรมนั้น ตัวอย่างเช่น รูปที่ 3 แสดงสองภาพที่มาจากเหตุการณ์เดียวกันเมื่อ Mario Götze ยิงประตูในช่วงต่อเวลาพิเศษ แต่เป็นภาพที่แตกต่างกันซึ่งถ่ายห่างกันไม่กี่วินาที ความสามารถในการบอกได้ว่าภาพสองภาพที่แตกต่างกันนั้นเหมือนกันเป็นสิ่งสำคัญ หากเราต้องการคำนวณ RBO หรือ Kendall Tau ในรายการภาพที่ได้รับการจัดอันดับ เราจะเปรียบเทียบภาพสองภาพและบอกได้ว่ามาจากเหตุการณ์เดียวกันได้อย่างไร

อ้างอิง

[1] คูมาร์, ราวี และเซอร์เก วาสซิลวิตสกี “ระยะทางทั่วไประหว่างการจัดอันดับ” การดำเนินการประชุมนานาชาติครั้งที่ 19 บนเวิลด์ไวด์เว็บ 2010.

[2] William Webber, Alistair Moffat และ Justin Zobel 2010. “การวัดความคล้ายคลึงกันสำหรับการจัดอันดับที่ไม่แน่นอน” ACM ทรานส์ ข้อมูล ระบบ 28, 4, บทความ 20 (พฤศจิกายน 2010), 38 หน้า DOI:https://doi.org/10.1145/1852102.1852106

(3) บาครัค, โยรัม, ราล์ฟ เฮิร์บริช และเอลี โพรัต “อัลกอริธึมการร่างสำหรับการประมาณความสัมพันธ์อันดับในระบบการกรองแบบร่วมมือ” การประชุมวิชาการระดับนานาชาติเกี่ยวกับการประมวลผลสตริงและการดึงข้อมูล สปริงเกอร์, เบอร์ลิน, ไฮเดลเบิร์ก, 2009.

[4] การระบุแหล่งที่มาของภาพฟุตบอลโลก:

[ภาพซ้าย] Danilo Borges/Portal da Copa copa2014.gov.br Licença Creative Commons Atribuição 3.0, CC BY 3.0 ‹https://creativecommons.org/licenses/by/3.0› ผ่าน Wikimedia Commons;

[ภาพขวา] Danilo Borges/copa2014.gov.br Licença Creative Commons Atribuição 3.0 Brasil, CC BY 3.0 BR ‹https://creativecommons.org/licenses/by/3.0/br/deed.en› ผ่าน Wikimedia Commons

(5) เบเนสตี้, เจค็อบ และคณะ “สัมประสิทธิ์สหสัมพันธ์เพียร์สัน” การลดเสียงรบกวนในการประมวลผลคำพูด สปริงเกอร์, เบอร์ลิน, ไฮเดลเบิร์ก, 2009. 1–4.

[6] Massey Jr, Frank J. “การทดสอบ Kolmogorov-Smirnov เพื่อความพอดี” วารสารสมาคมสถิติอเมริกัน 46.253 (1951): 68–78

[7] ฟากิน, โรนัลด์, ราวี คูมาร์ และ ดักชินามูร์ธี ซิวากุมาร์ “การเปรียบเทียบรายการ k อันดับต้น ๆ” วารสารสยามเรื่องคณิตศาสตร์ไม่ต่อเนื่อง 17.1 (2003): 134–160.

[8] การทดสอบความสำคัญของ Kendall Tau https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient#Significance_tests