frequent pattern growth algorithm data mining
फ़्रीक्वेंट पैटर्न ग्रोथ एल्गोरिथ्म पर विस्तृत ट्यूटोरियल जो फॉर्म द एफपी ट्री में डेटाबेस का प्रतिनिधित्व करता है। एफपी ग्रोथ बनाम एप्रीओरी तुलना शामिल है:
एपोरिरी एलगोरिदम हमारे पिछले ट्यूटोरियल में विस्तार से बताया गया था। इस ट्यूटोरियल में, हम फ़्रीक्वेंट पैटर्न ग्रोथ के बारे में जानेंगे - एफपी ग्रोथ लगातार आइटम्स को माइन करने का एक तरीका है।
कैसे एक धार फ़ाइल चलाने के लिए
जैसा कि हम सभी जानते हैं, एप्रीओरी लगातार पैटर्न खनन के लिए एक एल्गोरिथ्म है जो आइटम बनाने और सबसे लगातार आइटम की खोज पर केंद्रित है। यह डेटाबेस में आइटम के आकार को बहुत कम कर देता है, हालांकि, अप्रीरी की अपनी कमियां भी हैं।
हमारे माध्यम से पढ़ें संपूर्ण डेटा खनन प्रशिक्षण श्रृंखला अवधारणा की पूरी जानकारी के लिए।
आप क्या सीखेंगे:
- Apriori एल्गोरिथम की कमियों
- बार-बार पैटर्न का विकास एल्गोरिथम
- एफपी ट्री
- बार-बार पैटर्न एल्गोरिथ्म कदम
- एफपी-ग्रोथ एलगोरिदम का उदाहरण
- FP ग्रोथ एलगोरिदम के लाभ
- FP-Growth Algorithm के नुकसान
- एफपी ग्रोथ बनाम अप्रीरी
- चमक
- निष्कर्ष
- अनुशंसित पाठ
Apriori एल्गोरिथम की कमियों
- Apriori का उपयोग करने के लिए उम्मीदवार आइटम की एक पीढ़ी की जरूरत है। डेटाबेस में आइटमसेट विशाल होने पर ये आइटम संख्या में बड़े हो सकते हैं।
- एप्रीओरी को उत्पन्न होने वाले प्रत्येक आइटम के समर्थन की जांच करने के लिए डेटाबेस के कई स्कैन की आवश्यकता होती है और इससे उच्च लागत होती है।
एफपी ग्रोथ एल्गोरिथम का उपयोग करके इन कमियों को दूर किया जा सकता है।
बार-बार पैटर्न का विकास एल्गोरिथम
यह एल्गोरिथ्म Apriori विधि में सुधार है। उम्मीदवार पीढ़ी की आवश्यकता के बिना एक लगातार पैटर्न उत्पन्न होता है। FP वृद्धि एल्गोरिथ्म डेटाबेस का प्रतिनिधित्व एक वृक्ष के रूप में करता है जिसे अक्सर प्रतिरूप वृक्ष या FP वृक्ष कहा जाता है।
यह पेड़ संरचना आइटमसेट्स के बीच संबंध बनाए रखेगी। डेटाबेस को एक लगातार आइटम का उपयोग करके खंडित किया जाता है। इस खंडित भाग को 'पैटर्न टुकड़ा' कहा जाता है। इन खंडित प्रतिमानों के मदों का विश्लेषण किया जाता है। इस प्रकार इस पद्धति के साथ, लगातार आइटमसेट की खोज तुलनात्मक रूप से कम हो जाती है।
एफपी ट्री
फ़्रीक्वेंट पैटर्न ट्री एक ट्री जैसी संरचना है जो डेटाबेस के शुरुआती आइटमों के साथ बनाई जाती है। एफपी पेड़ का उद्देश्य सबसे लगातार पैटर्न मेरा है। एफपी ट्री के प्रत्येक नोड आइटम के एक आइटम का प्रतिनिधित्व करता है।
रूट नोड अशक्त का प्रतिनिधित्व करता है जबकि निचला नोड आइटमसेट का प्रतिनिधित्व करता है। निचले नोड्स के साथ नोड्स का जुड़ाव है जो अन्य आइटमों के साथ आइटम हैं पेड़ को बनाते समय बनाए रखा जाता है।
बार-बार पैटर्न एल्गोरिथ्म कदम
लगातार प्रतिमान वृद्धि विधि हमें उम्मीदवार पीढ़ी के बिना अक्सर प्रतिमान खोजने की सुविधा देती है।
आइए हम बार-बार पैटर्न विकास एल्गोरिथ्म का उपयोग करते हुए बार-बार मेरा अनुसरण करने वाले चरणों को देखें:
# 1) पहला कदम डेटाबेस में आइटमों की घटनाओं को खोजने के लिए डेटाबेस को स्कैन करना है। यह कदम Apriori के पहले चरण के समान है। डेटाबेस में 1-आइटम की गिनती को 1-आइटम की समर्थन गणना या आवृत्ति कहा जाता है।
#दो) दूसरा चरण एफपी पेड़ का निर्माण करना है। इसके लिए पेड़ की जड़ बनाएं। जड़ को अशक्त द्वारा दर्शाया गया है।
# 3) अगला कदम डेटाबेस को फिर से स्कैन करना और लेनदेन की जांच करना है। पहले लेन-देन की जांच करें और इसमें आइटमसेट का पता लगाएं। अधिकतम गिनती वाला आइटमसेट सबसे ऊपर लिया जाता है, अगला आइटम कम गिनती के साथ और इसी तरह। इसका अर्थ है कि पेड़ की शाखा का निर्माण गिनती के क्रम में लेनदेन के सामान के साथ किया जाता है।
# 4) डेटाबेस में अगले लेनदेन की जांच की जाती है। आइटम को गिनती के अवरोही क्रम में क्रमबद्ध किया जाता है। यदि इस लेनदेन का कोई भी आइटम पहले से ही किसी अन्य शाखा में मौजूद है (उदाहरण के लिए 1 लेन-देन में), तो यह लेनदेन शाखा रूट में एक सामान्य उपसर्ग साझा करेगी।
इसका मतलब यह है कि इस सौदे में आम आइटमसेट दूसरे आइटम के नए नोड से जुड़ा हुआ है।
कैसे जावा में एक सूची इनिशियलाइज़ करने के लिए
# 5) इसके अलावा, आइटम की गणना बढ़ जाती है क्योंकि यह लेनदेन में होती है। आम नोड और नई नोड संख्या दोनों में 1 की वृद्धि हुई है क्योंकि वे लेनदेन के अनुसार बनाई और जुड़ी हुई हैं।
# 6) अगला कदम बनाए गए FP ट्री को माइन करना है। इसके लिए, सबसे कम नोड की जांच सबसे पहले सबसे कम नोड के लिंक के साथ की जाती है। सबसे कम नोड आवृत्ति पैटर्न लंबाई का प्रतिनिधित्व करता है। इसमें से, एफपी ट्री में पथ को पार करता है। इस पथ या पथ को एक सशर्त पैटर्न आधार कहा जाता है।
सशर्त पैटर्न का आधार एक उप-डेटाबेस है जिसमें सबसे कम नोड (प्रत्यय) के साथ होने वाले एफपी पेड़ में उपसर्ग पथ शामिल हैं।
# 7) कंडिशनल एफपी ट्री का निर्माण करें, जो मार्ग में आइटमों की गिनती से बनता है। थ्रेसहोल्ड समर्थन से मिलने वाले आइटम को सशर्त एफपी ट्री में माना जाता है।
# 8) बार-बार पैटर्न सशर्त एफपी ट्री से उत्पन्न होते हैं।
एफपी-ग्रोथ एलगोरिदम का उदाहरण
समर्थन सीमा = 50%, आत्मविश्वास = 60%
तालिका एक
लेन-देन | वस्तुओं की सूचि |
---|---|
स्मृति उपयोग | |
टी 1 | I1, I2, I3 |
टी 2 | I2, I3, I4 |
टी 3 | I4, I5 |
टी -4 | I1, I2, I4 |
टी 5 | I1, I2, I3, I5 |
टी 6 | I1, I2, I3, I4 |
उपाय:
समर्थन सीमा = 50% => 0.5 * 6 = 3 => min_sup = 3
1. प्रत्येक आइटम की गिनती
तालिका 2
मद | गिनती |
---|---|
I1 | ४ |
I2 | ५ |
I3 | ४ |
I4 | ४ |
I5 | दो |
2. आइटम को अवरोही क्रम में क्रमबद्ध करें।
टेबल तीन
मद | गिनती |
---|---|
I2 | ५ |
I1 | ४ |
I3 | ४ |
I4 | ४ |
3. एफपी ट्री का निर्माण
- रूट नोड शून्य को ध्यान में रखते हुए।
- लेन-देन T1: I1, I2, I3 के पहले स्कैन में तीन आइटम {I1: 1}, {I2: 1}, {I3: 1} शामिल हैं, जहां I2 को मूल के रूप में बच्चे से जोड़ा गया है, I1 I2 और I3 से जुड़ा हुआ है I1 से जुड़ा हुआ है।
- T2: I2, I3, I4 में I2, I3 और I4 शामिल हैं, जहां I2 को रूट से जोड़ा जाता है, I3 I2 से जुड़ा हुआ है और I4 I3 से जुड़ा हुआ है। लेकिन यह शाखा I2 नोड को साझा करेगी क्योंकि यह पहले से ही T1 में उपयोग किया जाता है।
- I2 की गिनती को 1 से बढ़ाना और I3 को I2 से बच्चे के रूप में जोड़ा जाता है, I4 को I3 के बच्चे के रूप में जोड़ा जाता है। गिनती {I2: 2}, {I3: 1}, {I4: 1} है।
- T3: I4, I5। इसी तरह, I5 के साथ एक नई शाखा I4 से जुड़ी हुई है क्योंकि एक बच्चा बनाया गया है।
- T4: I1, I2, I4। अनुक्रम I2, I1 और I4 होगा। I2 पहले से ही रूट नोड से जुड़ा हुआ है, इसलिए इसे 1 से बढ़ाना होगा। इसी तरह I1 को 1 से बढ़ाना होगा क्योंकि यह T1 में I2 के साथ पहले से जुड़ा हुआ है, इस प्रकार {I2: 3}, {I1: 2}, {I4: 1} है।
- T5: I1, I2, I3, I5। अनुक्रम I2, I1, I3 और I5 होगा। इस प्रकार {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}।
- T6: I1, I2, I3, I4। अनुक्रम I2, I1, I3 और I4 होगा। इस प्रकार {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}।
4. एफपी-ट्री का खनन नीचे संक्षेप में प्रस्तुत किया गया है:
- सबसे कम नोड आइटम I5 को नहीं माना जाता है क्योंकि इसमें न्यूनतम समर्थन गणना नहीं है, इसलिए इसे हटा दिया गया है।
- अगला निचला नोड I4 है। I4 2 शाखाओं में होता है, {I2, I1, I3:, I41}, {I2, I3, I4: 1}। इसलिए I4 को प्रत्यय के रूप में मानते हुए उपसर्ग पथ {I2, I1, I3: 1}, {I2, I3: 1} होंगे। यह सशर्त पैटर्न आधार बनाता है।
- सशर्त पैटर्न का आधार लेनदेन डेटाबेस माना जाता है, एक एफपी-ट्री का निर्माण किया जाता है। इसमें {I2: 2, I3: 2} शामिल होगा, I1 को नहीं माना जाता है क्योंकि यह न्यूनतम समर्थन गणना को पूरा नहीं करता है।
- यह पथ लगातार पैटर्न के सभी संयोजनों को उत्पन्न करेगा: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
- I3 के लिए, उपसर्ग पथ होगा: {I2, I1: 3}, {I2: 1}, यह एक 2 नोड उत्पन्न करेगा FP-ट्री: {I2: 4, I1: 3} और लगातार पैटर्न उत्पन्न होते हैं: {2} , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}।
- I1 के लिए, उपसर्ग पथ होगा: {I2: 4} यह एकल नोड FP-ट्री उत्पन्न करेगा: {I2: 4} और लगातार पैटर्न उत्पन्न होते हैं: {I2, I1: 4}।
मद | सशर्त पैटर्न बेस | सशर्त एफपी-पेड़ | बार-बार बनाए गए पैटर्न |
---|---|---|---|
I4 | {२, आई १, आई ३: १}, {आई २, आई ३: १} | {2: 2, I3: 2} | {2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2} |
I3 | {२, आई १: ३}, {आई २: १} | {२: ४, आई १: ३} | {2, I3: 4}, {I1: I3: 3}, {I2, I1, I3: 2} |
I1 | {२: ४} | {२: ४} | {२, आई १: ४} |
नीचे दिए गए आरेख में सशर्त नोड I3 से जुड़े सशर्त FP पेड़ को दर्शाया गया है।
यह मदद डेस्क के लिए साक्षात्कार सवाल
FP ग्रोथ एलगोरिदम के लाभ
- इस एल्गोरिथ्म को अप्रीओरी की तुलना में केवल दो बार डेटाबेस को स्कैन करने की आवश्यकता होती है जो प्रत्येक पुनरावृत्ति के लिए लेनदेन को स्कैन करता है।
- इस एल्गोरिथ्म में आइटमों की जोड़ी नहीं की जाती है और इससे यह तेज हो जाता है।
- डेटाबेस को मेमोरी में एक कॉम्पैक्ट संस्करण में संग्रहीत किया जाता है।
- यह लंबे और छोटे दोनों प्रकार के पैटर्न के खनन के लिए कुशल और स्केलेबल है।
FP-Growth Algorithm के नुकसान
- एफपी ट्री एप्रीओरी की तुलना में अधिक बोझिल और कठिन है।
- यह महंगा हो सकता है।
- जब डेटाबेस बड़ा होता है, तो एल्गोरिथ्म साझा की गई मेमोरी में फिट नहीं हो सकता है।
एफपी ग्रोथ बनाम अप्रीरी
एफपी ग्रोथ | संभवतः |
---|---|
पैटर्न जनरेशन | |
FP ट्री एक FP ट्री का निर्माण करके पैटर्न उत्पन्न करता है | Apriori आइटम को एकल, जोड़े और ट्रिपल में जोड़कर पैटर्न उत्पन्न करता है। |
उम्मीदवार पीढ़ी | |
कोई उम्मीदवार पीढ़ी नहीं है | Apriori उम्मीदवार पीढ़ी का उपयोग करता है |
प्रोसेस | |
Apriori की तुलना में प्रक्रिया तेज है। आइटम की संख्या में वृद्धि के साथ प्रक्रिया का रनटाइम रैखिक रूप से बढ़ता है। | एफपी ग्रोथ की तुलना में प्रक्रिया अपेक्षाकृत धीमी है, रनटाइम आइटम की संख्या में वृद्धि के साथ तेजी से बढ़ता है |
डेटाबेस का एक कॉम्पैक्ट संस्करण सहेजा गया है | उम्मीदवार संयोजन स्मृति में सहेजे जाते हैं |
चमक
उपरोक्त विधि, एप्रीओरी और एफपी विकास, क्षैतिज डेटा प्रारूप का उपयोग करते हुए लगातार आइटम। ECLAT वर्टिकल डेटा फॉर्मेट का उपयोग करके लगातार आइटम को खनन करने की एक विधि है। यह क्षैतिज डेटा प्रारूप में डेटा को ऊर्ध्वाधर प्रारूप में बदल देगा।
उदाहरण के लिए,Apriori और FP विकास का उपयोग करें:
लेन-देन | वस्तुओं की सूचि |
---|---|
टी 1 | I1, I2, I3 |
टी 2 | I2, I3, I4 |
टी 3 | I4, I5 |
टी -4 | I1, I2, I4 |
टी 5 | I1, I2, I3, I5 |
टी 6 | I1, I2, I3, I4 |
ECLAT में तालिका का प्रारूप निम्नानुसार होगा:
मद | लेन-देन सेट |
---|---|
I1 | {T1, T4, T5, T6} |
I2 | {T1, T2, T4, T5, T6} |
I3 | {T1, T2, T5, T6} |
I4 | {T2, T3, T4, T5} |
I5 | {T3, T5} |
यह विधि ऊर्ध्वाधर डेटा प्रारूप में 2-आइटम, 3 आइटम, के आइटमसेट बनाएगी। K के साथ यह प्रक्रिया 1 तक बढ़ जाती है जब तक कोई उम्मीदवार आइटम नहीं मिलते हैं। अप्रीओरी के साथ कुछ अनुकूलन तकनीकें जैसे कि डिफसेट का उपयोग किया जाता है।
इस विधि का एप्रीओरी पर एक फायदा है क्योंकि इसे k + 1 आइटम के समर्थन को खोजने के लिए डेटाबेस को स्कैन करने की आवश्यकता नहीं है। इसका कारण यह है कि लेन-देन सेट लेन-देन (समर्थन) में प्रत्येक आइटम की घटना की गणना करेगा। अड़चन तब आती है जब सेटों को इंटरसेक्ट करने के लिए कई मेमोरी और कम्प्यूटेशनल समय में कई लेनदेन होते हैं।
निष्कर्ष
Apriori एल्गोरिथ्म का उपयोग खनन संघ के नियमों के लिए किया जाता है। यह सिद्धांत पर काम करता है, 'लगातार वस्तुओं के खाली न होने वाले सबसेट को भी अक्सर होना चाहिए'। यह (k-1) आइटमसेट्स से k- आइटमसेट उम्मीदवार बनाता है और बार-बार आने वाले आइटम खोजने के लिए डेटाबेस को स्कैन करता है।
फ्रिक्वेंट पैटर्न ग्रोथ एलगोरिदम उम्मीदवार पीढ़ी के बिना लगातार पैटर्न खोजने की विधि है। यह एप्रीओरी की उत्पन्न और परीक्षण रणनीति का उपयोग करने के बजाय एक एफपी ट्री का निर्माण करता है। एफपी ग्रोथ एल्गोरिथ्म का ध्यान वस्तुओं के मार्गों को खंडित करने और लगातार पैटर्न को खनन करने पर है।
हमें उम्मीद है कि डेटा माइनिंग सीरीज़ के ये ट्यूटोरियल डेटा माइनिंग के बारे में आपके ज्ञान को समृद्ध करते हैं !!
PREV ट्यूटोरियल | सबसे पहले ट्यूटोरियल
अनुशंसित पाठ
- डेटा माइनिंग तकनीक: एल्गोरिथम, तरीके और शीर्ष डेटा खनन उपकरण
- डेटा माइनिंग में एप्रीओरी एल्गोरिदम: उदाहरणों के साथ कार्यान्वयन
- डेटा खनन में निर्णय ट्री एल्गोरिदम उदाहरण
- डेटा माइनिंग उदाहरण: डेटा माइनिंग 2021 के अधिकांश सामान्य अनुप्रयोग
- डेटा माइनिंग: डेटा एनालिसिस में प्रक्रिया, तकनीक और प्रमुख मुद्दे
- डाटा माइनिंग प्रोसेस: मॉडल, प्रोसेस स्टेप्स और चुनौतियां शामिल हैं
- CSTE सॉफ्टवेयर टेस्टिंग सर्टिफिकेशन परीक्षा प्रश्न पैटर्न
- डाटा माइनिंग बनाम मशीन लर्निंग बनाम आर्टिफिशियल इंटेलिजेंस बनाम डीप लर्निंग