एफिनिटी प्रोपेगेशन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
सांख्यिकी और [[डेटा खनन]] में, एफ़िनिटी प्रोपेगेशन (एपी) डेटा बिंदुओं के बीच संदेश भेजने की अवधारणा पर आधारित [[क्लस्टर विश्लेषण]] है।<ref name="science">{{cite journal |author1=Brendan J. Frey |author2=Delbert Dueck |title=डेटा बिंदुओं के बीच संदेश भेजकर क्लस्टरिंग|journal=[[Science (journal)|Science]] |volume=315 |year=2007 |pages=972–976 |doi=10.1126/science.1136800 |pmid=17218491 |issue=5814|citeseerx=10.1.1.121.3145 |s2cid=6502291 }}</ref> K-मीन्स क्लस्टरिंग| जैसे क्लस्टरिंग एल्गोरिदम के विपरीत{{mvar|k}}-मीन्स या के-मेडोइड्स|{{mvar|k}}-मेडोइड्स, आत्मीयता प्रसार के लिए एल्गोरिदम चलाने से पहले समूहों की संख्या निर्धारित या अनुमान लगाने की आवश्यकता नहीं होती है। के समान {{mvar|k}}-मेडोइड्स, आत्मीयता प्रसार उदाहरणों को खोजता है, इनपुट सेट के सदस्य जो क्लस्टर के प्रतिनिधि हैं।<ref name="science"/>
सांख्यिकी और [[डेटा खनन]] में,'''आत्मीयता प्रसार''' (AP) डेटा बिंदुओं के बीच "संदेश पासिंग" की अवधारणा पर आधारित [[क्लस्टर विश्लेषण]] है। <ref name="science">{{cite journal |author1=Brendan J. Frey |author2=Delbert Dueck |title=डेटा बिंदुओं के बीच संदेश भेजकर क्लस्टरिंग|journal=[[Science (journal)|Science]] |volume=315 |year=2007 |pages=972–976 |doi=10.1126/science.1136800 |pmid=17218491 |issue=5814|citeseerx=10.1.1.121.3145 |s2cid=6502291 }}</ref> {{mvar|k}} -मीन्स या {{mvar|k}}-मेडोइड्स जैसे क्लस्टरिंग एल्गोरिदम के विपरीत, एफ़िनिटी प्रसार के लिए एल्गोरिदम चलाने से पहले क्लस्टर की संख्या निर्धारित या अनुमान लगाने की आवश्यकता नहीं होती है। {{mvar|k}}-मेडोइड्स के समान, आत्मीयता प्रसार इनपुट सेट के "उदाहरण" सदस्यों को ढूंढता है जो क्लस्टर के प्रतिनिधि हैं।<ref name="science"/>
 
 
==एल्गोरिदम==
==एल्गोरिदम==
होने देना {{math|''x''<sub>1</sub>}} द्वारा {{mvar|x<sub>n</sub>}} डेटा बिंदुओं का सेट हो, उनकी आंतरिक संरचना के बारे में कोई धारणा न बनाई जाए, और चलो {{mvar|s}} फ़ंक्शन बनें जो किन्हीं दो बिंदुओं के बीच समानता को मापता है, जैसे कि {{math|''s''(''i'', ''j'') > ''s''(''i'', ''k'')}} [[अगर और केवल अगर]] {{mvar|x<sub>i</sub>}} अधिक समान है {{mvar|x<sub>j</sub>}} की तुलना में {{mvar|x<sub>k</sub>}}. इस उदाहरण के लिए, दो डेटा बिंदुओं की नकारात्मक वर्ग दूरी का उपयोग किया गया था यानी बिंदुओं के लिए {{mvar|x<sub>i</sub>}} और {{mvar|x<sub>k</sub>}}, <math>s(i,k) = - \left\| x_i - x_k \right\|^2 </math><ref name="science"/>
मान लीजिए कि {{math|''x''<sub>1</sub>}} से {{mvar|x<sub>n</sub>}} तक डेटा बिंदुओं का सेट है, उनकी आंतरिक संरचना के बारे में कोई धारणा नहीं बनाई गई है, और {{mvar|s}} फ़ंक्शन है जो किन्हीं दो बिंदुओं के बीच समानता की मात्रा निर्धारित करता है, जैसे कि {{math|''s''(''i'', ''j'') > ''s''(''i'', ''k'')}} यदि [[अगर और केवल अगर|आई एफ एफ]] {{mvar|x<sub>i</sub>}}, {{mvar|x<sub>k</sub>}} की तुलना में {{mvar|x<sub>j</sub>}} के अधिक समान है। इस उदाहरण के लिए, दो डेटा बिंदुओं की नकारात्मक वर्ग दूरी का उपयोग किया गया था यानी बिंदुओं {{mvar|x<sub>i</sub>}} और {{mvar|x<sub>k</sub>}} के लिए, <math>s(i,k) = - \left\| x_i - x_k \right\|^2 </math> होती हैं | <ref name="science"/>


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


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


