✖

Min Value: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ

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

Min Value

इस लेख में हम केवल मात्रक अंतराल (0, 1) की वास्तविक संख्याओं के साथ काम करेंगे। इस अंतराल की संख्याओं के ऐसे समुच्चय की कल्पना कीजिए, जो समान रूप से फैला हो, जैसे संख्याओं का समुच्चय {0.25, 0.5, 0.75}। पड़ोसी संख्याओं के बीच (और शून्य तथा एक से) दूरी हमेशा 0.25 ही है। इससे हमें अद्वितीय अवयवों की संख्या गिनने में क्या मदद मिलेगी?

यदि मैं आपसे कहूँ कि हमारे पास मात्रक अंतराल की संख्याओं का ऐसा समान रूप से फैला समुच्चय है और इन संख्याओं के बीच की दूरी 0.2 है — तो क्या आप परिकलित कर सकते हैं कि ऐसे समुच्चय में कितने अवयव हैं? निश्चित रूप से, यह समुच्चय {0.2, 0.4, 0.6, 0.8} है, जिसकी गणनसंख्या (कार्डिनैलिटी) चार है। यदि इनपुट पर मात्रक अंतराल की समान रूप से फैली संख्याएँ हों और हमें पड़ोसी संख्याओं की दूरी पता हो, तो हम आसानी से अवयवों की संख्या परिकलित कर सकते हैं।

साथ ही पड़ोसी संख्याओं के बीच की दूरी समुच्चय के न्यूनतम अवयव के बराबर है — समुच्चय {0.25, 0.5, 0.75} के पड़ोसी अवयवों की दूरी 0.25 है, आदि। समान रूप से फैली संख्याओं के अवयवों की संख्या परिकलित करने के लिए हमें बस किसी तरह न्यूनतम अवयव ज्ञात करना है। तब अवयवों की संख्या p हम सरल सूत्र से परिकलित कर सकते हैं:

p=1m−1

जहाँ m वही न्यूनतम अवयव है।

और फिर से हैशिंग…

ठीक है, पर इसका उपयोग कैसे करें, यदि इनपुट पर कुछ स्ट्रिंगें या अन्य मान हों, जो मात्रक अंतराल में समान रूप से फैले होने की शर्त पूरी नहीं करते? यहाँ फिर हमारी मदद पुराना भरोसेमंद हैश फलन करेगा, जो किसी भी इनपुट के लिए मात्रक अंतराल की एक परिमेय संख्या लौटा सकता है। ऐसा हैश फलन बनाना आसान होगा।

इससे हमें आँकड़ों से परिमेय संख्याएँ मिल जाएँगी, पर यह कैसे सुनिश्चित करें कि ये संख्याएँ समान रूप से फैली हों? यह तो संभव नहीं होगा, परंतु हम दूसरी तरह से मदद ले सकते हैं। हमारी दृष्टि से हैश फलन काफ़ी “यादृच्छिक” ढंग से व्यवहार करता है। “hello”, “hellp” और “hellq” जैसे बहुत मिलते-जुलते शब्दों के लिए हैश फलन संभवतः बहुत भिन्न चेकसम लौटाएगा। दूसरे शब्दों में: यदि हम एक हज़ार भिन्न मानों को मात्रक अंतराल में हैश करें, तो इसकी प्रायिकता बहुत कम है कि अधिकांश संख्याएँ, उदाहरण के लिए, आधे से छोटी हों। इसके विपरीत, इसकी प्रायिकता बहुत अधिक है कि ये संख्याएँ लगभग नियमित रूप से फैली हों। जितने अधिक आँकड़े हम हैश करेंगे, फैलाव उतना ही नियमित होगा।

इस विचार से हमें एक सरल एल्गोरिद्म मिलता है: हम इनपुट आँकड़ों से गुज़रते हैं, प्रत्येक अवयव को मात्रक अंतराल में हैश करते हैं और न्यूनतम अवयव याद रखते हैं। अद्वितीय अवयवों की संख्या का अनुमान पिछले सूत्र से लगाते हैं। Python में कार्यान्वयन:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

फलन unit_interval_hash अंतराल (0, 1] की एक दशमलव संख्या लौटाता है। फलन count_unique_using_minimum पहले सभी इनपुट मानों को ऐसी संख्या में बदलता है, न्यूनतम ढूँढता है और 1 / minimum - 1 लौटाता है। ध्यान दीजिए कि इस बात से बिल्कुल फ़र्क नहीं पड़ता कि आँकड़ा-समूह में कितने मान एक जैसे हैं — दो एक जैसे मानों के लिए हैश फलन एक ही परिमेय संख्या लौटाता है, जिससे परिणामी न्यूनतम पर कोई असर नहीं पड़ता। इसलिए इस एल्गोरिद्म से हम अद्वितीय अवयवों की संख्या गिनते हैं।

