मशीनें बड़े डेटा का विश्लेषण कैसे करती हैं: क्लस्टरिंग एल्गोरिदम का एक परिचय

मशीनों का अनुवाद कैसे बड़ा डेटा बनाता है: क्लस्टरिंग एल्गोरिदम का एक परिचय ।

नीचे दी गई तस्वीर को देखें। यह विभिन्न आकार और आकारों के कीड़े (घोंघे कीड़े नहीं हैं, लेकिन हम गलती नहीं पाएंगे) का एक संग्रह है। अब उन्हें समानता की डिग्री के अनुसार कई समूहों में विभाजित करें। कोई पकड़ नहीं। मकड़ियों के समूह द्वारा शुरू करें।



आप समाप्त हो गया? यद्यपि यहाँ कोई "सही" समाधान नहीं है, फिर भी आपने इन प्राणियों को चार समूहों में विभाजित किया होगा। एक क्लस्टर में मकड़ियों होते हैं, दूसरे में - घोंघे की एक जोड़ी, तीसरे में - तितलियों और चौथे में - मधुमक्खियों और ततैया की तिकड़ी।

अच्छा किया, है ना? आप शायद ऐसा ही कर सकते हैं अगर तस्वीर में दो बार कई कीड़े थे। और अगर आपके पास बहुत समय था - या एंटोमोलॉजी के लिए तरस रहा है - तो आप शायद सैकड़ों कीड़ों का समूह बना लेंगे।

हालांकि, एक मशीन के लिए, दस वस्तुओं को सार्थक समूहों में समूहित करना आसान काम नहीं है। कॉम्बिनेटरिक्स के रूप में गणित की ऐसी जटिल शाखा के लिए धन्यवाद, हम जानते हैं कि 10 कीड़े 115,975 तरीकों से समूहीकृत हैं। और अगर 20 कीड़े हैं, तो क्लस्टरिंग विकल्पों की संख्या 50 ट्रिलियन से अधिक होगी ।

सौ कीड़ों के साथ, ज्ञात ब्रह्मांड में प्राथमिक कणों की संख्या की तुलना में संभव समाधानों की संख्या अधिक होगी। और कितना? मेरे अनुमान के अनुसार, लगभग पाँच सौ मिलियन बिलियन अरब गुना अधिक । यह चार मिलियन बिलियन से अधिक Google समाधान ( Google क्या है? ) का पता लगाता है । और यह केवल सैकड़ों वस्तुओं के लिए है।

इनमें से लगभग सभी संयोजन निरर्थक होंगे। समाधानों की अकल्पनीय संख्या के बावजूद, आपने स्वयं को बहुत तेज़ी से क्लस्टरिंग के कुछ उपयोगी तरीकों में से एक पाया।

हम मनुष्यों को बड़ी मात्रा में डेटा को सूचीबद्ध करने और समझने की हमारी उत्कृष्ट क्षमता के लिए लेते हैं। इससे कोई फर्क नहीं पड़ता कि यह पाठ है, या स्क्रीन पर चित्र, या वस्तुओं का एक क्रम है - लोग, सामान्य रूप से, आसपास के दुनिया से आने वाले डेटा को प्रभावी ढंग से समझते हैं।

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

प्रत्येक एल्गोरिथ्म के लिए, मैं वर्णन करूंगा कि इसका उपयोग कब किया जा सकता है, यह कैसे काम करता है, और मैं चरण-दर-चरण विश्लेषण के साथ एक उदाहरण भी दूंगा। मेरा मानना ​​है कि एल्गोरिथ्म की वास्तविक समझ के लिए, आपको अपना काम खुद दोहराने की जरूरत है। यदि आप वास्तव में रुचि रखते हैं , तो आपको एहसास होगा कि एल्गोरिदम को कागज पर चलाना सबसे अच्छा है। अधिनियम, कोई भी आपको दोष नहीं देगा!


के = 3 के साथ तीन संदिग्ध साफ-सुथरे क्लस्टर

K- मतलब क्लस्टरिंग

द्वारा उपयोग किया जाता है:

जब आप समझते हैं कि पूर्व निर्धारित (एक प्राथमिकता) खोजने के लिए कितने समूह प्राप्त किए जा सकते हैं।

यह कैसे काम करता है:

