მონაცემთა მედიანის პოვნის ტექნიკა

მონაცემთა მედიანის პოვნის ტექნიკა

მედიანა არის ცენტრალური ტენდენციის საზომი, რომელიც მონაცემთა ნაკრებას ორ თანაბარ ნაწილად ყოფს. საშუალო მნიშვნელობისგან განსხვავებით, რომლის გადახრაც შესაძლებელია გამონაკლისებით, მედიანა ცენტრალური მნიშვნელობის საიმედო მაჩვენებელს იძლევა. მედიანის პოვნა აუცილებელია სხვადასხვა სამეცნიერო, საინჟინრო, სოციალურ მეცნიერებებსა და ბიზნეს გამოყენებაში. ეს სტატია განიხილავს მონაცემთა მედიანის პოვნის რამდენიმე ტექნიკას, რომელიც მოიცავს როგორც ერთცვლადიან, ასევე მრავალცვლადიან მონაცემთა ნაკრებებს, ასევე მარტივ და უფრო რთულ მეთოდებს.

მედიანის გაგება

ტექნიკის შესწავლამდე მნიშვნელოვანია განვსაზღვროთ, თუ რა არის მედიანა. მედიანა არის მნიშვნელობა, რომელიც მონაცემთა ნაკრების ზედა ნახევარს ქვედა ნახევრისგან ჰყოფს. დახარისხებულ სიაში, თუ დაკვირვებების რაოდენობა (\(n\)) კენტია, მედიანა შუა ელემენტია. თუ \(n\) ლუწია, მედიანა ორი შუა ელემენტის საშუალოა.

მაგალითად, განვიხილოთ მონაცემთა ნაკრები \([3, 5, 7, 9]\). 4 ელემენტის შემთხვევაში, მედიანა არის \(\frac{5+7}{2} = 6\). კენტი რიცხვის მქონე მონაცემთა ნაკრებისთვის, როგორიცაა \([3, 5, 7]\), მედიანა არის 5.

მედიანის პოვნის ძირითადი ტექნიკა

1. დახარისხებისა და შერჩევის მეთოდი

მედიანის პოვნის ყველაზე მარტივი მეთოდია მონაცემების დახარისხება და შემდეგ საშუალო მნიშვნელობის არჩევა.

– ნაბიჯი 1: დაალაგეთ მონაცემთა ნაკრები ზრდადი თანმიმდევრობით.
– ნაბიჯი 2: თუ \(n\) კენტია, მედიანა არის ელემენტი \(\frac{n+1}{2}\) პოზიციაზე.
– ნაბიჯი 3: თუ \(n\) ლუწია, მედიანა არის ელემენტების საშუალო \(\frac{n}{2}\) და \(\frac{n}{2}+1\) პოზიციებზე.

ეს მეთოდი კარგად მუშაობს მცირე და საშუალო ზომის მონაცემთა ნაკრებებისთვის და მისი განხორციელება მარტივია. თუმცა, დახარისხების ნაბიჯი შეიძლება გამოთვლით ძვირი იყოს ძალიან დიდი მონაცემთა ნაკრებებისთვის, რომელთა დროის სირთულეა \(O(n \log n)\).

2. QuickSelect ალგორითმი

დიდი მონაცემთა ნაკრებებისთვის, QuickSelect ალგორითმი უფრო ეფექტურ მიდგომას გვთავაზობს. ის მუშაობს იმავე პრინციპით, როგორც QuickSort ალგორითმი, მაგრამ ფოკუსირებულია მხოლოდ k-ური უმცირესი ელემენტის პოვნაზე, სადაც \(k\) მედიანის პოზიციაა.

– ნაბიჯი 1: მონაცემთა ნაკრებიდან აირჩიეთ pivot ელემენტი.
– ნაბიჯი 2: მონაცემთა ნაკრები დაყავით ელემენტებად, რომლებიც ნაკლებია, ტოლია და მეტია პივოტზე.
– ნაბიჯი 3: განსაზღვრეთ, რომელ დანაყოფში ხვდება მედიანა და იტერაციულად გამოიყენეთ პროცესი მხოლოდ ამ დანაყოფზე.

QuickSelect-ის დროის სირთულე საშუალოდ \(O(n)\)-ია, რაც მას უფრო დიდი მონაცემთა ნაკრებებისთვის შესაფერისს ხდის.

მედიანა სიხშირის განაწილებაში

სიხშირის განაწილებასთან დაკავშირებით, მედიანა შეიძლება შეფასდეს და არა ზუსტად გამოითვალოს.

– კლასის ინტერვალის მეთოდი: ეს მეთოდი გულისხმობს მედიანური კლასის იდენტიფიცირებას — კლასის, სადაც კუმულაციური სიხშირე პირველად აღემატება მთლიანი სიხშირის ნახევარს.

დაჯგუფებული სიხშირის განაწილებებში მედიანის შეფასების ფორმულაა:

