วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2550

การวิเคราะห์การเกาะกลุ่มเป็นหนึ่งในหลักการทำเหมืองข้อมูล ซึ่งผู้วิจัยใช้แบ่งกั้นเซตข้อมูลออกเป็นกลุ่มย่อยขนาดเล็ก ในวิทยานิพนธ์นี้ เราสนใจการปรับปรุงเฉพาะขั้นตอนวิธีการเกาะกลุ่มที่เรียกว่า การแบ่งกั้นรอบเมดอยด์ (PAM) ขั้นตอนวิธีแพมค้นหาตัวแทนของแต่ละกลุ่มที่เรียก เมดอยด์ ซึ่งใช้คำนวณระยะทางรวมที่น้อยที่สุดจากเมดอยด์ไปยังจุดข้อมูลในกลุ่ม ในแต่ละรอบ วิธีแพมเลือกคู่สลับที่ดีที่สุดระหว่างเมดอยด์กับจุดข้อมูล โดยเปรียบเทียบระยะระหว่างทุกคู่ของการสลับ ทำให้ขั้นตอนวิธีแพมใช้เวลาประมวลผลนานต่อหนึ่งรอบการคำนวณ เราเสนอแนะการปรับปรุงขั้นตอนวิธีแพมผ่านขั้นตอนวิธี 4 แบบ ขั้นตอนวิธีแรกลดเวลาที่ใช้ในการเลือกคู่สลับที่ดีที่สุด โดยยอมรับคู่สลับคู่แรกที่ทำให้ผลรวมของระยะทางทั้งหมดดีขึ้น อย่างไรก็ดีวิธีการดังกล่าวทำให้จำนวนรอบของการประมวลผลมาก จึงทำให้ขั้นตอนวิธีแรกประมวลผลช้ากว่าขั้นตอนวิธีแพม ขั้นตอนวิธีที่สองปรับปรุงจากขั้นตอนวิธีแรกโดยการจัดเรียงคู่ของการสลับที่เหมาะสมก่อนการวนซ้ำ โดยเรียงลำดับเมดอยด์จาก 4 กลยุทธ์ วิธีการดังกล่าวเพิ่มประสิทธิภาพในการทำงานเพียงเล็กน้อย เพราะเมดอยด์ที่เหมาะสมยังไม่ถูกพบในตอนต้นของการทำงาน ขั้นตอนวิธีที่สามปรับปรุงจากขั้นตอนวิธีที่สองโดยเลือกคู่สลับคู่แรกที่ดีที่สุดก่อน แล้วจึงใช้วิธีปรับปรุงการวนซ้ำของรอบที่เหลือ วิธีการนี้ใช้ได้ดี อย่างไรก็ตามผลรวมของเวลาที่ใช้ในการประมวลผล ยังคงช้ากว่าขั้นตอนวิธีแพม ดังนั้นเราเสนอขั้นตอนวิธีสุดท้ายซึ่งปรับปรุงมาจากขั้นตอนวิธีที่สาม โดยพิจารณาการเลือกคู่สลับในกลุ่มก่อน หลังจากในรอบแรกผ่านไป วิธีดังกล่าวแสดงเวลาประมวลผลที่ดีที่สุดในขั้นตอนวิธีทั้งหมดรวมทั้งแพม ในการทดลองของเรากับข้อมูลที่จำลองมาจาก 2-20 มิติ ค่าเฉลี่ยของเวลาที่ใช้ในการประมวลผล 100 ตัวอย่างแสดงเวลาที่ดีกว่าในกลุ่มของขั้นตอนวิธีเหล่านี้ นอกจากนี้ สำหรับจำนวนจุดข้อมูลที่คงที่ มิติที่มากขึ้นนำไปสู่การใช้เวลาในการประมวลผลที่ลดลง