Skip to content
กลับไปยังผลการค้นหา

การจำแนกประเภทแบบเพื่อนบ้านใกล้เคียง K แบบกึ่งมีผู้สอน

ผู้เสนอ
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
ปี
2002 (semi-supervised extension); 1967 (KNN base)
ประเภท
Semi-supervised classifier / label propagation
กลุ่มวิธี
Machine learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Semi-supervised KNN เป็นการขยายอัลกอริทึม K-nearest neighbors แบบคลาสสิก เพื่อใช้ประโยชน์จากชุดข้อมูลขนาดใหญ่ที่ไม่มีป้ายกำกับ (unlabeled data) ควบคู่ไปกับชุดข้อมูลที่มีป้ายกำกับ (labeled data) ขนาดเล็ก โดยการสร้างกราฟ KNN เหนือจุดข้อมูลทั้งหมด และเผยแพร่ป้ายกำกับที่ทราบผ่านเส้นเชื่อมของกราฟ วิธีการนี้จะอนุมานป้ายกำกับสำหรับจุดข้อมูลที่ไม่มีป้ายกำกับ โดยไม่ต้องใช้การติดป้ายกำกับด้วยตนเองที่มีค่าใช้จ่ายสูงสำหรับทุกตัวอย่าง

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพห้องเรียนที่มีนักเรียนเพียงไม่กี่คนที่มีป้ายชื่อ และส่วนที่เหลือไม่มีชื่อ KNN แบบมาตรฐานสามารถจำแนกนักเรียนที่ไม่มีชื่อได้โดยดูจากเพื่อนบ้านที่มีป้ายชื่อที่อยู่ใกล้เคียงเพียงไม่กี่คนเท่านั้น แต่ Semi-supervised KNN จะสร้างแผนผังห้องเรียนทั้งหมดเป็นเครือข่าย โดยนักเรียนแต่ละคนเชื่อมโยงกับเพื่อนบ้านที่ใกล้ที่สุด และเผยแพร่ป้ายกำกับออกไปจากนักเรียนที่มีป้ายชื่อ เหมือนหมึกที่กระจายไปบนกระดาษเปียก เนื่องจากเครือข่ายจับโครงสร้างโดยรวมของข้อมูล ป้ายกำกับจึงไปถึงจุดข้อมูลที่ไม่มีป้ายกำกับด้วยวิธีที่มีหลักการ ซึ่งเคารพรูปทรงเรขาคณิตพื้นฐาน แทนที่จะละเลยข้อมูลส่วนใหญ่ที่ไม่มีป้ายกำกับ

ประวัติศาสตร์

การเผยแพร่ป้ายกำกับบนกราฟ KNN ได้รับการทำให้เป็นระบบโดย Zhu และ Ghahramani ในปี 2002 โดยต่อยอดจาก Vapnik's transductive SVM และแนวคิดการแพร่กระจายบนกราฟ (graph-based diffusion) ที่มาก่อนหน้านี้ กรอบงานนี้ได้รับการรวบรวมในหนังสือ Semi-Supervised Learning (Chapelle et al., 2006) ของ MIT Press ซึ่งยังคงเป็นเอกสารอ้างอิงมาตรฐาน ไลบรารีประมาณเพื่อนบ้านใกล้ที่สุด (approximate-KNN) ที่ปรับขนาดได้ (เช่น FAISS, Annoy) ได้ทำให้แนวทางนี้ใช้งานได้จริงกับข้อมูลหลายล้านจุดในภายหลัง และยังคงถูกใช้เป็นเกณฑ์มาตรฐานที่แข็งแกร่งสำหรับการจำแนกภาพและข้อความแบบกึ่งมีผู้สอน

ควรใช้เมื่อใด

