Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Partition-based Overlapping Clustering using Clusters' Relations
Year (A.D.)
2017
Document Type
Thesis
First Advisor
พีรพล เวทีกูล
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิทยาศาสตร์คอมพิวเตอร์
DOI
10.58837/CHULA.THE.2017.1257
Abstract
การจัดกลุ่มแบบดั้งเดิมตั้งอยู่บนสมมติฐานที่ว่าข้อมูลหนึ่งตัวอย่างสามารถถูกจัดให้อยู่ได้เพียงกลุ่มเดียว อย่างไรก็ตามการจัดกลุ่มประเภทนี้ไม่สามารถครอบคลุมข้อมูลได้หมดทุกประเภท สำหรับข้อมูลประเภทหลายหมวดหมู่จำเป็นที่จะต้องใช้การจัดกลุ่มอีกแบบที่อนุญาตให้ข้อมูลหนึ่งตัวอย่างสามารถอยู่ได้หลายกลุ่มข้อมูล และเนื่องจากข้อมูลหนึ่งตัวอย่างสามารถอยู่ได้หลายกลุ่ม ดังนั้นกลุ่มข้อมูลที่เกิดขึ้นจึงสามารถทับซ้อนกัน การจัดกลุ่มประเภทนี้จึงถูกเรียกว่า "การจัดกลุ่มทับซ้อน" งานวิจัยนี้ให้ความสนใจที่การจัดกลุ่มทับซ้อนแบบแบ่งส่วนซึ่งเป็นการจัดกลุ่มทับซ้อนที่มีประสิทธิภาพและสามารถประยุกต์ใช้ได้กับชุดข้อมูลส่วนใหญ่ การจัดกลุ่มทับซ้อนแบบแบ่งส่วนนั้นมักมีพัฒนาการมาจากขั้นตอนวิธี K-Means ซึ่งมีปัญหาสำคัญคือมีการเริ่มต้นกระบวนการโดยการสุ่มเซนทรอยด์ ซึ่งหากเซนทรอยด์ที่ได้จากการสุ่มนี้อยู่ในตำแหน่งที่ไม่เหมาะสม ประสิทธิภาพทางด้านความถูกต้องแม่นยำของการจัดกลุ่มจะถูกอิงอยู่กับค่าต่ำสุดสัมพัทธ์ของฟังก์ชันต้นทุน ซึ่งทำให้ความถูกต้องแม่นยำมีโอกาสที่จะออกมาต่ำกว่าที่ควรจะเป็น การจัดกลุ่มทับซ้อนที่พัฒนามาจากขั้นตอนวิธี K-Means ก็ประสบปัญหานี้เช่นเดียวกันเนื่องจากมีการเริ่มต้นกระบวนการที่เหมือนกัน นอกจากนี้งานวิจัยเกี่ยวกับการจัดกลุ่มทับซ้อนแบบแบ่งส่วนที่ผ่านมายังไม่มีการนำองค์ความรู้เกี่ยวกับความสัมพันธ์ระหว่างกลุ่มข้อมูลซึ่งเป็นตัวแปรสำคัญตัวแปรหนึ่งที่มีผลต่อรูปแบบของกลุ่มข้อมูลมาใช้ประโยชน์ งานวิจัยนี้จึงมีจุดประสงค์หลักสองประเด็นคือเพื่อแก้ปัญหาเซนทรอยด์ที่อยู่ในตำแหน่งที่ไม่เหมาะสม โดยการประยุกต์ใช้ขั้นตอนวิธี K-Harmonic-Means และขั้นตอนวิธี ELBG อีกประเด็นหนึ่งคือนำองค์ความรู้เกี่ยวกับความสัมพันธ์ระหว่างกลุ่มข้อมูลมาใช้ประโยชน์ เพื่อเพิ่มประสิทธิภาพของการจัดกลุ่มในด้านความถูกต้องแม่นยำ หลังจากค้นคว้าวิจัยจนได้ขั้นตอนวิธีใหม่และทดสอบกับชุดข้อมูล 20 ชุดข้อมูลพบว่าสามารถแก้ไขปัญหาที่เกิดขึ้น และเพิ่มประสิทธิภาพของการจัดกลุ่มด้านความถูกต้องแม่นยำได้จริง โดยความถูกต้องแม่นยำเพิ่มขึ้นเฉลี่ย 25.68% จากขั้นตอนวิธี OKM ซึ่งนำมาเป็นขั้นตอนวิธีพื้นฐานในการวัดด้วยค่า F1
Other Abstract (Other language abstract of ETD)
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.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
ลิมังกูร, ธนวัต, "การจัดกลุ่มทับซ้อนที่มีพื้นฐานมาจากการจัดกลุ่มแบบแบ่งส่วนโดยใช้ความสัมพันธ์ของกลุ่มข้อมูล" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 1747.
https://digital.car.chula.ac.th/chulaetd/1747