एल्गोरिथ्म बेतरतीब ढंग से कश्मीर श्रेणियों में से एक के लिए प्रत्येक अवलोकन प्रदान करता है, और फिर प्रत्येक श्रेणी के लिए औसत की गणना करता है। फिर वह प्रत्येक अवलोकन को निकटतम औसत के साथ श्रेणी के लिए पुन: सौंपता है, और फिर से औसत की गणना करता है। पुनर्मूल्यांकन की आवश्यकता होने तक प्रक्रिया को दोहराया जाता है।

कार्य उदाहरण:

12 खिलाड़ियों का एक समूह लें और वर्तमान सीज़न में उनमें से प्रत्येक द्वारा किए गए लक्ष्यों की संख्या (उदाहरण के लिए, 3 से 30 की सीमा में)। हम खिलाड़ियों को विभाजित करते हैं, कहते हैं, तीन समूहों में।

चरण 1 : आपको खिलाड़ियों को तीन समूहों में बेतरतीब ढंग से विभाजित करने और उनमें से प्रत्येक के लिए औसत की गणना करने की आवश्यकता है।

Group 1 Player A (5 goals), Player B (20 goals), Player C (11 goals) Group Mean = (5 + 20 + 11) / 3 = 12 Group 2 Player D (5 goals), Player E (3 goals), Player F (19 goals) Group Mean = 9 Group 3 Player G (30 goals), Player H (3 goals), Player I (15 goals) Group Mean = 16 

चरण 2 : प्रत्येक खिलाड़ी को निकटतम औसत के साथ समूह में पुन: असाइन करें। उदाहरण के लिए, खिलाड़ी A (5 गोल) समूह 2 (औसत = 9) पर जाता है। फिर हम समूह औसत की गणना करते हैं।

 Group 1 (Old Mean = 12) Player C (11 goals) New Mean = 11 Group 2 (Old Mean = 9) Player A (5 goals), Player D (5 goals), Player E (3 goals), Player H (3 goals) New Mean = 4 Group 3 (Old Mean = 16) Player G (30 goals), Player I (15 goals), Player B (20 goals), Player F (19 goals) New Mean = 21 

चरण 2 को बार-बार दोहराएं जब तक खिलाड़ी समूह बदलना बंद न कर दें। इस कृत्रिम उदाहरण में, यह अगले पुनरावृत्ति पर होगा। इसे रोको! आपने डेटासेट से तीन क्लस्टर बनाए हैं!

 Group 1 (Old Mean = 11) Player C (11 goals), Player I (15 goals) Final Mean = 13 Group 2 (Old Mean = 4) Player A (5 goals), Player D (5 goals), Player E (3 goals), Player H (3 goals) Final Mean = 4 Group 3 (Old Mean = 21) Player G (30 goals), Player B (20 goals), Player F (19 goals) Final Mean = 23 

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

इस प्रकार, प्रदर्शन में सांख्यिकीय भिन्नता के आधार पर, मशीन किसी भी टीम के खेल के लिए मैदान पर खिलाड़ियों के स्थान को सही ठहरा सकती है। यह स्पोर्ट्स एनालिटिक्स के लिए उपयोगी है, साथ ही किसी भी अन्य कार्यों के लिए जिसमें डेटासेट को पूर्वनिर्धारित समूहों में विभाजित करने से उचित निष्कर्ष निकालने में मदद मिलती है।

वर्णित एल्गोरिथ्म के कई रूप हैं। समूहों का प्रारंभिक गठन विभिन्न तरीकों से किया जा सकता है। हमने समूहों में खिलाड़ियों के यादृच्छिक वर्गीकरण की जांच की, इसके बाद औसत की गणना की। नतीजतन, प्रारंभिक समूह का औसत एक-दूसरे के करीब है, जिससे पुनरावृत्ति बढ़ जाती है।

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

K- साधन क्लस्टरिंग का स्पष्ट दोष यह है कि आपको पहले से अनुमान लगाने की आवश्यकता है कि आपके पास कितने क्लस्टर हैं। गुच्छों के एक विशेष सेट की अनुरूपता का आकलन करने के लिए तरीके हैं। उदाहरण के लिए, प्रत्येक क्लस्टर के भीतर भीतर-सम-वर्ग वर्ग परिवर्तनशीलता का एक उपाय है। "बेहतर" क्लस्टर, वर्गों की कुल इंट्राक्लस्टर राशि कम है।

