Зааныг хүснэгтэнд хэрхэн оруулах вэ

Холбоосуудын хүснэгт

Хураангуй болон 1 танилцуулга

2 Урьдчилсан болон холбогдох ажил

2.1 Түүвэрлэлтийн стратегийн тухай

2.2 Коресетийн бусад стратеги

2.3 Өгөгдлийн сангийн хэрэглээний коресет

2.4 Quadtree Embeddings

3 Хурдан коресет

4 Тархалтын нөлөөллийг бууруулах

4.1 Түүхий дээд хязгаарыг тооцоолох

4.2 Ойролцоо шийдэлээс тархалтыг багасгах

5 Практикт хурдан шахах

5.1 Эмпирик шинжилгээний зорилго, хамрах хүрээ

5.2 Туршилтын тохиргоо

5.3 Түүвэрлэлтийн стратегийг үнэлэх

5.4 Урсгалын тохиргоо ба 5.5 Авах мэдээлэл

6 Дүгнэлт

7 Талархал

8 Нотолгоо, псевдо-код, өргөтгөлүүд ба 8.1 Үр дүнгийн баталгаа 3.2

8.2 k-дунжийг k-медиан болгон бууруулна

8.3 Модны хамгийн оновчтой зардлын тооцоо

8.4 1-р алгоритмын өргөтгөлүүд

Лавлагаа

Хийсвэр

Бид том өгөгдлийн багц дээр k-дундаж ба k-медиан кластерын ажиллах хугацааны онолын болон практикийн хязгаарыг судалдаг. Бүх кластерын аргууд нь өгөгдлийн багцыг уншихаас удаан байдаг тул хамгийн хурдан арга бол өгөгдлийг хурдан шахаж, шахсан дүрслэл дээр кластер хийх явдал юм. Харамсалтай нь цэгийн тоог шахах бүх нийтийн хамгийн сайн сонголт байдаггүй – санамсаргүй түүвэрлэлт нь дэд шугаман хугацаанд хийгдэж, корсетууд нь онолын баталгааг өгдөг бол эхнийх нь нарийвчлалыг хангадаггүй, харин хоёр дахь нь цэг болон кластеруудын тоо өсөх тусам хэтэрхий удаан байдаг. Үнэн хэрэгтээ аливаа мэдрэмтгий чанарт суурилсан үндсэн багцын бүтэц нь өгөгдлийн багцын хэмжээнд хэт шугаман цаг хугацаа шаарддаг гэж таамаглаж байсан.

Бид эхлээд өгөгдлийг уншихад шаардагдах лог хүчин зүйлийн хүрээнд үр дүнтэй шугаман хугацаанд мэдрэмжийн түүвэрлэлтээр коресет авдаг алгоритм байдгийг харуулах замаар энэ хамаарлыг шалгана. Үүнийг мэдэгдэхүйц сайжруулсан аливаа арга нь практик эвристикийг ашиглах ёстой бөгөөд энэ нь биднийг статик болон дамжуулалтын тохиргоон дахь бодит болон хиймэл өгөгдлийн олонлогын түүвэрлэлтийн стратегийн спектрийг авч үзэхэд хүргэдэг. Үүгээр дамжуулан бид кластерын хүчин төгөлдөр байдлыг хадгалахад коресет шаардлагатай нөхцөл, мөн илүү хурдан, бүдүүлэг түүвэрлэлтийн стратеги хангалттай байх тохиргоог харуулна. Үүний үр дүнд бид өгөгдлийн хэмжээнээс үл хамааран үр дүнтэй кластер хийх онолын болон практикийн цогц төлөвлөгөөг гаргаж өгдөг. Манай код нь эх сурвалж дээр олон нийтэд нээлттэй бөгөөд туршилтыг дахин үүсгэх скриптүүдтэй.

1 Танилцуулга

