बाइक्लस्टरिंग
बाइक्लस्टरिंग, ब्लॉक क्लस्टरिंग[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)
पंक्तियों और स्तंभों पर सुसंगत मूल्यों वाले बाइक्लस्टर्स के लिए, पंक्तियों या स्तंभों पर स्थिर मूल्यों वाले बाइक्लस्टर्स के लिए एल्गोरिदम पर समग्र संशोधन पर विचार किया जाना चाहिए। इस एल्गोरिदम में पंक्तियों और स्तंभों दोनों के बीच सह-विचरण का उपयोग करके समूहों के बीच भिन्नता का विश्लेषण हो सकता है। चेंग और चर्च के प्रमेय में बाइक्लस्टर को लगभग समान स्कोर वाली पंक्तियों और स्तंभों के सबसेट के रूप में परिभाषित किया गया है। समानता स्कोर का उपयोग पंक्तियों और स्तंभों की सुसंगतता को मापने के लिए किया जाता है।
|
|
|
| 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 |
| 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 में प्रत्येक पंक्ति और प्रत्येक कॉलम में कम से कम एक गैर-शून्य तत्व होना चाहिए।
अन्य दृष्टिकोणों के विपरीत, एफएबीआईए गुणक मॉडल है जो हेवी-टेल्ड वितरण के साथ यथार्थवादी गैर-गॉसियनिटी संकेत वितरण मानता है। एफएबीआईए परिवर्तनशील दृष्टिकोण जैसी अच्छी तरह से समझी गई मॉडल चयन तकनीकों का उपयोग करता है और बायेसियन संभाव्यता फ्रेमवर्क को प्रयुक्त करता है। जेनरेटिव फ्रेमवर्क एफएबीआईए को काल्पनिक बाइक्लस्टर्स को वास्तविक बाइक्लस्टर्स से अलग करने के लिए प्रत्येक बाइक्लस्टर की सूचना सामग्री निर्धारित करने की अनुमति देता है।
यह भी देखें
संदर्भ
- ↑ 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.
- ↑ 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.
- ↑ G. Govaert; M. Nadif (2013). Co-clustering: models, algorithms and applications. ISTE, Wiley. ISBN 978-1-84821-473-6.
- ↑ 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.
- ↑ 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.0 6.1 Mirkin, Boris (1996). गणितीय वर्गीकरण और क्लस्टरिंग. Kluwer Academic Publishers. ISBN 978-0-7923-4159-8.