पदानुक्रमिक क्लस्टरिंग

द्वारा उपयोग किया जाता है:

जब आपको मूल्यों (टिप्पणियों) के बीच संबंधों को प्रकट करने की आवश्यकता होती है।

यह कैसे काम करता है:

दूरी मैट्रिक्स की गणना की जाती है जिसमें सेल का मूल्य ( i, j ) i और j के मूल्यों के बीच की दूरी का मीट्रिक होता है। फिर निकटतम मानों की एक जोड़ी ली जाती है और औसत की गणना की जाती है। एक नई दूरी का मैट्रिक्स बनाया जाता है, युग्मित मूल्यों को एक वस्तु में संयोजित किया जाता है। फिर निकटतम मानों की एक जोड़ी को इस नए मैट्रिक्स से लिया जाता है और एक नए औसत मूल्य की गणना की जाती है। सभी मूल्यों को समूहीकृत होने तक चक्र दोहराता है।

कार्य उदाहरण:

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



चरण 1 : सभी विचारों के बीच की दूरी की मैट्रिक्स की गणना की जाती है। हम यूक्लिडियन मीट्रिक का उपयोग करेंगे जो यह वर्णन करता है कि मानचित्र पर बस्तियों की तरह हमारा डेटा एक दूसरे से कितनी दूर है। आप संबंधित स्तंभ और पंक्ति के चौराहे पर मूल्य को पढ़कर प्रत्येक जोड़ी के निकायों की लंबाई में अंतर पा सकते हैं।



चरण 2 : एक दूसरे के सबसे करीब दो प्रजातियों की एक जोड़ी लें। इस मामले में, यह एक बॉटलनोज़ डॉल्फ़िन और एक ग्रे डॉल्फ़िन है, जिसमें शरीर की औसत लंबाई 3.3 मीटर है।

हम चरण 1 को दोहराते हैं, फिर से दूरी मैट्रिक्स की गणना करते हैं, लेकिन इस बार हम बॉटलनोज़ डॉल्फ़िन और ग्रे डॉल्फ़िन को 3.3 मीटर की लंबाई के साथ एक वस्तु में जोड़ते हैं।



अब हम चरण 2 को दोहराते हैं, लेकिन एक नई दूरी मैट्रिक्स के साथ। इस बार पीस और किलर व्हेल सबसे नज़दीकी होगी, तो चलो उन्हें एक जोड़े में रखें और औसत - 7 मीटर की गणना करें।

अगला, चरण 1 को दोहराएं: फिर से, दूरी मैट्रिक्स की गणना करें, लेकिन 7 मीटर के शरीर की लंबाई के साथ एकल ऑब्जेक्ट के रूप में पीस और हत्यारा व्हेल के साथ।



इस मैट्रिक्स के साथ चरण 2 को दोहराएं। सबसे छोटी दूरी (3.7 मीटर) दो संयुक्त वस्तुओं के बीच होगी, इसलिए हम उन्हें एक और भी बड़ी वस्तु में जोड़ देंगे और औसत मूल्य की गणना करेंगे - 5.2 मीटर।

फिर चरण 1 को दोहराएं और पीस / हत्यारा व्हेल के साथ बॉटलनोज़ डॉल्फ़िन / ग्रे डॉल्फ़िन के संयोजन से एक नई मैट्रिक्स की गणना करें।



दोहराएँ चरण 2. सबसे छोटी दूरी (5 मीटर) हम्पबैक और फिनाले के बीच होगी, इसलिए हम उन्हें जोड़ते हैं और औसत - 17.5 मीटर की गणना करते हैं।

फिर से चरण 1: मैट्रिक्स की गणना करें।



अंत में, चरण 2 को दोहराएं - केवल एक ही दूरी (12.3 मीटर) शेष है, इसलिए हम सभी को एक वस्तु में एकजुट करेंगे और रोकेंगे। यहाँ क्या हुआ:

 [[[BD, RD],[PW, KW]],[HW, FW]] 

ऑब्जेक्ट में एक पदानुक्रमित संरचना है ( JSON याद रखें), इसलिए इसे ट्री ग्राफ या डेंड्रोग्राम के रूप में प्रदर्शित किया जा सकता है। परिणाम एक परिवार के पेड़ के समान है। एक पेड़ पर करीब दो मूल्य हैं, जितना अधिक वे समान हैं या अधिक निकटता से जुड़े हुए हैं।