* जिम्मेदारी मैट्रिक्स {{math|'''R'''}} के मान हैं {{math|''r''(''i'', ''k'')}} जो यह बताता है कि कितना उपयुक्त है {{mvar|x<sub>k</sub>}} के लिए उदाहरण के रूप में कार्य करना है {{mvar|x<sub>i</sub>}}, अन्य उम्मीदवार उदाहरणों के सापेक्ष {{mvar|x<sub>i</sub>}}.
*"जिम्मेदारी" मैट्रिक्स {{math|'''R'''}} में मान {{math|''r''(''i'', ''k'')}} हैं जो यह निर्धारित करते हैं कि {{mvar|x<sub>k</sub>}}, {{mvar|x<sub>i</sub>}} के लिए अन्य उम्मीदवार उदाहरणों के सापेक्ष, {{mvar|x<sub>i</sub>}} के लिए उदाहरण के रूप में कार्य करने के लिए कितना उपयुक्त है।
* उपलब्धता मैट्रिक्स {{math|'''A'''}} में मान शामिल हैं {{math|''a''(''i'', ''k'')}} जो दर्शाता है कि यह कितना उपयुक्त होगा {{mvar|x<sub>i</sub>}} लेना {{mvar|x<sub>k</sub>}} इसके उदाहरण के रूप में, अन्य बिंदुओं की प्राथमिकता को ध्यान में रखते हुए {{mvar|x<sub>k</sub>}} उदाहरण के रूप में।
*"उपलब्धता" मैट्रिक्स {{math|'''A'''}} में मान {{math|''a''(''i'', ''k'')}} शामिल हैं जो दर्शाते हैं कि {{mvar|x<sub>i</sub>}} के लिए {{mvar|x<sub>k</sub>}} को अपने उदाहरण के रूप में चुनना कितना "उचित" होगा, उदाहरण के रूप में {{mvar|x<sub>k</sub>}} के लिए अन्य बिंदुओं की प्राथमिकता को ध्यान में रखते हुए।


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


* सबसे पहले, जिम्मेदारी संबंधी अपडेट इधर-उधर भेजे जाते हैं: <math>r(i,k) \leftarrow s(i,k) - \max_{k' \neq k} \left\{ a(i,k') + s(i,k') \right\}</math>
*सबसे पहले, जिम्मेदारी अद्यतन चारों ओर भेजे जाते हैं <math>r(i,k) \leftarrow s(i,k) - \max_{k' \neq k} \left\{ a(i,k') + s(i,k') \right\}</math>
* फिर, उपलब्धता प्रति अद्यतन की जाती है
* फिर, उपलब्धता प्रति अद्यतन की जाती है |
::<math>a(i,k) \leftarrow \min \left( 0, r(k,k) + \sum_{i' \not\in \{i,k\}} \max(0, r(i',k)) \right)</math> के लिए <math>i \neq k</math> और
::<math>a(i,k) \leftarrow \min \left( 0, r(k,k) + \sum_{i' \not\in \{i,k\}} \max(0, r(i',k)) \right)</math> के लिए <math>i \neq k</math> और
::<math>a(k,k) \leftarrow \sum_{i' \neq k} \max(0, r(i',k))</math>.
::<math>a(k,k) \leftarrow \sum_{i' \neq k} \max(0, r(i',k))</math>.


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