Орчин үеийн өгөгдлийн шинжээчид сонгохдоо кластер хийх алгоритм дутагдалтай байдаггүй ч холбогдох өгөгдлийн багцын хэмжээ байнга нэмэгдэж байгаа тул ихэнх нь практикт хэрэг болохуйц хэтэрхий удаан байдаг. Энэ нь ялангуяа кластерийн алгоритмыг шахахад ашигладаг том өгөгдлийн дамжуулах хоолойд хамаатай. Зорилго нь маш том өгөгдлийн багцыг жижгэвтэр, илүү удирдах боломжтой нэгээр солих бөгөөд энэ нь анхны оролтыг сайн илэрхийлнэ гэж найдаж байна. Ллойдын алгоритмыг [49] яг энэ шалтгааны улмаас нэвтрүүлсэн бөгөөд квантчлалын алдаа буюу оролтын цэг бүрээс шахсан өгөгдлийн багц дахь төлөөлөгч хүртэлх квадрат зайны нийлбэрийг багасгадаг. Хамгийн алдартай кластер хийх алгоритм болох Lloyd's нь давталт бүрд O(ndk) хугацаа шаардагддаг бөгөөд n нь цэгийн тоо, d нь функцын тоо, k нь кластерын тоо буюу зорилтот шахалтын хэмжээ юм. Ийм хэрэглээний хувьд онооны тоо амархан хэдэн зуун сая байж болох ба шахалтын чанар k-ээр нэмэгддэг тул стандарт зорилтууд нь k-тэй байж болно [41, 4]. Ийм тохиргоонд аливаа O(ndk) алгоритм нь маш удаан байдаг.

Эдгээр жишээнүүд нь онолын болон практикийн аль алиныг нь сайжруулах боломжийг олгодог том өгөгдлийн алгоритмуудыг хөгжүүлэхэд түлхэц болсон. Гэсэн хэдий ч онолын үндэслэл, практик үр дүнтэй байдлын хэтийн төлөв нь ихэвчлэн хоорондоо зөрчилддөг. Нэг талаас, онолын баталгаа нь алгоритм нь ямар ч азгүй оролтыг хүлээн авснаас үл хамааран ажиллах болно гэсэн баталгааг өгдөг. Нөгөөтэйгүүр, илүү хурдан гүйж, практик дээр сайн ажилладаг бүдүүлэг аргууд байгаа үед онолын хувьд оновчтой алгоритмыг хэрэгжүүлэхэд өөрийгөө итгүүлэхэд хэцүү байж болно.

Өгөгдлийн багц нь n цэгийн тоо ба/эсвэл d функцын тоогоор их байж болох тул том өгөгдлийн аргууд нь хоёулангийнх нь нөлөөг багасгах ёстой. Онцлогын орон зайн хувьд санамсаргүй төсөөлөл нь хурдан (үр дүнтэй шугаман хугацаанд ажилладаг), хэрэгжүүлэхэд практик [50], суулгацын хэмжээ, чанарт хатуу баталгаа өгдөг тул асуулт үр дүнтэй хаагдсан. n онооны тоог багасгахад хэтийн төлөв нь тодорхой бус бөгөөд тус бүр нь тодорхой давуу талыг өгдөг хоёр тусдаа парадигм байдаг. Нэг талаас, бид нэг төрлийн түүвэрлэлттэй бөгөөд энэ нь дэд шугаман хугацаанд ажилладаг боловч өгөгдлийн чухал дэд бүлгүүдийг алдаж болзошгүй тул өгөгдлийн тодорхой хүчтэй таамаглалуудын дагуу үнэн зөвийг баталгаажуулж чадна [45]. Нөгөөтэйгүүр, хамгийн үнэн зөв түүвэрлэлтийн стратеги нь шахагдсан өгөгдөл дээрх аливаа шийдлийн өртөг нь анхны өгөгдлийн багц дээрх уг шийдлийн зардлын ε хүчин зүйлийн дотор байх хүчтэй үндсэн багцын баталгааг өгдөг [25].

Бидний оруулсан хувь нэмэр Бид сонгодог асуудлын хувьд парадигмуудыг (нэгдмэл түүвэрлэлт ба хүчтэй корсет) хоёуланг нь судалдаг - k-дунд болон k-медиан зорилгын шахалт. Нэг төрлийн түүвэрлэлт нь оновчтой хурдыг хангадаг боловч хамгийн муу тохиолдолд нарийвчлалын баталгаа өгдөггүй боловч үнэн зөв шахахад шаардагдах хамгийн бага тооны дээжийг хатуу хязгаарлах үед боломжтой бүх үндсэн бүтцийн байгууламжууд хамгийн багадаа Ω˜(nd + nk) ажиллах хугацаатай байдаг.