R-Fiddle.org का उपयोग करके एक साधारण डेंड्रोग्राम उत्पन्न होता है

डेंड्रोग्राम की संरचना आपको स्वयं डेटासेट की संरचना को समझने की अनुमति देती है। हमारे उदाहरण में, हमें दो मुख्य शाखाएँ मिलीं- एक हम्पबैक और फ़िनवाल के साथ, दूसरी एक बॉटलनोज़ डॉल्फ़िन / ग्रे डॉल्फ़िन और एक ग्राइंड / किलर व्हेल के साथ।

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

इस दृष्टिकोण को आवश्यक संख्या में समूहों की भविष्यवाणी की आवश्यकता नहीं है। आप परिणामी डेंड्रोग्राम को क्लस्टर में विभाजित कर सकते हैं, वांछित ऊंचाई पर पेड़ को "ट्रिमिंग" कर सकते हैं। आप डेटा क्लस्टरिंग के वांछित रिज़ॉल्यूशन के आधार पर, विभिन्न तरीकों से ऊँचाई चुन सकते हैं।
उदाहरण के लिए, यदि उपरोक्त डेंड्रोग्राम 10 की ऊंचाई पर काट दिया जाता है, तो हम दो मुख्य शाखाओं को काटेंगे, जिससे डेंड्रोग्राम को दो स्तंभों में विभाजित किया जाएगा। यदि 2 की ऊंचाई पर काटा जाता है, तो डेंड्रोग्राम को तीन समूहों में विभाजित करें।

अन्य पदानुक्रमित क्लस्टरिंग एल्गोरिदम इस लेख में वर्णित लोगों से तीन पहलुओं में भिन्न हो सकते हैं।

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

दूरी मैट्रिसेस की गणना के लिए भी कई तरीके हैं। यूक्लिडियन मेट्रिक्स अधिकांश कार्यों के लिए पर्याप्त हैं, लेकिन अन्य मैट्रिक्स कुछ स्थितियों में बेहतर अनुकूल हैं।

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

मान लीजिए कि प्रत्येक क्लस्टर में कई असतत मूल्य हैं। दो समूहों के बीच की दूरी को उनके किसी भी मान के बीच न्यूनतम (या अधिकतम) दूरी के रूप में परिभाषित किया जा सकता है, जैसा कि नीचे दिखाया गया है। विभिन्न संदर्भों के लिए, जुड़ने की कसौटी की विभिन्न परिभाषाओं का उपयोग करना सुविधाजनक है।


लाल / नीला: केन्द्रक पूल; लाल / हरा: मिनीमा पर आधारित संयोजन; हरा / नीला: उच्च के आधार पर विलय।

रेखांकन में समुदायों की परिभाषा (ग्राफ सामुदायिक जांच)

द्वारा उपयोग किया जाता है:

जब आपका डेटा नेटवर्क, या "ग्राफ़" के रूप में प्रस्तुत किया जा सकता है।

यह कैसे काम करता है:

एक ग्राफ में एक समुदाय को मोटे तौर पर एक कोने के उपसमुच्चय के रूप में परिभाषित किया जा सकता है जो बाकी नेटवर्क की तुलना में एक दूसरे से अधिक जुड़े होते हैं। एज कम्युनिटी, मोड्युलैरिटी-मैक्सिमेशन, वॉकट्रैप, क्लिक परकोलेशन, लीडिंग एगेनिवेक्टर जैसे विभिन्न विशिष्ट परिभाषाओं के आधार पर अलग-अलग सामुदायिक परिभाषा एल्गोरिदम हैं ...

कार्य उदाहरण:

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

शायद ग्राफ का पहला आवेदन जो दिमाग में आता है, वह सामाजिक नेटवर्क का अध्ययन है। इस मामले में, चोटियाँ ऐसे लोगों का प्रतिनिधित्व करती हैं जो पसलियों द्वारा मित्रों / ग्राहकों से जुड़े होते हैं। लेकिन आप नेटवर्क के रूप में किसी भी प्रणाली की कल्पना कर सकते हैं यदि आप घटकों के सार्थक कनेक्शन की विधि को सही ठहरा सकते हैं। ग्राफ सिद्धांत का उपयोग करके क्लस्टरिंग के अभिनव अनुप्रयोगों में दृश्य डेटा से गुण निकालना और आनुवंशिक नियामक नेटवर्क का विश्लेषण करना शामिल है।

