ในทฤษฎีการวิเคราะห์คลัสเตอร์อัลกอริทึมลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดเป็นอัลกอริทึมที่สามารถเร่งความเร็ววิธีการจัดกลุ่มแบบลำดับชั้นแบบรวมกลุ่ม ได้หลาย วิธี วิธีการเหล่านี้รับชุดจุดเป็นอินพุต และสร้างลำดับชั้นของคลัสเตอร์จุดโดยการรวมคลัสเตอร์ขนาดเล็กสองคู่เข้าด้วยกันซ้ำๆ เพื่อสร้างคลัสเตอร์ขนาดใหญ่ วิธีการจัดกลุ่มที่สามารถใช้อัลกอริทึมลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดได้ ได้แก่วิธีของวอร์ด การจัด กลุ่มแบบเชื่อมโยงสมบูรณ์และการจัดกลุ่มแบบเชื่อมโยงเดี่ยว ซึ่งทั้งหมดนี้ทำงาน โดยการรวมคลัสเตอร์สองกลุ่มที่ใกล้ที่สุดเข้าด้วยกันซ้ำๆ แต่ใช้คำจำกัดความของระยะห่างระหว่างคลัสเตอร์ที่แตกต่างกัน ระยะห่างระหว่างคลัสเตอร์ที่อัลกอริทึมลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดใช้งานได้เรียกว่าระยะห่างที่ลดทอนได้และมีลักษณะเฉพาะด้วยอสมการอย่างง่ายระหว่างระยะห่างระหว่างคลัสเตอร์บางอย่าง

แนวคิดหลักของอัลกอริทึมนี้คือการค้นหาคู่ของกลุ่มข้อมูลที่จะรวมเข้าด้วยกันโดยการติดตามเส้นทางในกราฟเพื่อนบ้านที่ใกล้ที่สุดของกลุ่มข้อมูลเหล่านั้น เส้นทางแต่ละเส้นจะสิ้นสุดลงที่คู่ของกลุ่มข้อมูลที่เป็นเพื่อนบ้านที่ใกล้ที่สุด และอัลกอริทึมจะเลือกคู่ของกลุ่มข้อมูลนั้นเป็นคู่ที่จะรวมเข้าด้วยกัน เพื่อประหยัดเวลาโดยการใช้เส้นทางแต่ละเส้นซ้ำให้มากที่สุด อัลกอริทึมจึงใช้โครงสร้างข้อมูลแบบสแต็กเพื่อติดตามเส้นทางแต่ละเส้นที่มันติดตาม ด้วยการติดตามเส้นทางในลักษณะนี้ อัลกอริทึมแบบลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดจะรวมกลุ่มข้อมูลในลำดับที่แตกต่างจากวิธีการที่ค้นหาและรวมคู่ของกลุ่มข้อมูลที่ใกล้ที่สุดเสมอ อย่างไรก็ตาม แม้จะมีความแตกต่างนั้น อัลกอริทึมนี้ก็สร้างลำดับชั้นของกลุ่มข้อมูลเดียวกันเสมอ

