|
การปรับปรุงขั้นตอนวิธีแบ่งส่วนรอบเมดอยด์ |
|---|---|
| รหัสดีโอไอ | |
| Title | การปรับปรุงขั้นตอนวิธีแบ่งส่วนรอบเมดอยด์ |
| Creator | รุ่งโรจน์ พุ่มดวง |
| Contributor | กรุง สินอภิรมย์สราญ |
| Publisher | จุฬาลงกรณ์มหาวิทยาลัย |
| Publication Year | 2550 |
| Keyword | การวิเคราะห์จัดกลุ่ม, ดาต้าไมนิง, การแบ่งส่วน (คณิตศาสตร์) |
| Abstract | การวิเคราะห์การเกาะกลุ่มเป็นหนึ่งในหลักการทำเหมืองข้อมูล ซึ่งผู้วิจัยใช้แบ่งกั้นเซตข้อมูลออกเป็นกลุ่มย่อยขนาดเล็ก ในวิทยานิพนธ์นี้ เราสนใจการปรับปรุงเฉพาะขั้นตอนวิธีการเกาะกลุ่มที่เรียกว่า การแบ่งกั้นรอบเมดอยด์ (PAM) ขั้นตอนวิธีแพมค้นหาตัวแทนของแต่ละกลุ่มที่เรียก เมดอยด์ ซึ่งใช้คำนวณระยะทางรวมที่น้อยที่สุดจากเมดอยด์ไปยังจุดข้อมูลในกลุ่ม ในแต่ละรอบ วิธีแพมเลือกคู่สลับที่ดีที่สุดระหว่างเมดอยด์กับจุดข้อมูล โดยเปรียบเทียบระยะระหว่างทุกคู่ของการสลับ ทำให้ขั้นตอนวิธีแพมใช้เวลาประมวลผลนานต่อหนึ่งรอบการคำนวณ เราเสนอแนะการปรับปรุงขั้นตอนวิธีแพมผ่านขั้นตอนวิธี 4 แบบ ขั้นตอนวิธีแรกลดเวลาที่ใช้ในการเลือกคู่สลับที่ดีที่สุด โดยยอมรับคู่สลับคู่แรกที่ทำให้ผลรวมของระยะทางทั้งหมดดีขึ้น อย่างไรก็ดีวิธีการดังกล่าวทำให้จำนวนรอบของการประมวลผลมาก จึงทำให้ขั้นตอนวิธีแรกประมวลผลช้ากว่าขั้นตอนวิธีแพม ขั้นตอนวิธีที่สองปรับปรุงจากขั้นตอนวิธีแรกโดยการจัดเรียงคู่ของการสลับที่เหมาะสมก่อนการวนซ้ำ โดยเรียงลำดับเมดอยด์จาก 4 กลยุทธ์ วิธีการดังกล่าวเพิ่มประสิทธิภาพในการทำงานเพียงเล็กน้อย เพราะเมดอยด์ที่เหมาะสมยังไม่ถูกพบในตอนต้นของการทำงาน ขั้นตอนวิธีที่สามปรับปรุงจากขั้นตอนวิธีที่สองโดยเลือกคู่สลับคู่แรกที่ดีที่สุดก่อน แล้วจึงใช้วิธีปรับปรุงการวนซ้ำของรอบที่เหลือ วิธีการนี้ใช้ได้ดี อย่างไรก็ตามผลรวมของเวลาที่ใช้ในการประมวลผล ยังคงช้ากว่าขั้นตอนวิธีแพม ดังนั้นเราเสนอขั้นตอนวิธีสุดท้ายซึ่งปรับปรุงมาจากขั้นตอนวิธีที่สาม โดยพิจารณาการเลือกคู่สลับในกลุ่มก่อน หลังจากในรอบแรกผ่านไป วิธีดังกล่าวแสดงเวลาประมวลผลที่ดีที่สุดในขั้นตอนวิธีทั้งหมดรวมทั้งแพม ในการทดลองของเรากับข้อมูลที่จำลองมาจาก 2-20 มิติ ค่าเฉลี่ยของเวลาที่ใช้ในการประมวลผล 100 ตัวอย่างแสดงเวลาที่ดีกว่าในกลุ่มของขั้นตอนวิธีเหล่านี้ นอกจากนี้ สำหรับจำนวนจุดข้อมูลที่คงที่ มิติที่มากขึ้นนำไปสู่การใช้เวลาในการประมวลผลที่ลดลง |
| URL Website | cuir.car.chula.ac.th |
