एफिनिटी प्रोपेगेशन

सांख्यिकी और डेटा खनन में, एफ़िनिटी प्रोपेगेशन (एपी) डेटा बिंदुओं के बीच संदेश भेजने की अवधारणा पर आधारित एक क्लस्टर विश्लेषण है। K-मीन्स क्लस्टरिंग| जैसे क्लस्टरिंग एल्गोरिदम के विपरीतk-मीन्स या के-मेडोइड्स|k-मेडोइड्स, आत्मीयता प्रसार के लिए एल्गोरिदम चलाने से पहले समूहों की संख्या निर्धारित या अनुमान लगाने की आवश्यकता नहीं होती है। के समान k-मेडोइड्स, आत्मीयता प्रसार उदाहरणों को खोजता है, इनपुट सेट के सदस्य जो क्लस्टर के प्रतिनिधि हैं।

एल्गोरिदम

होने देना x₁ द्वारा x_n डेटा बिंदुओं का एक सेट हो, उनकी आंतरिक संरचना के बारे में कोई धारणा न बनाई जाए, और चलो s एक फ़ंक्शन बनें जो किन्हीं दो बिंदुओं के बीच समानता को मापता है, जैसे कि s(i, j) > s(i, k) अगर और केवल अगर x_i अधिक समान है x_j की तुलना में x_k. इस उदाहरण के लिए, दो डेटा बिंदुओं की नकारात्मक वर्ग दूरी का उपयोग किया गया था यानी बिंदुओं के लिए x_i और x_k, $s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}$

का विकर्ण s (अर्थात $s(i,i)$) विशेष रूप से महत्वपूर्ण है, क्योंकि यह उदाहरण वरीयता का प्रतिनिधित्व करता है, जिसका अर्थ है कि किसी विशेष उदाहरण के एक उदाहरण बनने की कितनी संभावना है। जब इसे सभी इनपुट के लिए समान मान पर सेट किया जाता है, तो यह नियंत्रित करता है कि एल्गोरिदम कितने वर्ग उत्पन्न करता है। न्यूनतम संभव समानता के निकट का मान कम वर्ग उत्पन्न करता है, जबकि अधिकतम संभव समानता के निकट या उससे बड़ा मान कई वर्ग उत्पन्न करता है। इसे आम तौर पर इनपुट के सभी जोड़े की औसत समानता के लिए प्रारंभ किया जाता है।

एल्गोरिथ्म दो संदेश-पासिंग चरणों के बीच बारी-बारी से आगे बढ़ता है, जो दो मैट्रिक्स को अपडेट करता है:

• जिम्मेदारी मैट्रिक्स R के मान हैं r(i, k) जो यह बताता है कि कितना उपयुक्त है x_k के लिए उदाहरण के रूप में कार्य करना है x_i, अन्य उम्मीदवार उदाहरणों के सापेक्ष x_i.
• उपलब्धता मैट्रिक्स A में मान शामिल हैं a(i, k) जो दर्शाता है कि यह कितना उपयुक्त होगा x_i लेना x_k इसके उदाहरण के रूप में, अन्य बिंदुओं की प्राथमिकता को ध्यान में रखते हुए x_k एक उदाहरण के रूप में।

दोनों मैट्रिक्स को सभी शून्यों से प्रारंभ किया गया है, और इन्हें लॉग-संभावना तालिकाओं के रूप में देखा जा सकता है। इसके बाद एल्गोरिदम निम्नलिखित अद्यतनों को पुनरावर्ती रूप से निष्पादित करता है:

• सबसे पहले, जिम्मेदारी संबंधी अपडेट इधर-उधर भेजे जाते हैं: $r(i,k)\leftarrow s(i,k)-\max _{k'\neq k}\left\{a(i,k')+s(i,k')\right\}$
• फिर, उपलब्धता प्रति अद्यतन की जाती है

$a(i,k)\leftarrow \min \left(0,r(k,k)+\sum _{i'\not \in \{i,k\}}\max(0,r(i',k))\right)$ के लिए $i\neq k$ और

$a(k,k)\leftarrow \sum _{i'\neq k}\max(0,r(i',k))$.

पुनरावृत्तियाँ तब तक की जाती हैं जब तक कि या तो क्लस्टर सीमाएँ कई पुनरावृत्तियों में अपरिवर्तित रहती हैं, या कुछ पूर्व निर्धारित संख्या (पुनरावृत्तियों की) तक नहीं पहुँच जाती हैं। अंतिम मैट्रिक्स से उदाहरण उन लोगों के रूप में निकाले जाते हैं जिनकी स्वयं के लिए 'जिम्मेदारी + उपलब्धता' सकारात्मक है (अर्थात $(r(i,i)+a(i,i))>0$).

अनुप्रयोग

एफ़िनिटी प्रसार के अन्वेषकों ने दिखाया कि यह कुछ कंप्यूटर विज़न और कम्प्यूटेशनल बायोलॉजी विज्ञान कार्यों के लिए बेहतर है, उदाहरण के लिए मानवीय चेहरों की तस्वीरों का समूह बनाना और विनियमित प्रतिलेखों की पहचान करना k-साधन,यहां तक ​​कि जब k-मीन्स को कई यादृच्छिक पुनरारंभ की अनुमति दी गई और प्रिंसिपल घटक विश्लेषण का उपयोग करके आरंभ किया गया। प्रोटीन इंटरेक्शन ग्राफ विभाजन पर आत्मीयता प्रसार और मार्कोव क्लस्टरिंग की तुलना करने वाले एक अध्ययन में पाया गया कि मार्कोव क्लस्टरिंग उस समस्या के लिए बेहतर काम करती है। टेक्स्ट खनन अनुप्रयोगों के लिए एक अर्ध-पर्यवेक्षित संस्करण प्रस्तावित किया गया है। एक और हालिया अनुप्रयोग अर्थशास्त्र में था, जब 1997 और 2017 के बीच अमेरिकी अर्थव्यवस्था के आउटपुट मल्टीप्लायरों में कुछ अस्थायी पैटर्न खोजने के लिए आत्मीयता प्रसार का उपयोग किया गया था।

सॉफ़्टवेयर

• ELKI डेटा माइनिंग फ्रेमवर्क में एक जावा (प्रोग्रामिंग भाषा) कार्यान्वयन शामिल है।
• एफ़िनिटी प्रसार का एक जूलिया (प्रोग्रामिंग भाषा) कार्यान्वयन जूलिया स्टैटिस्टिक्स के क्लस्टरिंग.जेएल पैकेज में निहित है।
• पायथन (प्रोग्रामिंग भाषा) संस्करण स्किकिट-लर्न लाइब्रेरी का हिस्सा है।
• एपीक्लस्टर पैकेज में एक आर (प्रोग्रामिंग भाषा) कार्यान्वयन उपलब्ध है।