Chulalongkorn University Theses and Dissertations (Chula ETD)

A divide-and-conquer approach to the Pairwise Opposite Class-Nearest Neighbor (POC-NN) algorithm for classification and regression problems

Other Title (Parallel Title in Other Language of ETD)

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

Year (A.D.)

2004

Document Type

Thesis

First Advisor

Chidchanok Lursinsap

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Computer Science

DOI

10.58837/CHULA.THE.2004.1005

Abstract

This paper presents a new method based on divide-and-conquer approach to the selection of a set of prototypes from the training data by the nearest neighbor rule. The method aims at reducing computational time and memory space as well as sensitivity of the order and noise of the training data. A reduced prototype set contains Pairwise Opposite Class-Nearest Neighbor (POC-NN) prototypes, which are close to the decision boundary and used instead of the training patterns. POC-NN prototypes are obtained by recursively analysis and iterative separation of the training data into two regions until each region is correctly grouped and classied. The separability is determined by the POC-NN prototypes essential to dene the locations of all separating hyperplanes. Our method is fast and order independent. The number of prototypes and the overtting of the model can be reduced by the user. This method can be used to solve not only classication but also regressionproblems. The experimental results signify the effectiveness of this technique and its performance in both accuracy and prototype rate as well as in training time over those obtained by classical nearest neighbor techniques.

Other Abstract (Other language abstract of ETD)

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

Link to Full Text

Share

COinS