อัลกอริทึม การจัดกลุ่มแบบเพื่อนบ้านที่ใกล้ที่สุด (nearest-neighbor chain algorithm) สร้างการจัดกลุ่มในเวลาที่แปรผันตรงกับกำลังสองของจำนวนจุดที่จะจัดกลุ่ม นอกจากนี้ยังแปรผันตรงกับขนาดของข้อมูลนำเข้า เมื่อข้อมูลนำเข้าอยู่ในรูปของเมทริกซ์ระยะทาง ที่ระบุไว้อย่างชัดเจน อัลกอริทึมนี้ใช้หน่วยความจำในปริมาณที่แปรผันตรงกับจำนวนจุด เมื่อใช้กับวิธีการจัดกลุ่ม เช่น วิธีของวอร์ด (Ward's method) ซึ่งช่วยให้คำนวณระยะทางระหว่างกลุ่มได้ในเวลาคงที่ อย่างไรก็ตาม สำหรับวิธีการจัดกลุ่มอื่นๆ บางวิธี อัลกอริทึมนี้ใช้หน่วยความจำในปริมาณที่มากกว่าในโครงสร้างข้อมูลเสริมที่ใช้ในการติดตามระยะทางระหว่างคู่ของกลุ่มต่างๆ

ปัญหามากมายในการวิเคราะห์ข้อมูลเกี่ยวข้องกับ การ จัดกลุ่ม (clustering) ซึ่งเป็นการ จัดกลุ่มรายการข้อมูลเข้าเป็นกลุ่มของรายการที่มีความสัมพันธ์กันอย่างใกล้ ชิด การจัดกลุ่มแบบลำดับชั้น (Hierarchical clustering)เป็นรูปแบบหนึ่งของการวิเคราะห์กลุ่ม (cluster analysis) ซึ่งกลุ่มต่างๆ จะก่อตัวเป็นโครงสร้างแบบลำดับชั้นหรือแบบต้นไม้ แทนที่จะเป็นการแบ่งแยกรายการข้อมูลอย่างเคร่งครัด ในบางกรณี การจัดกลุ่มประเภทนี้อาจดำเนินการเพื่อวิเคราะห์กลุ่มในหลายระดับพร้อมกัน ในกรณีอื่นๆ ข้อมูลที่จะวิเคราะห์โดยธรรมชาติมีโครงสร้างแบบต้นไม้ที่ไม่ทราบ และเป้าหมายคือการกู้คืนโครงสร้างนั้นโดยการวิเคราะห์ การวิเคราะห์ทั้งสองประเภทนี้สามารถพบได้ เช่น ในการประยุกต์ใช้การจัดกลุ่มแบบลำดับชั้นกับอนุกรมวิธานทางชีววิทยาในการประยุกต์ใช้นี้ สิ่งมีชีวิตต่างๆ จะถูกจัดกลุ่มเป็นกลุ่มในระดับหรือระดับความคล้ายคลึงกันที่แตกต่างกัน ( เช่น สปีชีส์ สกุล วงศ์ เป็นต้น ) การวิเคราะห์นี้ให้การจัดกลุ่มสิ่งมีชีวิตในหลายระดับพร้อมกันในยุคปัจจุบัน และมีเป้าหมายเพื่อสร้างกระบวนการแตกแขนงหรือต้นไม้แห่งวิวัฒนาการที่ก่อให้เกิดสิ่งมีชีวิตเหล่านี้ในอดีต ได้อย่างแม่นยำ ^{[ 1 ]}

อินพุตของปัญหาการจัดกลุ่มประกอบด้วยชุดของจุด^{[ 2 ]}กลุ่มคือเซตย่อยที่เหมาะสมของจุด และการจัดกลุ่มแบบลำดับชั้นคือตระกูล กลุ่ม สูงสุดที่มีคุณสมบัติว่ากลุ่มสองกลุ่มใดๆ ในตระกูลนั้นจะซ้อนกันหรือไม่ทับ ซ้อนกันก็ได้ หรือ อีกทางหนึ่ง การจัดกลุ่มแบบลำดับชั้นอาจแสดงเป็นต้นไม้ไบนารีที่มีจุดอยู่ที่ใบ กลุ่มของการจัดกลุ่มคือชุดของจุดในต้นไม้ย่อยที่สืบลงมาจากแต่ละโหนดของต้นไม้^{[ 3 ]}

ในวิธีการจัดกลุ่มแบบรวมกลุ่ม ข้อมูลนำเข้ายังรวมถึงฟังก์ชันระยะทางที่กำหนดบนจุด หรือการวัดเชิงตัวเลขของความไม่เหมือนกัน ระยะทางหรือความไม่เหมือนกันควรมีความสมมาตร กล่าวคือ ระยะทางระหว่างสองจุดไม่ขึ้นอยู่กับว่าจุดใดถูกพิจารณาก่อน อย่างไรก็ตาม ต่างจากระยะทางในปริภูมิเมตริกไม่จำเป็นต้องเป็นไปตามอสมการสามเหลี่ยม^{[ 2 ]} ต่อมา ฟังก์ชันความไม่เหมือนกันจะถูกขยายจากคู่ของจุดไปยังคู่ของกลุ่ม วิธีการจัดกลุ่มที่แตกต่างกันจะดำเนินการขยายนี้ในรูปแบบที่แตกต่างกัน ตัวอย่างเช่น ใน วิธีการ จัดกลุ่มแบบเชื่อมโยงเดี่ยวระยะทางระหว่างสองกลุ่มถูกกำหนดให้เป็นระยะทางขั้นต่ำระหว่างจุดสองจุดใดๆ จากแต่ละกลุ่ม เมื่อกำหนดระยะทางระหว่างกลุ่มนี้แล้ว การจัดกลุ่มแบบลำดับชั้นอาจถูกกำหนดโดยอัลกอริทึมแบบโลภที่ในตอนแรกวางแต่ละจุดไว้ในกลุ่มจุดเดียวของตนเอง จากนั้นสร้างกลุ่มใหม่ซ้ำๆ โดยการรวม คู่ กลุ่มที่ใกล้ที่สุด^{[ 2 ]}

ข้อจำกัดของอัลกอริทึมแบบโลภนี้คือปัญหาย่อยของการค้นหากลุ่มคลัสเตอร์สองกลุ่มที่จะรวมเข้าด้วยกันในแต่ละขั้นตอน วิธีการที่ทราบกันดีสำหรับการค้นหากลุ่มคลัสเตอร์คู่ที่ใกล้ที่สุดซ้ำๆ ในชุดคลัสเตอร์แบบไดนามิกนั้น จำเป็นต้องใช้พื้นที่มากกว่าเชิงเส้นเพื่อรักษาโครงสร้างข้อมูลที่สามารถค้นหาคู่ที่ใกล้ที่สุดได้อย่างรวดเร็ว หรือต้องใช้เวลามากกว่าเชิงเส้นในการค้นหาคู่ที่ใกล้ที่สุดแต่ละคู่^{[ 4 ] [ 5 ]}อัลกอริทึมแบบลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดใช้เวลาและพื้นที่น้อยกว่าอัลกอริทึมแบบโลภโดยการรวมกลุ่มคลัสเตอร์เป็นคู่ๆ ในลำดับที่แตกต่างกัน ด้วยวิธีนี้จึงหลีกเลี่ยงปัญหาการค้นหาคู่ที่ใกล้ที่สุดซ้ำๆ อย่างไรก็ตาม สำหรับปัญหาการจัดกลุ่มหลายประเภท สามารถรับประกันได้ว่าจะได้การจัดกลุ่มแบบลำดับชั้นเดียวกันกับอัลกอริทึมแบบโลภแม้ว่าลำดับการรวมจะแตกต่างกันก็ตาม^{[ 2 ]}

โดยสัญชาตญาณ อัลกอริทึมห่วงโซ่เพื่อนบ้านที่ใกล้ที่สุดจะติดตามห่วงโซ่ของกลุ่มA → B → C → ... ซ้ำๆ โดยที่แต่ละกลุ่มเป็นเพื่อนบ้านที่ใกล้ที่สุดของกลุ่มก่อนหน้า จนกระทั่งถึงคู่ของกลุ่มที่เป็นเพื่อนบ้านที่ใกล้ที่สุดซึ่งกันและกัน^{[ 2 ]}

โดยรายละเอียดเพิ่มเติม อัลกอริทึมจะดำเนินการตามขั้นตอนต่อไปนี้: ^{[ 2 ] [ 6 ]}

• เริ่มต้นชุดคลัสเตอร์ที่ใช้งานอยู่ให้ประกอบด้วยคลัสเตอร์แบบจุดเดียวจำนวนn คลัสเตอร์ โดยแต่ละคลัสเตอร์แทนจุดข้อมูลขาเข้าแต่ละจุด
• ให้Sเป็นโครงสร้างข้อมูลแบบสแต็กซึ่งว่างเปล่าในตอนเริ่มต้น โดยที่องค์ประกอบของสแต็กจะเป็นคลัสเตอร์ที่ทำงานอยู่
• แม้ว่าจะมีคลัสเตอร์มากกว่าหนึ่งคลัสเตอร์ในชุดคลัสเตอร์:
  • ถ้าSว่างเปล่า ให้เลือกคลัสเตอร์ที่ใช้งานอยู่โดยพลการ แล้วผลักคลัสเตอร์นั้นเข้าไปในS
  • ให้Cเป็นคลัสเตอร์ที่ทำงานอยู่บนสุดของSคำนวณระยะห่างจากCไปยังคลัสเตอร์อื่นๆ ทั้งหมด และให้Dเป็นคลัสเตอร์อื่นที่อยู่ใกล้ที่สุด
  • ถ้าDอยู่ในS อยู่แล้ว แสดงว่า D ต้องเป็นบรรพบุรุษโดยตรงของCนำคลัสเตอร์ทั้งสองออกจากSแล้วรวมเข้าด้วยกัน
  • มิฉะนั้น หากDยังไม่ได้อยู่ในSให้เพิ่ม D เข้าไปในS

เมื่อเป็นไปได้ที่คลัสเตอร์หนึ่งจะมีเพื่อนบ้านที่ใกล้ที่สุดที่เท่ากันหลายตัว อัลกอริทึมจะต้องใช้กฎการตัดสินความเสมอภาคที่สอดคล้องกัน ตัวอย่างเช่น อาจกำหนดหมายเลขดัชนีแบบสุ่มให้กับคลัสเตอร์ทั้งหมด จากนั้นเลือก (ในบรรดาเพื่อนบ้านที่ใกล้ที่สุดที่เท่ากัน) คลัสเตอร์ที่มีหมายเลขดัชนีน้อยที่สุด กฎนี้จะป้องกันพฤติกรรมที่ไม่สอดคล้องกันบางประเภทในอัลกอริทึม ตัวอย่างเช่น หากไม่มีกฎดังกล่าว คลัสเตอร์เพื่อนบ้านDอาจเกิดขึ้นก่อนในสแต็กมากกว่าที่จะเป็นตัวก่อนหน้า^ของ C ^{[ 7} ]

ในแต่ละรอบของการวนซ้ำ จะทำการค้นหาเพื่อนบ้านที่ใกล้ที่สุดของกลุ่มเพียงครั้งเดียว และจะเพิ่มกลุ่มหนึ่งลงในสแต็กหรือลบกลุ่มสองกลุ่มออกจากสแต็ก กลุ่มแต่ละกลุ่มจะถูกเพิ่มลงในสแต็กเพียงครั้งเดียวเท่านั้น เพราะเมื่อถูกลบออกอีกครั้ง กลุ่มนั้นจะถูกทำให้ไม่ทำงานและรวมเข้าด้วยกันทันที มีกลุ่มทั้งหมด2 n − 2กลุ่มที่จะถูกเพิ่มลงในสแต็ก ได้แก่ กลุ่มจุดเดียว nกลุ่มในชุดเริ่มต้น และ โหนดภายใน n − 2โหนดที่ไม่ใช่รากในต้นไม้ไบนารีที่แสดงถึงการจัดกลุ่ม ดังนั้น อัลกอริทึมจึงทำการวนซ้ำแบบ ผลัก 2 n − 2ครั้ง และวนซ้ำแบบดึงออกn − 1 ครั้ง ^{[ 2 ]}

แต่ละรอบการวนซ้ำเหล่านี้อาจใช้เวลาในการสแกน ระยะห่างระหว่างคลัสเตอร์มากถึงn − 1 เพื่อหาเพื่อนบ้านที่ใกล้ที่สุด ดังนั้นจำนวนการคำนวณระยะทางทั้งหมดจึงน้อยกว่า 3 n ²ด้วยเหตุผลเดียวกัน เวลาทั้งหมดที่ใช้โดยอัลกอริทึมนอกเหนือจากการคำนวณระยะทางเหล่านี้คือO ( n ² ) ^{[ 2 ]}

เนื่องจากโครงสร้างข้อมูลเพียงอย่างเดียวคือเซตของคลัสเตอร์ที่ใช้งานอยู่และสแต็กที่มีคลัสเตอร์ที่ใช้งานอยู่ย่อย พื้นที่ที่ต้องการจึงเป็นเชิงเส้นตามจำนวนจุดอินพุต^{[ 2 ]}

เพื่อให้ขั้นตอนวิธีถูกต้อง จะต้องเป็นกรณีที่การดึงและรวมคลัสเตอร์สองอันดับแรกจากสแต็กของขั้นตอนวิธีรักษาคุณสมบัติที่ว่าคลัสเตอร์ที่เหลืออยู่บนสแต็กจะก่อตัวเป็นห่วงโซ่ของเพื่อนบ้านที่ใกล้ที่สุด นอกจากนี้ คลัสเตอร์ทั้งหมดที่สร้างขึ้นระหว่างขั้นตอนวิธีจะต้องเหมือนกับคลัสเตอร์ที่สร้างขึ้นโดยขั้นตอนวิธีแบบโลภที่รวมคลัสเตอร์สองคลัสเตอร์ที่ใกล้ที่สุดเสมอ แม้ว่าโดยทั่วไปแล้วขั้นตอนวิธีแบบโลภจะทำการรวมในลำดับที่แตกต่างจากขั้นตอนวิธีห่วงโซ่เพื่อนบ้านที่ใกล้ที่สุดก็ตาม คุณสมบัติทั้งสองนี้ขึ้นอยู่กับการเลือกวิธีการวัดระยะห่างระหว่างคลัสเตอร์โดยเฉพาะ^{[ 2 ]}

ความถูกต้องของอัลกอริทึมนี้ขึ้นอยู่กับคุณสมบัติของฟังก์ชันระยะทางที่เรียกว่าความสามารถในการลดทอนคุณสมบัตินี้ถูกระบุโดยBruynooghe (1977)ในส่วนที่เกี่ยวข้องกับวิธีการจัดกลุ่มก่อนหน้านี้ที่ใช้คู่เพื่อนบ้านที่ใกล้ที่สุดร่วมกัน แต่ไม่ได้ใช้สายโซ่ของเพื่อนบ้านที่ใกล้ที่สุด^{[ 8 ]}ฟังก์ชันระยะทางdบนคลัสเตอร์จะถูกกำหนดให้สามารถลดทอนได้ ถ้าสำหรับคลัสเตอร์A , BและC ใดๆ ในการจัดกลุ่มแบบลำดับชั้นแบบโลภ โดยที่AและBเป็นเพื่อนบ้านที่ใกล้ที่สุดร่วมกัน อสมการต่อไปนี้เป็นจริง: ^{[ 2 ]}

d ( A ∪ B , C ) ≥ min(d( A , C ), d( B , C )) .

ถ้าฟังก์ชันระยะทางมีคุณสมบัติการลดทอนได้ การรวมคลัสเตอร์CและD สองคลัสเตอร์ จะทำให้เพื่อนบ้านที่ใกล้ที่สุดของEเปลี่ยนไปได้ก็ต่อเมื่อเพื่อนบ้านที่ใกล้ที่สุดนั้นเป็นหนึ่งในCและDเท่านั้น สิ่งนี้มีผลสำคัญสองประการสำหรับอัลกอริทึมห่วงโซ่เพื่อนบ้านที่ใกล้ที่สุด ประการแรก สามารถแสดงได้โดยใช้คุณสมบัตินี้ว่า ในแต่ละขั้นตอนของอัลกอริทึม คลัสเตอร์บนสแต็กSจะสร้างห่วงโซ่เพื่อนบ้านที่ใกล้ที่สุดที่ถูกต้อง เนื่องจากเมื่อใดก็ตามที่เพื่อนบ้านที่ใกล้ที่สุดไม่ถูกต้อง มันจะถูกลบออกจากสแต็กทันที^{[ 2 ]}

ประการที่สอง และที่สำคัญยิ่งกว่านั้น คือ จากคุณสมบัตินี้ หากคลัสเตอร์CและDทั้งสองอยู่ในคลัสเตอร์แบบลำดับชั้นแบบโลภ และเป็นเพื่อนบ้านที่ใกล้ที่สุดซึ่งกันและกัน ณ จุดเวลาใดๆ คลัสเตอร์แบบโลภก็จะรวมคลัสเตอร์ทั้งสองเข้าด้วยกัน เนื่องจากคลัสเตอร์ทั้งสองจะต้องยังคงเป็นเพื่อนบ้านที่ใกล้ที่สุดซึ่งกันและกันจนกว่าจะรวมเข้าด้วยกัน ดังนั้นจึงสรุปได้ว่า คู่เพื่อนบ้านที่ใกล้ที่สุดซึ่งกันและกันที่พบโดยอัลกอริทึมแบบลูกโซ่เพื่อนบ้านที่ใกล้ที่สุด ก็เป็นคู่คลัสเตอร์ที่พบโดยอัลกอริทึมแบบโลภเช่นกัน ดังนั้น อัลกอริทึมแบบลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดจึงคำนวณคลัสเตอร์แบบเดียวกัน (แม้ว่าจะอยู่ในลำดับที่แตกต่างกัน) กับอัลกอริทึมแบบโลภ^{[ 2 ]}

วิธีของ Wardเป็นวิธีการจัดกลุ่มแบบรวมกลุ่มซึ่งวัดความแตกต่างระหว่างสองกลุ่มAและB โดยพิจารณาจากปริมาณที่การรวมสองกลุ่มเข้าเป็นกลุ่มใหญ่กลุ่มเดียวจะเพิ่มระยะทางกำลังสองเฉลี่ยของจุด ไป ยัง จุดศูนย์กลางของกลุ่ม^{[ 9 ]}นั่นคือ

${\displaystyle d(A,B)=\sum _{x\in A,y\in B}{\frac {d^{2}(x,y)}{|A|+|B|}}-\sum _{x,y\in A}{\frac {d^{2}(x,y)}{|A|}}-\sum _{x,y\in B}{\frac {d^{2}(x,y)}{|B|}}.}$

เมื่อแสดงในรูปของจุดศูนย์กลางและจำนวนสมาชิกของคลัสเตอร์ทั้งสอง จะได้สูตรที่ง่ายกว่า ${\displaystyle c_{A}}$${\displaystyle n_{A}}$

${\displaystyle d(A,B)={\frac {d^{2}(c_{a},c_{b})}{1/n_{A}+1/n_{B}}},}$

ทำให้สามารถคำนวณได้ในเวลาคงที่ต่อการคำนวณระยะทาง แม้ว่าจะมีความไวต่อค่าผิดปกติ สูง แต่วิธีของ Ward ก็เป็นรูปแบบที่ได้รับความนิยมมากที่สุดของการจัดกลุ่มแบบรวมกลุ่ม ทั้งเนื่องจากรูปร่างกลมของกลุ่มที่มักจะเกิดขึ้น และเนื่องจากคำจำกัดความตามหลักการว่าเป็นการจัดกลุ่มที่ในแต่ละขั้นตอนมีความแปรปรวนน้อยที่สุดภายในกลุ่ม^{[ 10 ]} อีกทางหนึ่ง ระยะทางนี้สามารถมองได้ว่าเป็นความแตกต่างในต้นทุน k-meansระหว่างกลุ่มใหม่และกลุ่มเก่าสองกลุ่ม

ระยะทางของ Ward สามารถลดทอนได้เช่นกัน ดังที่เห็นได้ง่ายกว่าจากสูตรที่แตกต่างกันสำหรับการคำนวณระยะทางของกลุ่มที่รวมกันจากระยะทางของกลุ่มที่รวมเข้าด้วยกัน: ^{[ 9 ] [ 11 ]}

${\displaystyle d(A\cup B,C)={\frac {n_{A}+n_{C}}{n_{A}+n_{B}+n_{C}}}d(A,C)+{\frac {n_{B}+n_{C}}{n_{A}+n_{B}+n_{C}}}d(B,C)-{\frac {n_{C}}{n_{A}+n_{B}+n_{C}}}d(A,B).}$

สูตรการปรับปรุงระยะทางเช่นนี้เรียกว่าสูตร "แบบแลนซ์-วิลเลียมส์" ตามผลงานของแลนซ์และวิลเลียมส์ (1967)ถ้าเป็นระยะทางที่เล็กที่สุดในสามระยะทางทางด้านขวามือ (ซึ่งจะเป็นจริงอย่างแน่นอนหากและเป็นเพื่อนบ้านที่ใกล้ที่สุดซึ่งกันและกัน) แล้วค่าลบจากพจน์ของมันจะหักล้างด้วยสัมประสิทธิ์ของหนึ่งในสองพจน์ที่เหลือ ทำให้เหลือค่าบวกที่เพิ่มเข้าไปในค่าเฉลี่ยถ่วงน้ำหนักของระยะทางอีกสองระยะทาง ดังนั้น ระยะทางรวมจึงมีค่าอย่างน้อยเท่ากับค่าต่ำสุดของและเสมอ ซึ่งตรงตามนิยามของการลดทอนได้ ${\displaystyle d(A,B)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n_{C}}$${\displaystyle d(A,C)}$${\displaystyle d(B,C)}$

เนื่องจากระยะทางของ Ward สามารถลดทอนได้ อัลกอริทึมโซ่เพื่อนบ้านที่ใกล้ที่สุดโดยใช้ระยะทางของ Ward จึงคำนวณการจัดกลุ่มแบบเดียวกันกับอัลกอริทึมโลภมาตรฐาน สำหรับ จุด nจุดใน พื้นที่ ^ยุคลิดที่มีมิติคงที่ จะใช้เวลาO ( n ² )และพื้นที่O ( n ) [ ^{6 ]}

การจัดกลุ่ม แบบเชื่อมโยงสมบูรณ์หรือการจัดกลุ่มแบบเพื่อนบ้านไกลสุดเป็นรูปแบบหนึ่งของการจัดกลุ่มแบบรวมกลุ่มที่กำหนดความแตกต่างระหว่างกลุ่มให้เป็นระยะทางสูงสุดระหว่างจุดสองจุดใดๆ จากสองกลุ่มนั้น ในทำนองเดียวกัน การจัดกลุ่มแบบระยะทางเฉลี่ยใช้ระยะทางเฉลี่ยระหว่างคู่เป็นความแตกต่าง เช่นเดียวกับระยะทางของ Ward รูปแบบการจัดกลุ่มทั้งสองนี้เป็นไปตามสูตรประเภท Lance–Williams ในการเชื่อมโยงสมบูรณ์ ระยะทางคือค่าสูงสุดของระยะทางสองค่าและดังนั้น จึงต้องมีค่าอย่างน้อยเท่ากับค่าต่ำสุดของระยะทางสองค่านี้ ซึ่งเป็นข้อกำหนดสำหรับการลดทอนได้ สำหรับระยะทางเฉลี่ยคือค่าเฉลี่ยถ่วงน้ำหนักของระยะทางและอีกครั้ง ค่านี้ต้องมีค่าอย่างน้อยเท่ากับค่าต่ำสุดของระยะทางสองค่า ดังนั้น ในทั้งสองกรณี ระยะทางจึงสามารถลดทอนได้^{[ 9 ] [ 11 ]}${\displaystyle d(A\cup B,C)}$${\displaystyle d(A,C)}$${\displaystyle d(B,C)}$${\displaystyle d(A\cup B,C)}$${\displaystyle d(A,C)}$${\displaystyle d(B,C)}$

ต่างจากวิธีของ Ward การจัดกลุ่มทั้งสองรูปแบบนี้ไม่มีวิธีการคำนวณระยะห่างระหว่างคู่คลัสเตอร์ที่ใช้เวลาคงที่ แต่สามารถเก็บอาร์เรย์ของระยะห่างระหว่างคู่คลัสเตอร์ทั้งหมดได้ เมื่อใดก็ตามที่คลัสเตอร์สองคลัสเตอร์ถูกรวมเข้าด้วยกัน สามารถใช้สูตรนี้ในการคำนวณระยะห่างระหว่างคลัสเตอร์ที่รวมเข้าด้วยกันกับคลัสเตอร์อื่นๆ ทั้งหมด การรักษาอาร์เรย์นี้ตลอดระยะเวลาของอัลกอริธึมการจัดกลุ่มใช้เวลาและพื้นที่O(n²) อัลกอริ^{ธึ มลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดอาจใช้ร่วมกับอาร์เรย์ของระยะห่างนี้เพื่อค้นหาการ จัด}กลุ่มแบบเดียวกันกับอัลกอริธึมโลภสำหรับกรณีเหล่านี้ เวลาและพื้นที่ทั้งหมดโดยใช้อาร์เรย์นี้ก็คือ O ( n² )เช่น กัน ^{[ 12 ]}

ขอบเขตเวลาและพื้นที่ O ( n2 ⁾เดียวกันนี้ยังสามารถบรรลุได้ด้วยวิธีอื่น โดยใช้เทคนิคที่ซ้อนโครงสร้าง ข้อมูลคิวลำดับความสำคัญ แบบควอดทรีไว้บนเมทริกซ์ระยะทางและใช้เพื่อดำเนินการอัลกอริทึมการจัดกลุ่มแบบโลภมาตรฐาน วิธีควอดทรีนี้มีความทั่วไปมากกว่า เนื่องจากใช้งานได้แม้กระทั่งกับวิธีการจัดกลุ่มที่ไม่สามารถลดรูปได้^{[ 4 ]}อย่างไรก็ตาม อัลกอริทึมลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดตรงกับขอบเขตเวลาและพื้นที่ในขณะที่ใช้โครงสร้างข้อมูลที่ง่ายกว่า^{[ 12 ]}

ใน การจัดกลุ่มแบบ เชื่อมโยงเดี่ยวหรือแบบเพื่อนบ้านที่ใกล้ที่สุด ซึ่งเป็นรูปแบบที่เก่าแก่ที่สุดของการจัดกลุ่มแบบลำดับชั้นแบบรวมกลุ่ม^{[ 11 ]}ความแตกต่างระหว่างกลุ่มจะวัดจากระยะทางขั้นต่ำระหว่างจุดสองจุดใดๆ จากสองกลุ่ม ด้วยความแตกต่างนี้

${\displaystyle d(A\cup B,C)=\min(d(A,C),d(B,C)),}$

การประชุมเป็นความเท่าเทียมกันมากกว่าความไม่เท่าเทียมกันของข้อกำหนดการลดทอน (การเชื่อมโยงเดี่ยวยังปฏิบัติตามสูตร Lance–Williams ^{[ 9 ] [ 11 ]}แต่มีสัมประสิทธิ์ติดลบซึ่งทำให้พิสูจน์การลดทอนได้ยากขึ้น)

^{เช่นเดียวกับการเชื่อมโยงแบบสมบูรณ์และระยะทางเฉลี่ย ความยากลำบากในการคำนวณระยะทางคลัสเตอร์ทำให้ขั้น ตอน}วิธีลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดใช้เวลาและพื้นที่O ( n² )ในการคำนวณการจัดกลุ่มแบบเชื่อมโยงเดี่ยว อย่างไรก็ตาม การจัดกลุ่มแบบเชื่อมโยงเดี่ยวสามารถหาได้อย่างมีประสิทธิภาพมากขึ้นโดยใช้ขั้นตอนวิธีทางเลือกที่คำนวณต้นไม้แผ่คลุมขั้นต่ำของระยะทางอินพุตโดยใช้ขั้นตอนวิธีของ Primจากนั้นเรียงลำดับขอบของต้นไม้แผ่คลุมขั้นต่ำและใช้รายการที่เรียงลำดับนี้เพื่อเป็นแนวทางในการรวมคลัสเตอร์เป็นคู่ๆ ภายในขั้นตอนวิธีของ Prim ขอบของต้นไม้แผ่คลุมขั้นต่ำแต่ละขอบสามารถหาได้โดยการค้นหาตามลำดับผ่านรายการที่ไม่ได้เรียงลำดับของขอบที่เล็กที่สุดที่เชื่อมต่อต้นไม้ที่สร้างขึ้นบางส่วนกับจุดยอดเพิ่มเติมแต่ละจุด วิธีนี้ช่วยประหยัดเวลาที่ขั้นตอนวิธีจะต้องใช้ในการปรับน้ำหนักของจุดยอดในคิวลำดับความสำคัญ การใช้อัลกอริทึมของ Prim ในลักษณะนี้จะใช้เวลาO ( n ² )และพื้นที่O ( n )ซึ่งตรงกับขอบเขตที่ดีที่สุดที่สามารถทำได้ด้วยอัลกอริทึมโซ่เพื่อนบ้านที่ใกล้ที่สุดสำหรับระยะทางที่มีการคำนวณเวลาคงที่^{[ 13 ]}

การวัดระยะทางอีกวิธีหนึ่งที่นิยมใช้ในการจัดกลุ่มแบบรวมกลุ่มคือ ระยะทางระหว่างจุดศูนย์กลางของกลุ่มแต่ละคู่ หรือที่เรียกว่า วิธีกลุ่มถ่วงน้ำหนัก^{[ 9 ] [ 11 ]}สามารถคำนวณได้ง่ายในเวลาคงที่ต่อการคำนวณระยะทาง อย่างไรก็ตาม วิธีนี้ไม่สามารถลดทอนได้ ตัวอย่างเช่น หากข้อมูลนำเข้าประกอบด้วยจุดสามจุดของสามเหลี่ยมด้านเท่า การรวมจุดสองจุดเข้าด้วยกันเป็นกลุ่มที่ใหญ่ขึ้นจะทำให้ระยะทางระหว่างกลุ่มลดลง ซึ่งเป็นการละเมิดคุณสมบัติการลดทอนได้ ดังนั้น อัลกอริทึมแบบลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดจึงไม่จำเป็นต้องพบการจัดกลุ่มแบบเดียวกันกับอัลกอริทึมแบบโลภ อย่างไรก็ตามMurtagh (1983)เขียนว่า อัลกอริทึมแบบลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดให้ " ฮิวริสติก ที่ดี " สำหรับวิธีจุดศูนย์กลาง^{[ 2 ]} อัลกอริทึมที่แตกต่างกันโดยDay & Edelsbrunner (1984)สามารถใช้เพื่อค้นหาการจัดกลุ่มแบบโลภได้ใน เวลา O ( n ² )สำหรับการวัดระยะทางนี้^{[ 5 ]}

การนำเสนอข้างต้นไม่อนุญาตให้ใช้ระยะทางที่ไวต่อลำดับการรวมอย่างชัดเจน อันที่จริง การอนุญาตให้ใช้ระยะทางดังกล่าวอาจทำให้เกิดปัญหาได้ โดยเฉพาะอย่างยิ่ง มีระยะทางคลัสเตอร์ที่ไวต่อลำดับซึ่งตรงตามคุณสมบัติการลดรูป แต่สำหรับระยะทางคลัสเตอร์ดังกล่าว อัลกอริทึมข้างต้นจะส่งคืนลำดับชั้นที่มีต้นทุนที่ไม่เหมาะสม ดังนั้น เมื่อระยะทางคลัสเตอร์ถูกกำหนดโดยสูตรแบบเรียกซ้ำ (ดังเช่นบางสูตรที่กล่าวถึงข้างต้น) จะต้องระมัดระวังไม่ให้ใช้ลำดับชั้นในลักษณะที่ไวต่อลำดับการรวม^{[ 14 ]}

อัลกอริทึมแบบลูกโซ่เพื่อนบ้านที่ใกล้ที่สุดได้รับการพัฒนาและนำไปใช้ในปี พ.ศ. 2525 โดยJean-Paul Benzécri ^{[ 15 ]}และ J. Juan ^{[ 16 ]}พวกเขาใช้อัลกอริทึมนี้บนพื้นฐานของวิธีการก่อนหน้านี้ที่สร้างการจัดกลุ่มแบบลำดับชั้นโดยใช้คู่เพื่อนบ้านที่ใกล้ที่สุดร่วมกันโดยไม่ใช้ประโยชน์จากลูกโซ่เพื่อนบ้านที่ใกล้ที่สุด^{[ 8 ] [ 17 ]}