Шахалтын баталгааг хангасан аливаа алгоритм нь өгөгдлийн багцыг бүхэлд нь унших ёстой гэдгийг харуулахад хялбар байдаг[1]. Тиймээс шугаман эсвэл бараг шугаман хугацаанд ямар баталгааг хангах вэ гэдэг нь тодорхой нээлттэй асуулт юм. Үнэн хэрэгтээ, кластер хийх боломжтой хурдан түүвэрлэлтийн алгоритмууд [6, 5] нь үндсэн багцын баталгааг хангаж чадахгүй. Саяхан [31] O˜(nd + nk) хугацаанд ажилладаг хүчтэй корсетийн аргыг санал болгож, үүнийг k-медиан болон k-дундуудад оновчтой гэж таамагласан.

Энэ хязгаар нь k-ийн жижиг утгуудын хувьд оновчтой боловч компьютерийн хараа [34] эсвэл алгоритмын шударга байдал [18] зэрэг олон програмууд байдаг бөгөөд кластеруудын тоо нь шинж чанаруудын тооноос хэд хэдэн дарааллаар их байж болно. Ийм тохиргоонд цаг хугацааны оновчтой корсетийн тухай асуулт нээлттэй хэвээр байна. Хамгийн оновчтой хэмжээтэй үндсэн багцыг тодорхойлох асуудал саяхан хаагдсан [25, 28, 44] тул энэ нь төвд суурилсан кластерын судалгааны үндсэн нээлттэй асуудал болж магадгүй юм. Бид үүнийг өгөгдлийн багцыг уншихад шаардагдах хугацаанаас зөвхөн логарифмын хүчин зүйлсээр тооцож O˜(nd) хугацаанд корсетийг бүтээдэг хэрэгжүүлэхэд хялбар алгоритм байдгийг харуулах замаар шийдэж байна.

Гэсэн хэдий ч энэ нь практикт кластер хийх түүвэрлэлтийн алгоритмуудын ландшафтыг бүрэн гэрэлтүүлж чадахгүй байна. Хэдийгээр бидний алгоритм нь оновчтой ажиллах хугацаа, оновчтой шахалтыг хоёуланг нь хангаж өгдөг ч бусад, бүдүүлэг аргууд нь бүх практик зорилгоор ашиглах боломжтой байх нь гарцаагүй. Үүнийг бид дараах асуултад албан ёсоор тайлбарлаж байна: Оновчтой k-дундаж ба k-медиан корсетууд хэзээ шаардлагатай вэ, үндсэн багцын хурд ба нарийвчлалын хооронд ямар практик уялдаа холбоо байдаг вэ?

o үүнд хариулбал, бид санал болгож буй аргаас илүү хурдан түүвэрлэлтийн алгоритмуудын бүрэн хэмжээний харьцуулалтыг хийдэг. Үүгээр дамжуулан бид эдгээр илүү хурдан аргууд нь бодит ертөнцийн олон өгөгдлийн багцад хангалттай нарийвчлалтай байдаг ч тэдгээр нь тус бүрийн хувьд сүйрэлд хүргэдэг өгөгдлийн хуваарилалтууд байдгийг баталгаажуулдаг. Үнэн хэрэгтээ эдгээр тохиолдлуудыг зөвхөн хүчирхэг үндсэн аргачлалаар л зайлсхийх боломжтой. Тиймээс, олон практик тохиргоонууд нь үндсэн багцын бүрэн баталгаа шаарддаггүй ч шахалтанд итгэлтэй байхыг хүсвэл булангуудыг огтолж чадахгүй. Энэ нь урсгалын парадигмд хамаарах ба доод урсгалын кластерын хандлагуудад хамааралтай болохыг бид баталж байна.

Дүгнэж хэлэхэд бидний оруулсан хувь нэмэр дараах байдалтай байна.

• Бид O˜(nd) хугацаанд k-дундаж ба k-медианы хувьд хүчтэй коресет авч болохыг харуулж байна. Энэ нь k-means coresets [31]-д шаардлагатай ажиллах хугацааны талаарх таамаглалыг шийдэж, лог-фактор хүртэл онолын хувьд оновчтой юм.

• Өгөгдлийн багц, даалгавар, урсгалтай/гүйлгээгүй парадигмуудын талаар иж бүрэн дүн шинжилгээ хийснээр бид шугаман болон дэд шугаман цагийн түүвэрлэлтийн аргуудын хооронд хурд ба нарийвчлалын хооронд зайлшгүй шаардлагатай зөрүү байгааг баталгаажуулдаг. Энэ нь кластерын дадлагажигчдад аль болох хурдан хугацаанд үр дүнтэй кластерын үр дүнд хүрэхийн тулд шахалтын алгоритм бүрийг хэзээ ашиглах тухай төлөвлөгөөг өгдөг.