ใช้ semi-supervised KNN เมื่อคุณมีชุดข้อมูลที่มีป้ายกำกับขนาดเล็กและชุดข้อมูลที่ไม่มีป้ายกำกับขนาดใหญ่จากการกระจายเดียวกัน ข้อมูลอยู่ในปริภูมิที่มีมิติต่ำค่อนข้างมาก (น้อยกว่าประมาณ 50 คุณลักษณะ) และคุณเชื่อว่าจุดข้อมูลที่อยู่ใกล้เคียงกันมีคลาสเดียวกัน เหมาะสำหรับงานจำแนกประเภทภาพ (image patch classification) การจัดหมวดหมู่ข้อความ (text categorization) ที่มีการติดป้ายกำกับแบบเบาบาง และงานคัดกรองทางการแพทย์ที่การติดป้ายกำกับโดยผู้เชี่ยวชาญมีค่าใช้จ่ายสูง หลีกเลี่ยงการใช้งานเมื่อข้อมูลที่มีป้ายกำกับและไม่มีป้ายกำกับมาจากคนละการกระจาย (covariate shift) ปริภูมิคุณลักษณะมีมิติสูงมาก (กราฟ KNN จะไม่น่าเชื่อถือ) ชุดข้อมูลมีขนาดเล็กพอที่ KNN แบบมีผู้สอน (fully supervised KNN) ก็เพียงพอแล้ว หรือขอบเขตของคลาสไม่สอดคล้องกับโครงสร้างความหนาแน่นเฉพาะที่ของข้อมูล

ข้อจำกัดและข้อควรพิจารณา

  • การสร้างกราฟมีค่าใช้จ่ายตามกำลังสอง (quadratically) กับขนาดชุดข้อมูล เว้นแต่จะใช้วิธีการประมาณเพื่อนบ้านใกล้ที่สุด (approximate nearest-neighbor methods)
  • ประสิทธิภาพลดลงอย่างมากในปริภูมิที่มีมิติสูง ซึ่งเมตริกวัดระยะทางสูญเสียพลังในการจำแนก
  • สมมติว่าข้อมูลที่มีป้ายกำกับและไม่มีป้ายกำกับถูกดึงมาจากการกระจายเดียวกัน การเปลี่ยนโคแวริเอต (covariate shift) จะทำให้วิธีการนี้ล้มเหลว
  • ต้องมีการปรับแต่งค่า k, แบนด์วิดท์ของเส้นเชื่อม, และพารามิเตอร์ผสมการเผยแพร่ (propagation mixing parameter) อย่างระมัดระวัง
  • การเผยแพร่ป้ายกำกับอาจขยายข้อผิดพลาดในการติดป้ายกำกับเริ่มต้นไปทั่วส่วนใหญ่ของกราฟ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ใช้ประโยชน์จากข้อมูลที่ไม่มีป้ายกำกับราคาถูกเพื่อปรับปรุงความแม่นยำให้เหนือกว่าสิ่งที่สามารถทำได้ด้วยชุดข้อมูลที่มีป้ายกำกับเพียงอย่างเดียว
  • ไม่มีข้อสมมติฐานเกี่ยวกับแบบจำลองพาราเมตริก: อาศัยเฉพาะรูปทรงเรขาคณิตของเพื่อนบ้านในท้องถิ่นเท่านั้น
  • จัดการปัญหาหลายคลาส (multi-class problems) ได้อย่างเป็นธรรมชาติโดยไม่ต้องปรับเปลี่ยน
  • การสร้างกราฟ KNN มีความโปร่งใสและตรวจสอบได้ง่าย
  • ทำงานได้ดีเมื่อคลาสต่างๆ ก่อตัวเป็นกลุ่มที่กะทัดรัดและแยกออกจากกันได้ดีในปริภูมิคุณลักษณะ

