การสร้างแผนภาพตัดสินใจทวิภาคโดยเทคนิคการเรียนรู้ต้นไม้ตัดสินใจ

ศิริพรรณ วิญญูนันทกุล

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/68702

Title:	การสร้างแผนภาพตัดสินใจทวิภาคโดยเทคนิคการเรียนรู้ต้นไม้ตัดสินใจ
Other Titles:	Construction of binary decision diagrams by the decision tree learning technique
Authors:	ศิริพรรณ วิญญูนันทกุล
Advisors:	อาทิตย์ ทองทักษ์ บุญเสริม กิจศิริกุล
Other author:	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Advisor's Email:	Arthit.T@Chula.ac.th ฺBoonserm.K@Chula.ac.th
Subjects:	ต้นไม้ตัดสินใจ ต้นไม้ (ทฤษฎีกราฟ) Decision trees Trees (Graph theory)
Issue Date:	2542
Publisher:	จุฬาลงกรณ์มหาวิทยาลัย
Abstract:	เนื่องจากแผนภาพตัดสินใจทวิภาคเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับการแทนฟังก์ชันบูลีน จึงทำให้แผนภาพตัดสินใจทวิภาคถูกใช้อย่างกว้างขวางกับงานต่าง ๆ ของการออกแบบใช้คอมพิวเตอร์ช่วย แต่ปัญหาหนึ่งที่มักพบในภาพตัดสินใจทวิภาคก็คือ ขนาดของแผนภาพจะขึ้นอยู่กับการเลือกลำดับของตัวแปร ดังนั้นวิธีการหาลำดับของตัวแปรที่ดีจึงเป็นสิ่งสำคัญสำหรับการสร้างแผนภาพตัดสินใจทวิภาคที่มีขนาดเล็ก วิทยานิพนธ์ฉบับนี้ได้นำเสนอวิธีการสร้างแผนภาพตัดสินใจทวิภาค โดยวิธีการที่เสนอจะใช้การเรียนรู้ต้นไม้ตัดสินใจ ซึ่งเป็นเทคนิคหนึ่งของปัญญาประดิษฐ์ สำหรับการหาลำดับตัวแปรเริ่มต้นของแผนภาพตัดสินใจทวิภาค จากนั้นจะลดขนาดแผนภาพตัดสินใจทวิภาคเริ่มต้น ด้วยขั้นตอนวิธีการพัฒนาทีละขั้นที่มีอยู่เดิม เช่น AD2 AD3 AD4 AR ARSA และ SIFTING นอกจากนี้วิทยานิพนธ์ยังได้นำเสนอวิธีการปรับปรุงการเลือกตัวแปรและแผนภาพตัดสินใจทวิภาคที่ใช้ในขั้นตอนวิธีเหล่านี้ด้วย ผลการทดลองกับวงจรวัดเปรียบเทียบสมรรถนะของ MCNC แสดงให้เห็นว่าการสร้างแผนภาพตัดสินใจทวิภาคด้วยวิธีการที่นำเสนอ สามารถให้ขนาดแผนภาพที่เล็กกว่าวิธีการใช้ขั้นตอนวิธีการพัฒนาทีละขั้นเพียงอย่างเดียว โดยเฉพาะอย่างยิ่งการสร้างแผนภาพตัดสินใจทวิภาคด้วยวิธีการที่นำเสนอร่วมกับขั้นตอนวิธี SIFTING จะให้ผลดีที่สุด เมื่อเทียบกับขั้นตอนวิธีการพัฒนาทีละขั้นทุกแบบที่กล่าวข้างต้น
Other Abstract:	Since the Binary Decision Diagram is an efficient data structure for representing Boolean functions, it has been widely used in computer-aided design applications. One problem of the Binary Decision Diagram is that its size largely depends on the choice of an ordering of variables. Thus a method of finding good variable ordering is needed for small Binary Decision Diagram construction. This thesis presents a method for the Binary Decision Diagram construction. The method is based on the Decision Tree Learning technique appeared in artificial intelligence. Decision Tree Learning is employed to find an initial variable ordering for the Binary Decision Diagram. Then the initial Binary Decision Diagram is minimized by the gradual improvement algorithms known in the literature such as AD2, AD3, AD4, AR, ARSA and SIFTING. The thesis also presents a method for improving variables and the Binary Decision Diagram selection used in these algorithms. Experiments on the MCNC (Microelectronics Center of North Carolina) benchmark circuits show that the Binary Decision Diagram constructed by the proposed method is smaller than those by the only gradual improvement algorithms. Moreover, the Binary Decision Diagram produced by the proposed method with SIFTING algorithm yields the best of all gradual improvement algorithms above.
Description:	วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2542
Degree Name:	วิทยาศาสตรมหาบัณฑิต
Degree Level:	ปริญญาโท
Degree Discipline:	วิทยาศาสตร์คอมพิวเตอร์
URI:	http://cuir.car.chula.ac.th/handle/123456789/68702
ISBN:	9743330518
Type:	Thesis
Appears in Collections:	Eng - Theses

Files in This Item:

File	Description	Size	Format
Siriphan_vi_front_p.pdf	หน้าปก และบทคัดย่อ	1.02 MB	Adobe PDF	View/Open
Siriphan_vi_ch1_p.pdf	บทที่ 1	725.03 kB	Adobe PDF	View/Open
Siriphan_vi_ch2_p.pdf	บทที่ 2	1.46 MB	Adobe PDF	View/Open
Siriphan_vi_ch3_p.pdf	บทที่ 3	1.12 MB	Adobe PDF	View/Open
Siriphan_vi_ch4_p.pdf	บทที่ 4	839.15 kB	Adobe PDF	View/Open
Siriphan_vi_ch5_p.pdf	บทที่ 5	673.07 kB	Adobe PDF	View/Open
Siriphan_vi_back_p.pdf	บรรณานุกรม และภาคผนวก	2.39 MB	Adobe PDF	View/Open

Show full item record