Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/14311
| Title: | การปรับปรุงขั้นตอนวิธีแบ่งส่วนรอบเมดอยด์ |
| Other Titles: | Improvement of partitioning around medoid algorithm |
| Authors: | รุ่งโรจน์ พุ่มดวง |
| Advisors: | กรุง สินอภิรมย์สราญ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์ |
| Advisor's Email: | krung@math.sc.chula.ac.th |
| Subjects: | การวิเคราะห์จัดกลุ่ม ดาต้าไมนิง การแบ่งส่วน (คณิตศาสตร์) |
| Issue Date: | 2550 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | การวิเคราะห์การเกาะกลุ่มเป็นหนึ่งในหลักการทำเหมืองข้อมูล ซึ่งผู้วิจัยใช้แบ่งกั้นเซตข้อมูลออกเป็นกลุ่มย่อยขนาดเล็ก ในวิทยานิพนธ์นี้ เราสนใจการปรับปรุงเฉพาะขั้นตอนวิธีการเกาะกลุ่มที่เรียกว่า การแบ่งกั้นรอบเมดอยด์ (PAM) ขั้นตอนวิธีแพมค้นหาตัวแทนของแต่ละกลุ่มที่เรียก เมดอยด์ ซึ่งใช้คำนวณระยะทางรวมที่น้อยที่สุดจากเมดอยด์ไปยังจุดข้อมูลในกลุ่ม ในแต่ละรอบ วิธีแพมเลือกคู่สลับที่ดีที่สุดระหว่างเมดอยด์กับจุดข้อมูล โดยเปรียบเทียบระยะระหว่างทุกคู่ของการสลับ ทำให้ขั้นตอนวิธีแพมใช้เวลาประมวลผลนานต่อหนึ่งรอบการคำนวณ เราเสนอแนะการปรับปรุงขั้นตอนวิธีแพมผ่านขั้นตอนวิธี 4 แบบ ขั้นตอนวิธีแรกลดเวลาที่ใช้ในการเลือกคู่สลับที่ดีที่สุด โดยยอมรับคู่สลับคู่แรกที่ทำให้ผลรวมของระยะทางทั้งหมดดีขึ้น อย่างไรก็ดีวิธีการดังกล่าวทำให้จำนวนรอบของการประมวลผลมาก จึงทำให้ขั้นตอนวิธีแรกประมวลผลช้ากว่าขั้นตอนวิธีแพม ขั้นตอนวิธีที่สองปรับปรุงจากขั้นตอนวิธีแรกโดยการจัดเรียงคู่ของการสลับที่เหมาะสมก่อนการวนซ้ำ โดยเรียงลำดับเมดอยด์จาก 4 กลยุทธ์ วิธีการดังกล่าวเพิ่มประสิทธิภาพในการทำงานเพียงเล็กน้อย เพราะเมดอยด์ที่เหมาะสมยังไม่ถูกพบในตอนต้นของการทำงาน ขั้นตอนวิธีที่สามปรับปรุงจากขั้นตอนวิธีที่สองโดยเลือกคู่สลับคู่แรกที่ดีที่สุดก่อน แล้วจึงใช้วิธีปรับปรุงการวนซ้ำของรอบที่เหลือ วิธีการนี้ใช้ได้ดี อย่างไรก็ตามผลรวมของเวลาที่ใช้ในการประมวลผล ยังคงช้ากว่าขั้นตอนวิธีแพม ดังนั้นเราเสนอขั้นตอนวิธีสุดท้ายซึ่งปรับปรุงมาจากขั้นตอนวิธีที่สาม โดยพิจารณาการเลือกคู่สลับในกลุ่มก่อน หลังจากในรอบแรกผ่านไป วิธีดังกล่าวแสดงเวลาประมวลผลที่ดีที่สุดในขั้นตอนวิธีทั้งหมดรวมทั้งแพม ในการทดลองของเรากับข้อมูลที่จำลองมาจาก 2-20 มิติ ค่าเฉลี่ยของเวลาที่ใช้ในการประมวลผล 100 ตัวอย่างแสดงเวลาที่ดีกว่าในกลุ่มของขั้นตอนวิธีเหล่านี้ นอกจากนี้ สำหรับจำนวนจุดข้อมูลที่คงที่ มิติที่มากขึ้นนำไปสู่การใช้เวลาในการประมวลผลที่ลดลง |
| Other Abstract: | Cluster analysis is one of the data mining methodology which researchers use to partition data set into smaller groups. In this thesis, we are interested in improving one special clustering algorithm called Partitioning Around Medoid (PAM). PAM algorithm searches for the representatives for each group named medoid which constitutes the total minimal distance from a medoid to data points within a group. In each iteration, PAM determines the best swapping pair between a medoid and a data point by comparing all possible pairs. This causes PAM algorithm to run slowly per iteration. We suggest improving PAM algorithm via four successive algorithms. The first algorithm reduces the time to determine the best swapping pair by accepting the first swapping pair that improves the total distance. However, this increases the number of iterations that causes this first algorithm to run slower than PAM algorithm. The second algorithm improves from the first algorithm by ordering the most appropriate pair to be considered at the beginning of iterations by sorting medoids via 4 strategies. This gives a little improvement of the total running since the appropriate medoids are not found earlier. The third algorithm improves the second algorithm by choosing the best swapping pair for the first iteration, then it performs the iterative improvement for other iterations. This works well. However, the total running is still slower than PAM algorithm. Therefore, we suggest the last algorithm which improves the third algorithm by first considering the swapping pair within a medoid's group after the first iteration has been performed. This shows the best running time among all algorithms including PAM. In our experiment with the simulated data varying dimensions from 2 to 20, the average running time of 100 runs show the superior running time among other algorithms. Moreover, for a fixed number of data point, the larger the dimension, the lower the running time. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2550 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาการคณนา |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/14311 |
| URI: | http://doi.org/10.14457/CU.the.2007.1955 |
| metadata.dc.identifier.DOI: | 10.14457/CU.the.2007.1955 |
| Type: | Thesis |
| Appears in Collections: | Sci - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Roungroj_Po.pdf | 1.05 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.