उच्च-आयामी डेटा को क्लस्टर करना

From Vigyanwiki
Revision as of 20:10, 2 August 2023 by alpha>Karanpant (text)

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

समस्याएँ

उच्च-आयामी आंकड़ों में स्तवक के लिए चार समस्याओं को दूर करने की आवश्यकता है: [1]

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

हाल के शोध से संकेत मिलता है कि भेदभाव की समस्या तभी उत्पन्न होती है जब अप्रासंगिक आयामों की संख्या अधिक होती है, और साझा-निकटतम-पड़ोसी दृष्टिकोण परिणामों में सुधार कर सकते हैं। [2]


दृष्टिकोण

अक्ष-समानांतर या स्वेच्छाचारी रूप से उन्मुख एफ़िन उप-स्थानों में स्तवक के प्रति दृष्टिकोण इस बात में भिन्न होते हैं कि वे समग्र लक्ष्य की व्याख्या कैसे करते हैं, जो उच्च आयामीता वाले आंकड़ों में स्तवक ढूंढ रहा है। [1] आंकड़े आव्यूह में पतिरूप के आधार पर समूहों को ढूंढना एक समग्र रूप से भिन्न दृष्टिकोण है, जिसे प्रायः बाइस्तवक कहा जाता है, जो जैव सूचना विज्ञान में प्रायः उपयोग की जाने वाली तकनीक है।

सबस्पेस स्तवक

सबस्पेसस्तवक के साथ उदाहरण 2डी स्पेस

निकटवर्ती छवि केवल द्वि-आयामी स्थान दिखाती है जहां कई समूहों की पहचान की जा सकती है। एक-आयामी उप-स्थानों में, स्तवक (उपस्थान में ) और , , (उपस्थान में ) पाया जा सकता है। इसे द्वि-आयामी (उप-स्थान) में स्तवक नहीं माना जा सकता, क्योंकि यह एक्सिस से बहुत कम वितरित है । दो आयामों में, दो स्तवक और पहचाना जा सकता है.

सबस्पेस स्तवक की समस्या इस तथ्य से दी गई है कि वहाँ हैं किसी स्थान के विभिन्न उपस्थानों के साथ आयाम. यदि उप-स्थान अक्ष-समानांतर नहीं हैं, तो अनंत संख्या में उप-स्थान संभव हैं। इसलिए, सबस्पेस स्तवक एल्गोरिदम निम्न परिणाम उत्पन्न करने के जोखिम पर, कम्प्यूटेशनल रूप से व्यवहार्य बने रहने के लिए कुछ प्रकार के अनुमान का उपयोग करते हैं। उदाहरण के लिए, डाउनवर्ड-क्लोजर प्रॉपर्टी (सीएफ. एसोसिएशन नियम सीखना) का उपयोग केवल निचले-आयामी उप-स्थानों को मिलाकर उच्च-आयामी उप-स्थान बनाने के लिए किया जा सकता है, क्योंकि किसी भी उप-स्थान टी में एकस्तवक होता है, जिसके परिणामस्वरूप उसस्तवक को शामिल करने के लिए एक पूर्ण स्थान एस भी होगा (यानी एस ⊆ टी), अधिकांश पारंपरिक एल्गोरिदम जैसे कि CLIQUE द्वारा अपनाया गया दृष्टिकोण,[3] सबक्लू.[4] प्रत्येक आयाम के लिए प्रासंगिकता की विभिन्न डिग्री का उपयोग करके एक उप-स्थान को परिभाषित करना भी संभव है, आईएमडब्ल्यूके-मीन्स द्वारा अपनाया गया एक दृष्टिकोण,[5] ईबीके-मोड[6] और सीबीके-मोड।[7]


प्रोजेक्टेड स्तवक

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

उदाहरण के लिए, PreDeCon एल्गोरिदम जांचता है कि कौन सी विशेषताएँ प्रत्येक बिंदु के लिए स्तवक का समर्थन करती हैं, और दूरी फ़ंक्शन को समायोजित करती हैं जैसे कि कम विचरण वाले आयाम दूरी फ़ंक्शन में प्रवर्धित होते हैं।[8] उपरोक्त चित्र में,स्तवक एक दूरी फ़ंक्शन के साथ DBSCAN का उपयोग करते हुए पाया जा सकता है जो इस पर कम जोर देता है -अक्ष और इस प्रकार कम अंतर को बढ़ा देता है -अक्ष बिंदुओं को एकस्तवक में समूहित करने के लिए पर्याप्त रूप से पर्याप्त है।

