มีขั้นตอนวิธีหรือโครงสร้างข้อมูลที่ต้องการหาค่ามัธยฐานของชุดหรือไม่?

Sharan Duggirala 10/01/2017. 4 answers, 2.250 views
runtime-analysis randomized-algorithms

ฉันได้อ่านหนังสือเล่ม นี้ สำหรับชั้นเรียนของฉันอัลกอริธึมแบบสุ่ม ในหนังสือเล่มนี้มีทั้งส่วนที่ทุ่มเทให้กับการหาค่ามัธยฐานของอาร์เรย์โดยใช้การเลือกแบบสุ่มซึ่งจะนำไปสู่อัลกอริธึมที่มีประสิทธิภาพมากขึ้น ตอนนี้ฉันต้องการทราบว่ามีแอพพลิเคชันที่เป็นประโยชน์ในขั้นตอนนี้ในสาขาวิทยาการคอมพิวเตอร์หรือไม่นอกจากการปรับปรุงทฤษฎี มีขั้นตอนวิธีหรือโครงสร้างข้อมูลที่ต้องการหาค่ามัธยฐานของอาร์เรย์หรือไม่?

5 Comments
3 hoffmale 10/02/2017
คุณอาจต้องการพิจารณา quicksort: โดยการเลือกค่ามัธยฐานเป็น pivot กรณีที่แย่ที่สุดสามารถหลีกเลี่ยงได้ (กรณีรันไทม์ที่เลวร้ายที่สุด = O (n log n) แทน O (n ^ 2)) และความลึกของการทับทิมจะเป็น ลด (log2 (n))
1 gnasher729 10/02/2017
@hoffmale: แต่คุณไม่จำเป็นต้องหาค่ามัธยฐาน คุณต้องหาค่าที่ใกล้เคียงกับค่ามัธยฐาน ตัวอย่างเช่นการหาเดือยที่ไม่อยู่ในด้านบน 5% หรือด้านล่าง 5% รับประกัน O (n log n)
1 hoffmale 10/02/2017
@ gnasher729: แต่จะไม่ลดความลึกของการเรียกซ้ำ คุณสมบัติทั้งสองมีความสำคัญเช่นในสภาพแวดล้อมแบบเรียลไทม์ที่มีทรัพยากร จำกัด
Wildcard 10/03/2017
@hoffmale บังเอิญสัญกรณ์ปกติสำหรับลอการิทึม 2 ฐาน (โดยเฉพาะอย่างยิ่งในหมู่นักวิทยาการคอมพิวเตอร์) เป็นเพียง "lg" ใน (lg (n))
Konrad Rudolph 10/03/2017
@ gnasher729 เนื่องจากหัวข้อนี้เป็นอัลกอริทึมแบบสุ่ม (stichastic algorithms) นี้ (= สมควรปิด) น่าจะเป็นสิ่งที่อัลกอริทึมเหล่านี้กำลังทำอยู่

4 Answers


fade2black 10/01/2017.

ถ้ามีการใช้งานจริงของอัลกอริธึมนี้ในด้านวิทยาการคอมพิวเตอร์นอกเหนือจากการพัฒนาทฤษฎี

การประยุกต์ใช้อัลกอริธึมนี้เป็นเรื่องเล็กน้อย - คุณใช้มันเมื่อใดก็ตามที่คุณต้องการคำนวณ ค่ามัธยฐาน ของชุดข้อมูล (อาร์เรย์ในคำอื่น ๆ ) ข้อมูลนี้อาจมาจากโดเมนที่แตกต่างกัน ได้แก่ การสังเกตดาราศาสตร์สังคมศาสตร์ข้อมูลทางชีววิทยา ฯลฯ