परिणाम क्या हैं? (प्रत्येक पंक्ति में अनुमानित गणनसंख्या है, जबकि सही गणनसंख्या 10,000 है।)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

कुछ ख़ास नहीं, है न? एल्गोरिद्म पहचानकर्ताओं के दस भिन्न समूहों से गुज़रा, जिनमें हर बार दस हज़ार अद्वितीय मान थे। परिकलित अनुमान अधिकतर काफ़ी गलत हैं। यदि हम उनका माध्य लें, तो हमें 18,352 मिलेगा। यह भी काफ़ी गलत है, परंतु दूसरी ओर मेमोरी की आवश्यकता देखिए — यह अचर है! न्यूनतम ढूँढने के लिए आपको मेमोरी में केवल एक चर रखना है, जिसमें आप वर्तमान न्यूनतम सहेजते हैं, बस। तो हाँ, अनुमान बेकार है, पर उसकी कीमत भी लगभग कुछ नहीं।

सुधार

हम देखते हैं कि एल्गोरिद्म मुख्यतः अस्थिर है — एक बार यह काफ़ी अच्छा अनुमान (9362) लौटाता है, दूसरी बार ऐसा अनुमान, जो पूरी तरह गलत है (65536)। इससे कैसे निकलें? हम इनपुट आँकड़ों को कई भागों में बाँट सकते हैं, प्रत्येक भाग के लिए अद्वितीय अवयवों की संख्या गिन सकते हैं और अंत में सबका ठीक से माध्य ले सकते हैं। विभाजन हम अपने पहचानकर्ता के पहले अक्षर के आधार पर कर सकते हैं। यानी अक्षर “a” से शुरू होने वाले पहचानकर्ताओं के लिए अद्वितीय मानों की संख्या अलग से गिनेंगे, फिर अक्षर “b” से शुरू होने वालों के लिए, आदि। कोड:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

परिवर्तन फलन count_unique_using_minimum में हैं। चर min_values में हम प्रत्येक समूह का न्यूनतम रखते हैं। अंत में हम सभी न्यूनतमों को जोड़ते हैं और उन्हें सहेजे गए मानों की संख्या से भाग देते हैं — हमें औसत न्यूनतम मिलता है। व्यंजक 1/average_minimum से हम ज्ञात करते हैं कि प्रत्येक समूह में अद्वितीय मानों की औसत संख्या कितनी है — इस मान को हम समूहों की संख्या से गुणा करते हैं और हमें दिए गए आँकड़ा-समूह में अद्वितीय मानों की अनुमानित संख्या मिल जाती है। और यह संशोधित विधि कैसे काम करती है?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

अब भी अच्छा नहीं है, पर निश्चित रूप से बेहतर है। एल्गोरिद्म अधिक स्थिर है। हम फलन को ऐसे बदल सकते हैं कि समूह पहले अक्षर के आधार पर नहीं, बल्कि, उदाहरण के लिए, पहचानकर्ता के पहले दो अक्षरों के आधार पर बनें, अर्थात् इस प्रकार:

first_char = str(item)[0:2] # ToDo: choose better name for variable

तब परिणाम ऐसे होंगे:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

अब यह इतना बुरा भी नहीं है, है न? यदि हम एक लाख अद्वितीय मान, पहले दो अक्षर और n = 24 आज़माएँ, तो हमें ये परिणाम मिलते हैं:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

यह ठीक-ठाक है। पर चिंता मत कीजिए, इससे बेहतर एल्गोरिद्म भी मौजूद हैं।

और मेमोरी की आवश्यकता कितनी है? हमें प्रत्येक समूह का न्यूनतम रखना है, बस इतना ही। यदि पहचानकर्ता hex प्रारूप में हैं, तो इसका अर्थ है कि हमें अधिकतम 16x न्यूनतम याद रखने हैं, जहाँ x उन अक्षरों की संख्या है, जिनसे हम समूह की कुंजी बनाते हैं। एक न्यूनतम एक परिमेय संख्या है, अर्थात् double या float जैसा कोई प्रकार।

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

विषय-सूची: Linear counting: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, Min Value: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, LogLog: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, HyperLogLog: भिन्न मानों की संख्या का बहुत सटीक अनुमान कैसे लगाएँ