एक सरल उदाहरण के रूप में, नीचे दिए गए ग्राफ को देखें। यह उन आठ साइटों को दिखाता है जो मैं सबसे अधिक बार आता हूं। उनके बीच के लिंक विकिपीडिया लेखों के लिंक पर आधारित हैं। इस तरह के डेटा को मैन्युअल रूप से एकत्र किया जा सकता है, लेकिन बड़ी परियोजनाओं के लिए पायथन स्क्रिप्ट लिखना बहुत तेज है। उदाहरण के लिए, यह: https://raw.githubusercontent.com/pg0408/Medium-articles/master/graph_maker.py ।


ग्राफ R 3.3.3 के लिए igraph पैकेज का उपयोग करके बनाया गया है

चोटियों का रंग समुदायों में भागीदारी पर निर्भर करता है, और आकार केंद्रीयता पर निर्भर करता है। कृपया ध्यान दें कि सबसे केंद्रीय Google और ट्विटर हैं।

इसके अलावा, परिणामी समूह बहुत सटीक रूप से वास्तविक कार्यों को दर्शाता है (यह हमेशा प्रदर्शन का एक महत्वपूर्ण संकेतक है)। लिंक / खोज साइटों का प्रतिनिधित्व करने वाले कोने पीले रंग में हाइलाइट किए गए हैं; ऑनलाइन प्रकाशन (लेख, ट्वीट या कोड) के लिए नीली हाइलाइट की गई साइट; लाल रंग में हाइलाइट किए गए PayPal और YouTube, पूर्व PayPal कर्मचारियों द्वारा स्थापित किए गए हैं। कंप्यूटर के लिए अच्छा कटौती!

बड़ी प्रणालियों की कल्पना करने के अलावा, नेटवर्क की सच्ची शक्ति गणितीय विश्लेषण में निहित है। आइए नेटवर्क चित्र को गणितीय प्रारूप में परिवर्तित करके शुरू करें। निम्नलिखित नेटवर्क का आसन्न मैट्रिक्स है।



स्तंभों और पंक्तियों के चौराहों पर मान इंगित करते हैं कि क्या इस जोड़ी के बीच एक किनारे है। उदाहरण के लिए, मध्यम और ट्विटर के बीच यह है, इसलिए, इस पंक्ति और स्तंभ के चौराहे पर 1. खड़ा है और मध्यम और पेपैल के बीच कोई किनारा नहीं है, इसलिए संबंधित सेल में 0 है।

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

यदि हम सभी कोने की डिग्री को जोड़ते हैं और दो से विभाजित करते हैं, तो हमें एल मिलता है - नेटवर्क में किनारों की संख्या। और पंक्तियों और स्तंभों की संख्या एन के बराबर है - नेटवर्क में कोने की संख्या।

केवल k, L, N और आसन्न मैट्रिक्स A की सभी कोशिकाओं के मानों को जानने के बाद, हम किसी भी क्लस्टरिंग के प्रतिरूप की गणना कर सकते हैं।

मान लीजिए कि हमने कई समुदायों में एक नेटवर्क का क्लस्टर बनाया है। तब आप क्लस्टरिंग के "गुणवत्ता" की भविष्यवाणी करने के लिए मॉड्यूलरिटी मान का उपयोग कर सकते हैं। एक उच्च प्रतिरूपता इंगित करती है कि हमने नेटवर्क को "सटीक" समुदायों में विभाजित किया है, और एक निम्न प्रतिरूपता से पता चलता है कि गुच्छे यथोचित रूप से संयोग से बनते हैं। इसे स्पष्ट करने के लिए:


प्रतिरूपकता समूहों की "गुणवत्ता" के एक उपाय के रूप में कार्य करता है।

निम्न सूत्र का उपयोग करके मॉड्यूलरिटी की गणना की जा सकती है:



आइए इस सुंदर भयानक दिखने वाले सूत्र को देखें।

एम , जैसा कि आप जानते हैं, यह प्रतिरूपकता है।

1 / 2L गुणांक का मतलब है कि हम 2L द्वारा सूत्र के बाकी "शरीर" को विभाजित करते हैं, अर्थात, नेटवर्क में किनारों की दोहरी संख्या से। पायथन में, कोई लिख सकता है:

 sum = 0 for i in range(1,N): for j in range(1,N): ans = #stuff with i and j as indices sum += ans 