การประยุกต์ใช้

  • การจำแนกภาพด้วยชุดภาพที่มีป้ายกำกับขนาดเล็กและคลังข้อมูลที่ไม่มีป้ายกำกับขนาดใหญ่
  • การจัดหมวดหมู่ข้อความและเอกสารที่การติดป้ายกำกับด้วยตนเองมีค่าใช้จ่ายสูง
  • การจำแนกประเภทบันทึกทางการแพทย์หรือสไลด์พยาธิวิทยาที่มีคำอธิบายประกอบจากผู้เชี่ยวชาญจำกัด
  • การตรวจจับการฉ้อโกงเมื่อมีกรณีการฉ้อโกงที่ยืนยันแล้วจำนวนน้อยเท่านั้น
  • การติดป้ายกำกับข้อมูลเซ็นเซอร์ในสภาพแวดล้อม IoT อุตสาหกรรมที่มีเหตุการณ์จริง (ground-truth events) แบบเบาบาง

วิธีการทำงาน

วิธีการทำงาน

1

สร้างกราฟเหนือจุดข้อมูลทั้งหมด ทั้งที่มีป้ายกำกับและไม่มีป้ายกำกับ แต่ละโหนดแทนจุดข้อมูลหนึ่งจุด และเส้นเชื่อมแบบมีทิศทางหรือไม่มีทิศทางจะเชื่อมต่อแต่ละโหนดกับเพื่อนบ้าน k ตัวที่ใกล้ที่สุดในปริภูมิคุณลักษณะ (feature space) การเลือกค่า k จะควบคุมการเผยแพร่ป้ายกำกับในระดับท้องถิ่นหรือระดับโลก: ค่า k น้อยจะทำให้การเผยแพร่จำกัดอยู่ในวงแคบ ส่วนค่า k มากจะช่วยให้ป้ายกำกับข้ามผ่านช่องว่างที่ใหญ่ขึ้นได้

2

น้ำหนักของเส้นเชื่อม (Edge weights) จะจับความแข็งแกร่งของความคล้ายคลึงกันระหว่างโหนดที่เชื่อมต่อกัน โดยทั่วไปจะใช้ Gaussian (RBF) kernel ที่ใช้กับระยะทางแบบยุคลิด (Euclidean distance) ระหว่างเวกเตอร์คุณลักษณะ พารามิเตอร์แบนด์วิดท์ (bandwidth parameter) sigma จะควบคุมว่าความคล้ายคลึงกันจะลดลงตามระยะทางเร็วเพียงใด เส้นเชื่อมที่แข็งแกร่งจะส่งผ่านป้ายกำกับได้ง่ายขึ้นระหว่างการเผยแพร่

สูตร
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

ป้ายกำกับจะถูกกระจายแบบวนซ้ำจากโหนดที่มีป้ายกำกับไปยังเพื่อนบ้านที่ไม่มีป้ายกำกับ ในแต่ละรอบการวนซ้ำ แต่ละโหนดจะอัปเดตการกระจายป้ายกำกับแบบอ่อน (soft label distribution) เป็นการรวมกันแบบถ่วงน้ำหนักของการกระจายปัจจุบันของเพื่อนบ้านและป้ายกำกับเริ่มต้นของตัวเอง (หากมีป้ายกำกับ) พารามิเตอร์ผสม (mixing parameter) alpha จะสร้างสมดุลระหว่างอิทธิพลของโครงสร้างกราฟกับป้ายกำกับที่แน่นอน (hard labels) และการวนซ้ำจะดำเนินต่อไปจนกว่าการกระจายจะลู่เข้า (converge)

สูตร
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

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

สูตร
\hat{y}_i = \arg\max_c F_{ic}

ข้อผิดพลาดที่พบบ่อย

  • การสร้างกราฟ KNN โดยไม่ปรับมาตราส่วนคุณลักษณะ (normalizing features) ทำให้คุณลักษณะที่มีความแปรปรวนสูงมีอิทธิพลต่อการคำนวณระยะทาง
  • การตั้งค่า k สูงเกินไป ซึ่งจะทำให้ขอบเขตคลาสที่แท้จริงถูกทำให้เรียบ (smoothed over) และสร้างการกระจายป้ายกำกับที่เรียบเกินไป (over-smoothed)
  • การละเลยความเป็นไปได้ที่ข้อมูลที่ไม่มีป้ายกำกับอยู่นอกเหนือการกระจาย (out-of-distribution) เมื่อเทียบกับข้อมูลที่มีป้ายกำกับ
  • การรายงานความแม่นยำบนโหนดที่ไม่มีป้ายกำกับเสมือนว่าเป็นค่าประมาณของชุดทดสอบที่ไม่เอนเอียง (unbiased test-set estimate) — โหนดที่ไม่มีป้ายกำกับรั่วไหลเข้าไปในกราฟระหว่างการฝึก
  • การข้ามการตรวจสอบการลู่เข้า (convergence checks) และใช้จำนวนรอบการเผยแพร่ที่กำหนดไว้ล่วงหน้าและตามอำเภอใจ