PROCLUS k-medoid स्तवक के साथ एक समान दृष्टिकोण का उपयोग करता है।[9] प्रारंभिक मेडोइड्स का अनुमान लगाया जाता है, और प्रत्येक मेडॉइड के लिए कम विचरण वाले गुणों द्वारा फैला हुआ उप-स्थान निर्धारित किया जाता है। दूरी निर्धारित करने में केवल उस मेडॉइड के उपस्थान पर विचार करते हुए, निकटतम मेडॉइड को अंक दिए जाते हैं। इसके बाद एल्गोरिथम नियमित मेडोइड्स के आसपास विभाजन एल्गोरिथम के रूप में आगे बढ़ता है।

यदि दूरी फ़ंक्शन का वजन अलग-अलग होता है, लेकिन कभी भी 0 के साथ नहीं होता है (और इसलिए अप्रासंगिक विशेषताओं को कभी नहीं छोड़ता है), एल्गोरिदम को सॉफ्ट-प्रोजेक्टेड स्तवक एल्गोरिदम कहा जाता है।

प्रक्षेपण-आधारित स्तवक

प्रक्षेपण-आधारित स्तवक दो-आयामी अंतरिक्ष में उच्च-आयामी डेटा के गैर-रेखीय प्रक्षेपण पर आधारित है।[10] विशिष्ट प्रक्षेपण-विधियाँ जैसे टी-वितरित स्टोकेस्टिक पड़ोसी एम्बेडिंग (टी-एसएनई),[11] या पड़ोसी पुनर्प्राप्ति विज़ुअलाइज़र (NerV) [12] डेटा को स्पष्ट रूप से दो आयामों में प्रोजेक्ट करने के लिए उपयोग किया जाता है, जिसमें दो से अधिक आयाम के उप-स्थानों की उपेक्षा की जाती है और उच्च-आयामी डेटा में केवल प्रासंगिक पड़ोस को संरक्षित किया जाता है। अगले चरण में, डेलाउने त्रिभुज[13] अनुमानित बिंदुओं के बीच की गणना की जाती है, और दो अनुमानित बिंदुओं के बीच प्रत्येक शीर्ष को संबंधित उच्च-आयामी डेटा बिंदुओं के बीच उच्च-आयामी दूरी के साथ भारित किया जाता है। इसके बाद दिज्क्स्ट्रा के एल्गोरिदम का उपयोग करके प्रत्येक जोड़ी बिंदुओं के बीच सबसे छोटे पथ की गणना की जाती है।[14] स्तवक प्रक्रिया में सबसे छोटे रास्तों का उपयोग किया जाता है, जिसमें उच्च-आयामी डेटा में संरचना प्रकार के आधार पर दो विकल्प शामिल होते हैं।[10]यह बूलियन विकल्प उच्च-आयामी संरचनाओं के स्थलाकृतिक मानचित्र को देखकर तय किया जा सकता है।[15] 34 तुलनीय स्तवक विधियों की बेंचमार्किंग में, प्रक्षेपण-आधारित स्तवक एकमात्र एल्गोरिदम था जो हमेशा डेटासेट की उच्च-आयामी दूरी या घनत्व-आधारित संरचना को खोजने में सक्षम था।[10]प्रोजेक्शन-आधारित स्तवक सीआरएएन पर ओपन-सोर्स आर पैकेज प्रोजेक्शनबेस्डस्तवक में पहुंच योग्य है।[16]


हाइब्रिड दृष्टिकोण

