Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/58213
Title: การจัดกลุ่มทับซ้อนที่มีพื้นฐานมาจากการจัดกลุ่มแบบแบ่งส่วนโดยใช้ความสัมพันธ์ของกลุ่มข้อมูล
Other Titles: Partition-based Overlapping Clustering using Clusters' Relations
Authors: ธนวัต ลิมังกูร
Advisors: พีรพล เวทีกูล
Other author: จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Advisor's Email: Peerapon.V@chula.ac.th,peerapon.v@chula.ac.th
Issue Date: 2560
Publisher: จุฬาลงกรณ์มหาวิทยาลัย
Abstract: การจัดกลุ่มแบบดั้งเดิมตั้งอยู่บนสมมติฐานที่ว่าข้อมูลหนึ่งตัวอย่างสามารถถูกจัดให้อยู่ได้เพียงกลุ่มเดียว อย่างไรก็ตามการจัดกลุ่มประเภทนี้ไม่สามารถครอบคลุมข้อมูลได้หมดทุกประเภท สำหรับข้อมูลประเภทหลายหมวดหมู่จำเป็นที่จะต้องใช้การจัดกลุ่มอีกแบบที่อนุญาตให้ข้อมูลหนึ่งตัวอย่างสามารถอยู่ได้หลายกลุ่มข้อมูล และเนื่องจากข้อมูลหนึ่งตัวอย่างสามารถอยู่ได้หลายกลุ่ม ดังนั้นกลุ่มข้อมูลที่เกิดขึ้นจึงสามารถทับซ้อนกัน การจัดกลุ่มประเภทนี้จึงถูกเรียกว่า “การจัดกลุ่มทับซ้อน” งานวิจัยนี้ให้ความสนใจที่การจัดกลุ่มทับซ้อนแบบแบ่งส่วนซึ่งเป็นการจัดกลุ่มทับซ้อนที่มีประสิทธิภาพและสามารถประยุกต์ใช้ได้กับชุดข้อมูลส่วนใหญ่ การจัดกลุ่มทับซ้อนแบบแบ่งส่วนนั้นมักมีพัฒนาการมาจากขั้นตอนวิธี K-Means ซึ่งมีปัญหาสำคัญคือมีการเริ่มต้นกระบวนการโดยการสุ่มเซนทรอยด์ ซึ่งหากเซนทรอยด์ที่ได้จากการสุ่มนี้อยู่ในตำแหน่งที่ไม่เหมาะสม ประสิทธิภาพทางด้านความถูกต้องแม่นยำของการจัดกลุ่มจะถูกอิงอยู่กับค่าต่ำสุดสัมพัทธ์ของฟังก์ชันต้นทุน ซึ่งทำให้ความถูกต้องแม่นยำมีโอกาสที่จะออกมาต่ำกว่าที่ควรจะเป็น การจัดกลุ่มทับซ้อนที่พัฒนามาจากขั้นตอนวิธี K-Means ก็ประสบปัญหานี้เช่นเดียวกันเนื่องจากมีการเริ่มต้นกระบวนการที่เหมือนกัน นอกจากนี้งานวิจัยเกี่ยวกับการจัดกลุ่มทับซ้อนแบบแบ่งส่วนที่ผ่านมายังไม่มีการนำองค์ความรู้เกี่ยวกับความสัมพันธ์ระหว่างกลุ่มข้อมูลซึ่งเป็นตัวแปรสำคัญตัวแปรหนึ่งที่มีผลต่อรูปแบบของกลุ่มข้อมูลมาใช้ประโยชน์ งานวิจัยนี้จึงมีจุดประสงค์หลักสองประเด็นคือเพื่อแก้ปัญหาเซนทรอยด์ที่อยู่ในตำแหน่งที่ไม่เหมาะสม โดยการประยุกต์ใช้ขั้นตอนวิธี K-Harmonic-Means และขั้นตอนวิธี ELBG อีกประเด็นหนึ่งคือนำองค์ความรู้เกี่ยวกับความสัมพันธ์ระหว่างกลุ่มข้อมูลมาใช้ประโยชน์ เพื่อเพิ่มประสิทธิภาพของการจัดกลุ่มในด้านความถูกต้องแม่นยำ หลังจากค้นคว้าวิจัยจนได้ขั้นตอนวิธีใหม่และทดสอบกับชุดข้อมูล 20 ชุดข้อมูลพบว่าสามารถแก้ไขปัญหาที่เกิดขึ้น และเพิ่มประสิทธิภาพของการจัดกลุ่มด้านความถูกต้องแม่นยำได้จริง โดยความถูกต้องแม่นยำเพิ่มขึ้นเฉลี่ย 25.68% จากขั้นตอนวิธี OKM ซึ่งนำมาเป็นขั้นตอนวิธีพื้นฐานในการวัดด้วยค่า F1
Other Abstract: Traditional clusterings have the assumption that a data point can belong to only a single cluster; however, these kinds of clustering cannot handle all data types. For multi-category data clustering, a data point needs to be allowed to belong to more than one cluster, so called “Overlapping Clustering”. This research focuses on partition-based overlapping clustering that is a high-performance clustering with most data sets. Most of partition-based overlapping clusterings are developed from K-Means. This kind of algorithm has an issue, during the process of assigning centroid, the centroid can be shifted to inappropriate position that will yield poor clustering result. Same as K-Means, the partition-based overlapping clustering also encounter this problem. In addition, for overlapping clustering, information about relation between clusters is crucial, but there is still no research exploiting this information to enhance the clustering performance. This research has the objective to solve the inappropriate position of centroids problem by applying K-Harmonic-Means and ELBG to OKM algorithm. Moreover, the performance of algorithm will be enhanced by embedding clusters’ relations information to the cost function. After test with 20 multi-category data sets, the results show that the issue has been resolved and accuracy in term of F1 is improved from base-line algorithm OKM 25.68% on average.
Description: วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2560
Degree Name: วิทยาศาสตรมหาบัณฑิต
Degree Level: ปริญญาโท
Degree Discipline: วิทยาศาสตร์คอมพิวเตอร์
URI: http://cuir.car.chula.ac.th/handle/123456789/58213
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
5770548121.pdf2.05 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.