#stuff with i and j क्या है? कोष्ठक में बिट हमें A_ij से घटाना (k_i k_j) / 2L बताता है, जहां A_ij पंक्ति i और स्तंभ j के चौराहे पर मैट्रिक्स में मूल्य है।

मान k_i और k_j प्रत्येक शीर्ष की डिग्री हैं। वे क्रमशः पंक्ति i और स्तंभ j में मानों को जोड़कर पा सकते हैं। यदि हम उन्हें गुणा करते हैं और 2L से विभाजित करते हैं, तो हम नेटवर्क और बेतरतीब ढंग से मिश्रित किए गए कोने के बीच किनारों की अपेक्षित संख्या प्राप्त करते हैं।

ब्रैकेट की सामग्री नेटवर्क की वास्तविक संरचना और अपेक्षित एक के बीच अंतर को दर्शाती है यदि नेटवर्क को यादृच्छिक रूप से फिर से बनाया गया था। यदि आप मानों के साथ खेलते हैं, तो उच्चतम प्रतिरूप A_ij = 1 और निम्न (k_i k_j) / 2L पर होगा। यही है, अगर मैं और जम्मू के बीच एक "अप्रत्याशित" बढ़त है, तो मॉड्यूलरिटी बढ़ जाती है।

अंत में, हम उस कोष्ठक की सामग्री को उस सूत्र से गुणा करते हैं जिसे सूत्र में ic_i, c_j के रूप में दर्शाया गया है। यह क्रोनकर-डेल्टा फ़ंक्शन है। यहाँ पायथन में इसका कार्यान्वयन है:

 def Kronecker_Delta(ci, cj): if ci == cj: return 1 else: return 0 Kronecker_Delta("A","A") #returns 1 Kronecker_Delta("A","B") #returns 0 

हां, इतना आसान है। फ़ंक्शन दो तर्क लेता है, और यदि वे समान हैं, तो यह 1 लौटाता है, और यदि नहीं, तो 0।

दूसरे शब्दों में, यदि कोने i और j एक क्लस्टर में आते हैं, तो ic_i, c_j = 1. और यदि वे अलग-अलग समूहों में हैं, तो फ़ंक्शन 0 पर वापस आ जाएगा।

चूँकि हम कोष्ठक प्रतीक द्वारा कोष्ठक की सामग्री को गुणा करते हैं, इसलिए निवेशित राशि result का परिणाम सबसे अधिक होगा जब एक क्लस्टर के अंदर कोने एक बड़ी संख्या में "अप्रत्याशित" किनारों से जुड़े होते हैं। इस प्रकार, प्रतिरूपकता इस बात का सूचक है कि एक ग्राफ व्यक्तिगत समुदायों में कितना अच्छा है।

2 एल द्वारा डिवीजन एकता के लिए ऊपरी मॉड्यूलरिटी को सीमित करता है। यदि प्रतिरूपकता 0 या नकारात्मक के करीब है, तो इसका मतलब है कि नेटवर्क की वर्तमान क्लस्टरिंग का कोई मतलब नहीं है। प्रतिरूपकता को बढ़ाकर, हम नेटवर्क को क्लस्टर करने का एक बेहतर तरीका पा सकते हैं।

कृपया ध्यान दें कि एक ग्राफ को क्लस्टर करने की "गुणवत्ता" का मूल्यांकन करने के लिए, हमें पहले से यह निर्धारित करना होगा कि इसे कैसे क्लस्टर किया जाएगा। दुर्भाग्य से, जब तक कि नमूना बहुत छोटा नहीं होता है, कम्प्यूटेशनल जटिलता के कारण यह केवल शारीरिक रूप से असंभव है कि वे अपने मापांक की तुलना करके एक ग्राफ को क्लस्टर करने के सभी तरीकों से गुजरें।

संयोजकों का सुझाव है कि 8 कोने वाले नेटवर्क के लिए, 4,140 क्लस्टरिंग विधियां हैं। 16 कोने वाले नेटवर्क के लिए, पहले से ही 10 बिलियन से अधिक तरीके होंगे, 32 कोने वाले नेटवर्क के लिए - 128 सेप्टिलियन, और 80 कोने वाले नेटवर्क के लिए क्लस्टरिंग विधियों की संख्या अवलोकनीय ब्रह्मांड में परमाणुओं की संख्या से अधिक होगी।