คำถามที่พบบ่อย

ฉันจะเลือกค่า k ได้อย่างไร?

เริ่มต้นด้วยค่า k ในช่วง 5-15 และปรับแต่งโดยใช้ความแม่นยำของการตรวจสอบความถูกต้อง (validation accuracy) จากข้อมูลที่มีป้ายกำกับที่แยกไว้ ค่า k ที่น้อยกว่าจะให้ขอบเขตที่คมชัดและเฉพาะที่มากขึ้น ส่วนค่า k ที่มากกว่าจะช่วยให้ป้ายกำกับแพร่กระจายได้ไกลขึ้น แต่มีความเสี่ยงที่จะข้ามขอบเขตคลาสที่แท้จริง

ฉันสามารถประเมินวิธีการได้อย่างซื่อสัตย์เมื่อข้อมูลส่วนใหญ่ไม่มีป้ายกำกับหรือไม่?

แยกชุดทดสอบที่มีป้ายกำกับโดยเฉพาะออกมา ซึ่งจะไม่ถูกนำไปรวมในกราฟ โหนดในกราฟ — แม้แต่โหนดที่ไม่มีป้ายกำกับ — ก็เป็นส่วนหนึ่งของการฝึก ดังนั้นโหนดที่มีป้ายกำกับใดๆ ที่มีส่วนร่วมในการสร้างกราฟจะต้องไม่ถูกใช้เป็นจุดทดสอบด้วย

จะเกิดอะไรขึ้นหากชุดข้อมูลของฉันใหญ่เกินไปที่จะสร้างกราฟ KNN แบบเต็ม?

ใช้ไลบรารีประมาณเพื่อนบ้านใกล้ที่สุด (approximate nearest-neighbor libraries) เช่น FAISS หรือ Annoy เพื่อสร้างกราฟในเวลา O(n log n) แทนที่จะเป็น O(n^2) จากนั้นจึงใช้การเผยแพร่ป้ายกำกับบนกราฟประมาณแบบเบาบาง (sparse approximate graph)

Semi-supervised KNN ให้ประสิทธิภาพดีกว่า supervised KNN เสมอหรือไม่?

ไม่จำเป็นเสมอไป หากข้อมูลที่ไม่มีป้ายกำกับอยู่นอกเหนือการกระจาย หรือปริภูมิคุณลักษณะมีมิติสูงมาก กราฟจะเต็มไปด้วยสัญญาณรบกวน (noisy) และการเผยแพร่สามารถทำให้ประสิทธิภาพแย่ลงได้ ควรเปรียบเทียบกับเกณฑ์มาตรฐาน KNN แบบมีผู้สอน (supervised KNN baseline) เสมอก่อนที่จะอ้างว่าได้รับประโยชน์จากข้อมูลที่ไม่มีป้ายกำกับ

นี่เหมือนกับ label spreading หรือ label propagation ใน scikit-learn หรือไม่?

มีความเกี่ยวข้องกันอย่างใกล้ชิด LabelPropagation และ LabelSpreading ของ scikit-learn ใช้กรอบงานของ Zhu และ Ghahramani โดยใช้กราฟ KNN หรือ RBF kernel ดังนั้นจึงเป็นการนำวิธีการที่อธิบายไว้ที่นี่ไปใช้โดยตรง

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    คัดลอกแล้ว