ईएम (उम्मीद-अधिकतमकरण) एल्गोरिथ्म एक प्रसिद्ध पुनरावृत्त शोधन एल्गोरिदम है जिसका उपयोग पैरामीटर अनुमानों की खोज के लिए किया जा सकता है। इसे k- साधन प्रतिमान के विस्तार के रूप में माना जा सकता है, जो क्लस्टर के लिए एक ऑब्जेक्ट बनाता है जिसके साथ यह सबसे समान है, जो क्लस्टर माध्य पर निर्भर करता है।
EM सदस्यता की संभावना को परिभाषित करने वाले भार के अनुसार प्रत्येक वस्तु को एक क्लस्टर में बनाता है। दूसरे शब्दों में, समूहों के बीच कोई सख्त सीमाएँ नहीं हैं। इस प्रकार, नए साधनों का मूल्यांकन भारित मापों के आधार पर किया जाता है।
EM एक मूल अनुमान या संयोजन मॉडल के मापदंडों के "अनुमान" से शुरू होता है (सामूहिक रूप से पैरामीटर वेक्टर के रूप में परिभाषित)। यह पैरामीटर वेक्टर द्वारा बनाए गए मिश्रण घनत्व के विपरीत वस्तुओं को पुनरावृत्त रूप से पुन:व्यवस्थित कर सकता है। पुनः प्राप्त वस्तुओं का उपयोग पैरामीटर अनुमानों को पुनर्स्थापित करने के लिए किया जाता है। प्रत्येक ऑब्जेक्ट ने एक संभावना बनाई है कि इसमें विशेषता मानों का एक विशिष्ट सेट हो सकता है, क्योंकि यह किसी दिए गए क्लस्टर का सदस्य था। एल्गोरिथम को इस प्रकार दर्शाया गया है -
-
इसका उपयोग पैरामीटर वेक्टर का मूल अनुमान लगाने के लिए किया जा सकता है - इसमें क्लस्टर माध्यमों या केंद्रों को परिभाषित करने के लिए यादृच्छिक रूप से k ऑब्जेक्ट का चयन करना शामिल है (जैसे k- साधन विभाजन में), और नए मापदंडों के लिए अनुमान लगाना।
-
यह निम्नलिखित दो चरणों के आधार पर मापदंडों (या समूहों) को बार-बार परिष्कृत कर सकता है -
-
(a) उम्मीद चरण − यह प्रायिकता के साथ प्रत्येक वस्तु 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 |सी<उप>के ) =एन (एम<उप>के , ई<उप>के (x<उप>मैं )) माध्य के आसपास सामान्य (यानी, गाऊसी) वितरण का अनुसरण करता है, mk , उम्मीद के साथ, ईk . दूसरे शब्दों में, यह चरण 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 (अतिरेक की संख्या) में रैखिक है। बायेसियन क्लस्टरिंग तकनीक वर्ग-सशर्त संभाव्यता घनत्व की गणना को लक्षित करती है। वे आम तौर पर सांख्यिकी समुदाय में उपयोग किए जाते हैं।
उद्योग में, AutoClass एक प्रसिद्ध बायेसियन क्लस्टरिंग तकनीक है जो EM एल्गोरिथम के संशोधन का उपयोग करती है। सबसे अच्छा क्लस्टरिंग वस्तु के सटीक क्लस्टर को देखते हुए किसी वस्तु की विशेषताओं की भविष्यवाणी करने की क्षमता को अधिकतम करता है। AutoClasscan क्लस्टर की संख्या का भी अनुमान लगा सकता है। इसका उपयोग विभिन्न डोमेन में किया गया है और इन्फ्रारेड खगोल विज्ञान डेटा के आधार पर सितारों की एक नई श्रेणी खोजने में सक्षम था।