แต่ก็เป็นมูลค่าการกล่าวขวัญเมื่อต้องการเฉลี่ยหมายถึง (หรือโหมด) โดยทั่วไปในสถิติเชิงพรรณนาเมื่อข้อมูลของเรามีการแจกแจงแบบปกติอย่างสมบูรณ์แบบหมายความว่าโหมดและค่ามัธยฐานมีค่าเท่ากันนั่นคือตรงตามเวลา ในทางกลับกันเมื่อข้อมูลของเราเบ้เช่นการแจกแจงความถี่สำหรับข้อมูลของเราคือ (ซ้าย / ขวา) เบ้หมายความว่าไม่สามารถให้ตำแหน่งกลางที่ดีที่สุดเนื่องจากความเอียงถูกลากไปจากค่าปกติไปทางซ้ายหรือขวา ในขณะที่ค่ามัธยฐานไม่ได้รับอิทธิพลอย่างมากจากข้อมูลที่เอียงและทำให้ตำแหน่งนี้ชี้ไปที่ค่าโดยทั่วไปได้ดีที่สุด ดังนั้นการคำนวณมัธยฐานอาจเป็นที่นิยมเมื่อคุณจัดการกับข้อมูลที่บิดเบี้ยว

นอกจากนี้การเรียนรู้ด้วยเครื่องคือวิธีที่ใช้สถิติอย่างมากเช่น $ k $ -medians clustering

3 comments
Sharan Duggirala 10/01/2017
ขอขอบคุณ! นั่นเป็นประโยชน์อย่างยิ่ง! อัลกอริทึมหรือเทคนิคอื่น ๆ ที่อาจจำเป็นต้องหาค่ามัธยฐาน?
5 John Coleman 10/02/2017
แม้ว่าข้อมูลนี้จะเป็นจริง (+1) มากกว่าสถิติที่ใช้อยู่ แต่ข้อมูลจะถูกจัดเรียงก่อนที่จะหาค่ามัธยฐานเนื่องจากในบริบทมากหรือแม้แต่ส่วนใหญ่ที่ต้องการค่ามัธยฐานดังนั้นอย่างน้อยที่สุดคำสั่งอื่น ๆ สถิติ.
1 svick 10/02/2017
น่าสนใจ ฉันเคยได้ยินเกี่ยวกับ $ k $ - หมายถึง clustering แต่ไม่เกี่ยวกับ $ k $ -medians clustering

mathreadler 10/02/2017.

Median filtering เป็นเรื่องปกติในการลดเสียงรบกวนบางประเภทในการประมวลผลภาพ โดยเฉพาะอย่างยิ่งเสียงของเกลือและพริกไทย ทำงานโดยเลือกค่ามัธยฐานในช่องสีแต่ละช่องในแต่ละละแวกใกล้เคียงของภาพและแทนที่ด้วยค่ามัธยฐาน พื้นที่เหล่านี้มีขนาดใหญ่เพียงใด ขนาดตัวกรองยอดนิยม (ละแวกใกล้เคียง) เป็นเช่น 3x3 และ 5x5 พิกเซล

4 comments
1 Dunk 10/02/2017
Median ใช้ไม่ได้กับเสียงรบกวนในภาพ แต่มีสัญญาณรบกวนในการอ่านค่าเซ็นเซอร์ทั้งหมดซึ่งเป็นกล้องที่มีเพียงเซ็นเซอร์เดียว ตำราเรียนแสดงรูปร่างคลื่นไซน์และรูปสี่เหลี่ยมผืนผ้าที่ดีในการทำงานร่วมกับ ในโลกแห่งความเป็นจริงข้อมูลที่สะอาดเหมือนที่แทบไม่เคยเกิดขึ้น ถ้าเป็นเช่นนั้นเกือบทุกครั้งเพราะคนอื่นดูแลเอาข้อมูลออกก่อนที่คุณจะจับมัน ตัวอย่างเช่นข้อมูลการอ่านเซนเซอร์ทั่วไปที่คุณต้องเลือกค่า "ถูกต้อง": (1, 3, 5, 65, 68, 70, 75, 80, 82, 85, 540, 555) ฉันจัดเรียงข้อมูลเพื่อให้ชัดเจนยิ่งขึ้น
1 mathreadler 10/02/2017
ใช่คุณมีสิทธิ์ แต่จะทำให้คำตอบยาวมากและน่าเบื่อถ้าเราเขียนลงเล็ก ๆ น้อย ๆ ทั้งหมดในการประมวลผลสัญญาณที่จะสามารถใช้
1 Hagen von Eitzen 10/03/2017
Medians ในการประมวลผลภาพยังสามารถใช้ต่อพิกเซลกับลำดับของ 5 หรือดังนั้นภาพถ่ายซึ่งเป็นวิธีการกำจัดเสียงชั่วคราว (aka นักท่องเที่ยวปิดกั้นมุมมอง)
mathreadler 10/03/2017
@HagenvonEitzen คุณมีสิทธิ์! จริงๆแล้วฉันกำลังคิดถึงบางสิ่งที่ค่อนข้างคล้ายกันเมื่อไม่กี่วันก่อน นักท่องเที่ยวจำนวนมากรอบ ...

