बाइक्लस्टरिंग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 45: Line 45:
  | s2cid = 19058237
  | s2cid = 19058237
  }}
  }}
</ref> [[डेटा खनन]] तकनीक है। जो [[मैट्रिक्स (गणित)]] की पंक्तियों और स्तंभों के साथ [[क्लस्टर विश्लेषण]] की अनुमति देती है।
</ref> [[डेटा खनन]] तकनीक है। जो [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] की पंक्तियों और स्तंभों के साथ [[क्लस्टर विश्लेषण]] की अनुमति देती है।


यह शब्द सबसे पहले बोरिस मिर्किन द्वारा प्रस्तुत किया गया था।<ref name="mirkin">{{cite book | last = Mirkin | first = Boris | title = गणितीय वर्गीकरण और क्लस्टरिंग| publisher = Kluwer Academic Publishers | year = 1996 | isbn = 978-0-7923-4159-8 }}</ref> कई वर्ष पहले प्रारंभ की गई तकनीक का नाम बताने के लिए,<ref name="mirkin" />1972 में, जॉन ए. हार्टिगन द्वारा<ref name="Hartigan">{{cite journal | author = Hartigan JA | year = 1972 | title = डेटा मैट्रिक्स की प्रत्यक्ष क्लस्टरिंग| journal = Journal of the American Statistical Association | volume = 67 | issue = 337 | pages = 123–9 | doi = 10.2307/2284710 | jstor = 2284710}}</ref> का सेट <math>m</math> दिया गया द्वारा दर्शाए गए नमूने <math>n</math>-आयामी फीचर वेक्टर, संपूर्ण डेटासेट को इस रूप में दर्शाया जा सकता है <math>m</math> में पंक्तियाँ <math>n</math> कॉलम (यानी, an <math>m \times n</math> आव्यूह) बाइक्लस्टरिंग एल्गोरिदम बाइक्लस्टर उत्पन्न करता है। बाइक्लस्टर पंक्तियों का उपसमूह है जो स्तंभों के उपसमूह में समान व्यवहार प्रदर्शित करता है, या इसके विपरीत है।
यह शब्द सबसे पहले बोरिस मिर्किन द्वारा प्रस्तुत किया गया था।<ref name="mirkin">{{cite book | last = Mirkin | first = Boris | title = गणितीय वर्गीकरण और क्लस्टरिंग| publisher = Kluwer Academic Publishers | year = 1996 | isbn = 978-0-7923-4159-8 }}</ref> कई वर्ष पहले प्रारंभ की गई तकनीक का नाम बताने के लिए,<ref name="mirkin" />1972 में, जॉन ए. हार्टिगन द्वारा<ref name="Hartigan">{{cite journal | author = Hartigan JA | year = 1972 | title = डेटा मैट्रिक्स की प्रत्यक्ष क्लस्टरिंग| journal = Journal of the American Statistical Association | volume = 67 | issue = 337 | pages = 123–9 | doi = 10.2307/2284710 | jstor = 2284710}}</ref> का सेट <math>m</math> दिया गया द्वारा दर्शाए गए नमूने <math>n</math>-आयामी फीचर वेक्टर, संपूर्ण डेटासेट को इस रूप में दर्शाया जा सकता है: <math>m</math> में पंक्तियाँ <math>n</math> कॉलम (अर्थात्, एक <math>m \times n</math> आव्यूह) बाइक्लस्टरिंग एल्गोरिदम बाइक्लस्टर उत्पन्न करता है। बाइक्लस्टर पंक्तियों का उपसमूह है, जो स्तंभों के उपसमूह में समान व्यवहार प्रदर्शित करता है, या इसके विपरीत है।


== विकास ==
== विकास ==
बाइक्लस्टरिंग का प्रारंभ मूल रूप से 1972 में जॉन ए. हार्टिगन द्वारा की गई थी।<ref name=Hartigan></ref> बाइक्लस्टरिंग शब्द का उपयोग बाद में बोरिस जी. मिर्किन द्वारा किया गया और परिष्कृत किया गया। इस एल्गोरिदम को 2000 तक सामान्यीकृत नहीं किया गया था, जब वाई. चेंग और जॉर्ज एम. चर्च ने विचरण के आधार पर बाइक्लस्टरिंग एल्गोरिदम का प्रस्ताव रखा और इसे जैविक जीन अभिव्यक्ति डेटा पर प्रयुक्त किया।<ref>https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Cheng Y, Church G M. Biclustering of expression data[C]//Ismb. 2000, 8: 93–103.</ref> 2001 और 2003 में, आई.एस. ढिल्लों ने फ़ाइलों और शब्दों पर बाइक्लस्टरिंग प्रयुक्त करने वाले दो एल्गोरिदम प्रकाशित किए। संस्करण द्विदलीय वर्णक्रमीय ग्राफ़ विभाजन पर आधारित था।<ref>[http://dl.acm.org/citation.cfm?id=502550  Dhillon I S. Co-clustering documents and words using bipartite spectral graph partitioning&#91;C&#93;//Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2001: 269–274.]</ref> दूसरा सूचना सिद्धांत पर आधारित था। ढिल्लों ने माना कि बाइक्लस्टरिंग के समय [[आपसी जानकारी]] का हानि कुल्बैक-लीब्लर विचलन के बराबर था। P और Q के बीच कुल्बैक-लीब्लर-दूरी (KL-दूरी)। P बाइक्लस्टरिंग से पहले फ़ाइलों और फीचर शब्दों के वितरण का प्रतिनिधित्व करता है, जबकि Q वितरण है बाइक्लस्टरिंग के बाद. KL-दूरी दो यादृच्छिक वितरणों के बीच अंतर मापने के लिए है। KL = 0 जब दोनों वितरण समान होते हैं और अंतर बढ़ने पर KL बढ़ता है।<ref>[http://dl.acm.org/citation.cfm?id=956764 Dhillon I S, Mallela S, Modha D S. Information-theoretic co-clustering&#91;C&#93;//Proceedings of the ninth ACM SIGKDD international conference on KKluwer Academic Publishersnowledge discovery and data mining. ACM, 2003: 89–98.]</ref> इस प्रकार, एल्गोरिदम का उद्देश्य P और Q के बीच न्यूनतम [[केएल-दूरी|KL-दूरी]] का पता लगाना था। 2004 में, अरिंदम बनर्जी ने बाइक्लस्टरिंग एल्गोरिदम को डिजाइन करने के लिए KL-दूरी के अतिरिक्त भारित-[[ब्रेगमैन दूरी]] का उपयोग किया जो किसी भी प्रकार के मैट्रिक्स के लिए उपयुक्त था, केएल-दूरी एल्गोरिदम के विपरीत है।<ref>[http://dl.acm.org/citation.cfm?id=1014111 Banerjee A, Dhillon I, Ghosh J, et al. A generalized maximum entropy approach to Bregman co-clustering and matrix approximation&#91;C&#93;//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004: 509–514.]</ref>
बाइक्लस्टरिंग का प्रारंभ मूल रूप से 1972 में जॉन ए. हार्टिगन द्वारा की गई थी।<ref name=Hartigan></ref> बाइक्लस्टरिंग शब्द का उपयोग बाद में बोरिस जी. मिर्किन द्वारा किया गया और परिष्कृत किया गया। इस एल्गोरिदम को 2000 तक सामान्यीकृत नहीं किया गया था, जब वाई. चेंग और जॉर्ज एम. चर्च ने विचरण के आधार पर बाइक्लस्टरिंग एल्गोरिदम का प्रस्ताव रखा और इसे जैविक जीन अभिव्यक्ति डेटा पर प्रयुक्त किया था।<ref>https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Cheng Y, Church G M. Biclustering of expression data[C]//Ismb. 2000, 8: 93–103.</ref> 2001 और 2003 में, आई.एस. ढिल्लों ने फ़ाइलों और शब्दों पर बाइक्लस्टरिंग प्रयुक्त करने वाले दो एल्गोरिदम प्रकाशित किए थे। संस्करण द्विदलीय वर्णक्रमीय ग्राफ़ विभाजन पर आधारित था।<ref>[http://dl.acm.org/citation.cfm?id=502550  Dhillon I S. Co-clustering documents and words using bipartite spectral graph partitioning&#91;C&#93;//Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2001: 269–274.]</ref> दूसरा सूचना सिद्धांत पर आधारित था। ढिल्लों ने माना कि बाइक्लस्टरिंग के समय [[आपसी जानकारी]] का हानि कुल्बैक-लीब्लर विचलन के बराबर था। P और Q के बीच कुल्बैक-लीब्लर-दूरी (केएल-दूरी)। P बाइक्लस्टरिंग से पहले फ़ाइलों और फीचर शब्दों के वितरण का प्रतिनिधित्व करता है, जबकि Q वितरण है बाइक्लस्टरिंग के बाद. केएल-दूरी दो यादृच्छिक वितरणों के बीच अंतर मापने के लिए है। केएल = 0 जब दोनों वितरण समान होते हैं और अंतर बढ़ने पर केएल बढ़ता है।<ref>[http://dl.acm.org/citation.cfm?id=956764 Dhillon I S, Mallela S, Modha D S. Information-theoretic co-clustering&#91;C&#93;//Proceedings of the ninth ACM SIGKDD international conference on KKluwer Academic Publishersnowledge discovery and data mining. ACM, 2003: 89–98.]</ref> इस प्रकार, एल्गोरिदम का उद्देश्य P और Q के बीच न्यूनतम [[केएल-दूरी]] का पता लगाना था। 2004 में, अरिंदम बनर्जी ने बाइक्लस्टरिंग एल्गोरिदम को डिजाइन करने के लिए केएल-दूरी के अतिरिक्त भारित-[[ब्रेगमैन दूरी]] का उपयोग किया जो किसी भी प्रकार के आव्यूह के लिए उपयुक्त था, केएल-दूरी एल्गोरिदम के विपरीत है।<ref>[http://dl.acm.org/citation.cfm?id=1014111 Banerjee A, Dhillon I, Ghosh J, et al. A generalized maximum entropy approach to Bregman co-clustering and matrix approximation&#91;C&#93;//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004: 509–514.]</ref>