सभी एल्गोरिदम या तो प्रत्येक बिंदु के लिए एक अद्वितीयस्तवक असाइनमेंट या सभी उप-स्थानों में सभीस्तवक खोजने का प्रयास नहीं करते हैं; कई लोग बीच में एक परिणाम के लिए तैयार हो जाते हैं, जहां संभवतः अतिव्यापी, लेकिन जरूरी नहीं कि संपूर्ण समूहों के समूह पाए जाते हैं। एक उदाहरण FIRES है, जो अपने मूल दृष्टिकोण से एक सबस्पेस स्तवक एल्गोरिदम है, लेकिन सभी सबस्पेसस्तवकों को विश्वसनीय रूप से उत्पन्न करने के लिए एक हेयुरिस्टिक बहुत आक्रामक का उपयोग करता है।[17] एक अन्य हाइब्रिड दृष्टिकोण मानव-में-एल्गोरिदमिक-लूप को शामिल करना है: मानव डोमेन विशेषज्ञता नमूनों के अनुमानी चयन के माध्यम से एक घातीय खोज स्थान को कम करने में मदद कर सकती है। यह स्वास्थ्य क्षेत्र में फायदेमंद हो सकता है, उदाहरण के लिए, चिकित्सा डॉक्टरों को रोगी की स्थितियों के उच्च-आयामी विवरण और कुछ उपचारों की सफलता पर माप का सामना करना पड़ता है। ऐसे डेटा में एक महत्वपूर्ण प्रश्न आयामों के संयोजन के साथ-साथ रोगी की स्थितियों और चिकित्सा परिणामों की तुलना और सहसंबंध बनाना है। आयामों की संख्या प्रायः बहुत बड़ी होती है, परिणामस्वरूप विशेषज्ञ विश्लेषण के लिए अधिक उपयुक्त होने के लिए उन्हें कम संख्या में प्रासंगिक आयामों में मैप करने की आवश्यकता होती है। ऐसा इसलिए है क्योंकि अप्रासंगिक, अनावश्यक और परस्पर विरोधी आयाम संपूर्ण विश्लेषणात्मक प्रक्रिया की प्रभावशीलता और दक्षता को नकारात्मक रूप से प्रभावित कर सकते हैं।[18]


सहसंबंध स्तवक

सहसंबंध स्तवक|सहसंबंध स्तवक (डेटा माइनिंग) में एक अन्य प्रकार के उप-स्थान पर विचार किया जाता है।

सॉफ़्टवेयर

  • ELKI में विभिन्न उप-स्थान और सहसंबंध स्तवक एल्गोरिदम शामिल हैं
  • एफसीपीएस में पचास से अधिक स्तवक एल्गोरिदम शामिल हैं[19]