David Richerby 10/02/2017.

มัธยฐานในการคำนวณมีความสำคัญเป็นพิเศษในขั้นตอนวิธีแบบสุ่ม

บ่อยครั้งที่เรามีอัลกอริธึมประมาณซึ่งมีความน่าจะเป็นอย่างน้อย $ \ tfrac34 $ ให้คำตอบภายในค่า $ 1 \ pm \ epsilon $ ของคำตอบที่แท้จริง $ A $ แน่นอนว่าในความเป็นจริงเราต้องการรับคำตอบที่ถูกต้องเกือบจะมากกว่า $ \ tfrac34 $ ดังนั้นเราจึงทำซ้ำอัลกอริทึม $ k $ ครั้งแล้วใช้ค่ามัธยฐาน ค่ามัธยฐานจะอยู่ที่ $ A (1 \ pm \ epsilon) $ เว้นแต่อย่างน้อยครึ่งหนึ่งของตัวอย่าง $ k $ น้อยกว่า $ A (1- \ epsilon) $ หรืออย่างน้อยครึ่งหนึ่งมีค่ามากกว่า $ A (1+ \ epsilon) $ และมีความเป็นไปได้ที่จะมีขนาดเล็กในระดับ $ k $

"ผิดครั้งเดียวในสี่ขั้นตอน" และเปลี่ยนเป็น "ผิดครั้งเดียวใน $ 2 ^ n $ รัน" อัลกอริธึมในขณะที่เพิ่มเฉพาะปัจจัยบางอย่างเช่น $ n $ ไปยังเวลาทำงาน


Odo Frodo 10/02/2017.

มัธยฐานของมัธยฐาน มีบางโปรแกรม:

  • หาตำแหน่งเด็ดขาดสำหรับ quicksort ซึ่งทำให้ความซับซ้อนของเวลาที่เลวร้ายที่สุดคือ $ O (n \ log n) $
  • การค้นหาแกนสำหรับ quickselect นำความซับซ้อนที่เลวร้ายที่สุดไป $ O (n) $ จาก $ O (n ^ 2) $
3 comments
1 wchargin 10/02/2017
การใช้มัธยฐานของมัธยฐานเพื่อเลือกเดคคอร์สำหรับ quicksort ดูเหมือนว่าจะชะลอการทำงานของอัลกอริธึมในทางปฏิบัติเพราะมันจะทำให้แคชสูญเสียที่อยู่อาศัยซึ่งเป็นส่วนสำคัญในการเร่งความเร็วของ quicksort แต่ความคิดเห็นของคุณเกี่ยวกับความซับซ้อนของกรณีที่เลวร้ายที่สุดเป็นสิ่งที่ถูกต้องแน่นอน
Konrad Rudolph 10/03/2017
@wchargin คุณมีทางเลือกอะไรบ้าง? ไม่มีการใช้ quicksort ในทางปฏิบัติที่ฉันรู้ว่าใช้เดสก์ท็อปที่แคบเนื่องจากทำเพื่อการค้าในระยะเวลาที่เลวร้ายที่สุดในกรณีเลวร้าย เอกสาร "Engineering a sort function" ที่กล่าวถึงทางเลือกและไม่มีใครทราบแคช (และยังดีกว่าการเลือกเดือยไร้เดียงสา)
1 Konrad Rudolph 10/03/2017
@ wchargin ... ตอบคำถามของฉันเอง: Java 7 เปลี่ยนไปใช้กระบวนการ dual-pivot ใหม่ที่ฉันไม่รู้จัก นี่เป็นเรื่องที่น่าสนใจและ might ทำให้อัลกอริทึมของเดสก์ท็อปมีค่ามัธยฐานล้าสมัย

Related questions

Hot questions

Language

Popular Tags