==अनुप्रयोग==
==अनुप्रयोग==
एफ़िनिटी प्रसार के अन्वेषकों ने दिखाया कि यह कुछ कंप्यूटर विज़न और [[कम्प्यूटेशनल बायोलॉजी]] विज्ञान कार्यों के लिए बेहतर है, उदाहरण के लिए मानवीय चेहरों की तस्वीरों का समूह बनाना और विनियमित प्रतिलेखों की पहचान करना {{mvar|k}}-साधन,<ref name="science"/>यहां तक ​​कि जब {{mvar|k}}-मीन्स को कई यादृच्छिक पुनरारंभ की अनुमति दी गई और प्रिंसिपल घटक विश्लेषण का उपयोग करके आरंभ किया गया।<ref>{{cite conference |author1=Delbert Dueck |author2=Brendan J. Frey |title=बिना पर्यवेक्षित छवि वर्गीकरण के लिए गैर-मीट्रिक आत्मीयता प्रसार|conference=Int'l Conf. on Computer Vision |year=2007|doi=10.1109/ICCV.2007.4408853}}</ref> [[प्रोटीन इंटरेक्शन ग्राफ]] विभाजन पर आत्मीयता प्रसार और [[मार्कोव क्लस्टरिंग]] की तुलना करने वाले अध्ययन में पाया गया कि मार्कोव क्लस्टरिंग उस समस्या के लिए बेहतर काम करती है।<ref>{{cite journal |author1=James Vlasblom |author2=Shoshana Wodak |title=प्रोटीन इंटरेक्शन ग्राफ़ के विभाजन के लिए मार्कोव क्लस्टरिंग बनाम आत्मीयता प्रसार|journal=BMC Bioinformatics |volume=10 |number=1 |year=2009 |pages=99 |doi=10.1186/1471-2105-10-99 |pmid=19331680 |pmc=2682798}}</ref> [[ टेक्स्ट खनन |टेक्स्ट खनन]] अनुप्रयोगों के लिए अर्ध-पर्यवेक्षित संस्करण प्रस्तावित किया गया है।<ref>{{cite journal |author1=Renchu Guan |author2=Xiaohu Shi |author3=Maurizio Marchese |author4=Chen Yang |author5=Yanchun Liang |title=बीज एफ़िनिटी प्रसार के साथ टेक्स्ट क्लस्टरिंग|journal=IEEE Transactions on Knowledge & Data Engineering |volume=23 |number=4 |year=2011 |pages=627–637 |doi=10.1109/tkde.2010.144|hdl=11572/89884 |s2cid=14053903 |hdl-access=free }}</ref> और हालिया अनुप्रयोग अर्थशास्त्र में था, जब 1997 और 2017 के बीच अमेरिकी अर्थव्यवस्था के आउटपुट मल्टीप्लायरों में कुछ अस्थायी पैटर्न खोजने के लिए आत्मीयता प्रसार का उपयोग किया गया था।<ref>{{Cite journal|last1=Almeida|first1=Lucas Milanez de Lima|last2=Balanco|first2=Paulo Antonio de Freitas|date=2020-06-01|title=Application of multivariate analysis as complementary instrument in studies about structural changes: An example of the multipliers in the US economy|url=http://www.sciencedirect.com/science/article/pii/S0954349X17301406|journal=Structural Change and Economic Dynamics|language=en|volume=53|pages=189–207|doi=10.1016/j.strueco.2020.02.006|s2cid=216406772 |issn=0954-349X}}</ref>
एफ़िनिटी प्रसार के अन्वेषकों ने दिखाया कि यह कुछ कंप्यूटर विज़न और [[कम्प्यूटेशनल बायोलॉजी]] विज्ञान कार्यों के लिए बेहतर है, उदाहरण के लिए मानवीय चेहरों की तस्वीरों का समूह बनाना और विनियमित प्रतिलेखों की पहचान करना {{mvar|k}}-साधन,<ref name="science"/>यहां तक ​​कि जब {{mvar|k}}-मीन्स को कई यादृच्छिक पुनरारंभ की अनुमति दी गई और प्रिंसिपल घटक विश्लेषण का उपयोग करके आरंभ किया गया।<ref>{{cite conference |author1=Delbert Dueck |author2=Brendan J. Frey |title=बिना पर्यवेक्षित छवि वर्गीकरण के लिए गैर-मीट्रिक आत्मीयता प्रसार|conference=Int'l Conf. on Computer Vision |year=2007|doi=10.1109/ICCV.2007.4408853}}</ref> [[प्रोटीन इंटरेक्शन ग्राफ]] विभाजन पर आत्मीयता प्रसार और [[मार्कोव क्लस्टरिंग]] की तुलना करने वाले अध्ययन में पाया गया कि मार्कोव क्लस्टरिंग उस समस्या के लिए बेहतर काम करती है।<ref>{{cite journal |author1=James Vlasblom |author2=Shoshana Wodak |title=प्रोटीन इंटरेक्शन ग्राफ़ के विभाजन के लिए मार्कोव क्लस्टरिंग बनाम आत्मीयता प्रसार|journal=BMC Bioinformatics |volume=10 |number=1 |year=2009 |pages=99 |doi=10.1186/1471-2105-10-99 |pmid=19331680 |pmc=2682798}}</ref> [[ टेक्स्ट खनन |टेक्स्ट खनन]] अनुप्रयोगों के लिए अर्ध-पर्यवेक्षित संस्करण प्रस्तावित किया गया है।<ref>{{cite journal |author1=Renchu Guan |author2=Xiaohu Shi |author3=Maurizio Marchese |author4=Chen Yang |author5=Yanchun Liang |title=बीज एफ़िनिटी प्रसार के साथ टेक्स्ट क्लस्टरिंग|journal=IEEE Transactions on Knowledge & Data Engineering |volume=23 |number=4 |year=2011 |pages=627–637 |doi=10.1109/tkde.2010.144|hdl=11572/89884 |s2cid=14053903 |hdl-access=free }}</ref> और हालिया अनुप्रयोग अर्थशास्त्र में था, जब 1997 और 2017 के बीच अमेरिकी अर्थव्यवस्था के आउटपुट मल्टीप्लायरों में कुछ अस्थायी पैटर्न खोजने के लिए आत्मीयता प्रसार का उपयोग किया गया था।<ref>{{Cite journal|last1=Almeida|first1=Lucas Milanez de Lima|last2=Balanco|first2=Paulo Antonio de Freitas|date=2020-06-01|title=Application of multivariate analysis as complementary instrument in studies about structural changes: An example of the multipliers in the US economy|url=http://www.sciencedirect.com/science/article/pii/S0954349X17301406|journal=Structural Change and Economic Dynamics|language=en|volume=53|pages=189–207|doi=10.1016/j.strueco.2020.02.006|s2cid=216406772 |issn=0954-349X}}</ref>
एफ़िनिटी प्रसार के अन्वेषकों ने दिखाया कि यह कुछ कंप्यूटर विज़न और [[कम्प्यूटेशनल बायोलॉजी]] विज्ञान कार्यों के लिए बेहतर है, उदाहरण के लिए {{mvar|k}} -मीन्स की तुलना में मानव चेहरों की तस्वीरों का समूह बनाना और विनियमित प्रतिलेखों की पहचान करना,<ref name="science" /> तब भी जब के-मीन्स को कई यादृच्छिक पुनरारंभ की अनुमति दी गई थी और पीसीए का उपयोग करके आरंभ किया गया था। <ref>{{cite conference |author1=Delbert Dueck |author2=Brendan J. Frey |title=बिना पर्यवेक्षित छवि वर्गीकरण के लिए गैर-मीट्रिक आत्मीयता प्रसार|conference=Int'l Conf. on Computer Vision |year=2007|doi=10.1109/ICCV.2007.4408853}}</ref> [[प्रोटीन इंटरेक्शन ग्राफ]] विभाजन पर आत्मीयता प्रसार और [[मार्कोव क्लस्टरिंग]] की तुलना करने वाले अध्ययन में पाया गया कि मार्कोव क्लस्टरिंग उस समस्या के लिए बेहतर काम करती है।<ref>{{cite journal |author1=James Vlasblom |author2=Shoshana Wodak |title=प्रोटीन इंटरेक्शन ग्राफ़ के विभाजन के लिए मार्कोव क्लस्टरिंग बनाम आत्मीयता प्रसार|journal=BMC Bioinformatics |volume=10 |number=1 |year=2009 |pages=99 |doi=10.1186/1471-2105-10-99 |pmid=19331680 |pmc=2682798}}</ref> [[ टेक्स्ट खनन |टेक्स्ट खनन]] अनुप्रयोगों के लिए अर्ध-पर्यवेक्षित संस्करण प्रस्तावित किया गया है।<ref>{{cite journal |author1=Renchu Guan |author2=Xiaohu Shi |author3=Maurizio Marchese |author4=Chen Yang |author5=Yanchun Liang |title=बीज एफ़िनिटी प्रसार के साथ टेक्स्ट क्लस्टरिंग|journal=IEEE Transactions on Knowledge & Data Engineering |volume=23 |number=4 |year=2011 |pages=627–637 |doi=10.1109/tkde.2010.144|hdl=11572/89884 |s2cid=14053903 |hdl-access=free }}</ref> और हालिया अनुप्रयोग अर्थशास्त्र में था, जब 1997 और 2017 के बीच अमेरिकी अर्थव्यवस्था के आउटपुट मल्टीप्लायरों में कुछ अस्थायी पैटर्न खोजने के लिए आत्मीयता प्रसार का उपयोग किया गया था।<ref>{{Cite journal|last1=Almeida|first1=Lucas Milanez de Lima|last2=Balanco|first2=Paulo Antonio de Freitas|date=2020-06-01|title=Application of multivariate analysis as complementary instrument in studies about structural changes: An example of the multipliers in the US economy|url=http://www.sciencedirect.com/science/article/pii/S0954349X17301406|journal=Structural Change and Economic Dynamics|language=en|volume=53|pages=189–207|doi=10.1016/j.strueco.2020.02.006|s2cid=216406772 |issn=0954-349X}}</ref>




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


==संदर्भ==
==संदर्भ==

Revision as of 23:13, 17 July 2023

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

एल्गोरिदम

मान लीजिए कि x1 से xn तक डेटा बिंदुओं का सेट है, उनकी आंतरिक संरचना के बारे में कोई धारणा नहीं बनाई गई है, और s फ़ंक्शन है जो किन्हीं दो बिंदुओं के बीच समानता की मात्रा निर्धारित करता है, जैसे कि s(i, j) > s(i, k) यदि आई एफ एफ xi, xk की तुलना में xj के अधिक समान है। इस उदाहरण के लिए, दो डेटा बिंदुओं की नकारात्मक वर्ग दूरी का उपयोग किया गया था यानी बिंदुओं xi और xk के लिए, होती हैं | [1]

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

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

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

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

  • सबसे पहले, जिम्मेदारी अद्यतन चारों ओर भेजे जाते हैं
  • फिर, उपलब्धता प्रति अद्यतन की जाती है |
के लिए और
.

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

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

अनुप्रयोग

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

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


सॉफ़्टवेयर

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Brendan J. Frey; Delbert Dueck (2007). "डेटा बिंदुओं के बीच संदेश भेजकर क्लस्टरिंग". Science. 315 (5814): 972–976. CiteSeerX 10.1.1.121.3145. doi:10.1126/science.1136800. PMID 17218491. S2CID 6502291.
  2. ↑ Delbert Dueck; Brendan J. Frey (2007). बिना पर्यवेक्षित छवि वर्गीकरण के लिए गैर-मीट्रिक आत्मीयता प्रसार. Int'l Conf. on Computer Vision. doi:10.1109/ICCV.2007.4408853.
  3. ↑ James Vlasblom; Shoshana Wodak (2009). "प्रोटीन इंटरेक्शन ग्राफ़ के विभाजन के लिए मार्कोव क्लस्टरिंग बनाम आत्मीयता प्रसार". BMC Bioinformatics. 10 (1): 99. doi:10.1186/1471-2105-10-99. PMC 2682798. PMID 19331680.
  4. ↑ Renchu Guan; Xiaohu Shi; Maurizio Marchese; Chen Yang; Yanchun Liang (2011). "बीज एफ़िनिटी प्रसार के साथ टेक्स्ट क्लस्टरिंग". IEEE Transactions on Knowledge & Data Engineering. 23 (4): 627–637. doi:10.1109/tkde.2010.144. hdl:11572/89884. S2CID 14053903.
  5. ↑ Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (2020-06-01). "Application of multivariate analysis as complementary instrument in studies about structural changes: An example of the multipliers in the US economy". Structural Change and Economic Dynamics (in English). 53: 189–207. doi:10.1016/j.strueco.2020.02.006. ISSN 0954-349X. S2CID 216406772.
  6. ↑ Delbert Dueck; Brendan J. Frey (2007). बिना पर्यवेक्षित छवि वर्गीकरण के लिए गैर-मीट्रिक आत्मीयता प्रसार. Int'l Conf. on Computer Vision. doi:10.1109/ICCV.2007.4408853.
  7. ↑ James Vlasblom; Shoshana Wodak (2009). "प्रोटीन इंटरेक्शन ग्राफ़ के विभाजन के लिए मार्कोव क्लस्टरिंग बनाम आत्मीयता प्रसार". BMC Bioinformatics. 10 (1): 99. doi:10.1186/1471-2105-10-99. PMC 2682798. PMID 19331680.
  8. ↑ Renchu Guan; Xiaohu Shi; Maurizio Marchese; Chen Yang; Yanchun Liang (2011). "बीज एफ़िनिटी प्रसार के साथ टेक्स्ट क्लस्टरिंग". IEEE Transactions on Knowledge & Data Engineering. 23 (4): 627–637. doi:10.1109/tkde.2010.144. hdl:11572/89884. S2CID 14053903.
  9. ↑ Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (2020-06-01). "Application of multivariate analysis as complementary instrument in studies about structural changes: An example of the multipliers in the US economy". Structural Change and Economic Dynamics (in English). 53: 189–207. doi:10.1016/j.strueco.2020.02.006. ISSN 0954-349X. S2CID 216406772.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एफिनिटी_प्रोपेगेशन&oldid=224773’