एक डेटा सेट S में एक ऑब्जेक्ट o पैरामीटर्स p और d के साथ दूरी-आधारित (DB) आउटलेयर है, यानी DB(p, d), यदि S में ऑब्जेक्ट्स का न्यूनतम अंश p, o से d से अधिक दूरी पर स्थित है। दूसरे शब्दों में, सांख्यिकीय परीक्षणों पर निर्भर रहने के बजाय, दूरी-आधारित आउटलेयर्स को उन ऑब्जेक्ट्स के रूप में सोचा जा सकता है जिनके पास पर्याप्त पड़ोसी नहीं हैं।
पड़ोसियों को दिए गए ऑब्जेक्ट से दूरी के आधार पर दर्शाया जाता है। सांख्यिकीय-आधारित विधियों की तुलना में, दूरी-आधारित आउटलेयर पहचान मानक वितरण के लिए असंगति परीक्षण के पीछे के विचारों को सामान्यीकृत या विलय करती है। इसलिए, दूरी-आधारित आउटलेयर को एकीकृत आउटलेयर या UO-आउटलेयर के रूप में भी जाना जाता है।
दूरी-आधारित आउटलेयर पहचान उस अत्यधिक गणना को रोकती है जो देखे गए वितरण को कुछ मानक वितरण में फिट करने और असंगति परीक्षण चुनने से संबंधित हो सकती है। कुछ असंगति परीक्षणों के लिए, यह प्रदर्शित किया जा सकता है कि यदि कोई ऑब्जेक्ट o दिए गए परीक्षण के अनुसार आउटलेयर है, तो o कुछ उचित रूप से दर्शाए गए p और d के लिए DB(p, d) आउटलेयर भी है।
उदाहरण के लिए, यदि सामान्य वितरण को ध्यान में रखते हुए, माध्य से 3 या अधिक मानक विचलन पर स्थित ऑब्जेक्ट्स को आउटलेयर माना जाता है, तो इस प्रतिनिधित्व को DB(0.9988, 0.13s)-आउटलेयर द्वारा "एकीकृत" किया जा सकता है। दूरी-आधारित आउटलेयर्स के खनन के लिए कई कुशल एल्गोरिदम विकसित किए गए हैं जो निम्नलिखित हैं:
इंडेक्स-आधारित एल्गोरिदम - एक डेटा सेट दिए जाने पर, इंडेक्स-आधारित एल्गोरिदम बहुआयामी इंडेक्सिंग संरचनाओं की सुविधा देता है, जिसमें R-ट्रीज़ या k-d ट्रीज़ शामिल हैं, ताकि उस ऑब्जेक्ट के चारों ओर त्रिज्या d के अंदर प्रत्येक ऑब्जेक्ट o के पड़ोसियों की खोज की जा सके। मान लें कि M एक आउटलेयर के d-पड़ोस के भीतर ऑब्जेक्ट्स की अधिकतम संख्या है। इसलिए, एक बार ऑब्जेक्ट o के M + 1 पड़ोसी खोजे जाने के बाद, यह सुलभ है कि o आउटलेयर नहीं है। इस एल्गोरिदम का सबसे खराब स्थिति जटिलता O(k * n²) है, जहां k आयाम है, और n डेटा सेट में ऑब्जेक्ट्स की संख्या है।
नेस्टेड-लूप एल्गोरिदम - नेस्टेड-लूप एल्गोरिदम का इंडेक्स-आधारित एल्गोरिदम के समान मूल्यांकन जटिलता है लेकिन इंडेक्स संरचना निर्माण से बचाता है और I/O की संख्या को कम करने का प्रयास करता है। यह मेमोरी बफर क्षेत्रों को दो हिस्सों में विभाजित करता है, और डेटा को कई तार्किक ब्लॉकों में सेट करता है।
सेल-आधारित एल्गोरिदम - यह O(n²) कम्प्यूटेशनल जटिलता से बचने के लिए, मेमोरी-निवासी डेटा सेट के लिए एक सेल-आधारित एल्गोरिदम विकसित किया गया था। इसकी जटिलता O(cᵏ + n) है, जहां c सेल्स की संख्या पर आधारित एक स्थिरांक है, और k आयाम है।
इस विधि में, डेटा स्पेस को $\frac{d}{\sqrt[2]{k}}$ के बराबर साइड लंबाई वाले सेल्स में विभाजित किया जाता है। प्रत्येक सेल के आसपास दो परतें होती हैं।
पहली परत एक सेल मोटी होती है, जबकि दूसरी $\sqrt[2]{k}$ सेल मोटी होती है, जिसे निकटतम पूर्णांक तक पूर्णांकित किया जाता है। एल्गोरिदम ऑब्जेक्ट-दर-ऑब्जेक्ट के बजाय सेल-दर-सेल आधार पर आउटलेयर्स की गणना करता है। एक दिए गए सेल के लिए, यह तीन गणनाओं को संचित करता है जिसमें सेल में ऑब्जेक्ट्स की संख्या, सेल और पहली परत एक साथ, और सेल और दोनों परतें एक साथ शामिल होती हैं।
