EM (एक्सपेक्टेशन-मैक्सिमाइज़ेशन) एल्गोरिदम एक प्रसिद्ध पुनरावृत्त शोधन एल्गोरिदम है जिसका उपयोग पैरामीटर अनुमानों की खोज के लिए किया जा सकता है। इसे k-मीन्स प्रतिमान के विस्तार के रूप में माना जा सकता है, जो एक ऑब्जेक्ट को उस क्लस्टर को असाइन करता है जिसके साथ यह क्लस्टर माध्य के आधार पर सबसे समान है।
EM प्रत्येक ऑब्जेक्ट को सदस्यता की संभावना को परिभाषित करने वाले वजन के अनुसार एक क्लस्टर को असाइन करता है। दूसरे शब्दों में, क्लस्टर्स के बीच कोई सख्त सीमाएं नहीं हैं। इस प्रकार, नए माध्य भारित मापों के आधार पर गणना किए जाते हैं।
EM पैरामीटर वेक्टर के रूप में सामूहिक रूप से परिभाषित मिश्रण मॉडल के पैरामीटर्स के मूल अनुमान या "अनुमान" के साथ शुरू होता है। यह पैरामीटर वेक्टर द्वारा बनाए गए मिश्रण घनत्व के विरुद्ध ऑब्जेक्ट्स को पुनः स्कोर करके पुनरावृत्त रूप से परिष्कृत करता है। पुनः स्कोर किए गए ऑब्जेक्ट्स का उपयोग पैरामीटर अनुमानों को पुनर्स्थापित करने के लिए किया जाता है। प्रत्येक ऑब्जेक्ट में एक संभावना होती है कि उसके पास विशेषता मूल्यों का एक विशिष्ट सेट हो सकता है, यह देखते हुए कि वह एक दिए गए क्लस्टर का सदस्य था। एल्गोरिदम को निम्नानुसार दर्शाया गया है:
पैरामीटर वेक्टर का मूल अनुमान बनाने के लिए उपयोग किया जा सकता है - इसमें क्लस्टर माध्य या केंद्रों को परिभाषित करने के लिए k ऑब्जेक्ट्स को बेतरतीब ढंग से चुनना शामिल है (k-मीन्स पार्टीशनिंग के रूप में), और नए पैरामीटर्स के लिए अनुमान लगाना।
निम्नलिखित दो चरणों के आधार पर पैरामीटर्स (या क्लस्टर्स) को पुनरावृत्त रूप से परिष्कृत करने के लिए उपयोग किया जा सकता है:
(a) अपेक्षा चरण - यह प्रत्येक ऑब्जेक्ट $x_{i}$ को क्लस्टर $c_{k}$ को संभावना के साथ असाइन कर सकता है
$$P(x_{i}\in C_{k})=p(C_{k}|x_{i})=\frac{p(C_{k})p(x_{i}|C_{k})}{p(x_{i})}$$
जहां $p(x_{i}|C_{k}) = N(m_{k}, E_{k}(x_{i}))$ माध्य $m_{k}$ के चारों ओर सामान्य (यानी, गाउसियन) वितरण का पालन करता है, अपेक्षा $E_{k}$ के साथ। दूसरे शब्दों में, यह चरण प्रत्येक क्लस्टर के लिए ऑब्जेक्ट $x_{i}$ की क्लस्टर सदस्यता की संभावना की गणना करता है। ये संभावनाएं ऑब्जेक्ट $x_{i}$ के लिए "अपेक्षित" क्लस्टर सदस्यताएं हैं।
(b) अधिकतमकरण चरण - इसे ऊपर से संभावना अनुमानों की आवश्यकता होती है ताकि मॉडल पैरामीटर्स का पुनः अनुमान (या परिष्कृत) किया जा सके। उदाहरण के लिए,
$$m_{k}=\frac{1}{n}\sum_{i=1}^{n}\frac{x_{i}P(x_{i}\in C_{k})}{\sum_{j}P(x_{i}\in C_{j})}$$
यह चरण डेटा दिए गए आवंटन की संभावना का "अधिकतमकरण" है।
EM एल्गोरिदम निष्पादित करने के लिए सरल और समझने योग्य है। यह तेजी से अभिसरण करता है लेकिन वैश्विक ऑप्टिमा तक नहीं पहुंच सकता। विशिष्ट अनुकूलन फ़ंक्शन के रूपों के लिए अभिसरण की गारंटी है। कम्प्यूटेशनल जटिलता d (इनपुट विशेषताओं की संख्या), n (आइटम्स की संख्या), और t (रिडंडेंसी की संख्या) में रैखिक है। बेजियन क्लस्टरिंग तकनीकें क्लास-सशर्त संभावना घनत्व की गणना को लक्षित करती हैं। वे आमतौर पर सांख्यिकी समुदाय में उपयोग की जाती हैं।
उद्योग में, AutoClass एक प्रसिद्ध बेजियन क्लस्टरिंग तकनीक है जो EM एल्गोरिदम के संशोधन का उपयोग करती है। सर्वोत्तम क्लस्टरिंग ऑब्जेक्ट की विशेषताओं की भविष्यवाणी करने की क्षमता को अधिकतम करती है दिए गए ऑब्जेक्ट के सटीक क्लस्टर के। AutoClass क्लस्टर्स की संख्या का अनुमान भी लगा सकती है। इसका उपयोग विभिन्न डोमेन में किया गया है और इन्फ्रारेड खगोल विज्ञान डेटा के आधार पर सितारों का एक नया वर्ग खोजने में सक्षम था।
