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

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

एल्गोरिदम

मान लीजिए कि x₁ से x_n तक डेटा बिंदुओं का समुच्चय होता है | और उनकी आंतरिक संरचना के बारे में कोई धारणा नहीं बनाई गई है और s इसका फलन होता है | जो किन्हीं दो बिंदुओं के मध्य समानता की मात्रा को निर्धारित करता है, जैसे कि s(i, j) > s(i, k) हैं यदि आई एफ एफ x_i , x_k की तुलना में x_j के अधिक समान है। तब इसके उदाहरण के लिए, दो डेटा बिंदुओं की ऋणात्मक वर्ग दूरी का उपयोग किया गया था | अर्थात बिंदुओं 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 के मध्य अमेरिकी अर्थव्यवस्था के आउटपुट मल्टीप्लायरों में कुछ अस्थायी पैटर्न खोजने के लिए एफिनिटी प्रोपेगेशन का उपयोग किया गया था।

सॉफ़्टवेयर

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