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

มีปัญหา 4 ประการที่ต้องแก้ไขสำหรับการจัดกลุ่มในข้อมูลที่มีมิติสูง: ^{[ 1 ]}

• มิติหลายมิตินั้นยากต่อการคิด ยากต่อการมองเห็นภาพ และเนื่องจากจำนวนค่าที่เป็นไปได้เพิ่มขึ้นแบบทวีคูณในแต่ละมิติ การแจงนับพื้นที่ย่อยทั้งหมดจึงกลายเป็นเรื่องที่เป็นไปไม่ได้เมื่อมิติเพิ่มมากขึ้น ปัญหานี้เรียกว่า คำสาปแห่งมิติ (curse of dimensionality )
• แนวคิดเรื่องระยะทางจะมีความแม่นยำน้อยลงเมื่อจำนวนมิติเพิ่มขึ้น เนื่องจากระยะทางระหว่างจุดสองจุดใดๆ ในชุดข้อมูลที่กำหนดจะลู่เข้าหากัน การแยกแยะจุดที่ใกล้ที่สุดและจุดที่ไกลที่สุดจึงไม่มีความหมายอีกต่อไป

${\displaystyle \lim _{d\to \infty }{\frac {{\mathit {dist}}_{\max }-{\mathit {dist}}_{\min }}{{\mathit {dist}}_{\min }}}=0}$

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

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

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

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

ภาพด้านข้างแสดงพื้นที่สองมิติซึ่งสามารถระบุคลัสเตอร์ได้จำนวนหนึ่ง ในพื้นที่ย่อยหนึ่งมิติ สามารถพบ คลัสเตอร์ (ในพื้นที่ย่อย) และ, , (ในพื้นที่ย่อย ) ได้ ไม่สามารถพิจารณาว่าเป็นคลัสเตอร์ในพื้นที่ย่อยสองมิติได้ เนื่องจากมีการกระจายตัวอย่างเบาบางเกินไปใน แกน ในสองมิติ สามารถระบุ คลัสเตอร์สองคลัสเตอร์และ ได้${\displaystyle c_{a}}$${\displaystyle \{x\}}$${\displaystyle c_{b}}$${\displaystyle c_{c}}$${\displaystyle c_{d}}$${\displaystyle \{y\}}$${\displaystyle c_{c}}$${\displaystyle x}$${\displaystyle c_{ab}}$${\displaystyle c_{ad}}$

ปัญหาของการจัดกลุ่มแบบซับสเปซเกิดจากข้อเท็จจริงที่ว่ามีพื้นที่ย่อยที่แตกต่างกันของพื้นที่ที่มี มิติ หากพื้นที่ย่อยไม่ขนานกับแกน จะมีพื้นที่ย่อยที่เป็นไปได้จำนวนอนันต์ ดังนั้น อัลกอริทึมการจัดกลุ่มแบบซับสเปซจึงใช้ ฮิวริสติกบางอย่างเพื่อให้ยังคงสามารถคำนวณได้ โดยมีความเสี่ยงที่จะได้ผลลัพธ์ที่ด้อยกว่า ตัวอย่างเช่นคุณสมบัติการปิดลง (ดูกฎการเชื่อมโยง ) สามารถใช้สร้างพื้นที่ย่อยที่มีมิติสูงกว่าได้โดยการรวมพื้นที่ย่อยที่มีมิติต่ำกว่าเท่านั้น เนื่องจากพื้นที่ย่อย T ใดๆ ที่มีคลัสเตอร์ จะส่งผลให้พื้นที่เต็ม S มีคลัสเตอร์นั้นด้วย (เช่น S ⊆ T) ซึ่งเป็นแนวทางที่ใช้โดยอัลกอริทึมแบบดั้งเดิมส่วนใหญ่ เช่น CLIQUE [ ^{4 ] SUBCLU} [ ^{5 ] นอกจาก}นี้ยังสามารถกำหนดพื้นที่ย่อยโดยใช้ระดับความเกี่ยวข้องที่แตกต่างกันสำหรับแต่ละมิติ ซึ่งเป็นแนวทางที่ใช้โดย iMWK-Means ^{[ 6 ]} EBK-Modes ^{[ 7 ]}และ CBK-Modes ^{[ 8 ]}${\displaystyle 2^{d}}$${\displaystyle d}$

การจัดกลุ่มแบบฉายภาพ (Projected clustering) มีเป้าหมายที่จะกำหนดจุดแต่ละจุดให้อยู่ในกลุ่มที่ไม่ซ้ำกัน แต่กลุ่มต่างๆ อาจอยู่ในพื้นที่ย่อยที่แตกต่างกันได้ วิธีการทั่วไปคือการใช้ฟังก์ชันระยะ ทางพิเศษ ร่วมกับ อัลกอริธึ ม การจัดกลุ่ม แบบปกติ

ตัวอย่างเช่น อัลกอริทึม PreDeCon จะตรวจสอบว่าคุณลักษณะใดที่ดูเหมือนจะสนับสนุนการจัดกลุ่มสำหรับแต่ละจุด และปรับฟังก์ชันระยะทางเพื่อให้มิติที่มีความแปรปรวน ต่ำ ได้รับการขยายในฟังก์ชันระยะทาง^{[ 9 ]} ในรูปด้านบน อาจพบคลัสเตอร์ โดยใช้ DBSCANด้วยฟังก์ชันระยะทางที่ให้ความสำคัญกับแกน y น้อยลง และทำให้ความแตกต่างต่ำในแกน y เพิ่มมากขึ้นเพียงพอที่จะจัดกลุ่มจุดต่างๆ เข้าเป็นคลัสเตอร์ ${\displaystyle c_{c}}$${\displaystyle x}$${\displaystyle y}$

