Chulalongkorn University Theses and Dissertations (Chula ETD)

Multiclass support vector machines using reordering adaptive directed acyclic graphs

Other Title (Parallel Title in Other Language of ETD)

ซัพพอร์ตเวกเตอร์แมชชีนแบบหลายกลุ่มโดยใช้กราฟไม่มีวงมีทิศทางที่ปรับได้แบบจัดเรียงใหม่

Year (A.D.)

2004

Document Type

Thesis

First Advisor

Boonserm Kijsirikul

Second Advisor

Wanchai Rivepiboon

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2004.1536

Abstract

The problem of extending binary support vector machines (SVMs) for multiclass classification is still an ongoing research issue. The Decision Directed Acyclic Graph (DDAG) method reduces training and evaluation time, while maintaining accuracy compared to the Max Wins, which is probably the currently most accurate method for multiclass SVMs. The Adaptive Directed Acyclic Graph (ADAG) approach is proposed to alleviate the problem of the DDAG structure. However, different sequences of binary classifiers in nodes in the ADAG may provide different accuracy. In this research we present a new method, Reordering Adaptive Directed Acyclic Graph (RADAG), which is the modification of the original ADAG method. We propose an algorithm to choose an optimal sequence of binary classifiers in nodes in the ADAG by considering the generalization error bounds of all classifiers. We apply minimum-weight perfect matching with the reordering algorithm in order to select binary classifiers which have small generalization errors to be used in data classification and in order to find the best sequence of binary classifiers in polynomial time. We then compare the performance of our method with previous methods including the DDAG, the ADAG and the Max Wins. Experiments denote that our method gives higher accuracy. Moreover it runs faster than Max Wins, especially when the number of classes and/or the number of dimensions are relatively large. In this research we also present alternative ways to enhance the performance of the RADAG and the DDAG as well

Other Abstract (Other language abstract of ETD)

ปัญหาการพัฒนาซัพพอร์ตเวกเตอร์แมชชีนให้สามารถจำแนกข้อมูลได้หลายกลุ่มยังคงอยู่ในขั้นตอนการวิจัย วิธีดีดีเอจี (Decision Directed Acyclic Graph-DDAG) ให้ความถูกต้องเทียบได้กับวิธีแมกซ์วิน (Max Wins) ที่เป็นอัลกอริทึมที่ให้ค่าความถูกต้องสูงที่สุดในปัจจุบัน แต่ใช้เวลาในการสอนและประมวลผลต่ำกว่า วิธีเอดีเอจี (Adaptive Directed Acyclic Graph-ADAG) สามารถลดปัญหาที่เกิดจากโครงสร้างของดีดีเอจีได้ อย่างไรก็ตามลำดับของโนดที่แตกต่างกันในวิธีเอดีเอจีอาจให้ความถูกต้องที่แตกต่างกัน งานวิจัยนี้ได้เสนอวิธีการใหม่สำหรับการจำแนกข้อมูลแบบหลายกลุ่ม เรียกว่าอาร์เอดีเอจี (Reordering Adaptive Directed Acyclic Graph-RADAG) ซึ่งเป็นการปรับปรุงวิธีเอดีเอจีเดิมและได้เสนออัลกอริทึมสำหรับการเลือกลำดับที่เหมาะสมของโนดในวิธีเอดีเอจีเพื่อนำมาใช้ในการจำแนกข้อมูล โดยพิจารณาจากค่าขอบเขตของความผิดพลาดของตัวจำแนกข้อมูลทั้งหมด และได้นำอัลกอริทึมการจับคู่สมบูรณ์แบบน้ำหนักน้อยสุด (Minimum-weight perfect matching) มาประยุกต์ใช้กับอัลกอริทึมที่ทำการจัดเรียงลำดับเพื่อเลือกตัวจำแนกที่มีค่าขอบเขตของความผิดพลาดต่ำมาใช้ในการจำแนกข้อมูล และเพื่อเลือกลำดับของโนดที่เหมาะสมให้ได้ภายในเวลาพหุนาม (polynomial time) งานวิจัยนี้ได้เปรียบเทียบประสิทธิภาพของวิธีการใหม่กับวิธีดีดีเอจี เอดีเอจี และแมกซ์วิน ผลการทดลองที่ได้แสดงให้เห็นว่าวิธีการใหม่ให้ความถูกต้องที่สูงกว่า และมีการประมวลผลเร็วกว่าวิธีแมกซ์วิน โดยเฉพาะอย่างยิ่งเมื่อมีจำนวนกลุ่ม (class) และจำนวนมิติของข้อมูล (dimension) สูง งานวิจัยนี้ได้เสนอแนวทางในการเพิ่มประสิทธิภาพของวิธีอาร์เอดีเอจี และวิธีดีดีเอจีด้วย

Link to Full Text

Share

COinS