डन सूचकांक: Difference between revisions
(Created page with "{{short description|Metric for evaluating clustering algorithms}} डन इंडेक्स (डीआई) (1974 में जे. सी. डन द्वारा प्...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Metric for evaluating clustering algorithms}} | {{short description|Metric for evaluating clustering algorithms}} | ||
डन इंडेक्स (डीआई) (1974 में जे. सी. डन द्वारा प्रस्तुत) | '''डन इंडेक्स (डीआई)''' (1974 में जे. सी. डन द्वारा प्रस्तुत) क्लस्टरिंग एल्गोरिदम के मूल्यांकन के लिए एक मीट्रिक है।<ref>{{Cite journal|date=1973-09-17|title=ISODATA प्रक्रिया का एक अस्पष्ट सापेक्ष और कॉम्पैक्ट अच्छी तरह से अलग किए गए क्लस्टर का पता लगाने में इसका उपयोग|journal=Journal of Cybernetics|volume=3|issue=3|pages=32–57|doi=10.1080/01969727308546046|last1=Dunn|first1=J. C.|s2cid=120919314}}</ref><ref>{{Cite journal|last=Dunn|first=J. C.|date=1973-09-01|title=अच्छी तरह से अलग किए गए क्लस्टर और इष्टतम फ़ज़ी विभाजन|journal=Journal of Cybernetics|publication-date=1974|volume=4|issue=1|pages=95–104|doi=10.1080/01969727408546059|issn=0022-0280}}</ref> यह डेविस-बोल्डिन इंडेक्स या सिल्हूट इंडेक्स सहित वैधता सूचकांकों के एक समूह का हिस्सा है, इसमें यह एक आंतरिक मूल्यांकन योजना है, जहां परिणाम क्लस्टर किए गए डेटा पर आधारित होता है। ऐसे अन्य सभी सूचकांकों की तरह, इसका उद्देश्य उन समूहों के समुच्चय की पहचान करना है जो कॉम्पैक्ट हैं, क्लस्टर के सदस्यों के बीच एक छोटा सा अंतर है, और अच्छी तरह से अलग हैं, जहां विभिन्न समूहों के साधन भीतर की तुलना में पर्याप्त रूप से दूर हैं। क्लस्टर विचरण. क्लस्टर के दिए गए असाइनमेंट के लिए, एक उच्च डन इंडेक्स बेहतर क्लस्टरिंग को इंगित करता है। इसका उपयोग करने की कमियों में से एक कम्प्यूटेशनल लागत है क्योंकि क्लस्टर की संख्या और डेटा की आयामीता बढ़ जाती है। | ||
किसी क्लस्टर का आकार या व्यास परिभाषित करने के कई तरीके हैं। यह क्लस्टर के अंदर सबसे दूर के दो बिंदुओं के बीच की दूरी हो सकती है, यह क्लस्टर के अंदर डेटा बिंदुओं के बीच सभी जोड़ीदार दूरियों का माध्य हो सकता है, या यह क्लस्टर सेंट्रोइड से प्रत्येक डेटा बिंदु की दूरी भी हो सकती है। इनमें से प्रत्येक सूत्रीकरण को गणितीय रूप से नीचे दर्शाया गया है: | |||
क्लस्टर | |||
मान लीजिए ''C<sub>i</sub>'' सदिशों का एक समूह है। मान लीजिए कि x और y एक ही क्लस्टर ''C<sub>i</sub>'' को निर्दिष्ट कोई दो n आयामी फ़ीचर वैक्टर हैं | |||
: <math> \Delta_i = \underset{x , y \in C_i}{\text{max}} d(x,y) </math> , जो अधिकतम दूरी | : <math> \Delta_i = \underset{x , y \in C_i}{\text{max}} d(x,y) </math> , जो कि अधिकतम दूरी (डन द्वारा प्रस्तावित संस्करण) की गणना करता है। | ||
: <math> \Delta_i = \dfrac{2}{|C_i| (|C_i| - 1)} \underset{x , y \in C_i, x \neq y}{\sum} d(x,y) </math> , जो सभी जोड़ियों के बीच की औसत दूरी की गणना करता है। | : <math> \Delta_i = \dfrac{2}{|C_i| (|C_i| - 1)} \underset{x , y \in C_i, x \neq y}{\sum} d(x,y) </math> , जो सभी जोड़ियों के बीच की औसत दूरी की गणना करता है। | ||
| Line 13: | Line 12: | ||
: <math> \Delta_i = \dfrac{\underset{x \in C_i}{\sum} d(x,\mu)}{|C_i|} , \mu = \dfrac{\underset{x \in C_i}{\sum} x}{|C_i|} </math> , माध्य से सभी बिंदुओं की दूरी की गणना करता है। | : <math> \Delta_i = \dfrac{\underset{x \in C_i}{\sum} d(x,\mu)}{|C_i|} , \mu = \dfrac{\underset{x \in C_i}{\sum} x}{|C_i|} </math> , माध्य से सभी बिंदुओं की दूरी की गणना करता है। | ||
इसे इंटरक्लस्टर दूरी के बारे में भी कहा जा सकता है, जहां निकटतम दो डेटा बिंदुओं (डन द्वारा प्रयुक्त), प्रत्येक क्लस्टर में एक, या सबसे दूर दो, या सेंट्रोइड्स के बीच की दूरी आदि का उपयोग करके समान फॉर्मूलेशन | इसे इंटरक्लस्टर दूरी के बारे में भी कहा जा सकता है, जहां निकटतम दो डेटा बिंदुओं (डन द्वारा प्रयुक्त), प्रत्येक क्लस्टर में एक, या सबसे दूर के दो, या सेंट्रोइड्स के बीच की दूरी आदि का उपयोग करके समान फॉर्मूलेशन बनाया जा सकता है। सूचकांक की परिभाषा में ऐसे किसी भी सूत्रीकरण को शामिल किया गया है, और इस प्रकार गठित सूचकांकों के परिवार को डन-लाइक इंडेक्स कहा जाता है। मन लीजिये <math> \delta(C_i,C_j) </math> यह क्लस्टर ''C<sub>i</sub>'' और C<sub>j</sub> के बीच इंटरक्लस्टर दूरी मीट्रिक है। | ||
==परिभाषा== | ==परिभाषा== | ||
उपरोक्त नोटेशन के साथ, यदि एम क्लस्टर हैं, तो | उपरोक्त नोटेशन के साथ, यदि एम क्लस्टर हैं, तो समुच्चय के लिए डन इंडेक्स को इस प्रकार परिभाषित किया गया है: | ||
: <math> \mathit{DI}_m = \frac{ \underset{ 1 \leqslant i < j \leqslant m}{\text{min}} \left.\delta(C_i,C_j)\right.}{ \underset{ 1 \leqslant k \leqslant m}{\text{max}} \left.\Delta_k\right.} </math>. | : <math> \mathit{DI}_m = \frac{ \underset{ 1 \leqslant i < j \leqslant m}{\text{min}} \left.\delta(C_i,C_j)\right.}{ \underset{ 1 \leqslant k \leqslant m}{\text{max}} \left.\Delta_k\right.} </math>. | ||
==स्पष्टीकरण== | ==स्पष्टीकरण== | ||
इस तरह परिभाषित होने | इस तरह से परिभाषित होने पर, DI (डीआई) समुच्चय में क्लस्टर की संख्या, m पर निर्भर करता है। यदि क्लस्टरों की संख्या पहले से ज्ञात नहीं है, तो जिस एम के लिए डीआई उच्चतम है उसे क्लस्टरों की संख्या के रूप में चुना जा सकता है। जब d(x,y) की परिभाषा की बात आती है तो इसमें कुछ प्रतिस्थितित्व भी होता है, जहां क्लस्टरिंग समस्या की ज्यामिति के आधार पर किसी भी प्रसिद्ध मैट्रिक्स का उपयोग किया जा सकता है, जैसे मैनहट्टन दूरी या [[यूक्लिडियन दूरी]] है। इस सूत्रीकरण में एक अजीब समस्या है, इसमें यदि समूहों में से एक के साथ अनैतिक व्यवहार किया जाता है, जहां अन्य को कसकर पैक किया जाता है, क्योंकि हर में एक औसत शब्द के बजाय 'अधिकतम' शब्द होता है, तो समूहों के उस समुच्चय के लिए डन इंडेक्स होगा अस्वाभाविक रूप से निम्न है। इस प्रकार यह सबसे खराब स्थिति का संकेतक है, और इसे ध्यान में रखा जाना चाहिए। मैटलैब (MATLAB), R और अपाचे महौत (Apache Mahout) जैसी कुछ वेक्टर आधारित प्रोग्रामिंग भाषाओं में डन इंडेक्स का कार्यान्वयन तैयार है।<ref>{{cite web|url=http://www.mathworks.com/matlabcentral/fileexchange/27859-dunns-index |title=डन इंडेक्स का MATLAB कार्यान्वयन|access-date=5 December 2011}}</ref><ref>{{cite web|last=Lukasz|first=Nieweglowski|title=पैकेज 'सीएलवी'|url=https://cran.r-project.org/web/packages/clv/clv.pdf|work=R project|publisher=CRAN|access-date=2 April 2013}}</ref><ref>{{cite web|title=अपाचे महावत|url=http://mahout.apache.org/|publisher=Apache Software Foundation|access-date=9 May 2013}}</ref> | ||
Revision as of 16:55, 15 July 2023
डन इंडेक्स (डीआई) (1974 में जे. सी. डन द्वारा प्रस्तुत) क्लस्टरिंग एल्गोरिदम के मूल्यांकन के लिए एक मीट्रिक है।[1][2] यह डेविस-बोल्डिन इंडेक्स या सिल्हूट इंडेक्स सहित वैधता सूचकांकों के एक समूह का हिस्सा है, इसमें यह एक आंतरिक मूल्यांकन योजना है, जहां परिणाम क्लस्टर किए गए डेटा पर आधारित होता है। ऐसे अन्य सभी सूचकांकों की तरह, इसका उद्देश्य उन समूहों के समुच्चय की पहचान करना है जो कॉम्पैक्ट हैं, क्लस्टर के सदस्यों के बीच एक छोटा सा अंतर है, और अच्छी तरह से अलग हैं, जहां विभिन्न समूहों के साधन भीतर की तुलना में पर्याप्त रूप से दूर हैं। क्लस्टर विचरण. क्लस्टर के दिए गए असाइनमेंट के लिए, एक उच्च डन इंडेक्स बेहतर क्लस्टरिंग को इंगित करता है। इसका उपयोग करने की कमियों में से एक कम्प्यूटेशनल लागत है क्योंकि क्लस्टर की संख्या और डेटा की आयामीता बढ़ जाती है।
किसी क्लस्टर का आकार या व्यास परिभाषित करने के कई तरीके हैं। यह क्लस्टर के अंदर सबसे दूर के दो बिंदुओं के बीच की दूरी हो सकती है, यह क्लस्टर के अंदर डेटा बिंदुओं के बीच सभी जोड़ीदार दूरियों का माध्य हो सकता है, या यह क्लस्टर सेंट्रोइड से प्रत्येक डेटा बिंदु की दूरी भी हो सकती है। इनमें से प्रत्येक सूत्रीकरण को गणितीय रूप से नीचे दर्शाया गया है:
मान लीजिए Ci सदिशों का एक समूह है। मान लीजिए कि x और y एक ही क्लस्टर Ci को निर्दिष्ट कोई दो n आयामी फ़ीचर वैक्टर हैं
- , जो कि अधिकतम दूरी (डन द्वारा प्रस्तावित संस्करण) की गणना करता है।
- , जो सभी जोड़ियों के बीच की औसत दूरी की गणना करता है।
- , माध्य से सभी बिंदुओं की दूरी की गणना करता है।
इसे इंटरक्लस्टर दूरी के बारे में भी कहा जा सकता है, जहां निकटतम दो डेटा बिंदुओं (डन द्वारा प्रयुक्त), प्रत्येक क्लस्टर में एक, या सबसे दूर के दो, या सेंट्रोइड्स के बीच की दूरी आदि का उपयोग करके समान फॉर्मूलेशन बनाया जा सकता है। सूचकांक की परिभाषा में ऐसे किसी भी सूत्रीकरण को शामिल किया गया है, और इस प्रकार गठित सूचकांकों के परिवार को डन-लाइक इंडेक्स कहा जाता है। मन लीजिये यह क्लस्टर Ci और Cj के बीच इंटरक्लस्टर दूरी मीट्रिक है।
परिभाषा
उपरोक्त नोटेशन के साथ, यदि एम क्लस्टर हैं, तो समुच्चय के लिए डन इंडेक्स को इस प्रकार परिभाषित किया गया है:
- .
स्पष्टीकरण
इस तरह से परिभाषित होने पर, DI (डीआई) समुच्चय में क्लस्टर की संख्या, m पर निर्भर करता है। यदि क्लस्टरों की संख्या पहले से ज्ञात नहीं है, तो जिस एम के लिए डीआई उच्चतम है उसे क्लस्टरों की संख्या के रूप में चुना जा सकता है। जब d(x,y) की परिभाषा की बात आती है तो इसमें कुछ प्रतिस्थितित्व भी होता है, जहां क्लस्टरिंग समस्या की ज्यामिति के आधार पर किसी भी प्रसिद्ध मैट्रिक्स का उपयोग किया जा सकता है, जैसे मैनहट्टन दूरी या यूक्लिडियन दूरी है। इस सूत्रीकरण में एक अजीब समस्या है, इसमें यदि समूहों में से एक के साथ अनैतिक व्यवहार किया जाता है, जहां अन्य को कसकर पैक किया जाता है, क्योंकि हर में एक औसत शब्द के बजाय 'अधिकतम' शब्द होता है, तो समूहों के उस समुच्चय के लिए डन इंडेक्स होगा अस्वाभाविक रूप से निम्न है। इस प्रकार यह सबसे खराब स्थिति का संकेतक है, और इसे ध्यान में रखा जाना चाहिए। मैटलैब (MATLAB), R और अपाचे महौत (Apache Mahout) जैसी कुछ वेक्टर आधारित प्रोग्रामिंग भाषाओं में डन इंडेक्स का कार्यान्वयन तैयार है।[3][4][5]
नोट्स और संदर्भ
- ↑ Dunn, J. C. (1973-09-17). "ISODATA प्रक्रिया का एक अस्पष्ट सापेक्ष और कॉम्पैक्ट अच्छी तरह से अलग किए गए क्लस्टर का पता लगाने में इसका उपयोग". Journal of Cybernetics. 3 (3): 32–57. doi:10.1080/01969727308546046. S2CID 120919314.
- ↑ Dunn, J. C. (1973-09-01). "अच्छी तरह से अलग किए गए क्लस्टर और इष्टतम फ़ज़ी विभाजन". Journal of Cybernetics (published 1974). 4 (1): 95–104. doi:10.1080/01969727408546059. ISSN 0022-0280.
- ↑ "डन इंडेक्स का MATLAB कार्यान्वयन". Retrieved 5 December 2011.
- ↑ Lukasz, Nieweglowski. "पैकेज 'सीएलवी'" (PDF). R project. CRAN. Retrieved 2 April 2013.
- ↑ "अपाचे महावत". Apache Software Foundation. Retrieved 9 May 2013.
बाहरी संबंध
- Pakhira, Malay K.; Bandyopadhyay, Sanghamitra; Maulik, Ujjwal (2004). "Validity index for crisp and fuzzy clusters". Pattern Recognition. 37 (3): 487–501. doi:10.1016/j.patcog.2003.06.005.
- Bezdek, J.C.; Pal, N.R. (1995). "Cluster validation with generalized Dunn's indices". Proceedings 1995 Second New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems. IEEE Xplore: 190–193. doi:10.1109/ANNES.1995.499469. ISBN 0-8186-7174-2.
