Mining maximal high occupancy itemsets with a size-coupled upper bound

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

चुनौती तब उत्पन्न होती है जब डेटा इतना समृद्ध होता है कि वस्तुओं के संभावित समूहों की संख्या अत्यधिक हो जाती है। एक "उच्च ऑक्यूपेंसी" (high occupancy) समूह को परिभाषित करने की सख्त परिभाषा के बावजूद, उम्मीदवारों की सूची लाखों आइटम लंबी हो सकती है, जिससे वास्तव में महत्वपूर्ण पैटर्न खोजने के लिए किसी मानव या कंप्यूटर के लिए उन सभी को छानना असंभव हो जाता है। शोधकर्ताओं को शोर को काटकर केवल सबसे महत्वपूर्ण समूहों को खोजने के तरीके की आवश्यकता थी—वस्तुओं के सबसे बड़े संभव सेट जो अभी भी अपने लेनदेन पर हावी हों। यह वह समस्या है जिसे स्वतंत्र शोधकर्ता क्वान वैन (Quan Van) द्वारा हल किया गया है, जिन्होंने डेटा की विशाल मात्रा में खोए बिना इन 'मैक्सिमल' (maximal) समूहों को खोजने के लिए एक नई विधि विकसित की है।

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

इस चुनौती से निपटने के लिए, वैन ने MHOI-Miner नामक एक नया एल्गोरिदम डिज़ाइन किया। हर एक संभावित समूह को सूचीबद्ध करने और फिर छोटे समूहों को फ़िल्टर करने के बजाय, यह एल्गोरिदम सीधे सबसे बड़े समूहों की तलाश करने के लिए बनाया गया है। यह एक चतुर गणितीय शॉर्टकट, या "अपर बाउंड" (upper bound) का उपयोग करके करता है, जो एक समूह के पूरी तरह से बनने से पहले ही उसकी क्षमता का अनुमान लगा लेता है। एक हाइकर (पर्वतारोही) की कल्पना करें जो कोहरे से भरे पर्वत श्रृंखला में सबसे ऊँची चोटी खोजने की कोशिश कर रहा है। एक मानक दृष्टिकोण हर पहाड़ी पर चढ़ने और उसकी ऊंचाई मापने का होगा, और अंत में कम ऊँची पहाड़ियों को त्याग देने का होगा। वैन की विधि एक मानचित्र की तरह है जो हाइकर को बताता है, "यदि आप इस विशिष्ट रास्ते पर ऊपर जाते हैं, तो आप अधिकतम कितनी ऊँचाई तक पहुँच सकते हैं, वह उस शिखर से कम है जिसे आप पहले से ही देख रहे हैं।" यह एल्गोरिदम को तुरंत उस रास्ते की खोज बंद करने की अनुमति देता है, जिससे समय और कंप्यूटर मेमोरी की भारी बचत होती है।

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

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

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

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