दो से अधिक प्रकार की वस्तुओं को क्लस्टर करने के लिए, 2005 में, बेकरमैन ने ढिल्लों के प्रमेय में आपसी जानकारी को जोड़ी से कई जोड़े में विस्तारित किया।<ref>[https://doi.org/10.1145/1102351.1102357 Ron Bekkerman, Ran El-Yaniv, and Andrew McCallum (2005). "Multi-way distributional clustering via pairwise interactions". In ''Proceedings of the 22nd international conference on Machine learning (ICML '05)''. Association for Computing Machinery, 41–48.]</ref>
दो से अधिक प्रकार की वस्तुओं को क्लस्टर करने के लिए, 2005 में, बेकरमैन ने ढिल्लों के प्रमेय में आपसी जानकारी को जोड़ी से कई जोड़े में विस्तारित किया।<ref>[https://doi.org/10.1145/1102351.1102357 Ron Bekkerman, Ran El-Yaniv, and Andrew McCallum (2005). "Multi-way distributional clustering via pairwise interactions". In ''Proceedings of the 22nd international conference on Machine learning (ICML '05)''. Association for Computing Machinery, 41–48.]</ref>
Line 57: Line 57:


== जटिलता ==
== जटिलता ==
बाइक्लस्टरिंग समस्या की जटिलता सटीक समस्या निर्माण पर निर्भर करती है, और विशेष रूप से किसी दिए गए बाइक्लस्टर की गुणवत्ता का मूल्यांकन करने के लिए उपयोग किए जाने वाले योग्यता प्रणाली पर निर्भर करती है। चुकीं, इस समस्या का सबसे दिलचस्प रूप NP-पूर्ण है। NP-पूर्ण की दो शर्तें हैं। साधारण स्थिति में कि केवल एक ही तत्व a<sub>(''i'',''j'')</sub> है बाइनरी मैट्रिक्स a में या तो 0 या 1, बाइक्लस्टर संबंधित [[द्विदलीय ग्राफ]] में बाइक्लीक के बराबर है। अधिकतम आकार बाइक्लुस्टर द्विदलीय ग्राफ में अधिकतम किनारे वाले बाइक्लीक के बराबर है। जटिल स्थितियों में, मैट्रिक्स a में तत्व का उपयोग किसी दिए गए बाइक्लस्टर की गुणवत्ता की गणना करने और समस्या के अधिक प्रतिबंधित संस्करण को हल करने के लिए किया जाता है।<ref>{{cite journal| doi=10.1016/S0166-218X(03)00333-0 | volume=131 | issue=3 | title=अधिकतम एज बाइकलिक समस्या एनपी-पूर्ण है| year=2003 | journal=Discrete Applied Mathematics | pages=651–654 | vauthors=Peeters R| s2cid=3102766 | url=https://pure.uvt.nl/portal/en/publications/the-maximum-edge-biclique-problem-is-npcomplete(5f7679c1-14e1-465d-a2b5-38a01133047f).html | doi-access=free }}</ref> गणना को शॉर्ट-सर्किट करने के लिए या तो बड़े [[कंप्यूटर]] प्रयास या हानिपूर्ण अनुमानों के उपयोग की आवश्यकता होती है।<ref name="madeira-oliveira">
बाइक्लस्टरिंग समस्या की जटिलता सटीक समस्या निर्माण पर निर्भर करती है, और विशेष रूप से किसी दिए गए बाइक्लस्टर की गुणवत्ता का मूल्यांकन करने के लिए उपयोग किए जाने वाले योग्यता प्रणाली पर निर्भर करती है। चूँकि, इस समस्या का सबसे रोचक रूप एनपी-पूर्ण है। एनपी-पूर्ण की दो नियम हैं। साधारण स्थिति में कि केवल एक ही तत्व a<sub>(''i'',''j'')</sub>,बाइनरी आव्यूह a में या तो 0 या 1 है, बाइक्लस्टर संबंधित [[द्विदलीय ग्राफ]] में बाइक्लीक के बराबर है। अधिकतम आकार बाइक्लुस्टर द्विदलीय ग्राफ में अधिकतम किनारे वाले बाइक्लीक के बराबर है। जटिल स्थितियों में, आव्यूह a में तत्व का उपयोग किसी दिए गए बाइक्लस्टर की गुणवत्ता की गणना करने और समस्या के अधिक प्रतिबंधित संस्करण को हल करने के लिए किया जाता है।<ref>{{cite journal| doi=10.1016/S0166-218X(03)00333-0 | volume=131 | issue=3 | title=अधिकतम एज बाइकलिक समस्या एनपी-पूर्ण है| year=2003 | journal=Discrete Applied Mathematics | pages=651–654 | vauthors=Peeters R| s2cid=3102766 | url=https://pure.uvt.nl/portal/en/publications/the-maximum-edge-biclique-problem-is-npcomplete(5f7679c1-14e1-465d-a2b5-38a01133047f).html | doi-access=free }}</ref> गणना को शॉर्ट-सर्किट करने के लिए या तो बड़े [[कंप्यूटर]] प्रयास या हानिपूर्ण अनुमानों के उपयोग की आवश्यकता होती है।<ref name="madeira-oliveira">
{{cite journal |vauthors=Madeira SC, Oliveira AL |year=2004 |title=Biclustering Algorithms for Biological Data Analysis: A Survey |journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics |volume=1 |issue=1 |pages=24–45 |doi=10.1109/TCBB.2004.2 |pmid=17048406 |s2cid=206628783}}
{{cite journal |vauthors=Madeira SC, Oliveira AL |year=2004 |title=Biclustering Algorithms for Biological Data Analysis: A Survey |journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics |volume=1 |issue=1 |pages=24–45 |doi=10.1109/TCBB.2004.2 |pmid=17048406 |s2cid=206628783}}
</ref>
</ref>
Line 63: Line 63:


== बाइकलस्टर के प्रकार ==
== बाइकलस्टर के प्रकार ==
स्थिर मूल्यों के साथ बाइक्लस्टर (a)
'''स्थिर मूल्यों के साथ बाइक्लस्टर (a)'''


जब बाइक्लस्टरिंग एल्गोरिथ्म स्थिर-मूल्य वाले बाइक्लस्टर को खोजने का प्रयास करता है, तो यह मैट्रिक्स की पंक्तियों और स्तंभों को समान पंक्तियों और स्तंभों को साथ समूहित करने के लिए पुन: व्यवस्थित करता है, अंततः समान मूल्यों वाले बाइक्लस्टर्स को समूहीकृत करता है। डेटा सामान्यीकृत होने पर यह विधि पर्याप्त है।
जब बाइक्लस्टरिंग एल्गोरिथ्म स्थिर-मूल्य वाले बाइक्लस्टर को खोजने का प्रयास करता है, तो यह आव्यूह की पंक्तियों और स्तंभों को समान पंक्तियों और स्तंभों को साथ समूहित करने के लिए पुन: व्यवस्थित करता है, अंततः समान मूल्यों वाले बाइक्लस्टर्स को समूहीकृत करता है। डेटा सामान्यीकृत होने पर यह विधि पर्याप्त है। पूर्ण स्थिरांक बाइक्लस्टर आव्यूह (I,J) है। जिसमें सभी मान ''a(i,j)'' दिए गए स्थिरांक μ के बराबर हैं। मूर्त डेटा में, इन प्रविष्टियों ''a(i,j)'' को ''n(i,j) + μ'' के रूप में दर्शाया जा सकता है, जहां ''n(i,j)'' [[शोर में कमी|ध्वनि में कमी]] को दर्शाता है। हार्टिगन के एल्गोरिदम के अनुसार, मूल डेटा आव्यूह को बाइक्लस्टर्स के सेट में विभाजित करके, स्थिर बाइक्लस्टर्स की गणना करने के लिए विचरण का उपयोग किया जाता है। इसलिए, पूर्ण बाइक्लस्टर को शून्य के विचरण वाले आव्यूह के रूप में समान रूप से परिभाषित किया जा सकता है। केवल पंक्ति और कॉलम के साथ डेटा आव्यूह को बाइक्लस्टर्स में विभाजित होने से रोकने के लिए; हार्टिगन का मानना ​​है कि, उदाहरण के लिए, डेटा आव्यूह के अन्दर ''K'' बाइकलस्टर हैं। जब डेटा आव्यूह को ''K'' बाइक्लस्टर्स में विभाजित किया जाता है, तो एल्गोरिदम समाप्त हो जाता है।


पूर्ण स्थिरांक बाइक्लस्टर मैट्रिक्स (I,J) है। जिसमें सभी मान ''a(i,j)'' दिए गए स्थिरांक μ के बराबर हैं। मूर्त डेटा में, इन प्रविष्टियों ''a(i,j)'' को ''n(i,j) + μ'' के रूप में दर्शाया जा सकता है, जहां ''n(i,j)'' [[शोर में कमी]] को दर्शाता है। हार्टिगन के एल्गोरिदम के अनुसार, मूल डेटा मैट्रिक्स को बाइक्लस्टर्स के सेट में विभाजित करके, स्थिर बाइक्लस्टर्स की गणना करने के लिए विचरण का उपयोग किया जाता है। इसलिए, पूर्ण बाइक्लस्टर को शून्य के विचरण वाले मैट्रिक्स के रूप में समान रूप से परिभाषित किया जा सकता है। केवल पंक्ति और कॉलम के साथ डेटा मैट्रिक्स को बाइक्लस्टर्स में विभाजित होने से रोकने के लिए; हार्टिगन का मानना ​​है कि, उदाहरण के लिए, डेटा मैट्रिक्स के भीतर ''K'' बाइकलस्टर हैं। जब डेटा मैट्रिक्स को ''K'' बाइक्लस्टर्स में विभाजित किया जाता है, तो एल्गोरिदम समाप्त हो जाता है।
'''पंक्तियों (b) या कॉलम (c) पर स्थिर मानों वाला बाइक्लस्टर'''


पंक्तियों (b) या कॉलम (c) पर स्थिर मानों वाला बाइक्लस्टर
स्थिर-मूल्य वाले बाइक्लस्टर्स के विपरीत, इस प्रकार के बाइक्लस्टर्स का मूल्यांकन केवल उनके मूल्यों के भिन्नता के आधार पर नहीं किया जा सकता है। पहचान समाप्त करने के लिए, कॉलम और पंक्तियों को पहले सामान्यीकृत किया जाना चाहिए। चूँकि, सामान्यीकरण चरण के बिना, अन्य एल्गोरिदम हैं, जो अलग-अलग विधियों से पंक्तियों और स्तंभों वाले बाइक्लस्टर्स को ढूंढ सकते हैं।


स्थिर-मूल्य वाले बाइक्लस्टर्स के विपरीत, इस प्रकार के बाइक्लस्टर्स का मूल्यांकन केवल उनके मूल्यों के भिन्नता के आधार पर नहीं किया जा सकता है। पहचान समाप्त करने के लिए, कॉलम और पंक्तियों को पहले सामान्यीकृत किया जाना चाहिए। चुकीं, सामान्यीकरण चरण के बिना, अन्य एल्गोरिदम हैं, जो अलग-अलग विधियों से पंक्तियों और स्तंभों वाले बाइक्लस्टर्स को ढूंढ सकते हैं।
'''सुसंगत मूल्यों के साथ बाइक्लस्टर (d, e)'''


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


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


Line 82: Line 81:
|
|
{| | border="1px solid black" cellpadding="5" cellspacing="0"
{| | border="1px solid black" cellpadding="5" cellspacing="0"
|+a) Bicluster with constant values
|+a) स्थिर मूल्यों के साथ बाइक्लस्टर
|-
|-
| 2.0 || 2.0 || 2.0 || 2.0 || 2.0
| 2.0 || 2.0 || 2.0 || 2.0 || 2.0
Line 96: Line 95:
|
|
{| | border="1px solid black" cellpadding="5" cellspacing="0"
{| | border="1px solid black" cellpadding="5" cellspacing="0"
|+b) Bicluster with constant values on rows
|+b) पंक्तियों पर स्थिर मूल्यों के साथ बाइक्लस्टर
|-
|-
| 1.0 || 1.0 || 1.0 || 1.0 || 1.0
| 1.0 || 1.0 || 1.0 || 1.0 || 1.0
Line 110: Line 109:
|
|
{| | border="1px solid black" cellpadding="5" cellspacing="0"
{| | border="1px solid black" cellpadding="5" cellspacing="0"
|+c) Bicluster with constant values on columns
|+c) स्तंभों पर स्थिर मानों वाला बाइक्लस्टर
|-
|-
| 1.0 || 2.0 || 3.0 || 4.0 || 5.0
| 1.0 || 2.0 || 3.0 || 4.0 || 5.0
Line 155: Line 154:
| 5.0 || 2.5 || 10.0 || 1.0 || 4.0
| 5.0 || 2.5 || 10.0 || 1.0 || 4.0
|}
|}




Line 170: Line 172:
  }}
  }}