მედიანა = L + \left( \frac{\frac{N}{2} – CF}{f} \right) \times w \]

სადაც L არის მედიანური კლასის ქვედა საზღვარი, N არის სრული სიხშირე, CF არის მედიანურ კლასამდე კლასის კუმულაციური სიხშირე, f არის მედიანური კლასის სიხშირე და w არის კლასის სიგანე.

მედიანა მრავალვარიანტულ მონაცემებში

მრავალვარიანტული მონაცემთა ნაკრებები, სადაც თითოეული მონაცემთა წერტილი მრავალი ცვლადისგან შედგება, მედიანის პოვნის უფრო რთულ სცენარს წარმოადგენს.

– ზღვრული მედიანის მეთოდი: თითოეული ცვლადისთვის მედიანის ინდივიდუალურად გამოთვლა და ამ მნიშვნელობების გამოყენება მედიანის ვექტორის შესაქმნელად. სიმარტივის მიუხედავად, ეს მეთოდი არ ითვალისწინებს ცვლადებს შორის კავშირებს.

– გეომეტრიული მედიანა: ეს არის წერტილი, რომელიც მინიმუმამდე ამცირებს ევკლიდური მანძილების ჯამს მრავალცვლადიან მონაცემთა ნაკრებში ყველა მონაცემთა წერტილამდე. მისი პოვნა შესაძლებელია ისეთი იტერაციული მეთოდების გამოყენებით, როგორიცაა ვაისფელდის ალგორითმი, რომელიც იტერაციების განმავლობაში კონვერგირებს გეომეტრიულ მედიანასთან.

მედიანა დიდ მონაცემთა ნაკრებებში

დიდ მონაცემთა ნაკრებებში მედიანის პოვნა შეიძლება ოპტიმიზებული იყოს სხვადასხვა ტექნიკის გამოყენებით.

– ნაკადის ალგორითმები: იმ სცენარებში, როდესაც მონაცემთა ნაკრები ძალიან დიდია მეხსიერებაში მოსათავსებლად ან იკითხება ნაკადის სახით:

– მინიმალური და მაქსიმალური გროვის კომბინაცია: ორი გროვის შენარჩუნებით, ერთი მონაცემთა ქვედა ნახევრისთვის და მეორე მონაცემთა ზედა ნახევრისთვის, მედიანის ეფექტურად მოძიება შესაძლებელია. ჩასმის დროის სირთულეა \(O(\log n)\), ხოლო მედიანის პოვნა არის \(O(1)\).

– რეზერვუარის შერჩევა: ეს ტექნიკა სასარგებლოა მონაცემების ნაკადისთვის. ის გულისხმობს მონაცემთა ნაკრების ნიმუშის შენარჩუნებას და მის განახლებას, როდესაც მეტი ელემენტი შეინიშნება.

სანდო სტატისტიკური მეთოდები

გამონაკლისებით დაბინძურებულ მონაცემთა ნაკრებებში, სანდო სტატისტიკურ მეთოდებს შეუძლიათ უფრო სანდო საშუალო შეფასებების უზრუნველყოფა.

– ვინსორიზებული საშუალო: ეს მეთოდი გულისხმობს ექსტრემალური მნიშვნელობების ჩანაცვლებას უახლოესი არაექსტრემალური მნიშვნელობებით მედიანის გამოთვლამდე. ის აერთიანებს მედიანის სიმტკიცეს საშუალო მნიშვნელობის გამოთვლებიდან მიღებულ გარკვეულ ეფექტურობასთან.

– შემცირებული მედიანა: მედიანის გამოთვლამდე ყველაზე მაღალი და ყველაზე დაბალი მონაცემთა წერტილების განსაზღვრული პროცენტული მაჩვენებელი უგულებელყოფილია, რაც ამცირებს გამონაკლისების გავლენას.

დასკვნა

მონაცემთა მედიანის პოვნის ტექნიკა მნიშვნელოვნად განსხვავდება სირთულისა და გამოყენების მიხედვით, მარტივი დახარისხებისა და შერჩევის მეთოდებიდან დაწყებული ისეთი დახვეწილი ალგორითმებით დამთავრებული, როგორიცაა QuickSelect და დიდი მონაცემთა ნაკრებებისთვის განკუთვნილი ნაკადის ალგორითმები. ამ მეთოდების გაგება და მონაცემთა ნაკრების მახასიათებლებისა და გამოთვლითი რესურსების საფუძველზე შესაბამისის არჩევა აუცილებელია მედიანის ზუსტი და ეფექტური გამოთვლებისთვის. იქნება ეს მცირე თუ დიდი მონაცემთა ნაკრებები, სიხშირის განაწილება თუ მრავალვარიანტული მონაცემები, სწორ ტექნიკას შეუძლია მნიშვნელოვანი განსხვავება შეიტანოს მონაცემთა ცენტრალური ტენდენციის ზუსტად აღბეჭდვაში.