इसलिए, गणना के बजाय, हम हेयुरिस्टिक विधि का उपयोग करेंगे, जो क्लस्टर्स को अधिकतम मॉड्यूलरता के साथ अपेक्षाकृत आसानी से गणना करने में मदद करेगा। यह एक एल्गोरिथ्म है जिसे फास्ट-लालची मॉड्यूलरिटी-मैक्सिमाइजेशन कहा जाता है, ऊपर वर्णित एग्लोमेरेटिव पदानुक्रमित क्लस्टरिंग एल्गोरिदम का एक प्रकार का एनालॉग है। निकटता के आधार पर संयोजन के बजाय, मॉड-मैक्स समुदायों को मॉड्यूलरिटी में परिवर्तन के आधार पर एकजुट करता है। यह कैसे काम करता है:

सबसे पहले, प्रत्येक शीर्ष को अपने स्वयं के समुदाय को सौंपा गया है और पूरे नेटवर्क की प्रतिरूपकता की गणना की गई है - एम।

चरण 1 : कम से कम एक किनारे से जुड़े समुदायों की प्रत्येक जोड़ी के लिए, एल्गोरिथ्म इन समुदायों के जोड़े के संयोजन के मामले में मॉड्यूलरिटी ofM में परिणामी परिवर्तन की गणना करता है।

चरण 2 : फिर एक जोड़ी ली जाती है, जब संयुक्त, beM अधिकतम और संयुक्त होगा। इस क्लस्टरिंग के लिए, एक नई प्रतिरूपकता की गणना और संग्रहित किया जाता है।

चरण 1 और 2 दोहराए जाते हैं: हर बार समुदायों की एक जोड़ी जुड़ती है, जो सबसे बड़ा 2M, एक नया क्लस्टरिंग और एम / एम देता है।

जब सभी कोने एक विशाल क्लस्टर में वर्गीकृत किए जाते हैं, तो रोकना बंद हो जाता है। अब एल्गोरिथ्म संग्रहीत रिकॉर्ड की जांच करता है और उच्चतम मॉड्यूलरता के साथ क्लस्टरिंग योजना पाता है। यह वह है जो सामुदायिक संरचना के रूप में लौटता है।

यह कम्प्यूटेशनल रूप से कठिन था, कम से कम लोगों के लिए। ग्राफ सिद्धांत कठिन कम्प्यूटेशनल समस्याओं और एनपी-हार्ड समस्याओं का एक समृद्ध स्रोत है। ग्राफ़ का उपयोग करके, हम जटिल सिस्टम और डेटासेट के बारे में कई उपयोगी निष्कर्ष निकाल सकते हैं। लैरी पेज से पूछें, जिसका पेजरैंक एल्गोरिथम - जिसने Google को एक पीढ़ी से कम समय में एक वैश्विक प्रमुख से स्टार्टअप में बदलने में मदद की - पूरी तरह से ग्राफ सिद्धांत पर आधारित है।

ग्राफ सिद्धांत पर अध्ययन आज समुदायों की पहचान पर केंद्रित है। मॉड्यूलरिटी-मैक्सिमाइजेशन एल्गोरिथ्म के कई विकल्प हैं, जो हालांकि उपयोगी है, इसकी कमियों के बिना नहीं है।

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

अन्य एल्गोरिदम समुदायों को परिभाषित करने के लिए विभिन्न तरीकों का उपयोग करते हैं। उदाहरण के लिए, एज-बिचनेस एक विभाजनकारी (विभाजन) एल्गोरिथ्म है जो सभी वर्टीकल्स को एक विशाल क्लस्टर में समूहित करके शुरू होता है। तब कम से कम "महत्वपूर्ण" किनारों को पुनरावृत्त रूप से हटा दिया जाता है जब तक कि सभी कोने पृथक नहीं हो जाते। परिणाम एक पदानुक्रमित संरचना है जिसमें कोने एक-दूसरे के करीब होते हैं, वे समान हैं।

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

हम प्रत्येक एल्गोरिथ्म के लिए काम के उदाहरणों का विस्तार से विश्लेषण नहीं करेंगे। , , 20 .

निष्कर्ष

, - , , . , , 20-40 .

, — , . , , .

, , , , . , - , , ? - !