การจัดกลุ่มที่มีองค์ประกอบเท่ากัน
สมมติว่าเรามีข้อสังเกตดังนี้ $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$ที่มี $n$ ข้อสังเกตสำหรับมิติข้อมูลคงที่ $d$. สมมติว่าเรามีจำนวนเต็มคงที่$k$. k-mean clustering (ด้วยระยะ l2) เป็นปัญหาในการค้นหาเซนทรอยด์ของคลัสเตอร์$S_{1}, \dots, S_{k}$ ที่ย่อส่วน $$ cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2}, $$ ที่ไหน $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ เซนทรอยด์คือ $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$.
สมมติมีใน $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ มีองค์ประกอบเท่ากัน $\{x\} \subset \mathbf{X}$.
เป็นไปได้ไหมว่าในโซลูชันระดับโลก (ทางทฤษฎี) สิ่งเหล่านี้เท่ากับองค์ประกอบอื่น ๆ $\{x\}$ อยู่ในกลุ่มที่แตกต่างกัน?
คำตอบ
ก่อนอื่นเราต้องแยกความแตกต่างระหว่างโซลูชัน k-mean ที่เหมาะสมที่สุดในโลกกับผลลัพธ์ที่คุณได้รับจากอัลกอริทึม k-mean มีสิ่งเหล่านี้อยู่จำนวนมากและหากชุดข้อมูลมีขนาดเล็กมากพวกเขาจะส่งมอบค่าที่เหมาะสมที่สุดในท้องถิ่นซึ่งไม่จำเป็นต้องเป็นชุดข้อมูลทั่วโลก (คุณพูดว่า "ทั่วโลก" ในคำถามของคุณดังนั้นฉันจึงถือว่าคุณหมายถึงโซลูชันที่ดีที่สุดในระดับโลกเพียงเพื่อให้แน่ใจ)
คำตอบสำหรับคำถามของคุณเริ่มต้นด้วย "ไม่ปกติ" ของพวกเขา$\|x-q_j\|$- เห็นได้ชัดว่าค่าเท่ากันสำหรับทุกคน $q_j$ดังนั้นเมื่ออัลกอริทึมถูกรวมเข้าด้วยกัน (หรือเหมาะสมที่สุดทั่วโลก $q_j$ เป็นที่รู้จัก) พวกเขาทั้งหมดจะได้รับมอบหมายให้ใกล้ชิดที่สุด $q_j$ซึ่งเหมือนกันสำหรับพวกเขาทั้งหมด
สถานการณ์พิเศษที่ไม่ครอบคลุมโดยอาร์กิวเมนต์ข้างต้นเกิดขึ้นหากไม่เพียงหลายข้อ $x$ เท่ากัน แต่ก็มีระยะห่างเท่ากันตั้งแต่สองตัวขึ้นไป $q_j$. ฉันไม่ทราบอัลกอริทึมใด ๆ ที่ในกรณีนี้สามารถกำหนดให้กับคลัสเตอร์อื่น ๆ ได้ แต่ฉันไม่สามารถแยกออกได้ว่ามีการใช้งานดังกล่าวอยู่
ในความเป็นจริงฉันไม่ได้พยายามพิสูจน์ แต่ฉันสงสัยว่า global optimum จะไม่แยกการสังเกตที่เท่าเทียมกันเพราะมีโอกาสที่ถ้าการสังเกตที่เท่ากันถูกแยกออกจะมีทางออกที่ดีกว่าโดยวางทั้งหมดไว้ในกลุ่มที่มีคนส่วนใหญ่ ของพวกเขา (หรือเพียงกลุ่มใดก็ได้หากมีการกระจายอย่างเท่าเทียมกัน) ดูเหมือนจะไม่สมเหตุสมผลที่การสังเกตเหล่านี้จะมีอิทธิพลต่อค่าเฉลี่ยคลัสเตอร์มากกว่าหนึ่งค่า (ทำให้การสังเกตอื่น ๆ ส่วนใหญ่ในคลัสเตอร์นั้นแย่ลง) อาจพิสูจน์ได้ว่าใช้เวลาช่วงบ่ายในการทำคณิตศาสตร์ แต่ไม่มีการรับประกันที่นี่เป็นเพียงการเดา
สิ่งที่ฉันได้ดูคือตัวอย่าง 1 มิติจำนวนหนึ่งที่มีคะแนนเท่ากันอยู่ระหว่างสองครึ่งของข้อมูลเช่น 1,2,3,3,4,5 แน่นอนคุณจะได้รับทางออกที่ดีกว่า ($k=2$) ในแง่ของต้นทุนถ้าคุณใส่ 3 ทั้งสองในคลัสเตอร์ด้วย 1,2 หรือด้วย 4,5 แทนที่จะเป็นหนึ่งทางซ้ายและทางขวา (คุณสามารถตรวจสอบได้โดยคำนวณฟังก์ชันต้นทุนอย่างชัดเจน) .