PROCLUSใช้แนวทางที่คล้ายกันกับการจัดกลุ่มk-medoid ^{[ 10 ]}เดา medoid เริ่มต้น และสำหรับแต่ละ medoid จะกำหนดพื้นที่ย่อยที่ครอบคลุมโดยคุณลักษณะที่มีความแปรปรวนต่ำ จุดจะถูกกำหนดให้กับ medoid ที่ใกล้ที่สุด โดยพิจารณาเฉพาะพื้นที่ย่อยของ medoid นั้นในการกำหนดระยะทาง จากนั้นอัลกอริทึมจะดำเนินการตามอัลกอริทึม PAM ปกติ

หากฟังก์ชันระยะทางให้น้ำหนักคุณลักษณะแตกต่างกัน แต่ไม่เคยให้น้ำหนักเป็น 0 (และด้วยเหตุนี้จึงไม่ตัดคุณลักษณะที่ไม่เกี่ยวข้องออกไป) อัลกอริทึมดังกล่าวเรียกว่าอัลกอริทึมการจัดกลุ่มแบบ "อ่อน" (soft-projected clustering algorithm )

การจัดกลุ่มแบบอิงการฉายภาพนั้นอาศัยการฉายภาพแบบไม่เชิงเส้นของข้อมูลมิติสูงลงในพื้นที่สองมิติ^{[ 11 ]}วิธีการฉายภาพทั่วไป เช่นการฝังเพื่อนบ้านแบบสุ่มที่กระจายแบบ t (t-SNE) ^{[ 12 ]}หรือตัวแสดงภาพการดึงเพื่อนบ้าน (NerV) ^{[ 13 ]}ใช้เพื่อฉายข้อมูลอย่างชัดเจนลงในสองมิติโดยไม่คำนึงถึงพื้นที่ย่อยที่มีมิติสูงกว่าสองมิติและรักษาเฉพาะเพื่อนบ้านที่เกี่ยวข้องในข้อมูลมิติสูงเท่านั้น ในขั้นตอนต่อไป จะคำนวณ กราฟ Delaunay ^{[ 14 ]}ระหว่างจุดที่ฉายภาพ และแต่ละจุดยอดระหว่างจุดที่ฉายภาพสองจุดจะถูกถ่วงน้ำหนักด้วยระยะทางมิติสูงระหว่างจุดข้อมูลมิติสูงที่สอดคล้องกัน หลังจากนั้นจะคำนวณเส้นทางที่สั้นที่สุดระหว่างจุดแต่ละคู่โดยใช้ อัลกอริ ทึมDijkstra ^{[ 15 ]}เส้นทางที่สั้นที่สุดจะถูกนำไปใช้ในกระบวนการจัดกลุ่ม ซึ่งเกี่ยวข้องกับการเลือกสองแบบขึ้นอยู่กับประเภทโครงสร้างในข้อมูลมิติสูง^{[ 11 ]}ตัวเลือกบูลีนนี้สามารถตัดสินใจได้โดยการดูแผนที่ภูมิประเทศของโครงสร้างมิติสูง^{[ 16 ]}ในการเปรียบเทียบวิธีการจัดกลุ่ม 34 วิธีที่เทียบเคียงกันได้ การจัดกลุ่มตามการฉายภาพเป็นอัลกอริทึมเดียวที่สามารถค้นหาโครงสร้างตามระยะทางหรือความหนาแน่นมิติสูงของชุดข้อมูลได้เสมอ^{[ 11 ]}การจัดกลุ่มตามการฉายภาพสามารถเข้าถึงได้ในแพ็กเกจ R โอเพนซอร์ส "ProjectionBasedClustering" บน CRAN ^{[ 17 ]}

การรวมแบบบูตสแตรป (bagging) สามารถใช้เพื่อสร้างคลัสเตอร์หลายคลัสเตอร์และรวบรวมผลลัพธ์ได้ โดยทำโดยการสุ่มตัวอย่างย่อยของข้อมูล ทำการวิเคราะห์คลัสเตอร์ในแต่ละตัวอย่างย่อย จากนั้นรวบรวมผลลัพธ์ของการจัดคลัสเตอร์เพื่อสร้างมาตรวัดความไม่เหมือนกัน ซึ่งสามารถนำมาใช้ในการสำรวจและจัดคลัสเตอร์ข้อมูลดั้งเดิมได้^{[ 18 ] [ 19 ]} เนื่องจากข้อมูลที่มีมิติสูงมักจะมีคุณลักษณะที่ไม่ให้ข้อมูลจำนวนมาก จึงสามารถใช้ค่าน้ำหนักในระหว่างกระบวนการ bagging เพื่อเพิ่มผลกระทบของคุณลักษณะที่ให้ข้อมูลมากขึ้น ซึ่งจะสร้าง "ความไม่เหมือนกันแบบ ABC" ซึ่งสามารถนำมาใช้ในการสำรวจและจัดคลัสเตอร์ข้อมูลดั้งเดิม และยังใช้เพื่อประเมินว่าคุณลักษณะใดดูเหมือนจะมีผลกระทบมากกว่าในการกำหนดคลัสเตอร์ ^{[ 20 ] [ 21 ] [ 22 ]}

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

ในการ จัดกลุ่มความสัมพันธ์ (การทำเหมืองข้อมูล)มี การพิจารณาพื้นที่ย่อยอีกประเภทหนึ่ง

• ELKIประกอบด้วยอัลกอริธึมการจัดกลุ่มแบบซับสเปซและแบบสหสัมพันธ์ต่างๆ
• FCPS ประกอบด้วยอัลกอริธึมการจัดกลุ่มมากกว่าห้าสิบรายการ^{[ 25 ]}