उपयोगकर्ता गतिविधि के विभाजन को कैसे बेहतर बनाया जाए। यांडेक्स वर्कशॉप

यह ज्ञात है कि उपयोगकर्ता गतिविधि एक खोज इंजन के लिए कई उपयोगी जानकारी प्रदान करती है। विशेष रूप से, यह समझने में मदद करता है कि उपयोगकर्ता को अपनी व्यक्तिगत प्राथमिकताओं को उजागर करने के लिए किस जानकारी की आवश्यकता है, उस विषय का संदर्भ जो उपयोगकर्ता वर्तमान में रुचि रखता है। इस विषय पर पिछले अध्ययनों में से अधिकांश या तो समय की एक निश्चित अवधि के लिए सभी उपयोगकर्ता क्रियाओं पर विचार करते थे, या गतिविधि को भागों (सत्रों) में विभाजित करते थे जो निष्क्रियता (समयबाह्य) की पूर्व निर्धारित अवधि के आधार पर होता है।



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







किसी ब्राउज़र, खोज इंजन या किसी विशिष्ट साइट पर उपयोगकर्ता गतिविधि उपयोगी जानकारी का एक समृद्ध स्रोत है: किसी पोर्टल पर अनुरोध / यात्रा के पहले और बाद में सुधार करना, अनुरोधों में सुधार करना। दुर्भाग्य से, यह जानकारी किसी भी तरह से संरचित और बहुत शोर नहीं है। मुख्य कार्य कच्चे डेटा का प्रसंस्करण, संरचना और शुद्धिकरण है। मैं उपयोगकर्ता गतिविधि को तार्किक रूप से संबंधित घटकों में विभाजित करने के लिए एक विधि का सुझाव देना चाहूंगा।



उपयोगकर्ता लगातार खोज इंजन और ब्राउज़र के साथ बातचीत करता है:

• अनुरोध सेट करता है;
• जारी करने में दस्तावेजों पर क्लिक;
• जारी करने में नए पृष्ठों का अनुरोध करता है;
• ब्राउज़र लिंक और नेविगेशन बटन का उपयोग करके पृष्ठों के बीच की चाल;
• टैब के बीच स्विच;
• पृष्ठ को स्क्रॉल करता है, माउस के साथ उन पर ले जाता है;
• अन्य खोज इंजनों पर जाता है।

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



उपयोगकर्ता सत्रों के अध्ययन के संबंध में, कई कार्य उत्पन्न होते हैं:

1. तार्किक सत्रों की सीमाओं का निर्धारण;
2. सत्र में अगली कार्रवाई की भविष्यवाणी;
3. अगली कार्रवाई में सहायता के लिए सत्र की जानकारी प्राप्त करना;
4. एक सत्र में उपयोगकर्ता क्रियाओं को मॉडलिंग करना;
5. सत्र के दौरान छिपे हुए डेटा का मूल्यांकन - जानकारी की आवश्यकता, सत्र के साथ संतुष्टि, थकान।

अगला, हमें कई परिभाषाएँ तैयार करने और कई संकेतन प्रस्तुत करने की आवश्यकता है। मेरी कहानी का मुख्य चरित्र - ब्राउज़र सत्र - दिन के दौरान उपयोगकर्ता द्वारा देखे गए पृष्ठों का एक क्रम है: डी _यू - (डी ₁ ....... डी _एन ) । द्वितीयक ऑब्जेक्ट - अनुरोध सत्र - एक दिन के भीतर उपयोगकर्ता द्वारा निर्दिष्ट अनुरोधों का एक क्रम: क्यू _यू - (q ₁ ....... q _n ) । बनाम हम लॉजिकल ब्राउजर सेशन (और लॉजिकल रिक्वेस्ट सेशन) को भी हाइलाइट करना चाहते हैं - ब्राउजर सेशन के जिस हिस्से में समान जानकारी की जरूरत है, उसके साथ लॉजिस्टिकली कनेक्टेड पेज हैं।







उपयोगकर्ता सत्र क्या हो सकता है, इसके एक उदाहरण पर विचार करें:







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



बेशक, यह एक कृत्रिम उदाहरण है, लेकिन इस पर आप तार्किक सत्रों की कुछ महत्वपूर्ण विशेषताओं का पता लगा सकते हैं:

