হয়েফডিং ট্রি অ্যালগরিদম কী?

হোফডিং ট্রি অ্যালগরিদম হল স্ট্রীম ডেটা শ্রেণীবিভাগের জন্য একটি সিদ্ধান্ত গাছ শেখার পদ্ধতি। এটি প্রাথমিকভাবে ওয়েব ক্লিকস্ট্রিমগুলি ট্র্যাক করতে এবং ব্যবহারকারীর কোন ওয়েব হোস্ট এবং ওয়েব সাইটগুলি অ্যাক্সেস করার সম্ভাবনা রয়েছে তা ভবিষ্যদ্বাণী করতে মডেল তৈরি করতে ব্যবহৃত হয়েছিল। এটি সাধারণত সাবলাইনার টাইমে চলে এবং প্রথাগত ব্যাচের শিক্ষার্থীদের মতো প্রায় অভিন্ন সিদ্ধান্তের গাছ তৈরি করে।

এটি Hoeffding গাছ ব্যবহার করে, যা এই ধারণাটিকে কাজে লাগায় যে একটি ছোট নমুনা প্রায়শই একটি সর্বোত্তম বিভাজন বৈশিষ্ট্য বেছে নেওয়ার জন্য যথেষ্ট হতে পারে। এই ধারণা গাণিতিকভাবে Hoeffding আবদ্ধ (বা সংযোজন চেরনফ আবদ্ধ) দ্বারা সমর্থিত।

ধরুন আমরা রেঞ্জ R সহ একটি এলোমেলো পরিবর্তনশীল r-এর N স্বাধীন পর্যবেক্ষণ করি, যেখানে r হল একটি বৈশিষ্ট্য নির্বাচন পরিমাপ। (একটি সম্ভাব্যতার জন্য, R হল একটি, এবং একটি তথ্য লাভের জন্য, এটি হল লগ c, যেখানে c হল শ্রেণীর সংখ্যা।) Hoeffding গাছের ক্ষেত্রে, r হল তথ্য লাভ। যদি আমরা এই নমুনার গড়, r’, গণনা করি, Hoeffding বাউন্ড বলে যে r-এর প্রকৃত গড় কমপক্ষে r’−ε, সম্ভাব্যতা 1−δ সহ, যেখানে δ ব্যবহারকারী-নির্দিষ্ট এবং

$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$

Hoeffding Tree অ্যালগরিদম Hoeffding বাউন্ড ব্যবহার করে, উচ্চ সম্ভাবনা সহ, একটি বিভাজন বৈশিষ্ট্য নির্বাচন করার সময় একটি নোডে প্রয়োজনীয় উদাহরণগুলির ক্ষুদ্রতম সংখ্যা, N, নির্ধারণ করতে। Hoeffding আবদ্ধ সম্ভাব্যতা বন্টন থেকে স্বাধীন, অন্যান্য আবদ্ধ সমীকরণ থেকে ভিন্ন। এটি বাঞ্ছনীয়, কারণ তথ্য লাভের সম্ভাব্যতা বণ্টন বা যে কোনো বৈশিষ্ট্য নির্বাচন পরিমাপ ব্যবহার করা হয় তা জানা অসম্ভব।

অ্যালগরিদম ইনপুট হিসাবে প্রশিক্ষণ উদাহরণের একটি ক্রম নেয়, S, বৈশিষ্ট্য A দ্বারা বর্ণিত, এবং সঠিকতা পরামিতি, δ। মূল্যায়ন ফাংশন G(A_i ) সরবরাহ করা হয়, যা তথ্য লাভ, লাভ অনুপাত, জিনি সূচক, বা অন্য কিছু বৈশিষ্ট্য নির্বাচন পরিমাপ হতে পারে। সিদ্ধান্ত গাছের প্রতিটি নোডে, আমাদের G (A_i) সর্বাধিক করতে হবে ) অবশিষ্ট বৈশিষ্ট্যগুলির একটির জন্য, A_i . লক্ষ্য হল ক্ষুদ্রতম সংখ্যক টিপল, N খুঁজে বের করা, যার জন্য Hoeffding বাউন্ড সন্তুষ্ট।

অ্যালগরিদম ইনপুট হিসাবে প্রশিক্ষণ উদাহরণের একটি ক্রম গ্রহণ করে, S, বৈশিষ্ট্য A দ্বারা বর্ণিত, এবং সঠিকতা পরামিতি, δ। মূল্যায়ন ফাংশন G(A_i ) সরবরাহ করা হয়, যা তথ্য লাভ, লাভ অনুপাত, জিনি সূচক, বা অন্য কিছু বৈশিষ্ট্য নির্বাচন পরিমাপ হতে পারে। সিদ্ধান্ত গাছের প্রতিটি নোডে, আমাদের G (A_i) সর্বাধিক করতে হবে ) অবশিষ্ট বৈশিষ্ট্যগুলির একটির জন্য, A_i . লক্ষ্য হল ক্ষুদ্রতম সংখ্যক টিপল, N খুঁজে বের করা, যার জন্য Hoeffding বাউন্ড সন্তুষ্ট।

প্রদত্ত নোডের জন্য, A_a দিন যে অ্যাট্রিবিউটটি সর্বোচ্চ G অর্জন করে এবং Abbe সেই অ্যাট্রিবিউট যা দ্বিতীয়-সর্বোচ্চ G অর্জন করে। যদি G(A_a ) − G(A_b )> ε, যেখানে ε গণনা করা হয়।

Hoeffding গাছের অ্যালগরিদমে যে পরিসংখ্যানগুলি বজায় রাখতে হবে তা হল গণনা n_ijk v_j মানের জন্য A_i বৈশিষ্ট্যের ক্লাস লেবেল y_k সহ . তাই, যদি d হল অ্যাট্রিবিউটের সংখ্যা, v হল যে কোনও অ্যাট্রিবিউটের জন্য সর্বাধিক সংখ্যক মানের, c হল ক্লাসের সংখ্যা এবং l হল গাছের সর্বোচ্চ গভীরতা (বা স্তরের সংখ্যা), তাহলে মোট মেমরির প্রয়োজন O (ldvc) হয়।