MinHash
কম্পিউটার বিজ্ঞান এবং তথ্য খননে, মিনহ্যাশ (বা ন্যূনতম-ভিত্তিক স্বাধীন বিন্যাস স্থানীয় সংবেদনশীল হ্যাশিং স্কিম) হল দুটি সেট কতটা অনুরূপ তা দ্রুত অনুমান করার একটি কৌশল। এই প্রকল্পটি উদ্ভাবন করেছিলেন এবং প্রাথমিকভাবে আল্টাভিস্তা সার্চ ইঞ্জিনে ডুপ্লিকেট ওয়েব পৃষ্ঠাগুলি সনাক্ত করতে এবং অনুসন্ধানের ফলাফল থেকে তাদের নির্মূল করতে ব্যবহৃত হয়েছিল। এটি বড় আকারের ক্লাস্টারিং সমস্যাগুলিতেও প্রয়োগ করা হয়েছে, যেমন ক্লাস্টারিং নথিগুলি তাদের শব্দের সেটগুলির সাদৃশ্য দ্বারা। জ্যাকার্ডের সাদৃশ্য এবং ন্যূনতম হ্যাশ মান জ্যাকার্ডের সাদৃশ্য সহগ দুটি সেটের মধ্যে সাদৃশ্যের একটি সাধারণভাবে ব্যবহৃত সূচক। একটি সেট এবং এর উপসেট হতে দিন, তারপর জ্যাকার্ড সূচককে তাদের ছেদকারী উপাদানগুলির সংখ্যা এবং তাদের মিলনের উপাদানগুলির সংখ্যার অনুপাত হিসাবে সংজ্ঞায়িত করা হয়ঃ এই মানটি 0 হয় যখন দুটি সেট বিচ্ছিন্ন হয়, 1 যখন তারা সমান হয়, এবং অন্যথায় কঠোরভাবে 0 এবং 1 এর মধ্যে থাকে। দুটি সেট আরও অনুরূপ (অর্থাৎ। তুলনামূলকভাবে বেশি সদস্য রয়েছে) যখন তাদের জ্যাককার্ড সূচক 1-এর কাছাকাছি থাকে। মিনহ্যাশের লক্ষ্য হল ছেদ এবং সংযোগ স্পষ্টভাবে গণনা না করে দ্রুত অনুমান করা। একটি হ্যাশ ফাংশন হতে দিন যা সদস্যদের স্বতন্ত্র পূর্ণসংখ্যায় ম্যাপ করে, সেটের উপাদানগুলির একটি এলোমেলো বিন্যাস হতে দিন এবং সংজ্ঞার যে কোনও উপসেটের জন্য ন্যূনতম সদস্য হতে হবে-অর্থাৎ ন্যূনতম মান সহ সদস্য। (যে ক্ষেত্রে ব্যবহৃত হ্যাশ ফাংশনের ছদ্ম-এলোমেলো বৈশিষ্ট্য রয়েছে বলে ধরে নেওয়া হয়, সেখানে এলোমেলো বিন্যাস ব্যবহার করা হবে না।) এখন, এবং উভয় ক্ষেত্রেই প্রয়োগ করে, এবং কোনও হ্যাশ সংঘর্ষ ধরে না নিয়ে, আমরা দেখতে পাই যে মানগুলি সমান () যদি এবং শুধুমাত্র যদি সমস্ত উপাদানের মধ্যে, ন্যূনতম হ্যাশ মান সহ উপাদানটি ছেদস্থলে থাকে। এটি সত্য হওয়ার সম্ভাবনা ঠিক জ্যাককার্ড সূচক, তাইঃ অর্থাৎ, যে সম্ভাবনাটি সত্য তা সাদৃশ্যের সমান, একটি অভিন্ন বন্টন থেকে অঙ্কন ধরে নেওয়া। অন্য কথায়, যদি এলোমেলো পরিবর্তনশীল হয় যা কখন এক এবং অন্যথায় শূন্য হয়, তবে এটি একটি নিরপেক্ষ প্রাক্কলনকারী। জ্যাককার্ডের সাদৃশ্যের জন্য একটি দরকারী প্রাক্কলনকারী হওয়ার জন্য খুব বেশি বৈচিত্র্য রয়েছে, কারণ এটি সর্বদা শূন্য বা এক। মিনহ্যাশ স্কিমের ধারণাটি হল একইভাবে নির্মিত বেশ কয়েকটি ভেরিয়েবল একসাথে গড় করে এই বৈচিত্র্য হ্রাস করা। অনেক হ্যাশ ফাংশন সহ অ্যালগরিদম ভ্যারিয়েন্ট মিন্যাশ স্কিমের সহজতম সংস্করণ বিভিন্ন হ্যাশ ফাংশন ব্যবহার করে, যেখানে একটি নির্দিষ্ট পূর্ণসংখ্যা পরামিতি রয়েছে এবং এই ফাংশনগুলির মান দ্বারা প্রতিটি সেটকে উপস্থাপন করে। পরিকল্পনার এই সংস্করণটি ব্যবহার করে অনুমান করার জন্য, ধরা যাক হ্যাশ ফাংশনের সংখ্যা যার জন্য, এবং অনুমান হিসাবে ব্যবহার করুন। এই অনুমানটি বিভিন্ন 0-1 র্যান্ডম ভেরিয়েবলের গড়, যার প্রতিটি কখন এক এবং অন্যথায় শূন্য, এবং যার প্রতিটি একটি নিরপেক্ষ অনুমানকারী। অতএব, তাদের গড়ও একটি নিরপেক্ষ অনুমানকারী, এবং 0-1 র্যান্ডম ভেরিয়েবলের যোগফলের জন্য স্ট্যান্ডার্ড বিচ্যুতি দ্বারা, এর প্রত্যাশিত ত্রুটি হল। অতএব, যে কোনও ধ্রুবকের জন্য একটি ধ্রুবক থাকে যাতে অনুমানের প্রত্যাশিত ত্রুটি সর্বাধিক হয়। উদাহরণস্বরূপ,. 05 এর চেয়ে কম বা সমান একটি প্রত্যাশিত ত্রুটি অনুমান করার জন্য 400 টি হ্যাশের প্রয়োজন হবে। একক হ্যাশ ফাংশনের সাথে বৈকল্পিক একাধিক হ্যাশ ফাংশন গণনা করা গণনামূলকভাবে ব্যয়বহুল হতে পারে, তবে মিনহ্যাশ স্কিমের একটি সম্পর্কিত সংস্করণ শুধুমাত্র একটি হ্যাশ ফাংশন ব্যবহার করে এই পেনাল্টি এড়ায় এবং প্রতি হ্যাশ ফাংশনে শুধুমাত্র একটি ন্যূনতম মান নির্বাচন করার পরিবর্তে প্রতিটি সেট থেকে একাধিক মান নির্বাচন করতে এটি ব্যবহার করে। ধরা যাক একটি হ্যাশ ফাংশন, এবং একটি নির্দিষ্ট পূর্ণসংখ্যা। যদি ডোমেনের কোনও সেট বা আরও বেশি মান থাকে, তবে সদস্যদের উপসেট হিসাবে সংজ্ঞায়িত করুন যার সর্বনিম্ন মান রয়েছে। এই উপসেটটি সেটের জন্য স্বাক্ষর হিসাবে ব্যবহৃত হয় এবং যে কোনও দুটি সেটের সাদৃশ্য তাদের স্বাক্ষরের তুলনা করে অনুমান করা হয়। বিশেষ করে, এ এবং বি যে কোনও দুটি সেট হতে দিন। তারপর k উপাদানগুলির একটি সেট, এবং যদি h একটি র্যান্ডম ফাংশন হয় তবে k উপাদানগুলির যে কোনও উপসেট সমানভাবে নির্বাচিত হওয়ার সম্ভাবনা রয়েছে; অর্থাৎ, এর একটি সাধারণ র্যান্ডম নমুনা। উপসেট হল ছেদস্থলের অন্তর্গত সদস্যদের সমষ্টি। অতএব,।। একটি নিরপেক্ষ প্রাক্কলনকারী। এই প্রাক্কলনকারী এবং একাধিক হ্যাশ ফাংশন দ্বারা উত্পাদিত প্রাক্কলনকারীর মধ্যে পার্থক্য হল যে সর্বদা ঠিক সদস্য থাকে, যেখানে একাধিক হ্যাশ ফাংশন দুটি ভিন্ন হ্যাশ ফাংশনের একই মিনিমা থাকার সম্ভাবনার কারণে কম সংখ্যক নমুনা উপাদানের দিকে নিয়ে যেতে পারে। যাইহোক, যখন সেটগুলির আকারের তুলনায় ছোট হয়, তখন এই পার্থক্যটি নগণ্য। প্রতিস্থাপন ছাড়াই নমুনা সংগ্রহের জন্য স্ট্যান্ডার্ড চেরনফ সীমা দ্বারা, এই প্রাক্কলনকারী একাধিক-হ্যাশ-ফাংশন স্কিমের কার্যকারিতার সাথে মেলে ত্রুটি আশা করেছেন। সময় বিশ্লেষণ পরিকল্পনার যে কোনও সংস্করণে প্রদত্ত সেটগুলির দুটি স্বাক্ষর থেকে প্রাক্কলনকারীকে সময়মতো গণনা করা যেতে পারে। অতএব, কখন এবং কখন ধ্রুবক, স্বাক্ষর থেকে আনুমানিক মিল গণনা করার সময়ও ধ্রুবক। প্রতিটি সেটের স্বাক্ষর সেটের আকারের উপর রৈখিক সময়ে গণনা করা যেতে পারে, তাই যখন অনেক জোড়ার সাদৃশ্য অনুমান করার প্রয়োজন হয় তখন এই পদ্ধতিটি প্রতিটি সেটের সদস্যদের সম্পূর্ণ তুলনা করার তুলনায় চলমান সময়ে যথেষ্ট সঞ্চয় করতে পারে। বিশেষত, সেট আকারের জন্য অনেক হ্যাশ বৈকল্পিক সময় নেয়। একক হ্যাশ বৈকল্পিক সাধারণত দ্রুত হয়, অনুমান করে ন্যূনতম হ্যাশ মানগুলির সারি বজায় রাখতে সময়ের প্রয়োজন হয়। ওজন অন্তর্ভুক্ত করা মিনহ্যাশ গণনায় ওজন প্রবর্তনের জন্য বিভিন্ন কৌশল তৈরি করা হয়েছে। সহজতমটি এটিকে পূর্ণসংখ্যা ওজনে প্রসারিত করে। একটি সেট সদস্য এবং একটি পূর্ণসংখ্যা উভয়ই গ্রহণ করার জন্য আমাদের হ্যাশ ফাংশনটি প্রসারিত করুন, তারপরে প্রতিটি আইটেমের ওজন অনুযায়ী একাধিক হ্যাশ তৈরি করুন। যদি জিনিসটি বার বার ঘটে, তাহলে হ্যাশ তৈরি করুন। হ্যাশের এই প্রসারিত সেটটিতে মূল অ্যালগরিদমটি চালান। এটি করার ফলে সংঘর্ষের সম্ভাবনা হিসাবে ওজনযুক্ত জ্যাককার্ড সূচক পাওয়া যায়। আরও এক্সটেনশন যা আরও ভাল রানটাইম সহ বাস্তব ওজনের উপর এই সংঘর্ষের সম্ভাবনা অর্জন করে তা তৈরি করা হয়েছে, একটি ঘন ডেটার জন্য এবং অন্যটি বিরল ডেটার জন্য। এক্সটেনশনের আরেকটি পরিবার সূচকীয়ভাবে বিতরণকৃত হ্যাশ ব্যবহার করে। 0 এবং 1 এর মধ্যে একটি অভিন্ন র্যান্ডম হ্যাশকে সি. ডি. এফ ইনভার্সন দ্বারা একটি সূচকীয় বন্টন অনুসরণ করতে রূপান্তরিত করা যেতে পারে। এই পদ্ধতিটি এক্সপোনেনশিয়াল ভেরিয়েবলের ন্যূনতম সেটের অনেক সুন্দর বৈশিষ্ট্যকে কাজে লাগায়। এটি তার সংঘর্ষের সম্ভাবনা হিসাবে জ্যাককার্ড সূচকের ন্যূনতম-ভিত্তিক স্বাধীন বিন্যাস প্রদান করে। উপরে বর্ণিত মিনহ্যাশ স্কিমটি বাস্তবায়িত করার জন্য, উপাদানগুলির উপর একটি এলোমেলো বিন্যাস সংজ্ঞায়িত করার জন্য হ্যাশ ফাংশন প্রয়োজন, যেখানে সমস্ত সেটের সংযোগে স্বতন্ত্র উপাদানগুলির মোট সংখ্যা তুলনা করা হবে। কিন্তু যেহেতু বিভিন্ন বিন্যাস রয়েছে, তাই এর জন্য শুধুমাত্র একটি সত্যিকারের এলোমেলো বিন্যাস নির্দিষ্ট করার জন্য বিটের প্রয়োজন হবে, যা এর এমনকি মাঝারি মানের জন্য একটি অবিশ্বাস্যভাবে বড় সংখ্যা। এই কারণে, সার্বজনীন হ্যাশিং তত্ত্বের সাথে সাদৃশ্য রেখে, "ন্যূনতম-ভিত্তিক স্বাধীন" বিন্যাসের একটি পরিবার খুঁজে বের করার জন্য উল্লেখযোগ্য কাজ করা হয়েছে, যার অর্থ যে কোনও ডোমেনের উপসেটের জন্য, যে কোনও উপাদান ন্যূনতম হওয়ার সমান সম্ভাবনা রয়েছে। এটি প্রতিষ্ঠিত হয়েছে যে, বিন্যাসের একটি ন্যূনতম-ভিত্তিক স্বাধীন পরিবারে অবশ্যই কমপক্ষে বিভিন্ন বিন্যাস অন্তর্ভুক্ত থাকতে হবে, এবং তাই একক বিন্যাস নির্দিষ্ট করার জন্য এটির বিট প্রয়োজন, যা এখনও অসম্ভবভাবে বড়। ব্যবহারিক ন্যূনতম-ভিত্তিক স্বাধীন হ্যাশ ফাংশন উপরোক্ত অবাস্তবতার কারণে, ন্যূনতম-ভিত্তিক স্বাধীনতার দুটি বৈকল্পিক ধারণা চালু করা হয়েছেঃ সীমাবদ্ধ ন্যূনতম-ভিত্তিক স্বাধীন বিন্যাস পরিবার এবং আনুমানিক ন্যূনতম-ভিত্তিক স্বাধীন পরিবার। সীমাবদ্ধ ন্যূনতম-ভিত্তিক স্বাধীনতা হল ন্যূনতম-ভিত্তিক স্বাধীনতা সম্পত্তি যা সর্বাধিক কার্ডিনালিটির নির্দিষ্ট সেটের মধ্যে সীমাবদ্ধ। আনুমানিক ন্যূনতম-ভিত্তিক স্বাধীনতার সর্বাধিক পূর্ণ স্বাধীনতা থেকে পরিবর্তিত হওয়ার একটি নির্দিষ্ট সম্ভাবনা রয়েছে। 1999 সালে পিওটর ইন্ডিক প্রমাণ করেন যে হ্যাশ ফাংশনের যে কোনও কে-ভিত্তিক স্বাধীন পরিবারও যথেষ্ট বড়ের জন্য প্রায় ন্যূনতম-ভিত্তিক স্বাধীন। বিশেষত, এমন ধ্রুবক রয়েছে যে যদি, তারপর সমস্ত সেটের জন্য এবং। (লক্ষ্য করুন, এখানে এর অর্থ হল সম্ভাব্যতা সর্বাধিক একটি ফ্যাক্টর খুব বড়, এবং সর্বাধিক খুব ছোট।) এই নিশ্চয়তা, অন্যান্য বিষয়ের মধ্যে, মিনহ্যাশ অ্যালগরিদম দ্বারা প্রয়োজনীয় জ্যাককার্ড বাঁধা দেওয়ার জন্য যথেষ্ট। অর্থাৎ, যদি এবং সেট হয়, তাহলে যেহেতু কে-ভিত্তিক স্বাধীন হ্যাশ ফাংশনগুলি কেবল বিট ব্যবহার করে নির্দিষ্ট করা যেতে পারে, তাই এই পদ্ধতিটি সম্পূর্ণ ন্যূনতম-ভিত্তিক স্বাধীন বিন্যাস ব্যবহার করার চেয়ে অনেক বেশি ব্যবহারিক। হ্যাশ ফাংশনের আরেকটি ব্যবহারিক পরিবার যা আনুমানিক ন্যূনতম-ভিত্তিক স্বাধীনতা দেয় তা হল ট্যাবুলেশন হ্যাশিং। অ্যাপ্লিকেশন মিনহ্যাশের মূল অ্যাপ্লিকেশনগুলিতে ওয়েব নথির মধ্যে ক্লাস্টারিং এবং প্রায়-ডুপ্লিকেটগুলি বাদ দেওয়া জড়িত ছিল, যা সেই নথিতে উপস্থিত শব্দের সেট হিসাবে উপস্থাপিত হয়। অনুরূপ কৌশলগুলি অন্যান্য ধরনের তথ্যের জন্য ক্লাস্টারিং এবং প্রায়-ডুপ্লিকেট নির্মূলের জন্যও ব্যবহার করা হয়েছে, যেমন চিত্রঃ চিত্রের তথ্যের ক্ষেত্রে, একটি চিত্রকে এটি থেকে ক্রপ করা ছোট ছোট উপ-চিত্রের সেট হিসাবে বা আরও জটিল চিত্র বৈশিষ্ট্য বর্ণনার সেট হিসাবে উপস্থাপন করা যেতে পারে। ডেটা মাইনিং-এ, অ্যাসোসিয়েশন রুল লার্নিং-এর একটি হাতিয়ার হিসাবে মিনহ্যাশ ব্যবহার করুন। একটি ডাটাবেস দেওয়া হয়েছে যেখানে প্রতিটি এন্ট্রির একাধিক বৈশিষ্ট্য রয়েছে (প্রতি ডাটাবেস এন্ট্রির একটি সারি এবং প্রতি বৈশিষ্ট্যের একটি কলাম সহ 0-1 ম্যাট্রিক্স হিসাবে দেখা হয়) তারা জ্যাককার্ড সূচকে মিনহ্যাশ-ভিত্তিক আনুমানিক ব্যবহার করে এমন বৈশিষ্ট্যগুলির প্রার্থী জোড়া সনাক্ত করতে যা প্রায়শই সহ-ঘটে এবং তারপরে কেবল সেই জোড়াগুলির জন্য সূচকের সঠিক মান গণনা করে যাদের সহ-ঘটনার ফ্রিকোয়েন্সি প্রদত্ত কঠোর সীমার নিচে রয়েছে। মিনহ্যাশ অ্যালগরিদমটি বায়োইনফরম্যাটিক্সের জন্য অভিযোজিত হয়েছে, যেখানে জিনোম সিকোয়েন্সের তুলনা করার সমস্যাটি ওয়েবে নথির তুলনা করার মতো একই তাত্ত্বিক ভিত্তি রয়েছে। মিনহ্যাশ-ভিত্তিক সরঞ্জামগুলি রেফারেন্স জিনোমের সাথে পুরো জিনোম সিকোয়েন্সিং ডেটার দ্রুত তুলনা করার অনুমতি দেয় (রেফসেক-এর 90000 রেফারেন্স জিনোমের সাথে একটি জিনোমের তুলনা করার জন্য প্রায় 3 মিনিট), এবং প্রজাতির জন্য উপযুক্ত এবং সম্ভবত সীমিত মাত্রায় মাইক্রোবিয়াল সাব-টাইপিংয়ের জন্য উপযুক্ত। জিনোম সারিবদ্ধকরণ এবং জিনোম সমাবেশের জন্য মেটাজেনমিক্স এবং মিনহ্যাশ উদ্ভূত অ্যালগরিদম ব্যবহারের জন্যও প্রয়োগ রয়েছে। মিনহ্যাশ-ভিত্তিক অ্যালগরিদমগুলির সাহায্যে সঠিক গড় নিউক্লিওটাইড পরিচয় (এএনআই) মানগুলি খুব দক্ষতার সাথে তৈরি করা যেতে পারে। অন্যান্য ব্যবহার মিনহ্যাশ স্কিমকে স্থানীয়-সংবেদনশীল হ্যাশিংয়ের একটি উদাহরণ হিসাবে দেখা যেতে পারে, হ্যাশ ফাংশনগুলি ব্যবহার করার জন্য কৌশলগুলির একটি সংগ্রহ যাতে বড় আকারের বস্তুর সেটগুলি ছোট হ্যাশ মানগুলিতে এমনভাবে ম্যাপ করা যায় যে, যখন দুটি বস্তুর একে অপরের থেকে সামান্য দূরত্ব থাকে, তখন তাদের হ্যাশ মানগুলি একই হতে পারে। এই ক্ষেত্রে, একটি সেটের স্বাক্ষরকে তার হ্যাশ মান হিসাবে দেখা যেতে পারে। ভেক্টরগুলির মধ্যে সেট এবং কোসাইন দূরত্বের মধ্যে হ্যামিং দূরত্বের জন্য অন্যান্য স্থানীয় সংবেদনশীল হ্যাশিং কৌশল বিদ্যমান; স্থানীয় সংবেদনশীল হ্যাশিংয়ের নিকটতম প্রতিবেশী অনুসন্ধান অ্যালগরিদমগুলিতে গুরুত্বপূর্ণ প্রয়োগ রয়েছে। বড় ডিস্ট্রিবিউটেড সিস্টেমের জন্য, এবং বিশেষ করে ম্যাপরেডিউসের জন্য, মিনহ্যাশের পরিবর্তিত সংস্করণ রয়েছে যা বিন্দুর মাত্রার উপর কোনও নির্ভরতা ছাড়াই সাদৃশ্য গণনা করতে সহায়তা করে। মূল্যায়ন এবং মানদণ্ড মিনহাশ এবং সিমহাশ অ্যালগরিদমের কার্যকারিতার তুলনা করার জন্য 2006 সালে গুগল দ্বারা একটি বড় আকারের মূল্যায়ন পরিচালিত হয়েছিল। 2007 সালে গুগল ওয়েব ক্রলিং এবং গুগল নিউজ ব্যক্তিগতকরণের জন্য মিনহাশ এবং এলএসএইচ ব্যবহার করার জন্য নকল সনাক্তকরণের জন্য সিমহাশ ব্যবহার করার কথা জানায়। আরও দেখুন রেফারেন্স হ্যাশ ফাংশন ক্লাস্টারিং মানদণ্ড হ্যাশিং সম্ভাব্য তথ্য কাঠামো