</ref>
</ref>




Line 221: Line 224:
  | pages = 4302–4304
  | pages = 4302–4304
  | doi = 10.1093/bioinformatics/bty512
  | doi = 10.1093/bioinformatics/bty512
}}</ref> और हाल ही में प्रस्तावित हाइब्रिड विधि ईबीआईसी (विकासवादी-आधारित बाइक्लस्टरिंग),<ref>
}}</ref> और शीघ्र में प्रस्तावित हाइब्रिड विधि ईबीआईसी (विकासवादी-आधारित बाइक्लस्टरिंग),<ref>
{{cite journal
{{cite journal
  | vauthors = Orzechowski P, Sipper M, Huang X, Moore JH
  | vauthors = Orzechowski P, Sipper M, Huang X, Moore JH
Line 234: Line 237:
  | doi = 10.1093/bioinformatics/bty401
  | doi = 10.1093/bioinformatics/bty401
| arxiv = 1801.03039
| arxiv = 1801.03039
  }}</ref> जिसे बहुत अधिक सटीकता के साथ कई पैटर्न का पता लगाने के लिए दिखाया गया था। हाल ही में, आईएमएमडी-सीसी<ref>
  }}</ref> जिसे बहुत अधिक सटीकता के साथ कई पैटर्न का पता लगाने के लिए दिखाया गया था। शीघ्र में, आईएमएमडी-सीसी<ref>
{{cite journal
{{cite journal
  | vauthors = Fanaee-T H, Thoresen, M
  | vauthors = Fanaee-T H, Thoresen, M
Line 252: Line 255:
बाइक्लस्टरिंग एल्गोरिदम को सह-क्लस्टरिंग, द्वि-आयामी क्लस्टरिंग और सबस्पेस क्लस्टरिंग नाम के अंतर्गत अन्य अनुप्रयोग क्षेत्रों में भी प्रस्तावित और उपयोग किया गया है।<ref name="madeira-oliveira" />
बाइक्लस्टरिंग एल्गोरिदम को सह-क्लस्टरिंग, द्वि-आयामी क्लस्टरिंग और सबस्पेस क्लस्टरिंग नाम के अंतर्गत अन्य अनुप्रयोग क्षेत्रों में भी प्रस्तावित और उपयोग किया गया है।<ref name="madeira-oliveira" />


समय-श्रृंखला डेटा में स्थानीय पैटर्न की खोज के ज्ञात महत्व को देखते हुए। हाल के प्रस्तावों ने समय-श्रृंखला जीन अभिव्यक्ति डेटा के विशिष्ट स्थितियों में बाइक्लस्टरिंग समस्या को संबोधित किया है। इस स्थितियों में, दिलचस्प बाइकलस्टर को विकट: सन्निहित कॉलम वाले बाइकक्लस्टर तक ही सीमित किया जा सकता है। यह प्रतिबंध [[सुगम्य समस्या]] की ओर ले जाता है। और सीसीसी-बाइक्लस्टरिंग जैसे कुशल संपूर्ण [[गणना]] एल्गोरिदम के विकास को सक्षम बनाता है।<ref name="ccc-biclustering">
समय-श्रृंखला डेटा में स्थानीय पैटर्न की खोज के ज्ञात महत्व को देखते हुए। हाल के प्रस्तावों ने समय-श्रृंखला जीन अभिव्यक्ति डेटा के विशिष्ट स्थितियों में बाइक्लस्टरिंग समस्या को संबोधित किया है। इस स्थितियों में, रोचक बाइकलस्टर को विकट: सन्निहित कॉलम वाले बाइकक्लस्टर तक ही सीमित किया जा सकता है। यह प्रतिबंध [[सुगम्य समस्या]] की ओर ले जाता है। और सीसीसी-बाइक्लस्टरिंग जैसे कुशल संपूर्ण [[गणना]] एल्गोरिदम के विकास को सक्षम बनाता है।<ref name="ccc-biclustering">
{{cite journal
{{cite journal
  |vauthors=Madeira SC, Teixeira MC, Sá-Correia I, Oliveira AL | year = 2010
  |vauthors=Madeira SC, Teixeira MC, Sá-Correia I, Oliveira AL | year = 2010
Line 276: Line 279:
  | pmc = 2709627
  | pmc = 2709627
  }}
  }}
</ref> सीसीसी-बाइक्लस्टरिंग [[कलन विधि]] में अनुमानित पैटर्न, बाइक्लस्टर में अभिव्यक्ति पैटर्न का प्रतिनिधित्व करने वाले अभिव्यक्ति प्रोफ़ाइल के सापेक्ष, प्रति जीन त्रुटियों की निश्चित संख्या की अनुमति देते हैं। ई-सीसीसी-बाइक्लस्टरिंग एल्गोरिदम विवेकाधीन मैट्रिक्स a और कुशल [[स्ट्रिंग प्रोसेसिंग]] तकनीकों द्वारा सभी अधिकतम सीसीसी-बाइक्लस्टर को खोजने और रिपोर्ट करने के लिए अनुमानित अभिव्यक्तियों का उपयोग करता है।
</ref> सीसीसी-बाइक्लस्टरिंग [[कलन विधि]] में अनुमानित पैटर्न, बाइक्लस्टर में अभिव्यक्ति पैटर्न का प्रतिनिधित्व करने वाले अभिव्यक्ति प्रोफ़ाइल के सापेक्ष, प्रति जीन त्रुटियों की निश्चित संख्या की अनुमति देते हैं। ई-सीसीसी-बाइक्लस्टरिंग एल्गोरिदम विवेकाधीन आव्यूह a और कुशल [[स्ट्रिंग प्रोसेसिंग]] तकनीकों द्वारा सभी अधिकतम सीसीसी-बाइक्लस्टर को खोजने और रिपोर्ट करने के लिए अनुमानित अभिव्यक्तियों का उपयोग करता है।


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


कुछ हालिया एल्गोरिदम ने cMonkey सहित अन्य [[ डेटा प्रकार ]] के रूप में बाइक्लस्टरिंग आयताकार मैट्रिक्स के लिए अतिरिक्त समर्थन सम्मिलित करने का प्रयास किया है।
कुछ हालिया एल्गोरिदम ने cMonkey सहित अन्य [[ डेटा प्रकार |डेटा प्रकार]] के रूप में बाइक्लस्टरिंग आयताकार आव्यूह के लिए अतिरिक्त समर्थन सम्मिलित करने का प्रयास किया है।


इन विधियों के परिणामों का मूल्यांकन कैसे किया जाए, इस पर बहस चल रही है, क्योंकि बाइक्लस्टरिंग समूहों के बीच ओवरलैप की अनुमति देता है और कुछ एल्गोरिदम कठिन-से-समाधान वाले कॉलम/शर्तों को बाहर करने की अनुमति देते हैं। सभी उपलब्ध एल्गोरिदम नियतात्मक नहीं हैं और विश्लेषक को इस बात पर ध्यान देना चाहिए कि परिणाम किस सीमा तक स्थिर [[न्यूनतम]] का प्रतिनिधित्व करते हैं। क्योंकि यह अनियंत्रित वर्गीकरण समस्या है, [[स्वर्ण मानक (परीक्षण)]] की कमी के कारण परिणामों में त्रुटियों को पहचानना कठिन हो जाता है। दृष्टिकोण एकाधिक बाइक्लस्टरिंग एल्गोरिदम का उपयोग करना है, जिसमें सर्वोत्तम परिणाम तय करने के लिए बहुमत या सुपर-बहुमत मतदान होता है। दूसरी विधि बाइक्लस्टर्स में शिफ्टिंग और स्केलिंग पैटर्न की गुणवत्ता का विश्लेषण करना है।<ref>
इन विधियों के परिणामों का मूल्यांकन कैसे किया जाए, इस पर बहस चल रही है, क्योंकि बाइक्लस्टरिंग समूहों के बीच ओवरलैप की अनुमति देता है और कुछ एल्गोरिदम कठिन-से-समाधान वाले कॉलम/नियमों को बाहर करने की अनुमति देते हैं। सभी उपलब्ध एल्गोरिदम नियतात्मक नहीं हैं और विश्लेषक को इस बात पर ध्यान देना चाहिए कि परिणाम किस सीमा तक स्थिर [[न्यूनतम]] का प्रतिनिधित्व करते हैं। क्योंकि यह अनियंत्रित वर्गीकरण समस्या है, [[स्वर्ण मानक (परीक्षण)]] की कमी के कारण परिणामों में त्रुटियों को पहचानना कठिन हो जाता है। दृष्टिकोण एकाधिक बाइक्लस्टरिंग एल्गोरिदम का उपयोग करना है, जिसमें सर्वोत्तम परिणाम तय करने के लिए बहुमत या सुपर-बहुमत मतदान होता है। दूसरी विधि बाइक्लस्टर्स में शिफ्टिंग और स्केलिंग पैटर्न की गुणवत्ता का विश्लेषण करना है।<ref>
{{cite journal
{{cite journal
  | author = Aguilar-Ruiz JS
  | author = Aguilar-Ruiz JS
Line 295: Line 298:
| doi-access = free
| doi-access = free
  }}
  }}
</ref> बाइक्लस्टरिंग का उपयोग [[ टेक्स्ट खनन ]] (या वर्गीकरण) के क्षेत्र में किया गया है जिसे लोकप्रिय रूप से सह-क्लस्टरिंग के रूप में जाना जाता है।<ref name="chi-sim">{{cite book
</ref> बाइक्लस्टरिंग का उपयोग [[ टेक्स्ट खनन |टेक्स्ट खनन]] (या वर्गीकरण) के क्षेत्र में किया गया है जिसे लोकप्रिय रूप से सह-क्लस्टरिंग के रूप में जाना जाता है।<ref name="chi-sim">{{cite book
  |author1=Bisson G.  |author2=Hussain F.
  |author1=Bisson G.  |author2=Hussain F.
   |name-list-style=amp | year = 2008
   |name-list-style=amp | year = 2008
Line 305: Line 308:
   |s2cid=15506600
   |s2cid=15506600
  }}
  }}
</ref> टेक्स्ट कॉर्पोरा को [[वेक्टर (गणित और भौतिकी)]] रूप में मैट्रिक्स (गणित) D के रूप में दर्शाया जाता है, जिनकी पंक्तियाँ दस्तावेज़ों को दर्शाती हैं और जिनके कॉलम शब्दकोश में शब्दों को दर्शाते हैं। मैट्रिक्स तत्व D<sub>ij</sub> दस्तावेज़ i में शब्द j की उपस्थिति को निरूपित करें। फिर [[सह-क्लस्टरिंग]] एल्गोरिदम को D में ब्लॉक खोजने के लिए प्रयुक्त किया जाता है जो शब्दों के समूह (कॉलम) द्वारा विशेषता दस्तावेजों (पंक्तियों) के समूह से मेल खाता है।
</ref> टेक्स्ट कॉर्पोरा को [[वेक्टर (गणित और भौतिकी)]] रूप में आव्यूह (गणित) D के रूप में दर्शाया जाता है, जिनकी पंक्तियाँ दस्तावेज़ों को दर्शाती हैं और जिनके कॉलम शब्दकोश में शब्दों को दर्शाते हैं। आव्यूह तत्व D<sub>ij</sub> दस्तावेज़ i में शब्द j की उपस्थिति को निरूपित करें। फिर [[सह-क्लस्टरिंग]] एल्गोरिदम को D में ब्लॉक खोजने के लिए प्रयुक्त किया जाता है जो शब्दों के समूह (कॉलम) द्वारा विशेषता दस्तावेजों (पंक्तियों) के समूह से मेल खाता है।


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


परिणामी ब्लॉकों की सूचना सामग्री के आधार पर कई दृष्टिकोण प्रस्तावित किए गए हैं: मैट्रिक्स-आधारित दृष्टिकोण जैसे कि एकवचन मूल्य अपघटन और बीवीडी, और ग्राफ़-आधारित दृष्टिकोण [[सूचना-सैद्धांतिक]] एल्गोरिदम पुनरावृत्त रूप से प्रत्येक पंक्ति को दस्तावेजों के समूह और प्रत्येक कॉलम को शब्दों के समूह को निर्दिष्ट करते हैं ताकि पारस्परिक जानकारी अधिकतम हो। मैट्रिक्स-आधारित विधियाँ मैट्रिक्स को ब्लॉकों में विघटित करने पर ध्यान केंद्रित करती हैं जिससे मूल मैट्रिक्स और अपघटन से पुनर्जीवित मैट्रिक्स के बीच त्रुटि कम से कम हो। ग्राफ़-आधारित विधियाँ समूहों के बीच कटौती को कम करती हैं। दस्तावेज़ों के दो समूह दिए गए हैं d<sub>1</sub> और d<sub>2</sub>, कटौती की संख्या को समूह d<sub>1</sub> और d<sub>2</sub> के दस्तावेज़ों में आने वाले शब्दों की संख्या के रूप में मापा जा सकता है
परिणामी ब्लॉकों की सूचना सामग्री के आधार पर कई दृष्टिकोण प्रस्तावित किए गए हैं: आव्यूह-आधारित दृष्टिकोण जैसे कि एकवचन मूल्य अपघटन और बीवीडी, और ग्राफ़-आधारित दृष्टिकोण [[सूचना-सैद्धांतिक]] एल्गोरिदम पुनरावृत्त रूप से प्रत्येक पंक्ति को दस्तावेजों के समूह और प्रत्येक कॉलम को शब्दों के समूह को निर्दिष्ट करते हैं ताकि पारस्परिक जानकारी अधिकतम हो। आव्यूह-आधारित विधियाँ आव्यूह को ब्लॉकों में विघटित करने पर ध्यान केंद्रित करती हैं जिससे मूल आव्यूह और अपघटन से पुनर्जीवित आव्यूह के बीच त्रुटि कम से कम हो। ग्राफ़-आधारित विधियाँ समूहों के बीच कटौती को कम करती हैं। दस्तावेज़ों के दो समूह d<sub>1</sub> और d<sub>2</sub> दिए गए हैं, कटौती की संख्या को समूह d<sub>1</sub> और d<sub>2</sub> के दस्तावेज़ों में आने वाले शब्दों की संख्या के रूप में मापा जा सकता है


अभी हाल ही में (बिसन और हुसैन)<ref name="chi-sim"/> मैट्रिक्स को सह-क्लस्टरिंग सह-क्लस्टर करने के लिए शब्दों के बीच समानता और दस्तावेज़ों के बीच समानता का उपयोग करने का नया दृष्टिकोण प्रस्तावित किया है। उनकी विधि (क्रॉस समानता के लिए χ-सिम के रूप में जानी जाती है) दस्तावेज़-दस्तावेज़ समानता और शब्द-शब्द समानता खोजने और फिर [[पदानुक्रमित क्लस्टरिंग]] जैसे शास्त्रीय क्लस्टरिंग विधियों का उपयोग करने पर आधारित है। पंक्तियों और स्तंभों को वैकल्पिक रूप से स्पष्ट रूप से क्लस्टर करने के अतिरिक्त, वे शब्दों की उच्च-क्रम की घटनाओं पर विचार करते हैं, स्वाभाविक रूप से उन दस्तावेजों को ध्यान में रखते हैं जिनमें वे होते हैं। इस प्रकार, दो शब्दों के बीच समानता की गणना उन दस्तावेजों के आधार पर की जाती है जिनमें वे होते हैं और उन दस्तावेजों के आधार पर भी जिनमें समान शब्द होते हैं। यहां विचार यह है कि एक ही विषय के बारे में दो दस्तावेज़ इसका वर्णन करने के लिए आवश्यक रूप से शब्दों के एक ही सेट का उपयोग नहीं करते हैं, बल्कि शब्दों के उपसमूह और अन्य समान शब्दों का उपयोग करते हैं जो उस विषय की विशेषता हैं। उच्च-क्रम की समानताएं लेने का यह दृष्टिकोण दस्तावेजों और शब्दों की बेहतर क्लस्टरिंग उत्पन्न करने के परिणाम के साथ पूरे कॉर्पस की [[अव्यक्त अर्थ विश्लेषण]] संरचना को ध्यान में रखता है।
अभी शीघ्र में (बिसन और हुसैन)<ref name="chi-sim"/> आव्यूह को सह-क्लस्टरिंग सह-क्लस्टर करने के लिए शब्दों के बीच समानता और दस्तावेज़ों के बीच समानता का उपयोग करने का नया दृष्टिकोण प्रस्तावित किया है। उनकी विधि (क्रॉस समानता के लिए χ-सिम के रूप में जानी जाती है) दस्तावेज़-दस्तावेज़ समानता और शब्द-शब्द समानता खोजने और फिर [[पदानुक्रमित क्लस्टरिंग]] जैसे शास्त्रीय क्लस्टरिंग विधियों का उपयोग करने पर आधारित है। पंक्तियों और स्तंभों को वैकल्पिक रूप से स्पष्ट रूप से क्लस्टर करने के अतिरिक्त, वे शब्दों की उच्च-क्रम की घटनाओं पर विचार करते हैं, स्वाभाविक रूप से उन दस्तावेजों को ध्यान में रखते हैं जिनमें वे होते हैं। इस प्रकार, दो शब्दों के बीच समानता की गणना उन दस्तावेजों के आधार पर की जाती है जिनमें वे होते हैं और उन दस्तावेजों के आधार पर भी जिनमें समान शब्द होते हैं। यहां विचार यह है कि एक ही विषय के बारे में दो दस्तावेज़ इसका वर्णन करने के लिए आवश्यक रूप से शब्दों के एक ही सेट का उपयोग नहीं करते हैं, बल्कि शब्दों के उपसमूह और अन्य समान शब्दों का उपयोग करते हैं जो उस विषय की विशेषता हैं। उच्च-क्रम की समानताएं लेने का यह दृष्टिकोण दस्तावेजों और शब्दों की उत्तम क्लस्टरिंग उत्पन्न करने के परिणाम के साथ पूरे कॉर्पस की [[अव्यक्त अर्थ विश्लेषण]] संरचना को ध्यान में रखता है।


टेक्स्ट डेटाबेस में, किसी दस्तावेज़ द्वारा शब्द d मैट्रिक्स (आकार m गुणा n, m: दस्तावेजों की संख्या, n: शर्तों की संख्या) द्वारा परिभाषित दस्तावेज़ संग्रह के लिए कवर-गुणांक आधारित क्लस्टरिंग पद्धति<ref>
टेक्स्ट डेटाबेस में, किसी दस्तावेज़ द्वारा शब्द d आव्यूह (आकार m गुणा n, m: दस्तावेजों की संख्या, n: नियमों की संख्या) द्वारा परिभाषित दस्तावेज़ संग्रह के लिए कवर-गुणांक आधारित क्लस्टरिंग पद्धति<ref>
{{cite journal
{{cite journal
  |author1=Can, F. |author2=Ozkarahan, E. A. | year = 1990
  |author1=Can, F. |author2=Ozkarahan, E. A. | year = 1990
Line 327: Line 330:
</ref> दोहरे चरण संभाव्यता प्रयोग का उपयोग करके दस्तावेज़ों और शब्दों (शब्दों) दोनों के लिए समान संख्या में क्लस्टर प्राप्त होते हैं। आवरण गुणांक अवधारणा के अनुसार समूहों की संख्या का अनुमान निम्नलिखित सूत्र द्वारा भी लगाया जा सकता है <math>(m \times n) / t</math> जहां t, D में गैर-शून्य प्रविष्टियों की संख्या है। ध्यान दें कि D में प्रत्येक पंक्ति और प्रत्येक कॉलम में कम से कम एक गैर-शून्य तत्व होना चाहिए।
</ref> दोहरे चरण संभाव्यता प्रयोग का उपयोग करके दस्तावेज़ों और शब्दों (शब्दों) दोनों के लिए समान संख्या में क्लस्टर प्राप्त होते हैं। आवरण गुणांक अवधारणा के अनुसार समूहों की संख्या का अनुमान निम्नलिखित सूत्र द्वारा भी लगाया जा सकता है <math>(m \times n) / t</math> जहां t, D में गैर-शून्य प्रविष्टियों की संख्या है। ध्यान दें कि D में प्रत्येक पंक्ति और प्रत्येक कॉलम में कम से कम एक गैर-शून्य तत्व होना चाहिए।


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


== यह भी देखें ==
== यह भी देखें ==
Line 359: Line 362:
*एन.के. वर्मा, एस. बाजपेयी, ए. सिंह, ए. नागरारे, एस. मीना, यान कुई, आईआईटी खड़गपुर भारत में मेडिसिन और जीव विज्ञान में सिस्टम पर अंतर्राष्ट्रीय सम्मेलन में बाइक्लस्टरिंग एल्गोरिदम की तुलना (आईसीएसएमबी 2010), पीपी. 90-97, दिसम्बर 16-18.
*एन.के. वर्मा, एस. बाजपेयी, ए. सिंह, ए. नागरारे, एस. मीना, यान कुई, आईआईटी खड़गपुर भारत में मेडिसिन और जीव विज्ञान में सिस्टम पर अंतर्राष्ट्रीय सम्मेलन में बाइक्लस्टरिंग एल्गोरिदम की तुलना (आईसीएसएमबी 2010), पीपी. 90-97, दिसम्बर 16-18.
* जे. गुप्ता, एस. सिंह और एन.के. वर्मा एमटीबीए: बाइक्लस्टरिंग विश्लेषण के लिए मैटलैब टूलबॉक्स, कम्प्यूटेशनल इंटेलिजेंस पर आईईईई कार्यशाला: सिद्धांत, अनुप्रयोग और भविष्य की दिशाएं, आईआईटी कानपुर भारत, पीपी. 148-152, जुलाई 2013।
* जे. गुप्ता, एस. सिंह और एन.के. वर्मा एमटीबीए: बाइक्लस्टरिंग विश्लेषण के लिए मैटलैब टूलबॉक्स, कम्प्यूटेशनल इंटेलिजेंस पर आईईईई कार्यशाला: सिद्धांत, अनुप्रयोग और भविष्य की दिशाएं, आईआईटी कानपुर भारत, पीपी. 148-152, जुलाई 2013।
*ए तनय. आर. शरण, और आर. शमीर, बाइक्लस्टरिंग एल्गोरिदम: एक सर्वेक्षण, कम्प्यूटेशनल आणविक जीवविज्ञान की हैंडबुक में, [[श्रीनिवास अलुरु]], चैपमैन द्वारा संपादित (2004)
*ए तनय. आर. शरण, और आर. शमीर, बाइक्लस्टरिंग एल्गोरिदम: सर्वेक्षण, कम्प्यूटेशनल आणविक जीवविज्ञान की हैंडबुक में, [[श्रीनिवास अलुरु]], चैपमैन द्वारा संपादित (2004)
* {{cite journal |vauthors=Kluger Y, Basri R, Chang JT, Gerstein MB | year = 2003 | title = माइक्रोएरे डेटा की स्पेक्ट्रल बाइक्लस्टरिंग: सहक्लस्टरिंग जीन और स्थितियाँ| journal = Genome Research | volume = 13 | issue = 4| pages = 703–716 | doi = 10.1101/gr.648603 | pmid = 12671006 | pmc = 430175 }}
* {{cite journal |vauthors=Kluger Y, Basri R, Chang JT, Gerstein MB | year = 2003 | title = माइक्रोएरे डेटा की स्पेक्ट्रल बाइक्लस्टरिंग: सहक्लस्टरिंग जीन और स्थितियाँ| journal = Genome Research | volume = 13 | issue = 4| pages = 703–716 | doi = 10.1101/gr.648603 | pmid = 12671006 | pmc = 430175 }}
* एडेटायो कासिम, ज़िव शकेडी, सेबेस्टियन कैसर, सेप होक्रेइटर, विलेम टालोएन (2016), आर, चैपमैन और हॉल/सीआरसी प्रेस का उपयोग करके बड़े और उच्च-आयामी डेटा के लिए एप्लाइड बाइक्लस्टरिंग तरीके
* एडेटायो कासिम, ज़िव शकेडी, सेबेस्टियन कैसर, सेप होक्रेइटर, विलेम टालोएन (2016), आर, चैपमैन और हॉल/सीआरसी प्रेस का उपयोग करके बड़े और उच्च-आयामी डेटा के लिए एप्लाइड बाइक्लस्टरिंग तरीके
* ऑर्ज़ेचोव्स्की, पी., सिपर, एम., हुआंग, एक्स., और मूर, जे.एच. (2018)। ईबीआईसी: पैटर्न खोज के लिए एक विकासवादी-आधारित समानांतर बाइक्लस्टरिंग एल्गोरिदम। जैव सूचना विज्ञान।
* ऑर्ज़ेचोव्स्की, पी., सिपर, एम., हुआंग, एक्स., और मूर, जे.एच. (2018)। ईबीआईसी: पैटर्न खोज के लिए विकासवादी-आधारित समानांतर बाइक्लस्टरिंग एल्गोरिदम। जैव सूचना विज्ञान।


== बाहरी संबंध ==
== बाहरी संबंध ==
* [http://www.bioinf.jku.at/software/fabia/fabia.html FABIA: Factor Analysis for Bicluster Acquisition, an R package] &mdash;software
* [http://www.bioinf.jku.at/software/fabia/fabia.html FABIA: Factor Analysis for Bicluster Acquisition, an R package] &mdash;software
[[Category: क्लस्टर विश्लेषण]] [[Category: बायोइनफॉरमैटिक्स]]


[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:क्लस्टर विश्लेषण]]
[[Category:बायोइनफॉरमैटिक्स]]

Latest revision as of 13:35, 3 August 2023

बाइक्लस्टरिंग, ब्लॉक क्लस्टरिंग[1][2] सह-क्लस्टरिंग या दो-मोड क्लस्टरिंग[3][4][5] डेटा खनन तकनीक है। जो आव्यूह (गणित) की पंक्तियों और स्तंभों के साथ क्लस्टर विश्लेषण की अनुमति देती है।

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

विकास

बाइक्लस्टरिंग का प्रारंभ मूल रूप से 1972 में जॉन ए. हार्टिगन द्वारा की गई थी।[7] बाइक्लस्टरिंग शब्द का उपयोग बाद में बोरिस जी. मिर्किन द्वारा किया गया और परिष्कृत किया गया। इस एल्गोरिदम को 2000 तक सामान्यीकृत नहीं किया गया था, जब वाई. चेंग और जॉर्ज एम. चर्च ने विचरण के आधार पर बाइक्लस्टरिंग एल्गोरिदम का प्रस्ताव रखा और इसे जैविक जीन अभिव्यक्ति डेटा पर प्रयुक्त किया था।[8] 2001 और 2003 में, आई.एस. ढिल्लों ने फ़ाइलों और शब्दों पर बाइक्लस्टरिंग प्रयुक्त करने वाले दो एल्गोरिदम प्रकाशित किए थे। संस्करण द्विदलीय वर्णक्रमीय ग्राफ़ विभाजन पर आधारित था।[9] दूसरा सूचना सिद्धांत पर आधारित था। ढिल्लों ने माना कि बाइक्लस्टरिंग के समय आपसी जानकारी का हानि कुल्बैक-लीब्लर विचलन के बराबर था। P और Q के बीच कुल्बैक-लीब्लर-दूरी (केएल-दूरी)। P बाइक्लस्टरिंग से पहले फ़ाइलों और फीचर शब्दों के वितरण का प्रतिनिधित्व करता है, जबकि Q वितरण है बाइक्लस्टरिंग के बाद. केएल-दूरी दो यादृच्छिक वितरणों के बीच अंतर मापने के लिए है। केएल = 0 जब दोनों वितरण समान होते हैं और अंतर बढ़ने पर केएल बढ़ता है।[10] इस प्रकार, एल्गोरिदम का उद्देश्य P और Q के बीच न्यूनतम केएल-दूरी का पता लगाना था। 2004 में, अरिंदम बनर्जी ने बाइक्लस्टरिंग एल्गोरिदम को डिजाइन करने के लिए केएल-दूरी के अतिरिक्त भारित-ब्रेगमैन दूरी का उपयोग किया जो किसी भी प्रकार के आव्यूह के लिए उपयुक्त था, केएल-दूरी एल्गोरिदम के विपरीत है।[11]

दो से अधिक प्रकार की वस्तुओं को क्लस्टर करने के लिए, 2005 में, बेकरमैन ने ढिल्लों के प्रमेय में आपसी जानकारी को जोड़ी से कई जोड़े में विस्तारित किया।[12]


जटिलता

बाइक्लस्टरिंग समस्या की जटिलता सटीक समस्या निर्माण पर निर्भर करती है, और विशेष रूप से किसी दिए गए बाइक्लस्टर की गुणवत्ता का मूल्यांकन करने के लिए उपयोग किए जाने वाले योग्यता प्रणाली पर निर्भर करती है। चूँकि, इस समस्या का सबसे रोचक रूप एनपी-पूर्ण है। एनपी-पूर्ण की दो नियम हैं। साधारण स्थिति में कि केवल एक ही तत्व a(i,j),बाइनरी आव्यूह a में या तो 0 या 1 है, बाइक्लस्टर संबंधित द्विदलीय ग्राफ में बाइक्लीक के बराबर है। अधिकतम आकार बाइक्लुस्टर द्विदलीय ग्राफ में अधिकतम किनारे वाले बाइक्लीक के बराबर है। जटिल स्थितियों में, आव्यूह a में तत्व का उपयोग किसी दिए गए बाइक्लस्टर की गुणवत्ता की गणना करने और समस्या के अधिक प्रतिबंधित संस्करण को हल करने के लिए किया जाता है।[13] गणना को शॉर्ट-सर्किट करने के लिए या तो बड़े कंप्यूटर प्रयास या हानिपूर्ण अनुमानों के उपयोग की आवश्यकता होती है।[14]


बाइकलस्टर के प्रकार

स्थिर मूल्यों के साथ बाइक्लस्टर (a)

जब बाइक्लस्टरिंग एल्गोरिथ्म स्थिर-मूल्य वाले बाइक्लस्टर को खोजने का प्रयास करता है, तो यह आव्यूह की पंक्तियों और स्तंभों को समान पंक्तियों और स्तंभों को साथ समूहित करने के लिए पुन: व्यवस्थित करता है, अंततः समान मूल्यों वाले बाइक्लस्टर्स को समूहीकृत करता है। डेटा सामान्यीकृत होने पर यह विधि पर्याप्त है। पूर्ण स्थिरांक बाइक्लस्टर आव्यूह (I,J) है। जिसमें सभी मान a(i,j) दिए गए स्थिरांक μ के बराबर हैं। मूर्त डेटा में, इन प्रविष्टियों a(i,j) को n(i,j) + μ के रूप में दर्शाया जा सकता है, जहां n(i,j) ध्वनि में कमी को दर्शाता है। हार्टिगन के एल्गोरिदम के अनुसार, मूल डेटा आव्यूह को बाइक्लस्टर्स के सेट में विभाजित करके, स्थिर बाइक्लस्टर्स की गणना करने के लिए विचरण का उपयोग किया जाता है। इसलिए, पूर्ण बाइक्लस्टर को शून्य के विचरण वाले आव्यूह के रूप में समान रूप से परिभाषित किया जा सकता है। केवल पंक्ति और कॉलम के साथ डेटा आव्यूह को बाइक्लस्टर्स में विभाजित होने से रोकने के लिए; हार्टिगन का मानना ​​है कि, उदाहरण के लिए, डेटा आव्यूह के अन्दर K बाइकलस्टर हैं। जब डेटा आव्यूह को K बाइक्लस्टर्स में विभाजित किया जाता है, तो एल्गोरिदम समाप्त हो जाता है।

पंक्तियों (b) या कॉलम (c) पर स्थिर मानों वाला बाइक्लस्टर

स्थिर-मूल्य वाले बाइक्लस्टर्स के विपरीत, इस प्रकार के बाइक्लस्टर्स का मूल्यांकन केवल उनके मूल्यों के भिन्नता के आधार पर नहीं किया जा सकता है। पहचान समाप्त करने के लिए, कॉलम और पंक्तियों को पहले सामान्यीकृत किया जाना चाहिए। चूँकि, सामान्यीकरण चरण के बिना, अन्य एल्गोरिदम हैं, जो अलग-अलग विधियों से पंक्तियों और स्तंभों वाले बाइक्लस्टर्स को ढूंढ सकते हैं।

सुसंगत मूल्यों के साथ बाइक्लस्टर (d, e)

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



a) स्थिर मूल्यों के साथ बाइक्लस्टर
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
b) पंक्तियों पर स्थिर मूल्यों के साथ बाइक्लस्टर
1.0 1.0 1.0 1.0 1.0
2.0 2.0 2.0 2.0 2.0
3.0 3.0 3.0 3.0 3.0
4.0 4.0 4.0 4.0 4.0
5.0 5.0 5.0 5.0 5.0
c) स्तंभों पर स्थिर मानों वाला बाइक्लस्टर
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0



d) सुसंगत मूल्यों के साथ बाइक्लस्टर (एडिटिव)
1.0 4.0 5.0 0.0 1.5
4.0 7.0 8.0 3.0 4.5
3.0 6.0 7.0 2.0 3.5
5.0 8.0 9.0 4.0 5.5
2.0 5.0 6.0 1.0 2.5
e) सुसंगत मूल्यों के साथ बाइक्लस्टर (गुणात्मक)
1.0 0.5 2.0 0.2 0.8
2.0 1.0 4.0 0.4 1.6
3.0 1.5 6.0 0.6 2.4
4.0 2.0 8.0 0.8 3.2
5.0 2.5 10.0 1.0 4.0



इन क्लस्टर मॉडल और अन्य प्रकार की क्लस्टरिंग जैसे सहसंबंध क्लस्टरिंग के बीच संबंध पर चर्चा की गई है।[15]


एल्गोरिदम

जैव सूचना विज्ञान के लिए कई बाइक्लस्टरिंग एल्गोरिदम विकसित किए गए हैं, जिनमें सम्मिलित हैं: ब्लॉक क्लस्टरिंग, सीटीडब्ल्यूसी (कपल्ड टू-वे क्लस्टरिंग), आईटीडब्ल्यूसी (इंटररिलेटेड टू-वे क्लस्टरिंग), δ-बाइकलस्टर, δ-पीक्लस्टर, δ-पैटर्न, एफएलओसी, ओपीसी, प्लेड मॉडल , ओपीएसएम (ऑर्डर-प्रिजर्विंग सबमैट्रिक्स), गिब्स, एसएएमबीए (बाइक्लस्टर विश्लेषण के लिए सांख्यिकीय-एल्गोरिदमिक विधि),[16] मजबूत बाइक्लस्टरिंग एल्गोरिदम (आरओबीए), क्रॉसिंग मिनिमाइजेशन[17] सीमंकी[18] पीआरएम, डीसीसी, एलईबी (स्थानीयकरण और बाइकलस्टर निकालें), क्यूबिक (गुणात्मक बाइकलस्टरिंग), बीसीसीए (द्वि-सहसंबंध क्लस्टरिंग एल्गोरिदम) बीआईमैक्स, आईएसए और एफएबीआईए (बाइकलस्टर अधिग्रहण के लिए कारक विश्लेषण)[19] रुनिबिक[20] और शीघ्र में प्रस्तावित हाइब्रिड विधि ईबीआईसी (विकासवादी-आधारित बाइक्लस्टरिंग),[21] जिसे बहुत अधिक सटीकता के साथ कई पैटर्न का पता लगाने के लिए दिखाया गया था। शीघ्र में, आईएमएमडी-सीसी[22] प्रस्तावित है कि इसे पुनरावृत्तीय जटिलता न्यूनीकरण अवधारणा के आधार पर विकसित किया गया है। आईएमएमडी-सीसी पुनरावृत्त मल्टी-मोड विवेकीकरण द्वारा प्राप्त अत्यधिक विरल परिवर्तन से सह-क्लस्टर सेंट्रोइड की पहचान करने में सक्षम है।

बाइक्लस्टरिंग एल्गोरिदम को सह-क्लस्टरिंग, द्वि-आयामी क्लस्टरिंग और सबस्पेस क्लस्टरिंग नाम के अंतर्गत अन्य अनुप्रयोग क्षेत्रों में भी प्रस्तावित और उपयोग किया गया है।[14]

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

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

कुछ हालिया एल्गोरिदम ने cMonkey सहित अन्य डेटा प्रकार के रूप में बाइक्लस्टरिंग आयताकार आव्यूह के लिए अतिरिक्त समर्थन सम्मिलित करने का प्रयास किया है।

इन विधियों के परिणामों का मूल्यांकन कैसे किया जाए, इस पर बहस चल रही है, क्योंकि बाइक्लस्टरिंग समूहों के बीच ओवरलैप की अनुमति देता है और कुछ एल्गोरिदम कठिन-से-समाधान वाले कॉलम/नियमों को बाहर करने की अनुमति देते हैं। सभी उपलब्ध एल्गोरिदम नियतात्मक नहीं हैं और विश्लेषक को इस बात पर ध्यान देना चाहिए कि परिणाम किस सीमा तक स्थिर न्यूनतम का प्रतिनिधित्व करते हैं। क्योंकि यह अनियंत्रित वर्गीकरण समस्या है, स्वर्ण मानक (परीक्षण) की कमी के कारण परिणामों में त्रुटियों को पहचानना कठिन हो जाता है। दृष्टिकोण एकाधिक बाइक्लस्टरिंग एल्गोरिदम का उपयोग करना है, जिसमें सर्वोत्तम परिणाम तय करने के लिए बहुमत या सुपर-बहुमत मतदान होता है। दूसरी विधि बाइक्लस्टर्स में शिफ्टिंग और स्केलिंग पैटर्न की गुणवत्ता का विश्लेषण करना है।[25] बाइक्लस्टरिंग का उपयोग टेक्स्ट खनन (या वर्गीकरण) के क्षेत्र में किया गया है जिसे लोकप्रिय रूप से सह-क्लस्टरिंग के रूप में जाना जाता है।[26] टेक्स्ट कॉर्पोरा को वेक्टर (गणित और भौतिकी) रूप में आव्यूह (गणित) D के रूप में दर्शाया जाता है, जिनकी पंक्तियाँ दस्तावेज़ों को दर्शाती हैं और जिनके कॉलम शब्दकोश में शब्दों को दर्शाते हैं। आव्यूह तत्व Dij दस्तावेज़ i में शब्द j की उपस्थिति को निरूपित करें। फिर सह-क्लस्टरिंग एल्गोरिदम को D में ब्लॉक खोजने के लिए प्रयुक्त किया जाता है जो शब्दों के समूह (कॉलम) द्वारा विशेषता दस्तावेजों (पंक्तियों) के समूह से मेल खाता है।

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

परिणामी ब्लॉकों की सूचना सामग्री के आधार पर कई दृष्टिकोण प्रस्तावित किए गए हैं: आव्यूह-आधारित दृष्टिकोण जैसे कि एकवचन मूल्य अपघटन और बीवीडी, और ग्राफ़-आधारित दृष्टिकोण सूचना-सैद्धांतिक एल्गोरिदम पुनरावृत्त रूप से प्रत्येक पंक्ति को दस्तावेजों के समूह और प्रत्येक कॉलम को शब्दों के समूह को निर्दिष्ट करते हैं ताकि पारस्परिक जानकारी अधिकतम हो। आव्यूह-आधारित विधियाँ आव्यूह को ब्लॉकों में विघटित करने पर ध्यान केंद्रित करती हैं जिससे मूल आव्यूह और अपघटन से पुनर्जीवित आव्यूह के बीच त्रुटि कम से कम हो। ग्राफ़-आधारित विधियाँ समूहों के बीच कटौती को कम करती हैं। दस्तावेज़ों के दो समूह d1 और d2 दिए गए हैं, कटौती की संख्या को समूह d1 और d2 के दस्तावेज़ों में आने वाले शब्दों की संख्या के रूप में मापा जा सकता है

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

टेक्स्ट डेटाबेस में, किसी दस्तावेज़ द्वारा शब्द d आव्यूह (आकार m गुणा n, m: दस्तावेजों की संख्या, n: नियमों की संख्या) द्वारा परिभाषित दस्तावेज़ संग्रह के लिए कवर-गुणांक आधारित क्लस्टरिंग पद्धति[27] दोहरे चरण संभाव्यता प्रयोग का उपयोग करके दस्तावेज़ों और शब्दों (शब्दों) दोनों के लिए समान संख्या में क्लस्टर प्राप्त होते हैं। आवरण गुणांक अवधारणा के अनुसार समूहों की संख्या का अनुमान निम्नलिखित सूत्र द्वारा भी लगाया जा सकता है जहां t, D में गैर-शून्य प्रविष्टियों की संख्या है। ध्यान दें कि D में प्रत्येक पंक्ति और प्रत्येक कॉलम में कम से कम एक गैर-शून्य तत्व होना चाहिए।

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

यह भी देखें

संदर्भ

  1. ↑ G. Govaert; M. Nadif (2008). "Block clustering with bernoulli mixture models: Comparison of different approaches". Computational Statistics and Data Analysis. 52 (6): 3233–3245. doi:10.1016/j.csda.2007.09.007.
  2. ↑ R. Balamurugan; A.M. Natarajan; K. Premalatha (2015). "Stellar-Mass Black Hole Optimization for Biclustering Microarray Gene Expression Data". Applied Artificial Intelligence. 29 (4): 353–381. doi:10.1080/08839514.2015.1016391. S2CID 44624424.
  3. ↑ G. Govaert; M. Nadif (2013). Co-clustering: models, algorithms and applications. ISTE, Wiley. ISBN 978-1-84821-473-6.
  4. ↑ R. Balamurugan; A.M. Natarajan; K. Premalatha (2016). "A Modified Harmony Search Method for Biclustering Microarray Gene Expression Data". International Journal of Data Mining and Bioinformatics. 16 (4): 269–289. doi:10.1504/IJDMB.2016.082205.
  5. ↑ Van Mechelen I, Bock HH, De Boeck P (2004). "Two-mode clustering methods:a structured overview". Statistical Methods in Medical Research. 13 (5): 363–94. CiteSeerX 10.1.1.706.4201. doi:10.1191/0962280204sm373ra. PMID 15516031. S2CID 19058237.
  6. ↑ 6.0 6.1 Mirkin, Boris (1996). गणितीय वर्गीकरण और क्लस्टरिंग. Kluwer Academic Publishers. ISBN 978-0-7923-4159-8.
  7. ↑ 7.0 7.1 Hartigan JA (1972). "डेटा मैट्रिक्स की प्रत्यक्ष क्लस्टरिंग". Journal of the American Statistical Association. 67 (337): 123–9. doi:10.2307/2284710. JSTOR 2284710.
  8. ↑ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Cheng Y, Church G M. Biclustering of expression data[C]//Ismb. 2000, 8: 93–103.
  9. ↑ Dhillon I S. Co-clustering documents and words using bipartite spectral graph partitioning[C]//Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2001: 269–274.
  10. ↑ Dhillon I S, Mallela S, Modha D S. Information-theoretic co-clustering[C]//Proceedings of the ninth ACM SIGKDD international conference on KKluwer Academic Publishersnowledge discovery and data mining. ACM, 2003: 89–98.
  11. ↑ Banerjee A, Dhillon I, Ghosh J, et al. A generalized maximum entropy approach to Bregman co-clustering and matrix approximation[C]//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004: 509–514.
  12. ↑ Ron Bekkerman, Ran El-Yaniv, and Andrew McCallum (2005). "Multi-way distributional clustering via pairwise interactions". In Proceedings of the 22nd international conference on Machine learning (ICML '05). Association for Computing Machinery, 41–48.
  13. ↑ Peeters R (2003). "अधिकतम एज बाइकलिक समस्या एनपी-पूर्ण है". Discrete Applied Mathematics. 131 (3): 651–654. doi:10.1016/S0166-218X(03)00333-0. S2CID 3102766.
  14. ↑ 14.0 14.1 Madeira SC, Oliveira AL (2004). "Biclustering Algorithms for Biological Data Analysis: A Survey". IEEE/ACM Transactions on Computational Biology and Bioinformatics. 1 (1): 24–45. doi:10.1109/TCBB.2004.2. PMID 17048406. S2CID 206628783.
  15. ↑ Kriegel, H.-P.; Kröger, P.; Zimek, A. (March 2009). "Clustering High Dimensional Data: A Survey on Subspace Clustering, Pattern-based Clustering, and Correlation Clustering". ACM Transactions on Knowledge Discovery from Data. 3 (1): 1–58. doi:10.1145/1497577.1497578. S2CID 17363900.
  16. ↑ Tanay A, Sharan R, Kupiec M, Shamir R (2004). "Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data". Proc Natl Acad Sci USA. 101 (9): 2981–2986. Bibcode:2004PNAS..101.2981T. doi:10.1073/pnas.0308661100. PMC 365731. PMID 14973197.
  17. ↑ Abdullah, Ahsan; Hussain, Amir (2006). "A new biclustering technique based on crossing minimization". Neurocomputing. 69 (16–18): 1882–1896. doi:10.1016/j.neucom.2006.02.018.
  18. ↑ Reiss DJ, Baliga NS, Bonneau R (2006). "Integrated biclustering of heterogeneous genome-wide datasets for the inference of global regulatory networks". BMC Bioinformatics. 7: 280–302. doi:10.1186/1471-2105-7-280. PMC 1502140. PMID 16749936.
  19. ↑ Hochreiter S, Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, Gohlmann HWH, Shkedy Z, Clevert DA (2010). "FABIA: factor analysis for bicluster acquisition". Bioinformatics. 26 (12): 1520–1527. doi:10.1093/bioinformatics/btq227. PMC 2881408. PMID 20418340.
  20. ↑ Orzechowski P, Pańszczyk A, Huang X, Moore JH (2018). "runibic: a Bioconductor package for parallel row-based biclustering of gene expression data". Bioinformatics. 34 (24): 4302–4304. doi:10.1093/bioinformatics/bty512. PMC 6289127. PMID 29939213.
  21. ↑ Orzechowski P, Sipper M, Huang X, Moore JH (2018). "EBIC: an evolutionary-based parallel biclustering algorithm for pattern discovery". Bioinformatics. 34 (21): 3719–3726. arXiv:1801.03039. doi:10.1093/bioinformatics/bty401. PMC 6198864. PMID 29790909.
  22. ↑ Fanaee-T H, Thoresen, M (2020). "Iterative Multi-mode Discretization: Applications to Co-clustering". Lecture Notes in Computer Science. 12323: 94–105. doi:10.1007/978-3-030-61527-7_7. hdl:10852/82994. ISBN 978-3-030-61526-0. S2CID 222832035.
  23. ↑ Madeira SC, Teixeira MC, Sá-Correia I, Oliveira AL (2010). "Identification of Regulatory Modules in Time Series Gene Expression Data using a Linear Time Biclustering Algorithm". IEEE/ACM Transactions on Computational Biology and Bioinformatics. 1 (7): 153–165. doi:10.1109/TCBB.2008.34. PMID 20150677. S2CID 7369531.
  24. ↑ Madeira SC, Oliveira AL (2009). "A polynomial time biclustering algorithm for finding approximate expression patterns in gene expression time series". Algorithms for Molecular Biology. 4 (8): 8. doi:10.1186/1748-7188-4-8. PMC 2709627. PMID 19497096.
  25. ↑ Aguilar-Ruiz JS (2005). "Shifting and scaling patterns from gene expression data". Bioinformatics. 21 (10): 3840–3845. doi:10.1093/bioinformatics/bti641. PMID 16144809.
  26. ↑ 26.0 26.1 Bisson G. & Hussain F. (2008). Chi-Sim: A new similarity measure for the co-clustering task. pp. 211–217. doi:10.1109/ICMLA.2008.103. ISBN 978-0-7695-3495-4. S2CID 15506600. {{cite book}}: |journal= ignored (help)
  27. ↑ Can, F.; Ozkarahan, E. A. (1990). "Concepts and effectiveness of the cover coefficient based clustering methodology for text databases" (PDF). ACM Transactions on Database Systems. 15 (4): 483–517. doi:10.1145/99935.99938. hdl:2374.MIA/246. S2CID 14309214.



अन्य

  • एन.के. वर्मा, एस. बाजपेयी, ए. सिंह, ए. नागरारे, एस. मीना, यान कुई, आईआईटी खड़गपुर भारत में मेडिसिन और जीव विज्ञान में सिस्टम पर अंतर्राष्ट्रीय सम्मेलन में बाइक्लस्टरिंग एल्गोरिदम की तुलना (आईसीएसएमबी 2010), पीपी. 90-97, दिसम्बर 16-18.
  • जे. गुप्ता, एस. सिंह और एन.के. वर्मा एमटीबीए: बाइक्लस्टरिंग विश्लेषण के लिए मैटलैब टूलबॉक्स, कम्प्यूटेशनल इंटेलिजेंस पर आईईईई कार्यशाला: सिद्धांत, अनुप्रयोग और भविष्य की दिशाएं, आईआईटी कानपुर भारत, पीपी. 148-152, जुलाई 2013।
  • ए तनय. आर. शरण, और आर. शमीर, बाइक्लस्टरिंग एल्गोरिदम: सर्वेक्षण, कम्प्यूटेशनल आणविक जीवविज्ञान की हैंडबुक में, श्रीनिवास अलुरु, चैपमैन द्वारा संपादित (2004)
  • Kluger Y, Basri R, Chang JT, Gerstein MB (2003). "माइक्रोएरे डेटा की स्पेक्ट्रल बाइक्लस्टरिंग: सहक्लस्टरिंग जीन और स्थितियाँ". Genome Research. 13 (4): 703–716. doi:10.1101/gr.648603. PMC 430175. PMID 12671006.
  • एडेटायो कासिम, ज़िव शकेडी, सेबेस्टियन कैसर, सेप होक्रेइटर, विलेम टालोएन (2016), आर, चैपमैन और हॉल/सीआरसी प्रेस का उपयोग करके बड़े और उच्च-आयामी डेटा के लिए एप्लाइड बाइक्लस्टरिंग तरीके
  • ऑर्ज़ेचोव्स्की, पी., सिपर, एम., हुआंग, एक्स., और मूर, जे.एच. (2018)। ईबीआईसी: पैटर्न खोज के लिए विकासवादी-आधारित समानांतर बाइक्लस्टरिंग एल्गोरिदम। जैव सूचना विज्ञान।

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बाइक्लस्टरिंग&oldid=235799’