संदर्भ

  1. ↑ 1.0 1.1 Kriegel, H. P.; Kröger, P.; Zimek, A. (2009). "उच्च-आयामी डेटा को क्लस्टर करना". ACM Transactions on Knowledge Discovery from Data. 3: 1–58. doi:10.1145/1497577.1497578. S2CID 17363900.
  2. ↑ Houle, M. E.; Kriegel, H. P.; Kröger, P.; Schubert, E.; Zimek, A. (2010). Can Shared-Neighbor Distances Defeat the Curse of Dimensionality? (PDF). Scientific and Statistical Database Management. Lecture Notes in Computer Science. Vol. 6187. p. 482. doi:10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.
  3. ↑ Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). "उच्च आयामी डेटा की स्वचालित उप-स्थान क्लस्टरिंग". Data Mining and Knowledge Discovery. 11: 5–33. CiteSeerX 10.1.1.131.5152. doi:10.1007/s10618-005-1396-1. S2CID 9289572.
  4. ↑ Kailing, K.; Kriegel, H. P.; Kröger, P. (2004). उच्च-आयामी डेटा के लिए घनत्व-कनेक्टेड सबस्पेस क्लस्टरिंग. Proceedings of the 2004 SIAM International Conference on Data Mining. pp. 246. doi:10.1137/1.9781611972740.23. ISBN 978-0-89871-568-2.
  5. ↑ De Amorim, R.C.; Mirkin, B. (2012). "मिन्कोव्स्की मीट्रिक, के-मीन्स क्लस्टरिंग में फ़ीचर वेटिंग और विसंगतिपूर्ण क्लस्टर आरंभीकरण". Pattern Recognition. 45 (3): 1061. Bibcode:2012PatRe..45.1061C. doi:10.1016/j.patcog.2011.08.012.
  6. ↑ Carbonera, Joel Luis; Abel, Mara (November 2014). "An Entropy-Based Subspace Clustering Algorithm for Categorical Data". 2014 IEEE 26th International Conference on Tools with Artificial Intelligence. IEEE. pp. 272–277. doi:10.1109/ictai.2014.48. ISBN 9781479965724. S2CID 7208538.
  7. ↑ Carbonera, Joel Luis; Abel, Mara (2015). CBK-Modes: A Correlation-based Algorithm for Categorical Data Clustering. doi:10.5220/0005367106030608. ISBN 9789897580963. {{cite book}}: |journal= ignored (help)
  8. ↑ Böhm, C.; Kailing, K.; Kriegel, H. -P.; Kröger, P. (2004). स्थानीय उप-स्थान प्राथमिकताओं के साथ घनत्व कनेक्टेड क्लस्टरिंग (PDF). Fourth IEEE International Conference on Data Mining (ICDM'04). p. 27. doi:10.1109/ICDM.2004.10087. ISBN 0-7695-2142-8.
  9. ↑ Aggarwal, C. C.; Wolf, J. L.; Yu, P. S.; Procopiuc, C.; Park, J. S. (1999). "अनुमानित क्लस्टरिंग के लिए तेज़ एल्गोरिदम". ACM SIGMOD Record. 28 (2): 61. CiteSeerX 10.1.1.681.7363. doi:10.1145/304181.304188.
  10. ↑ 10.0 10.1 10.2 Thrun, M. C., & Ultsch, A. : Using Projection based Clustering to Find Distance and Density based Clusters in High-Dimensional Data, J. Classif., pp. 1-33, doi: 10.1007/s00357-020-09373-2.
  11. ↑ Van der Maaten, L., & Hinton, G.: Visualizing Data using t-SNE, Journal of Machine Learning Research, Vol. 9(11), pp. 2579-2605. 2008.
  12. ↑ Venna, J., Peltonen, J., Nybo, K., Aidos, H., & Kaski, S.: Information retrieval perspective to nonlinear dimensionality reduction for data visualization, The Journal of Machine Learning Research, Vol. 11, pp. 451-490. 2010.
  13. ↑ Delaunay, B.: Sur la sphere vide, Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, Vol. 7(793-800), pp. 1-2. 1934.
  14. ↑ Dijkstra, E. W.: A note on two problems in connexion with graphs, Numerische mathematik, Vol. 1(1), pp. 269-271. 1959.
  15. ↑ Thrun, M. C., & Ultsch, A.: Uncovering High-Dimensional Structures of Projections from Dimensionality Reduction Methods, MethodsX, Vol. 7, pp. 101093, doi: 10.1016/j.mex.20200.101093,2020.
  16. ↑ "सीआरएएन - पैकेज प्रोजेक्शन आधारित क्लस्टरिंग". Archived from the original on 2018-03-17.
  17. ↑ Kriegel, H.; Kröger, P.; Renz, M.; Wurst, S. (2005). उच्च-आयामी डेटा के कुशल उप-स्थान क्लस्टरिंग के लिए एक सामान्य रूपरेखा (PDF). Fifth IEEE International Conference on Data Mining (ICDM'05). p. 250. doi:10.1109/ICDM.2005.5. ISBN 0-7695-2278-5.
  18. ↑ Hund, M.; Böhm, D.; Sturm, W.; Sedlmair, M.; Schreck, T.; Keim, D.A.; Majnaric, L.; Holzinger, A. (2016). "Visual analytics for concept exploration in subspaces of patient groups: Making sense of complex datasets with the Doctor-in-the-loop". Brain Informatics. 3 (4): 233–247. doi:10.1007/s40708-016-0043-5. PMC 5106406. PMID 27747817.
  19. ↑ Thrun, M. C., & Stier, Q.: Fundamental Clustering Algorithms Suite, SoftwareX, Vol. 13(C), pp. 100642, doi: 10.1016/j.softx.2020.100642, 2021.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=उच्च-आयामी_डेटा_को_क्लस्टर_करना&oldid=241174’