Multiclass support vector machines using reordering adaptive directed acyclic graphs

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

Name: Thimaporn Phetkaew

LCSH: Pattern recognition systems

LCSH: Algorithms

Othors: Support vector machines

Othors: Recording adaptive directed acyclic graph

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

Abstract: ปัญหาการพัฒนาซัพพอร์ตเวกเตอร์แมชชีนให้สามารถจำแนกข้อมูลได้หลายกลุ่มยังคงอยู่ในขั้นตอนการวิจัย วิธีดีดีเอจี (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) สูง งานวิจัยนี้ได้เสนอแนวทางในการเพิ่มประสิทธิภาพของวิธีอาร์เอดีเอจี และวิธีดีดีเอจีด้วย

Chulalongkorn University

Address: กรุงเทพมหานคร (Bangkok)

Email: cuir@car.chula.ac.th

Name: Boonserm Kijsirikul

Role: Advisor

Name: Wanchai Rivepiboon

Role: Advisor

Created: 2004

Issued: 2006-01-13

Modified: 2006-08-05

วิทยานิพนธ์/Thesis

URL: http://thailis-db.car.chula.ac.th/CU_DC/Thesis/January2006/Thimaporn.pdf

ISBN: 9741759142

eng

DegreeName: Doctor of Engineering

Level: Doctoral Degree

Descipline: Computer Engineering

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	Thimaporn.pdf	980.87 KB	141	2025-08-06 15:58:31

ใช้เวลา

0.028556 วินาที