FTCA डेटा क्लस्टरिंग एल्गोरिथम

प्रस्तावना

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

शुरुआत के लिए, क्लस्टरिंग क्या है?

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

और इस त्रुटि से कैसे बचें?

त्रुटियों से बचने के कई तरीके हैं। आप ऑब्जेक्ट के प्रमुख गुणों को स्पष्ट रूप से उजागर कर सकते हैं, जो किसी भी तरह से एक क्लस्टर में नहीं हो सकते हैं, लेकिन आदर्श रूप से दूसरे में फिट हो सकते हैं। उदाहरण के लिए, ऊपर दिए गए उदाहरण में, आप "जीवित-थे", "राज्य-राज्य" और इसी तरह के शब्दों की उपस्थिति के लिए खोज कर सकते हैं, और इस दस्तावेज़ को कुछ समूहों में शामिल नहीं कर सकते हैं। और आप वस्तुओं के बीच निर्भरता का एक ग्राफ बना सकते हैं और पहले से ही इस ग्राफ को देख कर आगे inferences बनाते हैं (यह विधि काम करती है, उदाहरण के लिए, SCT और लिंगो)। कई समाधान हैं, यहां तक ​​कि कुछ डेटा सेटों पर संपत्ति को संतुष्ट करने के लिए एक बैसाखी की स्थिति सामान्य रूप से क्लस्टरिंग की सटीकता को बढ़ा सकती है।

और आपने किस तरह के एल्गोरिथम के बारे में शुरुआत में बात की थी?

डेविड द्वारा वर्णित एल्गोरिथ्म ने मेरा ध्यान अपनी विषमता या व्यावहारिक प्रयोज्यता से नहीं, बल्कि इसकी सादगी से आकर्षित किया। यह सामान्य मानव तर्क पर बनाया गया है और यह अन्य एल्गोरिदम के समान है।

शुरू करने के लिए, कल्पना करें कि हमारे पास उन वस्तुओं का एक समूह है, जिन्हें हम समूह बनाना चाहते हैं और एक फ़ंक्शन जो कहता है कि दो वस्तुएं प्रतिशत शब्दों में एक दूसरे के समान हैं:
F (x, y) = F (y, x) = ...%
- दो वस्तुओं का सहसंबंध समारोह।
(वास्तव में यह वह सब है जो मानव मस्तिष्क आमतौर पर वस्तुओं को समूहित करते समय उपयोग करता है।)

अगला, हम औसत समानता की अवधारणा पेश करते हैं:
G (x, y1, y2, ..., yn) = SUM (F (x, yk)) / n
- यह फ़ंक्शन दर्शाता है कि ऑब्जेक्ट अन्य ऑब्जेक्ट के समूह से कितना मिलता जुलता है।

एल्गोरिथ्म

पहले (और लंबे) कदम पर, सुविधा के लिए, हमारी सभी वस्तुओं को उनके औसत सहसंबंध के अनुसार आरोही क्रम में अन्य वस्तुओं के साथ क्रमबद्ध करना आवश्यक है। यही है, हमें पहले तत्व की एक सूची मिलती है जिसमें सबसे छोटे औसत सहसंबंध के साथ तत्व होगा, और अंतिम, इसके विपरीत, सबसे बड़ा के साथ।
इसके बाद, हमें यह तय करना चाहिए कि कितने क्लस्टर बनाने हैं और किस सिद्धांत से हैं। सिद्धांत क्या है? और यह हमारी त्रिशूल है - ऊपर की सीमा जिसके ऊपर वस्तुओं को एक साथ एक ही समूह में समान माना जाता है।

निम्नलिखित एल्गोरिथ्म का उपयोग करके क्लस्टर बनाए जाते हैं:
1) वस्तुओं को क्रमबद्ध करें।
2) हम अपनी सॉर्ट की गई सूची से पहली और आखिरी वस्तु लेते हैं।
• यदि उनका सहसंबंध हमारी समानता की सीमा से अधिक है - हम इन दो वस्तुओं के पहले तत्वों के साथ एक क्लस्टर बनाते हैं और शेष सभी वस्तुओं को ढूंढते हैं, तो पूरे समूह के साथ औसत सहसंबंध एक कचरा से अधिक होगा।
• यदि उनका सहसंबंध समानता की सीमा से कम है, तो हम तत्वों के दो समूह बनाते हैं जिसमें वे ऊपर वर्णित एक ही सिद्धांत के अनुसार गिरेंगे।
3) यदि कोई एक वस्तु बची है - एक अलग क्लस्टर बनाएं और उसे वहां से हटा दें। अन्यथा, हम चरण 1 पर लौटते हैं।

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

परिणाम

संक्षेप में, मैं कहना चाहता हूं कि यहां तक ​​कि मुझे अभी तक समझ नहीं आया कि डेविड ने "फास्ट" शब्द के साथ नाम क्यों शुरू किया, जिसका अनुवाद "फास्ट" के रूप में किया गया है। जब तक आप प्रत्येक वस्तु के लिए प्रत्येक औसत मान के साथ प्रत्येक वस्तु के विशाल सहसंबंध मैट्रिक्स का उपयोग नहीं करते हैं, तब तक यह एल्गोरिथ्म तेजी से नहीं कहा जा सकता है, लेकिन सहसंबंध समारोह की संभावित जटिलता के कारण यह सब गणना करना एक बहुत ही मुश्किल ऑपरेशन है। सैद्धांतिक रूप से, विचार बहुत अच्छा है, व्यावहारिक रूप से समान है - यह छोटी मात्रा में डेटा को संसाधित कर सकता है।
एल्गोरिथ्म की सामान्य स्पर्शोन्मुख जटिलता संभवतः जटिल फ़ंक्शन F (x, y) का O (n ^ 3) है। सहसंबंध मैट्रिक्स का उपयोग करते समय, हमें मेमोरी में ओ (एन ^ 2) और मेमोरी में ओ (एन ^ 2) मिलता है, जो रैम से सभी ट्रैफिक जाम को बाहर कर देगा। ये हैं प्यारे, ख़बरखाने वाले।

अगली बार मैं आपको इस एल्गोरिथ्म के मेरे परीक्षण के परिणामों के बारे में बताने की कोशिश करूंगा।

स्रोत: cssanalytics.wordpress.com/2013/11/26/fast-threshold-clustering-al आजादी