Rumah >Peranti teknologi >AI >Enam algoritma pengelompokan yang mesti diketahui oleh saintis data
Pada masa ini, banyak aplikasi seperti Google News menggunakan algoritma pengelompokan sebagai kaedah pelaksanaan utama mereka boleh menggunakan sejumlah besar data tidak berlabel untuk membina pengelompokan topik yang hebat. Artikel ini memperkenalkan 6 jenis kaedah arus perdana daripada pengelompokan K-means yang paling asas kepada kaedah berasaskan kepadatan yang berkuasa Mereka masing-masing mempunyai bidang kepakaran dan senario mereka sendiri, dan idea asas tidak semestinya terhad kepada kaedah pengelompokan.
Artikel ini akan bermula dengan pengelompokan K-means yang mudah dan cekap, dan kemudian memperkenalkan pengelompokan anjakan min, pengelompokan berasaskan kepadatan, campuran Gaussian dan pengelompokan kaedah jangkaan maksimum, Pengelompokan hierarki dan pengesanan kumpulan graf digunakan pada data berstruktur. Kami bukan sahaja akan menganalisis konsep pelaksanaan asas, tetapi juga memberikan kelebihan dan kekurangan setiap algoritma untuk menjelaskan senario aplikasi sebenar.
Pengkelompokan ialah teknik pembelajaran mesin yang melibatkan pengumpulan titik data. Memandangkan satu set titik data, kita boleh menggunakan algoritma pengelompokan untuk mengklasifikasikan setiap titik data ke dalam kumpulan tertentu. Secara teori, titik data kepunyaan kumpulan yang sama harus mempunyai sifat dan/atau ciri yang serupa, manakala titik data kepunyaan kumpulan berbeza harus mempunyai sifat dan/atau ciri yang sangat berbeza. Pengelompokan ialah kaedah pembelajaran tanpa pengawasan dan teknik analisis data statistik yang biasa digunakan dalam banyak bidang.
K-Means mungkin merupakan algoritma pengelompokan yang paling terkenal. Ia adalah sebahagian daripada banyak kursus pengenalan sains data dan pembelajaran mesin. Sangat mudah untuk difahami dan dilaksanakan dalam kod! Sila lihat gambar di bawah.
K-Means Clustering
Mula-mula, kami memilih beberapa kelas/kumpulan dan secara rawak memulakan titik tengah masing-masing. Untuk menentukan bilangan kelas untuk digunakan, adalah idea yang baik untuk melihat data dengan cepat dan cuba mengenal pasti kumpulan yang berbeza. Titik tengah ialah lokasi dengan panjang yang sama dengan setiap vektor titik data, iaitu "X" dalam imej di atas.
Kelaskan setiap titik dengan mengira jarak antara titik data dan pusat setiap kumpulan, dan kemudian kelaskan titik itu ke dalam kumpulan yang paling hampir dengan pusat kumpulan itu.
Berdasarkan titik pengelasan ini, kami mengira semula pusat kumpulan menggunakan min semua vektor dalam kumpulan.
Ulang langkah ini untuk bilangan lelaran tertentu, atau sehingga pusat kumpulan berubah sedikit selepas setiap lelaran. Anda juga boleh memilih untuk memulakan pusat kumpulan secara rawak beberapa kali dan kemudian memilih larian yang nampaknya memberikan hasil terbaik.
K-Means mempunyai kelebihan kerana pantas, kerana apa yang kita lakukan sebenarnya ialah mengira jarak antara titik dan pusat kumpulan: pengiraan yang sangat sedikit! Jadi ia mempunyai kerumitan linear O(n).
K-Means pula mempunyai beberapa kelemahan. Pertama, anda perlu memilih berapa banyak kumpulan/kelas yang ada. Ini tidak selalu dilakukan dengan berhati-hati, dan secara idealnya kami mahu algoritma pengelompokan membantu kami menyelesaikan masalah bilangan kelas untuk dikelaskan, kerana tujuannya adalah untuk mendapatkan beberapa cerapan daripada data. K-means juga bermula dari pusat kluster yang dipilih secara rawak, jadi ia mungkin menghasilkan hasil kluster yang berbeza dalam algoritma yang berbeza. Oleh itu, keputusan mungkin tidak boleh dihasilkan semula dan kurang konsisten. Kaedah pengelompokan lain lebih konsisten.
K-Medians ialah satu lagi algoritma pengelompokan yang berkaitan dengan K-Means, kecuali daripada menggunakan min, pusat kumpulan dikira semula menggunakan vektor median kumpulan. Kaedah ini tidak sensitif kepada outlier (kerana median digunakan), tetapi jauh lebih perlahan untuk set data yang lebih besar kerana pengisihan diperlukan pada setiap lelaran semasa mengira vektor median.
Pengkelompokan Anjakan Min ialah algoritma berasaskan tetingkap gelongsor yang cuba mencari kawasan padat titik data. Ini adalah algoritma berasaskan centroid, yang bermaksud matlamatnya adalah untuk mencari titik tengah setiap kumpulan/kelas, yang dicapai dengan mengemas kini titik calon titik tengah kepada min titik dalam tetingkap gelongsor. Tetingkap calon ini kemudiannya ditapis dalam peringkat pasca pemprosesan untuk menghapuskan hampir duplikasi, membentuk set akhir titik tengah dan kumpulan yang sepadan. Sila lihat lagenda di bawah.
Pengkelompokan anjakan min untuk satu tetingkap gelongsor
Keseluruhan proses dari awal hingga akhir untuk semua tingkap gelongsor ditunjukkan di bawah. Setiap titik hitam mewakili centroid tetingkap gelongsor, dan setiap titik kelabu mewakili titik data.
Keseluruhan proses pengelompokan anjakan min
Berbanding dengan pengelompokan K-means, kaedah ini tidak perlu memilih bilangan kelompok kerana anjakan min secara automatik Temui ini. Ini adalah kelebihan yang besar. Hakikat bahawa kluster memusatkan kluster ke arah ketumpatan titik maksimum juga sangat memuaskan, kerana ia sangat intuitif untuk memahami dan menyesuaikan diri dengan implikasi yang dipacu data semula jadi. Kelemahannya ialah pilihan saiz/radius tetingkap "r" mungkin tidak penting.
DBSCAN ialah algoritma pengelompokan berasaskan ketumpatan yang serupa dengan anjakan min tetapi mempunyai beberapa kelebihan ketara. Lihat satu lagi grafik yang menyeronokkan di bawah dan mari mulakan!
DBSCAN mempunyai banyak kelebihan berbanding algoritma pengelompokan lain. Pertama, ia tidak memerlukan bilangan kluster yang tetap sama sekali. Ia juga mengenal pasti outlier sebagai hingar, tidak seperti anjakan min, yang hanya mengumpulkan titik data ke dalam kelompok walaupun ia sangat berbeza. Selain itu, ia mampu mencari kluster dari sebarang saiz dan bentuk dengan baik.
Kelemahan utama DBSCAN ialah ia tidak berfungsi sebaik algoritma pengelompokan lain apabila ketumpatan kelompok berbeza. Ini kerana tetapan ambang jarak ε dan minPoints yang digunakan untuk mengenal pasti titik kejiranan akan berubah dengan kelompok apabila ketumpatan berubah. Kelemahan ini juga timbul dalam data berdimensi sangat tinggi, kerana ambang jarak ε sekali lagi menjadi sukar untuk dianggarkan.
Kelemahan utama K-Means ialah penggunaan kaedah pusat kluster yang mudah. Daripada rajah di bawah, kita dapat melihat mengapa ini bukan pendekatan terbaik. Di sebelah kiri, anda boleh melihat dengan jelas bahawa terdapat dua kelompok bulat dengan jejari berbeza, berpusat pada min yang sama. K-Means tidak dapat menangani keadaan ini kerana cara kluster ini sangat dekat. K-Means juga gagal dalam kes di mana kluster tidak bulat, sekali lagi kerana menggunakan min sebagai pusat kluster.
Dua Kes Kegagalan K-Means
Model Campuran Gaussian (GMM) memberi kita lebih fleksibiliti daripada K-Means. Untuk GMM, kami menganggap bahawa titik data adalah diedarkan Gaussian ini adalah andaian yang kurang ketat daripada menggunakan min untuk menganggap bahawa ia adalah bulat. Dengan cara ini, kita mempunyai dua parameter untuk menerangkan bentuk kelompok: min dan sisihan piawai! Mengambil 2D sebagai contoh, ini bermakna gugusan boleh mengambil sebarang bentuk bentuk elips (memandangkan kita mempunyai sisihan piawai dalam kedua-dua arah x dan y). Oleh itu, setiap taburan Gaussian ditugaskan kepada satu kelompok.
Untuk mencari parameter Gaussian (seperti min dan sisihan piawai) setiap kelompok, kami akan menggunakan algoritma pengoptimuman yang dipanggil Expectation Maximum (EM). Lihat rajah di bawah, yang merupakan contoh kesesuaian Gaussian dengan gugusan. Kami kemudiannya boleh meneruskan proses pengelompokan jangkaan maksimum menggunakan GMM.
Terdapat dua kelebihan utama untuk menggunakan GMM. Pertama, GMM lebih fleksibel daripada K-Means dari segi kovarians kelompok kerana parameter sisihan piawai, kelompok boleh mengambil bentuk elips dan bukannya terhad kepada bulatan. K-Means sebenarnya adalah kes khas GMM, di mana kovarians setiap kluster menghampiri 0 dalam semua dimensi. Kedua, kerana GMM menggunakan kebarangkalian, boleh terdapat banyak kelompok bagi setiap titik data. Jadi jika titik data berada di tengah-tengah dua kelompok bertindih, kita boleh menentukan kelasnya hanya dengan mengatakan bahawa X peratus daripadanya tergolong dalam kelas 1 dan Y peratus kepada kelas 2. Iaitu, GMM menyokong kelayakan hibrid.
Algoritma pengelompokan hierarki sebenarnya dibahagikan kepada dua kategori: atas ke bawah atau bawah ke atas. Algoritma bawah ke atas mula-mula merawat setiap titik data sebagai gugusan tunggal dan kemudian menggabungkan (atau mengagregat) dua gugusan berturut-turut sehingga semua gugusan digabungkan menjadi satu gugusan yang mengandungi semua titik data. Oleh itu, pengelompokan hierarki bawah ke atas dipanggil pengelompokan hierarki aglomeratif atau HAC. Hierarki kelompok ini diwakili oleh pokok (atau dendrogram). Akar pokok adalah satu-satunya kelompok yang mengumpul semua sampel, dan daun adalah kelompok dengan hanya satu sampel. Sebelum pergi ke langkah algoritma, sila lihat legenda di bawah.
Penghimpunan hierarki aglomeratif
Pengelompokan hierarki tidak memerlukan kita menyatakan bilangan gugusan, malah kita boleh memilih bilangan gugusan yang mana kelihatan paling baik memandangkan kita sedang membina pokok. Selain itu, algoritma tidak sensitif kepada pilihan metrik jarak, semuanya berprestasi sama baik, manakala bagi algoritma pengelompokan lain, pilihan metrik jarak adalah penting. Contoh kaedah pengelompokan hierarki yang sangat baik ialah apabila data asas mempunyai struktur hierarki dan anda ingin memulihkan hierarki algoritma pengelompokan lain tidak boleh melakukan ini. Tidak seperti kerumitan linear K-Means dan GMM, kelebihan pengelompokan hierarki ini datang pada kos kecekapan yang lebih rendah kerana ia mempunyai kerumitan masa O(n³).
Apabila data kami boleh diwakili sebagai rangkaian atau graf, kami boleh menggunakan kaedah pengesanan komuniti graf untuk melengkapkan pengelompokan. Dalam algoritma ini, komuniti graf biasanya ditakrifkan sebagai subset bucu yang bersambung lebih rapat daripada bahagian lain rangkaian.
Mungkin kes yang paling intuitif ialah rangkaian sosial. Bucu mewakili orang, dan tepi yang menghubungkan bucu mewakili pengguna yang merupakan rakan atau peminat. Walau bagaimanapun, untuk memodelkan sistem sebagai rangkaian, kita mesti mencari cara untuk menyambungkan pelbagai komponen dengan cekap. Beberapa aplikasi inovatif teori graf untuk pengelompokan termasuk pengekstrakan ciri data imej, analisis rangkaian pengawalseliaan gen, dsb.
Di bawah ialah rajah ringkas yang menunjukkan 8 tapak web yang dilihat baru-baru ini, disambungkan berdasarkan pautan dari halaman Wikipedia mereka.
Warna bucu ini menunjukkan perhubungan kumpulannya dan saiz ditentukan berdasarkan pusatnya. Kelompok ini juga masuk akal dalam kehidupan sebenar, di mana bucu kuning biasanya merupakan tapak rujukan/carian dan bucu biru adalah semua tapak penerbitan dalam talian (artikel, tweet atau kod).
Andaikan kita telah mengelompokkan rangkaian ke dalam kumpulan. Kami kemudiannya boleh menggunakan skor modulariti ini untuk menilai kualiti pengelompokan. Skor yang lebih tinggi bermakna kami membahagikan rangkaian kepada kumpulan "tepat", manakala skor rendah bermakna pengelompokan kami lebih hampir kepada rawak. Seperti yang ditunjukkan dalam rajah di bawah:
Modulariti boleh dikira menggunakan formula berikut:
di mana L mewakili tepi dalam rangkaian Kuantiti, k_i dan k_j merujuk kepada darjah setiap bucu, yang boleh didapati dengan menjumlahkan sebutan bagi setiap baris dan lajur. Mendarab dua dan membahagi dengan 2L mewakili jangkaan bilangan tepi antara bucu i dan j apabila rangkaian ditugaskan secara rawak.
Secara keseluruhan, istilah dalam kurungan mewakili perbezaan antara struktur sebenar rangkaian dan struktur yang dijangkakan apabila digabungkan secara rawak. Mengkaji nilainya menunjukkan bahawa ia mengembalikan nilai tertinggi apabila A_ij = 1 dan ( k_i k_j ) / 2L adalah kecil. Ini bermakna apabila terdapat kelebihan "tidak dijangka" antara titik tetap i dan j, nilai yang terhasil adalah lebih tinggi.
δc_i yang terakhir, c_j ialah fungsi Kronecker δ yang terkenal (fungsi Kronecker-delta). Berikut ialah penjelasan Pythonnya:
Kemodulatan graf boleh dikira melalui formula di atas, dan lebih tinggi modulariti, lebih baik tahap rangkaian dikelompokkan ke dalam kumpulan yang berbeza. Oleh itu, cara terbaik untuk mengelompokkan rangkaian boleh didapati dengan mencari modulariti maksimum melalui kaedah pengoptimuman.
Kombinatorik memberitahu kita bahawa untuk rangkaian dengan hanya 8 bucu, terdapat 4140 kaedah pengelompokan yang berbeza. Rangkaian 16 bucu akan dikelompokkan dalam lebih 10 bilion cara. Kaedah pengelompokan yang mungkin bagi rangkaian dengan 32 bucu akan melebihi 128 septillion (10^21); jika rangkaian anda mempunyai 80 bucu, bilangan kaedah pengelompokan yang mungkin telah melebihi bilangan kaedah pengelompokan dalam alam semesta yang boleh diperhatikan.
Oleh itu, kita mesti menggunakan heuristik yang berfungsi dengan baik dalam menilai kelompok yang menghasilkan skor modulariti tertinggi, tanpa mencuba setiap kemungkinan. Ini ialah algoritma yang dipanggil Fast-Greedy Modularity-Maximization, yang agak serupa dengan algoritma pengelompokan hierarki aglomeratif yang diterangkan di atas. Cuma Mod-Max tidak menggabungkan kumpulan berdasarkan jarak, tetapi menggabungkan kumpulan berdasarkan perubahan dalam modulariti.
Begini cara ia berfungsi:
Pengesanan komuniti ialah bidang penyelidikan yang popular dalam teori graf Keterbatasannya ditunjukkan terutamanya dalam fakta bahawa ia mengabaikan beberapa kelompok kecil dan hanya terpakai pada model graf berstruktur. Walau bagaimanapun, jenis algoritma ini mempunyai prestasi yang sangat baik dalam data berstruktur biasa dan data rangkaian sebenar.
Di atas ialah 6 algoritma pengelompokan utama yang perlu diketahui oleh saintis data! Kami akan menamatkan artikel ini dengan menunjukkan visualisasi pelbagai algoritma!
Atas ialah kandungan terperinci Enam algoritma pengelompokan yang mesti diketahui oleh saintis data. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!