อัลกอริธึม EM (Expectation-Maximization) เป็นอัลกอริธึมการปรับแต่งซ้ำที่มีชื่อเสียงซึ่งสามารถใช้สำหรับการค้นหาค่าประมาณพารามิเตอร์ ถือได้ว่าเป็นส่วนขยายของกระบวนทัศน์ k-mean ซึ่งสร้างวัตถุให้กับคลัสเตอร์ที่มีความคล้ายคลึงกันมากที่สุด ขึ้นอยู่กับค่าเฉลี่ยของคลัสเตอร์
EM สร้างแต่ละอ็อบเจ็กต์ไปยังคลัสเตอร์ตามน้ำหนักที่กำหนดความน่าจะเป็นของการเป็นสมาชิก ในอีกแง่หนึ่ง ไม่มีขอบเขตที่เข้มงวดระหว่างคลัสเตอร์ ดังนั้น วิธีการใหม่จึงได้รับการประเมินตามการวัดน้ำหนัก
EM เริ่มต้นด้วยการประมาณการเดิมหรือ "การเดา" ของพารามิเตอร์ของรูปแบบการรวมกัน (กำหนดรวมกันเป็นเวกเตอร์พารามิเตอร์) มันสามารถให้คะแนนวัตถุซ้ำ ๆ ได้เมื่อเทียบกับความหนาแน่นของส่วนผสมที่ทำโดยเวกเตอร์พารามิเตอร์ ออบเจ็กต์ที่ให้คะแนนจะใช้เพื่อคืนค่าการประมาณค่าพารามิเตอร์ แต่ละอ็อบเจ็กต์สร้างความน่าจะเป็นที่สามารถมีค่าแอตทริบิวต์เฉพาะได้เนื่องจากเป็นสมาชิกของกลุ่มที่กำหนด อัลกอริทึมถูกแสดงดังนี้ −
-
สามารถใช้ในการเดาดั้งเดิมของเวกเตอร์พารามิเตอร์ - ประกอบด้วยการเลือกวัตถุ k แบบสุ่มเพื่อกำหนดค่าเฉลี่ยหรือศูนย์กลางของคลัสเตอร์ (เช่นเดียวกับการแบ่งพาร์ติชัน k-mean) และการคาดเดาสำหรับพารามิเตอร์ใหม่
-
มันสามารถปรับแต่งพารามิเตอร์ (หรือคลัสเตอร์) ซ้ำ ๆ ขึ้นอยู่กับสองขั้นตอนต่อไปนี้ -
-
(ก) ขั้นตอนที่คาดหวัง − สามารถสร้างแต่ละวัตถุ xi เพื่อจัดกลุ่ม ck ด้วยความน่าจะเป็น
$$P(x_{i}\epsilon C_{k})=p(C_{k}|x_{i})=\frac{p(C_{k})p(x_{i}|C_{k} )}{p(x_{i})}$$
โดยที่ p(xi |Ck ) =N(mk , Ek (xผม )) ตามการแจกแจงแบบปกติ (เช่น เกาส์เซียน) รอบค่ากลาง mk , ด้วยความคาดหวัง Ek . ในอีกแง่หนึ่ง ขั้นตอนนี้คำนวณความน่าจะเป็นของการเป็นสมาชิกคลัสเตอร์ของอ็อบเจ็กต์ xi สำหรับแต่ละคลัสเตอร์ ความน่าจะเป็นเหล่านี้เป็นสมาชิกของคลัสเตอร์ "ที่คาดหวัง" สำหรับวัตถุ xi .
-
(b) ขั้นตอนการขยายสูงสุด − อาจต้องใช้การประมาณความน่าจะเป็นจากด้านบนเพื่อประเมิน (หรือปรับแต่ง) พารามิเตอร์ของแบบจำลองใหม่ ตัวอย่างเช่น
$$m_{k}=\frac{1}{n}\sum_{i=1}^{n}\frac{x_{i}P(x_{i}\epsilon C_{k})}{\sum_ {j}P(x_{i}\epsilon C_{j})}$$
ระยะนี้เป็น “การเพิ่มสูงสุด” ของความเป็นไปได้ของการจัดสรรตามข้อมูล
อัลกอริทึม EM นั้นใช้งานง่ายและเข้าใจได้ มันมาบรรจบกันอย่างรวดเร็วแต่ไม่สามารถเข้าถึงการเพิ่มประสิทธิภาพระดับโลกได้ รับประกันคอนเวอร์เจนซ์สำหรับรูปแบบเฉพาะของฟังก์ชันการปรับให้เหมาะสม ความซับซ้อนในการคำนวณเป็นแบบเส้นตรงใน d (จำนวนคุณลักษณะอินพุต) n (จำนวนรายการ) และ t (จำนวนความซ้ำซ้อน) เทคนิคการจัดกลุ่มแบบ Bayesian กำหนดเป้าหมายการคำนวณความหนาแน่นของความน่าจะเป็นแบบเงื่อนไขคลาส โดยทั่วไปจะใช้ในชุมชนสถิติ
ในอุตสาหกรรม AutoClass เป็นเทคนิคการจัดกลุ่ม Bayesian ที่มีชื่อเสียงซึ่งใช้การปรับเปลี่ยนอัลกอริทึม EM การจัดกลุ่มที่ดีที่สุดจะเพิ่มความสามารถสูงสุดในการคาดการณ์แอตทริบิวต์ของวัตถุที่กำหนดคลัสเตอร์ที่ถูกต้องของวัตถุ AutoClasscan ยังประเมินจำนวนคลัสเตอร์ มีการใช้ในหลายโดเมนและสามารถค้นหาดาวประเภทใหม่ได้ขึ้นอยู่กับข้อมูลดาราศาสตร์อินฟราเรด
