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

सांख्यिकी और डेटा खनन में,आत्मीयता प्रसार (AP) डेटा बिंदुओं के बीच "संदेश पासिंग" की अवधारणा पर आधारित क्लस्टर विश्लेषण है। 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$).

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

अनुप्रयोग

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

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

सॉफ़्टवेयर

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