1. एक नियम के रूप में, तार्किक सत्रों में हस्तक्षेप किया जाता है।
2. कुछ पृष्ठ कई तार्किक सत्रों में भाग लेते हैं।
3. अनुरोध किए जाने से पहले उपयोगकर्ता की आवश्यकता बदल जाती है।

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







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



आमतौर पर, डी _यू निष्क्रियता की अवधि के आधार पर खंडित किया _{जाता है} here (यहां d (डी) डी खोलने का क्षण है)। d _i और d _{i + 1} क्रमशः एक ही सत्र के हैं, d (d _{i + 1} ) - τ (d _i ) < ₊ । यह सबसे लोकप्रिय और आम दृष्टिकोण है। लेकिन यह स्पष्ट है कि यह तब काम नहीं करता है जब सत्र एक-दूसरे के साथ जुड़ जाते हैं। यदि उपयोगकर्ता इस दृष्टिकोण के दृष्टिकोण से किसी विषय पर लौटता है, तो यह पहले से ही एक नया तार्किक सत्र होगा।



क्वेरी सत्रों के तार्किक विभाजन का कार्य पहले ही दो पेपरों में हल हो चुका है:

• पी। बोल्डी एट अल। क्वेरी-प्रवाह ग्राफ़: मॉडल और अनुप्रयोग।
• आर। जोन्स एट अल। सत्र के समय से परे: क्वेरी लॉग में खोज विषयों के स्वचालित श्रेणीबद्ध विभाजन।

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



अपने शोध में, मैंने कई सवाल उठाए:

• क्या ब्राउज़र सत्रों के स्तर पर अनुरोध सत्रों के तार्किक टूटने को स्पष्ट करना संभव है?
• निष्क्रियता की अवधि के आधार पर गुणवत्ता विभाजन कितना दृष्टिकोण देता है?
• विभिन्न क्लस्टरिंग एल्गोरिदम विभाजन की गुणवत्ता को कैसे प्रभावित करते हैं?
• तार्किक विभाजन के लिए कारकों के कौन से स्रोत महत्वपूर्ण हैं?

विधि

उपयोग किए गए कच्चे डेटा में कच्चे ब्राउज़र सत्र थे - उपयोगकर्ता द्वारा देखे गए पृष्ठों का एक क्रम। सेगमेंटेशन स्वयं दो चरणों में बनाया गया है:

1. जोड़ीदार वर्गीकरण। हम यह अनुमान लगाते हैं कि क्या उपयोगकर्ता ने एक उद्देश्य के लिए कुछ पृष्ठों ( d _i , d _j ) का दौरा किया: हम फ़ंक्शन p (d _i , d _j ) d [0; 1] सीखते हैं, जो एक तार्किक सत्र से संबंधित d _i , d _j की संभावना का अनुमान लगाता है।
2. क्लस्टरिंग। P के विभिन्न अनुमानों (d _i , d _j ) के लिए, N कोने पर d का पूरा ग्राफ क्लस्टर _I , किनारों p (d _i , d _j ) के भार के साथ दृढ़ता से जुड़े घटकों में।

परिणामस्वरूप, हमें विभाजन मिलता है:





अधिक विस्तार से दो चरणों में से प्रत्येक पर विचार करें। वर्गीकरण से शुरू करते हैं। मशीन लर्निंग में, आपको हमेशा पहले स्थान पर एक साथ उदाहरणों का एक सेट रखने की आवश्यकता होती है। हमने अपने हाथों से जोड़ों के एक पर्याप्त बड़े सेट को निर्धारित किया है कि क्या वे एक ही तार्किक सत्र से संबंधित हैं। अगला, प्रत्येक मूल्यांकन जोड़ी ( डी, डी ' ) के लिए, हम कारकों को निकालते हैं



उसके बाद हम क्लासिफायर पी (डी _आई , डी _जे ) सीखते हैं।



क्लासिफायरियर के लिए एक मॉडल के रूप में, हम लॉजिस्टिक लॉस फ़ंक्शन के साथ एक निर्णय ट्री का उपयोग करते हैं। यह सभी जोड़े के सही वर्गीकरण की संभावना को अधिकतम करता है:



प्रत्येक जोड़ी ( डी, डी ' ) के लिए, हम चार प्रकार के कारक निकालते हैं (कुल लगभग 29 टुकड़े):

1. URL आधारित कारक।
2. पाठ संबंधी कारक।
3. सत्र के कारक। विज़िट के बीच का समय d, d ' , उनके बीच दस्तावेजों की संख्या, चाहे एक लिंक क्लिक हो।
4. प्रासंगिक सामान्यीकरण। पिछले तीन पैराग्राफों की तरह ही, केवल दस्तावेज़ d के लिए गणना " पूर्ववर्ती डी ' ।

हम मानते हैं कि वर्गीकरण किया गया है, और अब हमारा लक्ष्य पूरा ग्राफ क्लस्टर करना है, उस विभाजन को ढूंढें जो संभावना को अधिकतम करता है ( ρ के मूल्य तय किए गए हैं, विभाजन बदलता है):





Π 'एक क्लस्टर से सभी जोड़े ( डी, डी' ) का उत्पाद है;

; विभिन्न समूहों से सभी जोड़े ( डी, डी ' ) का योग है;

। "सभी समूहों से सभी जोड़े ( डी, डी ' ) का उत्पाद है।



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







मैंने तीन लालची एल्गोरिदम का उपयोग किया:

1. अंतिम पृष्ठ की अधिकतम संभावना। d _g खंड g का अंतिम पृष्ठ है। सभी पी (डी _जी , डी _नया ) <1/2, इसलिए, हम एक नया सत्र शुरू करते हैं। अन्यथा, अधिकतम संभावना वाले सत्र में d _नया जोड़ें।
2. सभी पृष्ठों की अधिकतम संभावना। सभी पी (डी, डी _नया ) <1/2, इसलिए हम एक नया सत्र शुरू करते हैं। अन्यथा, अधिकतम संभावना वाले दस्तावेज़ वाले सत्र में d _नया जोड़ें।
3. लालची जोड़। Adding की वृद्धि को अधिकतम करने के लिए d _नया जोड़ना। यदि g हमेशा सभी जी के लिए घटता है, तो हम एक नया खंड शुरू करते हैं।

दूसरे प्रकार के एल्गोरिदम एक बार में उपयोगकर्ता की सभी दैनिक गतिविधि के साथ काम करते हैं, अर्थात। पोस्ट-क्लस्टरिंग आयोजित करता है। इस प्रकार में लालची विलय शामिल है। हम N - | डी _यू | समूहों। हम उत्सुक रूप से मौजूदा समूहों को मर्ज करते हैं, जबकि existing को बढ़ाया जा सकता है।







पहले एल्गोरिथ्म की जटिलता हे (जी × एन) , जहां जी सेगमेंट की संख्या है। अन्य सभी एल्गोरिदम में ओ (एन ² ) जटिलता है ।

प्रयोगों

टूलबार का उपयोग करके एकत्र किए गए अनाम ब्राउज़र-आधारित लॉग को कच्चे डेटा के रूप में उपयोग किया गया था। उनके पास सार्वजनिक पृष्ठों के पते थे, जिनमें से प्रत्येक के लिए, यात्रा का समय, यात्रा का स्रोत (यदि कोई लिंक था), दस्तावेज़ का पाठ और लिंक जो उपयोगकर्ता ने उन्हें छोड़ दिया (यदि ऐसा हुआ)। प्रशिक्षण के नमूने के लिए, प्रत्येक ब्राउज़र सत्र मैन्युअल रूप से मूल्यांकनकर्ताओं द्वारा तार्किक सत्रों में विभाजित किया गया था। कुल मिलाकर, हमारे पास 220 ब्राउज़र तार्किक सत्र और क्लासिफायर प्रशिक्षण के लिए 151 हजार जोड़े थे: एक सत्र से 78 हजार और विभिन्न से 73 हजार जोड़े। एक तार्किक सत्र की औसत लंबाई 12 पृष्ठों की थी, और प्रति दिन प्रति उपयोगकर्ता तार्किक सत्रों की औसत संख्या 4.4 थी।



नीचे दी गई तालिका कारकों के विभिन्न सेटों पर प्रशिक्षित समय विभाजन और क्लासिफायर की गुणवत्ता को दर्शाती है:

कारकों का सेट	अस्थायी विभाजन	सब	संदर्भ से बाहर	कोई पाठ नहीं
एफ उपाय	80%	83%	83%	82%
शुद्धता	72%	82%	81%	81%

एक विधि है जो आपको मशीन सीखने की प्रक्रिया में प्रत्येक कारक के योगदान की गणना करने की अनुमति देती है। नीचे दी गई तालिका शीर्ष 10 कारकों और उनके योगदान को सूचीबद्ध करती है।

आर	फ़ैक्टर	ऐनक
1	डी 1 और डी 1 के बीच का समय	1
2	LCS	0.58
3	LCS / लंबाई ( url 1 )	0.40
4	LCS / लंबाई ( url 2 )	0.40
5	# पृष्ठ d 1 b d 1 के बीच	0.33
6	URL ट्रिग्राम मैच	0.32
7	प्रासंगिक LCS / लंबाई ( url 1 )	0.32
8	एकल मेजबान	0.22
9	LCS / लंबाई ( url 2 )	0.20
10	प्रासंगिक एलसीएस	0.20

जैसा कि हमने उम्मीद की थी, सबसे महत्वपूर्ण कारक दस्तावेजों का दौरा करने के बीच का समय है। यह भी काफी स्वाभाविक है कि URL और LCS (एक सामान्य URL की लंबाई) एक महत्वपूर्ण भूमिका निभाते हैं। संदर्भ कारकों द्वारा एक भूमिका निभाई जाती है। हालाँकि, एक भी पाठ्य कारक नहीं है।



अब चलिए क्लस्टरिंग प्रयोगों की ओर बढ़ते हैं। एल्गोरिदम की गुणवत्ता का एक माप रैंड इंडेक्स पर आधारित है। दो सेगमेंट S ₁ , S _{2 के} सेट D _{u के लिए,} यह समान रूप से संबंधित जोड़े के दस्तावेजों के हिस्से के बराबर है:







यहाँ n ₁ - # जोड़े एक खंड S ₁ , S ₂ , n ₂ - # जोड़े अलग-अलग खंड S ₁ , S ₂ , N - # तत्वों से D _{u में हैं} । इसके अलावा, एस ₁ आदर्श विभाजन है, और एस ₂ अनुमानित है। आर (एस ₁ , एस ₂ ) इसी क्लासिफायरियर की सटीकता का प्रतिनिधित्व करता है। नीचे दिया गया ग्राफ shows में गतिविधि की अवधि के लिए रैंड इंडेक्स दिखाता है:







अब देखते हैं कि ऊपर वर्णित एल्गोरिदम कैसे काम करते हैं:

विधि	रैंड इंडेक्स	जटिलता
अस्थायी	0.72	-
मैक्स। संभावना अंतिम है पृष्ठों	0.75	O (N × G)
मैक्स। सभी पृष्ठों की संभावना	0.79	ओ (एन 2 )
लालची जोड़	0.82	ओ (एन 2 )
लालची विलय	0.86	ओ (एन 2 )

लालची विलय (0.86) के अनुरूप क्लासिफायर की गुणवत्ता मूल क्लासिफायरियर (0.82) की तुलना में भी अधिक है।

निष्कर्ष

1. ब्राउज़र लॉग के स्वचालित प्रसंस्करण के लिए एक विधि प्रस्तावित है, जो क्वेरी लॉग के विभाजन को स्पष्ट करती है।
2. हमने वर्गीकरण और क्लस्टरिंग की अच्छी तरह से अध्ययन की गई समस्याओं के विभाजन की समस्या को कम कर दिया है।
3. हालांकि समय का दृष्टिकोण बहुत अच्छा है, अधिक परिष्कृत क्लस्टरिंग एल्गोरिदम इसे बहुत दूर करते हैं।
4. सत्र डेटा और URL मिलान पर आधारित कारकों की तुलना में एकल सत्र के भीतर पृष्ठों के बीच तार्किक लिंक का निर्धारण करने के लिए प्रासंगिक और पाठ संबंधी कारक बहुत कम महत्वपूर्ण हैं।

यांडेक्स में अगला वैज्ञानिक और तकनीकी सेमिनार 10 जून को आयोजित किया जाएगा। यह अनुशंसा प्रणालियों और वितरित एल्गोरिदम के विषय के लिए समर्पित होगा ।