Электрондук таблицага пилди кантип батырса болот

Шилтемелер таблицасы

Аннотация жана 1 Киришүү

2 Алдын ала иштер жана ага байланыштуу иштер

2.1 Тандоо стратегиялары жөнүндө

2.2 Башка Коресет стратегиялары

2.3 Маалыматтар базасынын колдонмолору үчүн коресеттер

2.4 Quadtree кыстаруу

3 Fast-Coresets

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 менен көбөйгөндүктөн, стандарттык максаттарда миңдеген к болот [41, 4]. Мындай орнотууларда каалаган O(ndk) алгоритми өтө жай иштейт.

Бул сыяктуу мисалдар теориялык жана практикалык иштөө убактысын жакшыртууну камсыз кылган чоң маалымат алгоритмдеринин өсүшүнө түрткү болду. Теориялык негиздүүлүктүн жана практикалык натыйжалуулуктун перспективалары көп учурда бири-бирине карама-каршы келет. Бир жагынан алганда, теориялык кепилдиктер алгоритм кандай гана бактысыз киргизүүлөргө карабастан иштей тургандыгына кепилдик берет. Башка жагынан алганда, тезирээк чуркай турган жана практикада жакшы иштеген чийки ыкмалар болгондо, теориялык жактан оптималдуу алгоритмди ишке ашырууга өзүн ынандыруу кыйын болушу мүмкүн.

Берилиштер топтомдору n чекиттеринин жана/же d өзгөчөлүктөрүнүн саны боюнча чоң болушу мүмкүн болгондуктан, чоң маалымат ыкмалары экөөнүн тең таасирин азайтышы керек. Функция мейкиндигине келсек, суроо эффективдүү жабылат, анткени кокустук проекциялар тез (эффективдүү сызыктуу убакытта иштейт), ишке ашыруу үчүн практикалык [50] жана кыстаруунун өлчөмүнө жана сапатына бекем кепилдиктерди берет. n пункттарынын санын кыскартууда көз караш анча ачык эмес жана ар бири өзүнчө артыкчылыктарды берген эки өзүнчө парадигма бар. Бир жагынан алганда, бизде бирдиктүү тандоо бар, ал субсызыктуу убакытта иштейт, бирок маалыматтардын маанилүү бөлүмдөрүн өткөрүп жибериши мүмкүн жана ошондуктан маалыматтар боюнча белгилүү бир күчтүү божомолдордо гана тактыкка кепилдик бере алат [45]. Башка жагынан алганда, эң так тандап алуу стратегиялары күчтүү өзөктүү кепилдикти камсыз кылат, мында кысылган маалыматтар боюнча кандайдыр бир чечимдин баасы баштапкы маалымат топтомундагы ошол чечимдин наркынын ε факторунун чегинде болот [25].

Биздин салымдар Биз эки парадигманы (бирдиктүү тандап алуу жана күчтүү корсететтер) классикалык көйгөйгө – k-каражаттары жана k-медиана максаттары үчүн кысуу боюнча изилдейбиз. Бир калыпта үлгү алуу оптималдуу ылдамдыкты камсыз кылат, бирок эң начар тактыкка кепилдик бербейт, так кысуу үчүн талап кылынган үлгүлөрдүн минималдуу санына бекем чектерди бергенде, бардык колдо болгон өзөктүү түзүлүштөрдүн иштөө убактысы жок дегенде Ω˜(nd + nk) болот.

Кысуу кепилдигине жеткен ар кандай алгоритм маалымат топтомун толугу менен окушу керек экенин көрсөтүү оңой [1]. Ошентип, ачык ачык суроо - сызыктуу же дээрлик сызыктуу убакытта кандай кепилдиктерге жетүүгө болот. Чынында эле, кластердик [6, 5] үчүн учурда жеткиликтүү тез үлгү алуу алгоритмдери күчтүү coreset кепилдикке жете албайт. Жакында [31] O˜(nd + nk) убакытта иштей турган күчтүү коресеттер үчүн методду сунуштады жана муну k-медиана жана k-ортодор үчүн оптималдуу деп божомолдоду.

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

Ошого карабастан, бул иш жүзүндө кластерлөө үчүн үлгүлөрдү алуу алгоритмдеринин пейзажын толугу менен жарык кыла албайт. Биздин алгоритм оптималдуу иштөө убактысына да, оптималдуу кысууга да жетишсе да, башка, чийки ыкмалар бардык практикалык максаттар үчүн жарактуу болушу мүмкүн. Биз муну формалдуу түрдө төмөнкү суроодо айтабыз: Оптималдуу k-каражаттар жана k-медиандык корсеталар качан зарыл жана корсеттин ылдамдыгы менен тактыгынын ортосунда кандай практикалык айырма бар?

о буга жооп берсеңиз, биз сунуш кылган ыкмага караганда ылдамыраак үлгү алуу алгоритмдеринин толук диапазону боюнча кылдат салыштыруу жүргүзөбүз. Бул аркылуу биз бул тезирээк ыкмалар көптөгөн реалдуу дүйнө маалымат топтомдорунда жетиштүү так болгону менен, алардын ар бири үчүн катастрофалык бузулууга алып келген маалыматтарды бөлүштүрүү бар экенин текшеребиз. Чынында эле, мындай учурлардан гана күчтүү-coreset ыкмасы менен качууга болот. Ошентип, көптөгөн практикалык орнотуулар толук coreset кепилдикти талап кылбаса да, алардын кысылышына ишенгиси келсе, бурчтарды кесүүгө болбойт. Бул агымдык парадигмага жайыларын жана ылдый агымдагы кластердик ыкмаларга тиешелүү экендигин текшеребиз.

Кыскача айтканда, биздин салымдар төмөнкүдөй:

• O˜(nd) убакытта k-ортолору жана к-медиандары үчүн күчтүү коресеттерди алууга болорун көрсөтөбүз. Бул k-каражаттарынын коресеттери [31] үчүн керектүү иштөө убактысы жөнүндөгү божомолду чечет жана лог-факторлорго чейин теориялык жактан оптималдуу.

• Берилиштер топтому, тапшырмалар жана агымдык/төкмө эмес парадигмалар боюнча ар тараптуу талдоо аркылуу биз сызыктуу жана сублиниялык убакыт үлгүлөрүн алуу ыкмаларынын ортосунда ылдамдык менен тактыктын ортосунда зарыл болгон айырбаштоо бар экенин текшеребиз. Бул кластердик практикке максималдуу тез убакытта эффективдүү кластерлөө натыйжалары үчүн ар бир кысуу алгоритмин качан колдонуу керектиги боюнча планды берет.