فایل ورد کامل الگوریتم های داده جریانی برای آزمون کولموگروف – اسمیرنوف

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

این مقاله، ترجمه شده یک مقاله مرجع و معتبر انگلیسی می باشد که به صورت بسیار عالی توسط متخصصین این رشته ترجمه شده است و به صورت فایل ورد (microsoft word) ارائه می گردد

متن داخلی مقاله بسیار عالی، پر محتوا و قابل درک می باشد و شما از استفاده ی آن بسیار لذت خواهید برد. ما عالی بودن این مقاله را تضمین می کنیم

فایل ورد این مقاله بسیار خوب تایپ شده و قابل کپی و ویرایش می باشد و تنظیمات آن نیز به صورت عالی انجام شده است؛ به همراه فایل ورد این مقاله یک فایل پاور پوینت نیز به شما ارئه خواهد شد که دارای یک قالب بسیار زیبا و تنظیمات نمایشی متعدد می باشد

توجه : در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی فایل ورد کامل الگوریتم های داده جریانی برای آزمون کولموگروف – اسمیرنوف،به هیچ وجه بهم ریختگی وجود ندارد

تعداد صفحات این فایل: ۲۹ صفحه

  نتایج
دراین مقاله مسئله عملکرد آزمون KS برروی جریان داده را درنظرگرفتیم. ما الگوریتم هایی برای هردو نسخه یک نمونه ای و دونمونه ای همراه با تضمین عملکرد آنها ارائه کردیم. الگوریتم های ما ازتکنیک هایی برای محاسبه چندک ها درجریان استفاده می کنند و ازاین رو، ممکن است نتایج بهتری وقتی پیشرفت بیشتری برروی این مسئله رخ دهد، داشته باشند. علاوه برآن، ما با آزمایش برروی داده واقعی و ترکیبی نشان می دهیم که الگوریتم های پیشنهادشده قادرند آزمون را با کاهش دودرجه بزرگی در اندازه داده انجام دهند. همچنین آزمایشات ما نشان می-دهد که طرح GK بهترین تطبیق را برای الگوریتم ما دارد و به طور چشمگیری نسبت به دیگر تکنیک ها نظیر نمونه سازی برتری دارد.
چندین مسئله بازدیگر هنوز باقی مانده است. الگوریتم های پیشنهادشده دراین مقاله نیازبه نمونه های O(n logn) دارد وباز باقی می ماند تا وقتی این مورد بیشتر کاهش یابد. اگرچه الگوریتم پیشنهادشده در این مقاله ازطرح های چندک استفاده می کند، وازاین رو فضای استفاده یکسانی همچون آنها دارد، اما وجود الگوریتم تست شده که ازفضای کمتر مجانبی نسبت به دیگرطرح های چندک استفاده کند، نامعلوم است. پیداکردن چنین الگوریتمی یا متعاقبا اثبات اینکه هرطرح چندک باید از فضای بیشتری همچون تست الگوریتم استفاده کند، جالب خواهدبود. باتوجه به آزمایشات، طراحی دیگر الگوریتم های چندک که به سمت بهبود دقت نتایج الگوریتم آزمون KS در این مقاله هدف گیری کنند، نیز جالب خواهد بود.
همچنین بسیاری ازآزمون های عددی دیگر، هم پارامتری و هم غیرپارامتری، وجود دارد که الگوریتم های جریانی مشخصی ندارند. شناسایی اینکه کدام یک الگوریتم های فضای زیرخطی دارند و توسعه این الگوریتم ها زمینه دیگری برای تحقیقات آینده می باشد.

عنوان انگلیسی:Data Streaming Algorithms for the Kolmogorov-Smirnov Test~~en~~

VIII. CONCLUSIONS

In this paper, we considered the problem of performing the Kolmogorov-Smirnov test on streaming data. We gave algorithms for both the one-sample and the two-sample versions of the test, along with guarantees of their performance. Our algorithms make use of the techniques for computing quantiles on a stream and hence may have improved results when further progress is made on this problem. Moreover, we show via experiments on real and synthetic data that the proposed algorithms are capable of performing the test with a two order magnitude reduction in the size of the data. Our experiments also showed that the Greenwald-Khanna sketch is best suited for our algorithm, and that it is considerably 104 superior to other simple techniques such as sampling. There are several open problems that still remain. The algorithms proposed in this paper need O( n log n) samples, and it remains open whether this can be further reduced. While the algorithm proposed in this paper makes use of quantile sketches, and hence has the same space usage as them, it is unclear whether a testing algorithm exists that uses asymptotically less space than any quantile sketch. It would be interesting to find such an algorithm, or alternatively to prove that any quantile sketch must use as much space as any testing algorithm. From the experimental side, it would be interesting to design other quantile algorithms that are targeted towards improving the accuracy of the result of the KS test algorithm in this paper. There are also many other statistical tests, both parametric and non-parametric, that do not have known streaming algorithms. Identifying which ones have sublinear space algorithms and developing these algorithms is another avenue for future work.

$$en!!