Algoritma pengelompokan data. Algoritma berdasarkan teori graf

Analisis kluster ialah

selamat hari. Di sini saya menghormati orang yang peminat karya mereka.

Maxim, kawan saya, tergolong dalam kategori ini. Sentiasa bekerja dengan angka, menganalisisnya, membuat laporan yang berkaitan.

Semalam kami makan tengah hari bersama-sama, jadi selama hampir setengah jam dia memberitahu saya tentang analisis kelompok - apakah itu dan dalam kes apa penggunaannya adalah munasabah dan suai manfaat. Nah, bagaimana dengan saya?

Saya mempunyai ingatan yang baik, jadi saya akan memberikan anda semua data ini, dengan cara itu, yang saya sudah tahu dalam bentuk asal dan paling bermaklumat.

Analisis kluster direka untuk membahagikan satu set objek kepada kumpulan homogen (kluster atau kelas). Ini adalah tugas klasifikasi data multivariate.

Terdapat kira-kira 100 algoritma pengelompokan yang berbeza, namun, yang paling biasa digunakan ialah analisis kelompok hierarki dan pengelompokan k-means.

Di manakah analisis kluster digunakan? Dalam pemasaran, ini adalah pembahagian pesaing dan pengguna.

Dalam pengurusan: pembahagian kakitangan kepada kumpulan tahap motivasi yang berbeza, klasifikasi pembekal, pengenalpastian situasi pengeluaran yang serupa di mana perkahwinan berlaku.

Dalam perubatan, klasifikasi gejala, pesakit, ubat. Dalam sosiologi, pembahagian responden kepada kumpulan homogen. Malah, analisis kelompok telah membuktikan dirinya dengan baik dalam semua bidang kehidupan manusia.

Keindahan kaedah ini ialah ia berfungsi walaupun terdapat sedikit data dan keperluan untuk kenormalan taburan pembolehubah rawak dan keperluan lain kaedah klasik analisis statistik tidak dipenuhi.

Mari kita terangkan intipati analisis kelompok tanpa menggunakan istilah yang ketat:
Katakan anda menjalankan tinjauan terhadap pekerja dan ingin menentukan cara anda boleh mengurus kakitangan anda dengan paling berkesan.

Iaitu, anda ingin membahagikan pekerja kepada kumpulan dan memilih tuas kawalan yang paling berkesan untuk setiap daripada mereka. Pada masa yang sama, perbezaan antara kumpulan harus jelas, dan dalam kumpulan itu, responden harus sesama mungkin.

Untuk menyelesaikan masalah, dicadangkan untuk menggunakan analisis kelompok hierarki.

Akibatnya, kita akan mendapat pokok, melihat di mana kita mesti memutuskan berapa banyak kelas (kluster) yang kita mahu bahagikan kakitangan.

Katakan kita memutuskan untuk membahagikan kakitangan kepada tiga kumpulan, kemudian untuk mengkaji responden yang jatuh ke dalam setiap kelompok, kita mendapat tablet dengan kandungan berikut:

Mari kita terangkan bagaimana jadual di atas terbentuk. Lajur pertama mengandungi nombor kluster — kumpulan yang datanya ditunjukkan dalam baris.

Sebagai contoh, kelompok pertama ialah 80% lelaki. 90% daripada kluster pertama jatuh ke dalam kumpulan umur dari 30 hingga 50 tahun, dan 12% daripada responden percaya bahawa faedah adalah sangat penting. Dan sebagainya.

Mari cuba buat potret responden setiap kluster:

Kumpulan pertama kebanyakannya adalah lelaki yang sudah matang, menduduki jawatan kepimpinan. Pakej sosial (MED, LGOTI, masa lapang MASA) tidak menarik minat mereka. Mereka lebih suka menerima gaji yang lumayan, daripada bantuan daripada majikan.
Kumpulan dua, sebaliknya, lebih suka pakej sosial. Ia terdiri terutamanya daripada orang "tua" yang menduduki jawatan rendah. Gaji sememangnya penting bagi mereka, tetapi ada keutamaan lain.
Kumpulan ketiga adalah "termuda". Tidak seperti dua sebelumnya, terdapat minat yang jelas dalam pembelajaran dan peluang pertumbuhan profesional. Kategori pekerja ini mempunyai peluang yang baik untuk menambah kumpulan pertama tidak lama lagi.

Oleh itu, apabila merancang kempen untuk memperkenalkan kaedah pengurusan kakitangan yang berkesan, adalah jelas bahawa dalam situasi kita adalah mungkin untuk meningkatkan pakej sosial untuk kumpulan kedua yang merugikan, contohnya, gaji.

Jika kita bercakap tentang pakar mana yang harus dihantar untuk latihan, maka kami pasti boleh mengesyorkan memberi perhatian kepada kumpulan ketiga.

Sumber: http://www.nickart.spb.ru/analysis/cluster.php

Ciri-ciri analisis kelompok

Kelompok ialah harga aset dalam tempoh masa tertentu semasa urus niaga dibuat. Jumlah pembelian dan jualan yang terhasil ditunjukkan oleh nombor dalam kelompok.

Bar mana-mana TF mengandungi, sebagai peraturan, beberapa kelompok. Ini membolehkan anda melihat secara terperinci jumlah pembelian, jualan dan bakinya dalam setiap bar individu, untuk setiap tahap harga.

Perubahan dalam harga satu aset tidak dapat dielakkan melibatkan rantaian pergerakan harga pada instrumen lain juga.

Perhatian!

Dalam kebanyakan kes, pemahaman tentang pergerakan arah aliran sudah berlaku pada masa ia berkembang pesat, dan memasuki pasaran sepanjang arah aliran penuh dengan jatuh ke dalam gelombang pembetulan.

Untuk dagangan yang berjaya, adalah perlu untuk memahami situasi semasa dan dapat menjangka pergerakan harga masa hadapan. Ini boleh dipelajari dengan menganalisis graf kelompok.

Dengan bantuan analisis kelompok, anda boleh melihat aktiviti peserta pasaran di dalam bar harga terkecil sekalipun. Ini adalah analisis yang paling tepat dan terperinci, kerana ia menunjukkan pengagihan mata volum transaksi untuk setiap tahap harga aset.

Dalam pasaran terdapat konfrontasi berterusan antara kepentingan penjual dan pembeli. Dan setiap pergerakan harga terkecil (tandakan) adalah langkah kepada kompromi - tahap harga - yang sesuai dengan kedua-dua pihak pada masa ini.

Tetapi pasaran adalah dinamik, bilangan penjual dan pembeli sentiasa berubah. Jika pada satu ketika pasaran dikuasai oleh penjual, maka saat berikutnya, kemungkinan besar, akan ada pembeli.

Bilangan urus niaga selesai pada tahap harga jiran juga tidak sama. Namun, pertama, keadaan pasaran dicerminkan dalam jumlah jumlah urus niaga, dan hanya kemudian pada harga.

Jika anda melihat tindakan peserta pasaran yang dominan (penjual atau pembeli), maka anda boleh meramalkan pergerakan harga itu sendiri.

Untuk berjaya menggunakan analisis kluster, anda perlu terlebih dahulu memahami maksud kluster dan delta.

Kluster dipanggil pergerakan harga, yang dibahagikan kepada tahap di mana transaksi dibuat dengan volum yang diketahui. Delta menunjukkan perbezaan antara pembelian dan penjualan yang berlaku dalam setiap kelompok.

Setiap kelompok, atau kumpulan delta, membolehkan anda memikirkan sama ada pembeli atau penjual menguasai pasaran pada masa tertentu.

Cukup sekadar mengira jumlah delta dengan menjumlahkan jualan dan pembelian. Jika delta negatif, maka pasaran terlebih jual, terdapat transaksi jual berlebihan. Apabila delta positif, pasaran jelas dikuasai oleh pembeli.

Delta itu sendiri boleh mengambil nilai normal atau kritikal. Nilai volum delta melebihi nilai normal dalam kelompok diserlahkan dengan warna merah.

Jika delta adalah sederhana, maka ini mencirikan keadaan rata dalam pasaran. Dengan nilai delta biasa, pergerakan arah aliran diperhatikan dalam pasaran, tetapi nilai kritikal sentiasa menjadi petanda kepada pembalikan harga.

Dagangan forex dengan CA

Untuk mendapatkan keuntungan maksimum, anda perlu dapat menentukan peralihan delta dari tahap sederhana kepada normal. Malah, dalam kes ini, anda boleh melihat permulaan peralihan dari rata kepada pergerakan trend dan boleh mendapatkan keuntungan yang paling banyak.

Carta kelompok lebih visual, padanya anda boleh melihat tahap pengumpulan dan pengedaran volum yang ketara, membina tahap sokongan dan rintangan. Ini membolehkan peniaga mencari kemasukan yang tepat kepada perdagangan.

Menggunakan delta, seseorang boleh menilai dominasi jualan atau pembelian di pasaran. Analisis kelompok membolehkan anda memerhati urus niaga dan menjejaki volumnya di dalam bar mana-mana TF.

Ini amat penting apabila menghampiri tahap sokongan atau rintangan yang ketara. Pertimbangan kelompok adalah kunci untuk memahami pasaran.

Sumber: http://orderflowtrading.ru/analitika-rynka/obemy/klasternyy-analiz/

Bidang dan ciri aplikasi analisis kelompok

Istilah analisis kelompok (pertama kali diperkenalkan oleh Tryon, 1939) sebenarnya termasuk satu set algoritma klasifikasi yang berbeza.

Soalan lazim yang ditanya oleh penyelidik dalam banyak bidang ialah cara menyusun data yang diperhatikan ke dalam struktur visual, i.e. mengembangkan taksonomi.

Menurut sistem moden yang diterima dalam biologi, manusia tergolong dalam primata, mamalia, amniot, vertebrata dan haiwan.

Ambil perhatian bahawa dalam pengelasan ini, semakin tinggi tahap pengagregatan, semakin kurang persamaan antara ahli dalam kelas yang sepadan.

Manusia mempunyai lebih banyak persamaan dengan primata lain (iaitu, beruk) berbanding dengan ahli keluarga mamalia yang "jauh" (iaitu, anjing), dan sebagainya.

Ambil perhatian bahawa perbincangan sebelumnya merujuk kepada algoritma pengelompokan, tetapi tidak menyebut apa-apa tentang ujian untuk kepentingan statistik.

Sebenarnya, analisis kelompok bukanlah kaedah statistik biasa sebagai "set" pelbagai algoritma untuk "mengedarkan objek ke dalam kelompok".

Terdapat pandangan bahawa, tidak seperti kebanyakan prosedur statistik lain, kaedah analisis kelompok digunakan dalam kebanyakan kes apabila anda tidak mempunyai sebarang hipotesis priori tentang kelas, tetapi masih dalam peringkat deskriptif penyelidikan.

Perhatian!

Perlu difahami bahawa analisis kelompok menentukan "keputusan yang paling mungkin bermakna".

Oleh itu, ujian untuk kepentingan statistik tidak benar-benar terpakai di sini, walaupun dalam kes di mana tahap-p diketahui (seperti, sebagai contoh, dalam kaedah K-means).

Teknik pengelompokan digunakan dalam pelbagai bidang. Hartigan (1975) telah memberikan gambaran yang sangat baik tentang banyak kajian yang diterbitkan yang mengandungi keputusan yang diperoleh melalui kaedah analisis kelompok.

Sebagai contoh, dalam bidang perubatan, pengelompokan penyakit, rawatan penyakit, atau gejala penyakit membawa kepada taksonomi yang digunakan secara meluas.

Dalam bidang psikiatri, diagnosis yang betul bagi kumpulan gejala seperti paranoia, skizofrenia, dan lain-lain adalah penting untuk terapi yang berjaya. Dalam arkeologi, menggunakan analisis kluster, penyelidik cuba mewujudkan taksonomi alat batu, objek pengebumian, dll.

Terdapat aplikasi luas analisis kluster dalam penyelidikan pemasaran. Secara umum, apabila perlu untuk mengklasifikasikan "gunung" maklumat ke dalam kumpulan yang sesuai untuk pemprosesan selanjutnya, analisis kelompok ternyata sangat berguna dan berkesan.

Pengelompokan Pokok

Contoh dalam bahagian Tujuan Utama menerangkan tujuan algoritma gabungan (kelompok pokok).

Tujuan algoritma ini adalah untuk menggabungkan objek (contohnya, haiwan) ke dalam kelompok yang cukup besar menggunakan beberapa ukuran persamaan atau jarak antara objek. Hasil tipikal pengelompokan sedemikian ialah pokok hierarki.

Pertimbangkan gambar rajah pokok mendatar. Gambar rajah bermula dengan setiap objek dalam kelas (di sebelah kiri gambar rajah).

Sekarang bayangkan bahawa secara beransur-ansur (dalam langkah yang sangat kecil) anda "melemahkan" kriteria anda untuk objek apa yang unik dan apa yang tidak.

Dalam erti kata lain, anda menurunkan ambang yang berkaitan dengan keputusan untuk menggabungkan dua atau lebih objek ke dalam satu kelompok.

Akibatnya, anda memautkan lebih banyak objek bersama-sama dan mengagregat (menggabungkan) lebih banyak kumpulan elemen yang semakin berbeza.

Akhirnya, dalam langkah terakhir, semua objek digabungkan bersama. Dalam carta ini, paksi mendatar mewakili jarak pengumpulan (dalam dendrogram menegak, paksi menegak mewakili jarak pengumpulan).

Jadi, untuk setiap nod dalam graf (di mana kluster baharu terbentuk), anda boleh melihat jumlah jarak yang mana unsur-unsur yang sepadan dipautkan ke dalam kluster tunggal baharu.

Apabila data mempunyai "struktur" yang jelas dari segi kelompok objek yang serupa antara satu sama lain, maka struktur ini berkemungkinan akan dicerminkan dalam pokok hierarki oleh pelbagai cabang.

Hasil daripada analisis yang berjaya dengan kaedah gabungan, ia menjadi mungkin untuk mengesan kelompok (cawangan) dan mentafsirnya.

Kaedah pengelompokan kesatuan atau pokok digunakan dalam pembentukan gugusan ketidaksamaan atau jarak antara objek. Jarak ini boleh ditakrifkan dalam ruang satu dimensi atau multidimensi.

Sebagai contoh, jika anda perlu mengelompokkan jenis makanan di kafe, anda boleh mengambil kira jumlah kalori yang terkandung di dalamnya, harga, penilaian subjektif rasa, dll.

Cara paling langsung untuk mengira jarak antara objek dalam ruang berbilang dimensi ialah mengira jarak Euclidean.

Jika anda mempunyai ruang 2D atau 3D, maka ukuran ini ialah jarak geometri sebenar antara objek dalam ruang (seolah-olah jarak antara objek diukur dengan pita pengukur).

Walau bagaimanapun, algoritma pengumpulan tidak "mengambil berat" sama ada jarak "disediakan" untuk itu adalah sebenar atau beberapa ukuran jarak terbitan lain, yang lebih bermakna kepada penyelidik; dan cabaran bagi penyelidik adalah untuk memilih kaedah yang betul untuk aplikasi tertentu.

Jarak Euclidean. Ini nampaknya jenis jarak yang paling biasa. Ia hanyalah jarak geometri dalam ruang berbilang dimensi dan dikira seperti berikut:

Ambil perhatian bahawa jarak Euclidean (dan segi empat samanya) dikira daripada data asal, bukan daripada data piawai.

Ini adalah cara biasa untuk mengiranya, yang mempunyai kelebihan tertentu (sebagai contoh, jarak antara dua objek tidak berubah apabila objek baharu dimasukkan ke dalam analisis, yang mungkin berubah menjadi outlier).

Perhatian!

Walau bagaimanapun, jarak boleh dipengaruhi oleh perbezaan antara paksi dari mana jarak dikira. Sebagai contoh, jika salah satu paksi diukur dalam sentimeter, dan kemudian anda menukarnya kepada milimeter (dengan mendarabkan nilai dengan 10), maka jarak Euclidean akhir (atau kuasa dua jarak Euclidean) yang dikira daripada koordinat akan berubah secara mendadak, dan, akibatnya, hasil analisis kelompok boleh sangat berbeza daripada yang sebelumnya.

Kuadrat jarak Euclidean. Kadang-kadang anda mungkin mahu kuasa duakan jarak Euclidean standard untuk memberi lebih berat kepada objek yang lebih jauh.

Jarak ini dikira seperti berikut:

Jarak blok bandar (jarak Manhattan). Jarak ini hanyalah purata perbezaan ke atas koordinat.

Dalam kebanyakan kes, ukuran jarak ini membawa kepada keputusan yang sama seperti untuk jarak Euclid biasa.

Walau bagaimanapun, ambil perhatian bahawa untuk ukuran ini pengaruh perbezaan besar individu (outlier) berkurangan (kerana ia tidak kuasa dua). Jarak Manhattan dikira menggunakan formula:

Jarak Chebyshev. Jarak ini boleh berguna apabila seseorang ingin mentakrifkan dua objek sebagai "berbeza" jika ia berbeza dalam mana-mana satu koordinat (mana-mana satu dimensi). Jarak Chebyshev dikira dengan formula:

Jarak kuasa. Kadangkala dikehendaki untuk menambah atau mengurangkan berat yang berkaitan dengan dimensi secara progresif yang objek yang sepadan sangat berbeza.

Ini boleh dicapai menggunakan jarak undang-undang kuasa. Jarak kuasa dikira dengan formula:

di mana r dan p ialah parameter yang ditentukan pengguna. Beberapa contoh pengiraan boleh menunjukkan cara ukuran ini "berfungsi".

Parameter p bertanggungjawab untuk pemberatan beransur-ansur perbezaan dalam koordinat individu, parameter r bertanggungjawab untuk pemberat progresif jarak yang jauh antara objek. Jika kedua-dua parameter - r dan p, adalah sama dengan dua, maka jarak ini bertepatan dengan jarak Euclidean.

Peratusan perselisihan faham. Ukuran ini digunakan apabila data adalah kategori. Jarak ini dikira dengan formula:

Peraturan persatuan atau persatuan

Pada langkah pertama, apabila setiap objek adalah kelompok yang berasingan, jarak antara objek ini ditentukan oleh ukuran yang dipilih.

Walau bagaimanapun, apabila beberapa objek disambungkan bersama, persoalan timbul, bagaimanakah jarak antara kluster harus ditentukan?

Dalam erti kata lain, anda memerlukan peraturan gabungan atau pautan untuk dua kluster. Terdapat pelbagai kemungkinan di sini: sebagai contoh, anda boleh memautkan dua gugusan bersama apabila mana-mana dua objek dalam dua gugusan lebih dekat antara satu sama lain daripada jarak pautan yang sepadan.

Dalam erti kata lain, anda menggunakan "peraturan jiran terdekat" untuk menentukan jarak antara kelompok; kaedah ini dipanggil kaedah pautan tunggal.

Peraturan ini membina kelompok "berserabut", i.e. kelompok "dihubungkan bersama" hanya oleh elemen individu yang kebetulan lebih dekat antara satu sama lain daripada yang lain.

Sebagai alternatif, anda boleh menggunakan jiran dalam kelompok yang paling jauh antara satu sama lain daripada semua pasangan ciri lain. Kaedah ini dipanggil kaedah pautan penuh.

Terdapat juga banyak kaedah lain untuk menyertai kluster, sama seperti yang telah dibincangkan.

Sambungan tunggal (kaedah jiran terdekat). Seperti yang diterangkan di atas, dalam kaedah ini, jarak antara dua kelompok ditentukan oleh jarak antara dua objek terdekat (jiran terdekat) dalam kelompok yang berbeza.

Peraturan ini mesti, dalam erti kata lain, rentetan objek bersama-sama untuk membentuk gugusan, dan gugusan yang terhasil cenderung diwakili oleh "rentetan" yang panjang.

Sambungan penuh (kaedah jiran yang paling jauh). Dalam kaedah ini, jarak antara kelompok ditakrifkan sebagai jarak terbesar antara mana-mana dua objek dalam kelompok yang berbeza (iaitu "jiran paling jauh").

Min berpasangan tidak berwajaran. Dalam kaedah ini, jarak antara dua kelompok berbeza dikira sebagai jarak purata antara semua pasangan objek di dalamnya.

Kaedah ini berkesan apabila objek sebenarnya membentuk "kebun" yang berbeza, tetapi ia berfungsi sama baik dalam kes kelompok lanjutan (jenis "rantaian").

Perhatikan bahawa dalam buku mereka Sneath dan Sokal (1973) memperkenalkan singkatan UPGMA untuk merujuk kepada kaedah ini sebagai kaedah kumpulan pasangan tidak berwajaran menggunakan purata aritmetik.

Min berpasangan wajaran. Kaedah ini adalah sama dengan kaedah purata berpasangan tidak berwajaran, kecuali saiz kelompok masing-masing (iaitu, bilangan objek yang terkandung di dalamnya) digunakan sebagai faktor pemberat dalam pengiraan.

Oleh itu, kaedah yang dicadangkan harus digunakan (bukan yang sebelumnya) apabila saiz kelompok yang tidak sama diandaikan.

Sneath dan Sokal (1973) memperkenalkan singkatan WPGMA untuk merujuk kaedah ini sebagai kaedah kumpulan pasangan berwajaran menggunakan purata aritmetik.

Kaedah centroid tanpa pemberat. Dalam kaedah ini, jarak antara dua gugusan ditakrifkan sebagai jarak antara pusat graviti mereka.

Perhatian!

Sneath dan Sokal (1973) menggunakan akronim UPGMC untuk merujuk kaedah ini sebagai kaedah kumpulan pasangan tidak berwajaran menggunakan purata centroid.

Kaedah centroid berwajaran (median). Kaedah ini adalah sama dengan yang sebelumnya, kecuali pemberat digunakan dalam pengiraan untuk mengambil kira perbezaan antara saiz kelompok (iaitu, bilangan objek di dalamnya).

Oleh itu, jika terdapat (atau disyaki) perbezaan ketara dalam saiz kelompok, kaedah ini adalah lebih baik daripada yang sebelumnya.

Sneath dan Sokal (1973) menggunakan singkatan WPGMC untuk merujuknya sebagai kaedah kumpulan pasangan berwajaran menggunakan purata centroid.

Kaedah wad. Kaedah ini berbeza daripada semua kaedah lain kerana ia menggunakan kaedah ANOVA untuk menganggar jarak antara kelompok.

Kaedah ini meminimumkan jumlah kuasa dua (SS) untuk mana-mana dua kelompok (hipotesis) yang boleh dibentuk pada setiap langkah.

Butiran boleh didapati dalam Ward (1963). Secara umum, kaedah ini nampaknya sangat cekap, tetapi ia cenderung untuk mencipta kelompok kecil.

Terdahulu kaedah ini telah dibincangkan dari segi "objek" yang sepatutnya dikelompokkan. Dalam semua jenis analisis yang lain, persoalan yang menarik minat penyelidik biasanya dinyatakan dalam bentuk pemerhatian atau pembolehubah.

Ternyata pengelompokan, baik melalui pemerhatian dan pembolehubah, boleh membawa kepada hasil yang agak menarik.

Sebagai contoh, bayangkan seorang penyelidik perubatan sedang mengumpul data tentang pelbagai ciri (pembolehubah) keadaan pesakit (pemerhatian) dengan penyakit jantung.

Penyiasat mungkin ingin membuat pemerhatian kelompok (pesakit) untuk mengenal pasti kelompok pesakit yang mempunyai simptom yang sama.

Pada masa yang sama, penyelidik mungkin ingin mengelompokkan pembolehubah untuk mengenal pasti kelompok pembolehubah yang dikaitkan dengan keadaan fizikal yang serupa.e

Selepas perbincangan ini mengenai sama ada untuk mengelompokkan pemerhatian atau pembolehubah, seseorang mungkin bertanya, mengapa tidak berkelompok dalam kedua-dua arah?

Modul Analisis Kluster mengandungi prosedur gabungan dua hala yang cekap untuk melakukan perkara itu.

Walau bagaimanapun, pengumpulan dua hala digunakan (agak jarang) dalam keadaan di mana kedua-dua pemerhatian dan pembolehubah dijangka menyumbang secara serentak kepada penemuan kelompok yang bermakna.

Jadi, kembali kepada contoh sebelumnya, kita boleh mengandaikan bahawa penyelidik perubatan perlu mengenal pasti kelompok pesakit yang serupa berkaitan dengan kelompok ciri keadaan fizikal tertentu.

Kesukaran dalam mentafsir keputusan yang diperoleh timbul daripada fakta bahawa persamaan antara kelompok yang berbeza mungkin datang daripada (atau menjadi punca) beberapa perbezaan dalam subset pembolehubah.

Oleh itu, kluster yang terhasil sememangnya heterogen. Mungkin ia kelihatan agak kabur pada mulanya; sesungguhnya, berbanding dengan kaedah analisis kelompok lain yang diterangkan, pengumpulan dua hala mungkin merupakan kaedah yang paling jarang digunakan.

Walau bagaimanapun, sesetengah penyelidik percaya bahawa ia menawarkan alat yang berkuasa untuk analisis data penerokaan (untuk maklumat lanjut, lihat penerangan Hartigan tentang kaedah ini (Hartigan, 1975)).

K bermaksud kaedah

Kaedah pengelompokan ini berbeza dengan ketara daripada kaedah aglomeratif seperti Kesatuan (kelompok pokok) dan Kesatuan Dua Hala. Katakan anda sudah mempunyai hipotesis tentang bilangan kelompok (mengikut pemerhatian atau mengikut pembolehubah).

Anda boleh memberitahu sistem untuk membentuk tiga gugusan dengan tepat supaya ia berbeza yang mungkin.

Ini betul-betul jenis masalah yang diselesaikan oleh algoritma K-Means. Secara umum, kaedah K-means membina gugusan K yang berbeza dengan jarak yang berbeza sejauh mungkin.

Dalam contoh keadaan fizikal, penyelidik perubatan mungkin mempunyai "firasat" daripada pengalaman klinikal mereka bahawa pesakit mereka secara amnya termasuk dalam tiga kategori berbeza.

Perhatian!

Jika ya, maka cara pelbagai ukuran parameter fizikal bagi setiap kelompok akan menyediakan cara kuantitatif untuk mewakili hipotesis penyiasat (cth, pesakit dalam kelompok 1 mempunyai parameter tinggi 1, parameter lebih rendah 2, dsb.).

Dari sudut pengiraan, anda boleh menganggap kaedah ini sebagai analisis varians "secara terbalik". Program ini bermula dengan K gugusan yang dipilih secara rawak, dan kemudian menukar kepunyaan objek kepada mereka untuk:

meminimumkan kebolehubahan dalam kelompok,
memaksimumkan kebolehubahan antara kelompok.

Kaedah ini adalah serupa dengan analisis terbalik varians (ANOVA) kerana ujian keertian dalam ANOVA membandingkan antara kumpulan berbanding kebolehubahan dalam kumpulan dalam menguji hipotesis bahawa kumpulan bermakna berbeza antara satu sama lain.

Dalam pengelompokan K-means, atur cara memindahkan objek (iaitu, pemerhatian) dari satu kumpulan (kluster) ke kumpulan lain untuk mendapatkan hasil yang paling ketara apabila melakukan analisis varians (ANOVA).

Lazimnya, sebaik sahaja keputusan analisis kluster K-means diperoleh, seseorang boleh mengira min untuk setiap kluster bagi setiap dimensi untuk menilai bagaimana kluster berbeza antara satu sama lain.

Sebaik-baiknya, anda harus mendapatkan cara yang sangat berbeza untuk kebanyakan, jika tidak semua, ukuran yang digunakan dalam analisis.

Sumber: http://www.biometrica.tomsk.ru/textbook/modules/stcluan.html

Pengelasan objek mengikut ciri-cirinya

Analisis kluster (analisis kluster) - satu set kaedah statistik multidimensi untuk mengklasifikasikan objek mengikut ciri-ciri mereka, membahagikan satu set objek ke dalam kumpulan homogen yang rapat dari segi menentukan kriteria, memilih objek kumpulan tertentu.

Kelompok ialah sekumpulan objek yang dikenal pasti sebagai hasil analisis kelompok berdasarkan ukuran persamaan atau perbezaan yang diberikan antara objek.

Objek adalah subjek kajian khusus yang perlu diklasifikasikan. Objek dalam pengelasan adalah, sebagai peraturan, pemerhatian. Contohnya, pengguna produk, negara atau wilayah, produk, dsb.

Walaupun adalah mungkin untuk menjalankan analisis kelompok dengan pembolehubah. Pengelasan objek dalam analisis kelompok multidimensi berlaku mengikut beberapa kriteria secara serentak.

Ini boleh menjadi pembolehubah kuantitatif dan kategori, bergantung pada kaedah analisis kelompok. Jadi, matlamat utama analisis kelompok adalah untuk mencari kumpulan objek yang serupa dalam sampel.

Set kaedah statistik multidimensi analisis kelompok boleh dibahagikan kepada kaedah hierarki (aglomeratif dan pembahagian) dan bukan hierarki (kaedah k-means, analisis kelompok dua peringkat).

Walau bagaimanapun, tiada klasifikasi kaedah yang diterima umum, dan kadangkala kaedah analisis kelompok juga termasuk kaedah untuk membina pepohon keputusan, rangkaian saraf, analisis diskriminasi, dan regresi logistik.

Skop analisis kluster, kerana serba boleh, adalah sangat luas. Analisis kluster digunakan dalam ekonomi, pemasaran, arkeologi, perubatan, psikologi, kimia, biologi, pentadbiran awam, filologi, antropologi, sosiologi dan bidang lain.

Berikut ialah beberapa contoh penggunaan analisis kelompok:

perubatan - klasifikasi penyakit, gejala mereka, kaedah rawatan, klasifikasi kumpulan pesakit;
pemasaran - tugas mengoptimumkan barisan produk syarikat, membahagikan pasaran mengikut kumpulan barangan atau pengguna, mengenal pasti pengguna berpotensi;
sosiologi - pembahagian responden kepada kumpulan homogen;
psikiatri - diagnosis yang betul bagi kumpulan gejala adalah penting untuk terapi yang berjaya;
biologi - pengelasan organisma mengikut kumpulan;
ekonomi - klasifikasi subjek Persekutuan Rusia mengikut daya tarikan pelaburan.

Sumber: http://www.statmethods.ru/konsalting/statistics-methody/121-klasternyj-analyz.html

Maklumat am tentang analisis kelompok

Analisis kelompok termasuk satu set algoritma pengelasan yang berbeza. Soalan lazim yang ditanya oleh penyelidik dalam banyak bidang ialah cara menyusun data yang diperhatikan ke dalam struktur visual.

Sebagai contoh, ahli biologi bertujuan untuk memecahkan haiwan kepada spesies yang berbeza untuk menerangkan secara bermakna perbezaan antara mereka.

Tugas analisis kelompok adalah untuk membahagikan set awal objek kepada kumpulan objek yang serupa dan rapat. Kumpulan ini dipanggil kelompok.

Dengan kata lain, analisis kelompok adalah salah satu cara untuk mengklasifikasikan objek mengikut ciri-cirinya. Adalah wajar bahawa keputusan klasifikasi mempunyai tafsiran yang bermakna.

Keputusan yang diperoleh melalui kaedah analisis kelompok digunakan dalam pelbagai bidang. Dalam pemasaran, ia adalah pembahagian pesaing dan pengguna.

Dalam psikiatri, diagnosis simptom yang betul seperti paranoia, skizofrenia, dll. adalah penting untuk terapi yang berjaya.

Dalam pengurusan, klasifikasi pembekal adalah penting, pengenalpastian situasi pengeluaran yang serupa di mana perkahwinan berlaku. Dalam sosiologi, pembahagian responden kepada kumpulan homogen. Dalam pelaburan portfolio, adalah penting untuk mengumpulkan sekuriti mengikut persamaan mereka dalam arah aliran pulangan untuk menyusun, berdasarkan maklumat yang diperoleh tentang pasaran saham, portfolio pelaburan optimum yang membolehkan memaksimumkan pulangan pelaburan untuk tahap risiko tertentu. .

Secara umum, apabila perlu untuk mengklasifikasikan sejumlah besar maklumat seperti ini dan membentangkannya dalam bentuk yang sesuai untuk pemprosesan selanjutnya, analisis kelompok ternyata sangat berguna dan berkesan.

Analisis kelompok membolehkan mempertimbangkan jumlah maklumat yang agak besar dan memampatkan susunan besar maklumat sosio-ekonomi, menjadikannya padat dan visual.

Perhatian!

Analisis kelompok adalah sangat penting berhubung dengan set siri masa yang mencirikan pembangunan ekonomi (contohnya, keadaan ekonomi dan komoditi am).

Di sini adalah mungkin untuk memilih tempoh apabila nilai penunjuk yang sepadan agak hampir, serta menentukan kumpulan siri masa, yang dinamiknya paling serupa.

Dalam masalah ramalan sosio-ekonomi, adalah sangat menjanjikan untuk menggabungkan analisis kelompok dengan kaedah kuantitatif lain (contohnya, dengan analisis regresi).

Kelebihan dan kekurangan

Analisis kelompok membolehkan klasifikasi objektif bagi mana-mana objek yang dicirikan oleh beberapa ciri. Terdapat beberapa faedah yang boleh diperolehi daripada ini:

Kelompok yang terhasil boleh ditafsirkan, iaitu untuk menerangkan jenis kumpulan yang sebenarnya wujud.
Kelompok individu boleh dimusnahkan. Ini berguna dalam kes di mana ralat tertentu dibuat dalam set data, akibatnya nilai penunjuk untuk objek individu menyimpang dengan ketara. Apabila menggunakan analisis kelompok, objek tersebut jatuh ke dalam kelompok yang berasingan.
Untuk analisis lanjut, hanya kluster yang mempunyai ciri-ciri minat boleh dipilih.

Seperti kaedah lain, analisis kelompok mempunyai kelemahan dan batasan tertentu. Khususnya, komposisi dan bilangan kluster bergantung pada kriteria pembahagian yang dipilih.

Apabila mengurangkan tatasusunan data awal kepada bentuk yang lebih padat, herotan tertentu mungkin berlaku, dan ciri individu objek individu juga mungkin hilang disebabkan oleh penggantian mereka dengan ciri-ciri nilai umum parameter kelompok.

Kaedah

Pada masa ini, lebih daripada seratus algoritma pengelompokan yang berbeza diketahui. Kepelbagaian mereka dijelaskan bukan sahaja oleh kaedah pengiraan yang berbeza, tetapi juga oleh konsep yang berbeza yang mendasari pengelompokan.

Pakej Statistica melaksanakan kaedah pengelompokan berikut.

Algoritma hierarki - pengelompokan pokok. Algoritma hierarki adalah berdasarkan idea pengelompokan berjujukan. Pada langkah awal, setiap objek dianggap sebagai gugusan yang berasingan. Pada langkah seterusnya, beberapa kluster yang paling hampir antara satu sama lain akan digabungkan menjadi kluster yang berasingan.
Kaedah K-means. Kaedah ini adalah yang paling biasa digunakan. Ia tergolong dalam kumpulan kaedah rujukan analisis kluster yang dipanggil. Bilangan kelompok K ditetapkan oleh pengguna.
Persatuan dua hala. Apabila menggunakan kaedah ini, pengelompokan dijalankan secara serentak oleh pembolehubah (lajur) dan oleh hasil pemerhatian (baris).

Prosedur cantuman dua hala dilakukan apabila boleh dijangkakan pengelompokan serentak pada pembolehubah dan pemerhatian akan memberikan hasil yang bermakna.

Keputusan prosedur adalah statistik deskriptif mengenai pembolehubah dan kes, serta carta warna dua dimensi di mana nilai data berkod warna.

Dengan pengedaran warna, anda boleh mendapatkan idea tentang kumpulan bhomogen.

Normalisasi pembolehubah

Pembahagian set awal objek ke dalam kelompok dikaitkan dengan pengiraan jarak antara objek dan pilihan objek, jarak antara yang paling kecil dari semua yang mungkin.

Yang paling biasa digunakan ialah jarak Euclidean (geometrik) yang biasa kita semua. Metrik ini sepadan dengan idea intuitif tentang kedekatan objek dalam ruang (seolah-olah jarak antara objek diukur dengan pita pengukur).

Tetapi untuk metrik tertentu, jarak antara objek boleh dipengaruhi dengan kuat oleh perubahan dalam skala (unit ukuran). Sebagai contoh, jika salah satu ciri diukur dalam milimeter dan kemudian nilainya ditukar kepada sentimeter, jarak Euclidean antara objek akan berubah secara mendadak. Ini akan membawa kepada fakta bahawa keputusan analisis kelompok mungkin berbeza dengan ketara daripada yang sebelumnya.

Jika pembolehubah diukur dalam unit pengukuran yang berbeza, maka normalisasi awal mereka diperlukan, iaitu, transformasi data awal, yang menukarnya kepada kuantiti tanpa dimensi.

Normalisasi sangat memesongkan geometri ruang asal, yang boleh mengubah hasil pengelompokan

Dalam pakej Statistica, sebarang pembolehubah x dinormalkan mengikut formula:

Untuk melakukan ini, klik kanan pada nama pembolehubah dan pilih urutan arahan daripada menu yang terbuka: Isi/ Piawai Blok/ Piawai Lajur. Nilai pembolehubah ternormal akan menjadi sama dengan sifar, dan varians akan menjadi sama dengan satu.

Kaedah K-means dalam Statistica

Kaedah K-means membahagikan satu set objek ke dalam nombor K tertentu gugusan berbeza yang terletak pada jarak yang paling mungkin antara satu sama lain.

Biasanya, sebaik sahaja keputusan analisis kluster bermakna K diperoleh, seseorang boleh mengira purata bagi setiap kluster bagi setiap dimensi untuk menilai bagaimana kluster berbeza antara satu sama lain.

Sebaik-baiknya, anda harus mendapatkan cara yang sangat berbeza untuk kebanyakan ukuran yang digunakan dalam analisis.

Nilai statistik F yang diperoleh untuk setiap dimensi adalah penunjuk lain tentang sejauh mana dimensi yang sepadan mendiskriminasi antara kelompok.

Sebagai contoh, pertimbangkan hasil tinjauan terhadap 17 pekerja sebuah perusahaan tentang kepuasan terhadap petunjuk kualiti kerjaya. Jadual mengandungi jawapan kepada soalan soal selidik pada skala sepuluh mata (1 adalah markah minimum, 10 adalah maksimum).

Nama pembolehubah sepadan dengan jawapan kepada soalan berikut:

SLT - gabungan matlamat peribadi dan matlamat organisasi;
OSO - rasa adil dalam gaji;
TBD - kedekatan wilayah dengan rumah;
PEW - rasa kesejahteraan ekonomi;
CR - pertumbuhan kerjaya;
ZhSR - keinginan untuk menukar pekerjaan;
OSB ialah rasa kesejahteraan sosial.

Menggunakan data ini, adalah perlu untuk membahagikan pekerja kepada kumpulan dan memilih tuas kawalan yang paling berkesan untuk setiap daripada mereka.

Pada masa yang sama, perbezaan antara kumpulan harus jelas, dan dalam kumpulan itu, responden harus sesama mungkin.

Sehingga kini, kebanyakan tinjauan sosiologi hanya memberikan peratusan undi: bilangan utama jawapan positif dipertimbangkan, atau peratusan mereka yang tidak berpuas hati, tetapi isu ini tidak dipertimbangkan secara sistematik.

Selalunya, tinjauan tidak menunjukkan arah aliran dalam situasi tersebut. Dalam sesetengah kes, adalah perlu untuk mengira bukan bilangan orang yang "untuk" atau "menentang", tetapi jarak, atau ukuran persamaan, iaitu, untuk menentukan kumpulan orang yang berfikir tentang perkara yang sama.

Prosedur analisis kelompok boleh digunakan untuk mengenal pasti, berdasarkan data tinjauan, beberapa perhubungan ciri yang benar-benar sedia ada dan menjana tipologinya atas dasar ini.

Perhatian!

Kehadiran sebarang hipotesis a priori ahli sosiologi apabila bekerja dengan prosedur analisis kelompok bukanlah syarat yang diperlukan.

Dalam program Statistica, analisis kelompok dilakukan seperti berikut.

Apabila memilih bilangan kluster, berpandukan perkara berikut: bilangan kluster, jika boleh, tidak boleh terlalu besar.

Jarak di mana objek gugusan tertentu dicantumkan, jika boleh, jauh lebih kecil daripada jarak di mana sesuatu yang lain menyertai gugusan ini.

Apabila memilih bilangan kluster, selalunya terdapat beberapa penyelesaian yang betul pada masa yang sama.

Kami berminat, sebagai contoh, bagaimana jawapan kepada soalan soal selidik berkaitan dengan pekerja biasa dan pengurusan perusahaan. Oleh itu, kami memilih K=2. Untuk pembahagian selanjutnya, anda boleh menambah bilangan kluster.

pilih cerapan dengan jarak maksimum antara pusat kluster;
menyusun jarak dan pilih pemerhatian pada selang masa yang tetap (tetapan lalai);
ambil pusat pemerhatian pertama dan pasangkan objek yang lain padanya.

Pilihan 1 sesuai untuk tujuan kami.

Banyak algoritma pengelompokan sering "mengenakan" struktur yang tidak wujud dalam data dan mengelirukan penyelidik. Oleh itu, adalah amat perlu untuk menggunakan beberapa algoritma analisis kelompok dan membuat kesimpulan berdasarkan penilaian umum keputusan algoritma.

Hasil analisis boleh dilihat dalam kotak dialog yang muncul:

Jika anda memilih tab Graf cara, graf koordinat pusat kluster akan diplotkan:

Setiap garis putus pada graf ini sepadan dengan salah satu kelompok. Setiap pembahagian paksi mendatar graf sepadan dengan salah satu pembolehubah yang disertakan dalam analisis.

Paksi menegak sepadan dengan nilai purata pembolehubah untuk objek yang disertakan dalam setiap kelompok.

Dapat diambil perhatian bahawa terdapat perbezaan yang ketara dalam sikap kedua-dua kumpulan manusia terhadap kerjaya perkhidmatan dalam hampir semua isu. Hanya dalam satu isu terdapat sebulat suara yang lengkap - dalam erti kata kesejahteraan sosial (OSB), atau lebih tepatnya, kekurangannya (2.5 mata daripada 10).

Ia boleh diandaikan bahawa kluster 1 mewakili pekerja dan kluster 2 mewakili pengurusan. Pengurus lebih berpuas hati dengan pembangunan kerjaya (CR), gabungan matlamat peribadi dan matlamat organisasi (SOL).

Mereka mempunyai rasa kesejahteraan ekonomi (SEW) dan rasa ekuiti gaji (SWA) yang lebih tinggi.

Mereka kurang mengambil berat tentang kedekatan dengan rumah berbanding pekerja, mungkin kerana masalah pengangkutan yang kurang. Selain itu, pengurus kurang keinginan untuk menukar pekerjaan (JSR).

Walaupun fakta bahawa pekerja dibahagikan kepada dua kategori, mereka memberikan jawapan yang agak sama kepada kebanyakan soalan. Dalam erti kata lain, jika sesuatu tidak sesuai dengan kumpulan umum pekerja, perkara yang sama tidak sesuai dengan pengurusan kanan, dan sebaliknya.

Penyelarasan graf membolehkan kita membuat kesimpulan bahawa kesejahteraan satu kumpulan dicerminkan dalam kesejahteraan kumpulan yang lain.

Kluster 1 tidak berpuas hati dengan kedekatan wilayah dengan rumah. Kumpulan ini adalah bahagian utama pekerja yang kebanyakannya datang ke perusahaan dari bahagian-bahagian yang berlainan di bandar.

Oleh itu, adalah mungkin untuk menawarkan pengurusan tertinggi untuk memperuntukkan sebahagian daripada keuntungan kepada pembinaan perumahan untuk pekerja perusahaan.

Perbezaan ketara dilihat pada sikap kedua-dua kumpulan manusia terhadap kerjaya perkhidmatan. Mereka pekerja yang berpuas hati dengan pertumbuhan kerjaya, yang mempunyai kebetulan tinggi matlamat peribadi dan matlamat organisasi, tidak mempunyai keinginan untuk menukar pekerjaan dan berasa kepuasan dengan hasil kerja mereka.

Sebaliknya, pekerja yang ingin bertukar kerja dan tidak berpuas hati dengan hasil kerja mereka tidak berpuas hati dengan petunjuk di atas. Pengurusan kanan harus memberi perhatian khusus kepada keadaan semasa.

Keputusan analisis varians bagi setiap atribut dipaparkan dengan menekan butang Analisis varians.

Jumlah kuasa dua sisihan objek dari pusat kluster (SS Within) dan jumlah kuasa dua sisihan antara pusat kluster (SS Between), nilai statistik-F dan tahap keertian p dipaparkan.

Perhatian!

Sebagai contoh kami, tahap keertian bagi kedua-dua pembolehubah adalah agak besar, yang dijelaskan oleh bilangan pemerhatian yang kecil. Dalam versi penuh kajian, yang boleh didapati dalam kertas kerja, hipotesis tentang kesamaan cara untuk pusat kluster ditolak pada tahap keertian kurang daripada 0.01.

Butang Simpan klasifikasi dan jarak memaparkan bilangan objek yang disertakan dalam setiap kelompok dan jarak objek ke tengah setiap kelompok.

Jadual menunjukkan nombor kes (CASE_NO) yang membentuk gugusan dengan nombor KLUSTER dan jarak dari tengah setiap gugusan (DISTANCE).

Maklumat tentang objek kepunyaan kelompok boleh ditulis ke fail dan digunakan dalam analisis lanjut. Dalam contoh ini, perbandingan keputusan yang diperoleh dengan soal selidik menunjukkan bahawa kluster 1 terdiri terutamanya daripada pekerja biasa, dan kluster 2 - pengurus.

Oleh itu, dapat dilihat bahawa apabila memproses hasil tinjauan, analisis kelompok ternyata menjadi kaedah yang kuat yang membolehkan membuat kesimpulan yang tidak dapat dicapai dengan membina histogram purata atau dengan mengira peratusan mereka yang berpuas hati dengan pelbagai penunjuk kualiti kehidupan bekerja.

Pengelompokan pokok ialah contoh algoritma hierarki, yang prinsipnya ialah mengelompokkan secara berurutan yang paling hampir, dan kemudian elemen yang semakin jauh antara satu sama lain ke dalam gugusan.

Kebanyakan algoritma ini bermula daripada matriks persamaan (jarak), dan setiap elemen individu pada mulanya dianggap sebagai gugusan yang berasingan.

Selepas memuatkan modul analisis kelompok dan memilih Menyertai (kelompok pokok), anda boleh menukar parameter berikut dalam tetingkap masuk parameter pengelompokan:

Data awal (Input). Mereka boleh dalam bentuk matriks data yang dikaji (data mentah) dan dalam bentuk matriks jarak (matriks jarak).
Pemerhatian pengelompokan (Kluster) (Kes (mentah)) atau pembolehubah (Pembolehubah (lajur)), menerangkan keadaan objek.
Langkah-langkah jarak. Di sini anda boleh memilih langkah-langkah berikut: Jarak Euclidean, Jarak Euclidean Kuasa Dua, Jarak blok Kota (Manhattan), metrik jarak Chebychev, Kuasa ...), peratusan perselisihan faham (Peratus perselisihan pendapat).
Kaedah pengelompokan (Peraturan Penggabungan (hubungan)). Pilihan berikut boleh dilakukan di sini: Pautan Tunggal, Pautan Lengkap, Purata kumpulan berpasangan tidak berwajaran, Purata kumpulan berpasangan berwajaran ), Sentroid kumpulan berpasangan tidak berwajaran, Sentroid kumpulan pasangan berwajaran (median), kaedah Ward.

Hasil daripada pengelompokan, dendrogram mendatar atau menegak dibina - graf di mana jarak antara objek dan kelompok ditentukan apabila ia digabungkan secara berurutan.

Struktur pokok graf membolehkan anda menentukan kelompok bergantung pada ambang yang dipilih - jarak tertentu antara kelompok.

Di samping itu, matriks jarak antara objek asal (Matriks jarak) dipaparkan; min dan sisihan piawai bagi setiap objek sumber (Distiptive statistics).

Untuk contoh yang dipertimbangkan, kami akan menjalankan analisis kelompok pembolehubah dengan tetapan lalai. Dendrogram yang terhasil ditunjukkan dalam rajah.

Paksi menegak dendrogram memplot jarak antara objek dan antara objek dan kelompok. Jadi, jarak antara pembolehubah SEB dan OSD adalah sama dengan lima. Pembolehubah ini pada langkah pertama digabungkan menjadi satu kelompok.

Segmen mendatar dendrogram dilukis pada tahap yang sepadan dengan jarak ambang yang dipilih untuk langkah pengelompokan tertentu.

Ia boleh dilihat daripada graf bahawa soalan "keinginan untuk menukar pekerjaan" (JSR) membentuk kelompok yang berasingan. Secara umum, keinginan untuk membuang mana-mana melawati semua orang secara sama rata. Selanjutnya, kluster yang berasingan ialah soal kedekatan wilayah dengan rumah (LHB).

Dari segi kepentingan, ia berada di tempat kedua, yang mengesahkan kesimpulan tentang keperluan pembinaan perumahan, dibuat mengikut hasil kajian menggunakan kaedah K-means.

Perasaan kesejahteraan ekonomi (PEW) dan ekuiti gaji (PWA) digabungkan - ini adalah blok isu ekonomi. Perkembangan kerjaya (CR) dan gabungan matlamat peribadi dan matlamat organisasi (COL) juga digabungkan.

Kaedah pengelompokan lain, serta pilihan jenis jarak lain, tidak membawa kepada perubahan ketara dalam dendrogram.

Keputusan:

Analisis kelompok ialah alat yang berkuasa untuk analisis data penerokaan dan penyelidikan statistik dalam mana-mana bidang subjek.
Program Statistica melaksanakan kedua-dua kaedah hierarki dan struktur analisis kelompok. Kelebihan pakej statistik ini adalah kerana keupayaan grafiknya. Perwakilan grafik dua dimensi dan tiga dimensi bagi kelompok yang diperoleh dalam ruang pembolehubah yang dikaji disediakan, serta keputusan prosedur hierarki untuk mengumpulkan objek.
Ia adalah perlu untuk menggunakan beberapa algoritma analisis kelompok dan membuat kesimpulan berdasarkan penilaian umum keputusan algoritma.
Analisis kluster boleh dianggap berjaya jika ia dilakukan dengan cara yang berbeza, hasilnya dibandingkan dan corak biasa ditemui, dan kluster yang stabil ditemui tanpa mengira kaedah pengelompokan.
Analisis kelompok membolehkan anda mengenal pasti situasi masalah dan menggariskan cara untuk menyelesaikannya. Oleh itu, kaedah statistik bukan parametrik ini boleh dianggap sebagai bahagian penting dalam analisis sistem.

Jenis Input

Penerangan indikatif objek. Setiap objek diterangkan oleh satu set ciri-cirinya, dipanggil tanda-tanda. Ciri boleh berbentuk angka atau bukan angka.
Matriks jarak antara objek. Setiap objek diterangkan mengikut jarak ke semua objek lain dalam sampel latihan.

Matlamat pengelompokan

Memahami data dengan mengenal pasti struktur kluster. Membahagikan sampel kepada kumpulan objek yang serupa memungkinkan untuk memudahkan pemprosesan data selanjutnya dan membuat keputusan dengan menggunakan kaedah analisisnya sendiri untuk setiap kelompok (strategi "bahagi dan takluk").
Pemampatan data. Jika sampel awal terlalu besar, maka ia boleh dikurangkan, meninggalkan salah satu wakil yang paling tipikal dari setiap kelompok.
pengesanan kebaharuan. pengesanan kebaharuan). Objek atipikal dipilih yang tidak boleh dilampirkan pada mana-mana kelompok.

Dalam kes pertama, mereka cuba menjadikan bilangan kluster lebih kecil. Dalam kes kedua, adalah lebih penting untuk memastikan tahap persamaan objek yang tinggi dalam setiap gugusan, dan boleh terdapat sebarang bilangan gugusan. Dalam kes ketiga, objek individu yang tidak sesuai dengan mana-mana kelompok adalah yang paling diminati.

Dalam semua kes ini, pengelompokan hierarki boleh digunakan, apabila gugusan besar dibahagikan kepada yang lebih kecil, yang, seterusnya, dibahagikan dengan lebih kecil lagi, dsb. Tugas sedemikian dipanggil tugas taksonomi.

Hasil taksonomi ialah struktur hierarki seperti pokok. Di samping itu, setiap objek dicirikan oleh penghitungan semua kelompok yang mana ia tergolong, biasanya dari besar ke kecil.

Contoh klasik taksonomi berdasarkan persamaan ialah tatanama binomial makhluk hidup yang dicadangkan oleh Carl Linnaeus pada pertengahan abad ke-18. Sistematisasi yang serupa dibina dalam banyak bidang pengetahuan untuk menyusun maklumat tentang sejumlah besar objek.

Kaedah pengelompokan

Pernyataan Formal Masalah Pengelompokan

Biarkan menjadi satu set objek, menjadi satu set nombor (nama, label) kelompok. Fungsi jarak antara objek diberikan. Terdapat set latihan terhingga objek. Ia diperlukan untuk membahagikan sampel kepada subset tidak bertindih, dipanggil kelompok, supaya setiap gugusan terdiri daripada objek yang rapat dalam metrik , dan objek daripada gugusan yang berbeza berbeza dengan ketara. Dalam kes ini, setiap objek diberikan nombor kluster.

Algoritma pengelompokan ialah fungsi yang mengaitkan sebarang objek dengan nombor kelompok. Set dalam beberapa kes diketahui terlebih dahulu, tetapi lebih kerap tugasnya adalah untuk menentukan bilangan gugusan yang optimum, dari sudut pandangan satu atau yang lain kriteria kualiti berkelompok.

kesusasteraan

Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Statistik Gunaan: Pengelasan dan Pengurangan Dimensi. - M.: Kewangan dan perangkaan, 1989.
Zhuravlev Yu. I., Ryazanov V. V., Senko O. V."Pengiktirafan". Kaedah matematik. Sistem perisian. Aplikasi praktikal. - M.: Fazis, 2006. ISBN 5-7036-0108-8.
Zagoruiko N. G. Kaedah gunaan data dan analisis pengetahuan. - Novosibirsk: IM SO RAN, 1999. ISBN 5-86134-060-9.
Mandel I. D. analisis kelompok. - M.: Kewangan dan perangkaan, 1988. ISBN 5-279-00050-7.
Shlesinger M., Glavach V. Sepuluh kuliah mengenai pengiktirafan statistik dan struktur. - Kyiv: Naukova Dumka, 2004. ISBN 966-00-0341-2.
Hastie T., Tibshirani R., Friedman J. Elemen Pembelajaran Statistik. - Springer, 2001. ISBN 0-387-95284-5.
Jain Murty Flynn Pengelompokan data: semakan . // ACM Comput. Surv. 31 (3) , 1999

Pautan luar

Dalam bahasa Rusia

www.MachineLearning.ru - sumber wiki profesional khusus untuk pembelajaran mesin dan perlombongan data
S. Nikolenko. Slaid kuliah tentang algoritma pengelompokan

Dalam Bahasa Inggeris

COMPACT - Pakej Perbandingan untuk Penilaian Pengelompokan. Pakej Matlab percuma, 2006.
P. Berkhin, Tinjauan Teknik Perlombongan Data Pengelompokan, Perisian Accrue, 2002.
Jain, Murty dan Flynn: Pengelompokan Data: Satu Tinjauan, ACM Comp. Surv., 1999.
untuk pembentangan lain bagi hierarki, k-means dan fuzzy c-means lihat pengenalan kepada pengelompokan ini. Juga mempunyai penjelasan tentang campuran Gaussians.
david dowe, Halaman Pemodelan Campuran- pautan model pengelompokan dan campuran lain.
tutorial tentang pengelompokan
Buku teks dalam talian: Teori Maklumat, Inferens, dan Algoritma Pembelajaran, oleh David J.C. MacKay merangkumi bab tentang pengelompokan k-means, pengelompokan k-means lembut, dan terbitan termasuk algoritma E-M dan pandangan variasi bagi algoritma E-M.
"The Self-Organized Gene" , tutorial menerangkan pengelompokan melalui pembelajaran kompetitif dan peta penyusunan diri.
kernlab - Pakej R untuk pembelajaran mesin berasaskan kernel (termasuk pelaksanaan pengelompokan spektrum)
Tutorial - Tutorial dengan pengenalan Algoritma Pengelompokan (k-means, fuzzy-c-means, hierarki, campuran gaussians) + beberapa demo interaktif (java applets)
Perisian Perlombongan Data - Perisian perlombongan data kerap menggunakan teknik pengelompokan.
Aplikasi Pembelajaran Java Competitve Satu set Rangkaian Neural Tanpa Selia untuk pengelompokan. Ditulis dalam bahasa Jawa. Lengkap dengan semua kod sumber.

analisis kelompok

Kebanyakan penyelidik cenderung untuk mempercayai bahawa buat pertama kalinya istilah "analisis kelompok" (eng. kelompok- bunch, clot, bunch) telah dicadangkan oleh ahli matematik R. Trion. Selepas itu, timbul beberapa istilah yang kini dianggap sinonim dengan istilah "analisis kelompok": pengelasan automatik; botaniologi.

Analisis kluster ialah prosedur statistik multidimensi yang mengumpul data yang mengandungi maklumat tentang sampel objek, dan kemudian menyusun objek ke dalam kumpulan yang agak homogen (kluster) (Q-clustering, atau Q-teknik, analisis kluster betul). Kluster - sekumpulan elemen yang dicirikan oleh sifat sepunya, matlamat utama analisis kelompok adalah untuk mencari kumpulan objek yang serupa dalam sampel. Julat aplikasi analisis kelompok sangat luas: ia digunakan dalam arkeologi, perubatan, psikologi, kimia, biologi, pentadbiran awam, filologi, antropologi, pemasaran, sosiologi dan disiplin lain. Walau bagaimanapun, kesejagatan aplikasi telah membawa kepada kemunculan sejumlah besar istilah, kaedah dan pendekatan yang tidak serasi yang menyukarkan untuk menggunakan dan mentafsir analisis kluster secara jelas. Orlov A. I. mencadangkan untuk membezakan seperti berikut:

Tugas dan syarat

Analisis kluster melakukan perkara berikut matlamat utama:

Pembangunan tipologi atau klasifikasi.
Meneroka skema konsep yang berguna untuk mengumpulkan objek.
Penjanaan hipotesis berdasarkan penerokaan data.
Ujian atau penyelidikan hipotesis untuk menentukan sama ada jenis (kumpulan) yang dikenal pasti dalam satu cara atau yang lain sebenarnya terdapat dalam data yang tersedia.

Tanpa mengira subjek kajian, penggunaan analisis kelompok melibatkan langkah seterusnya:

Persampelan untuk pengelompokan. Difahamkan bahawa masuk akal untuk mengelompokkan data kuantitatif sahaja.
Definisi set pembolehubah yang mana objek dalam sampel akan dinilai, iaitu ruang ciri.
Pengiraan nilai satu atau satu lagi ukuran persamaan (atau perbezaan) antara objek.
Aplikasi kaedah analisis kelompok untuk mencipta kumpulan objek yang serupa.
Pengesahan keputusan penyelesaian kluster.

Analisis kluster membentangkan perkara berikut keperluan data:

penunjuk tidak boleh berkait antara satu sama lain;
penunjuk tidak boleh bercanggah dengan teori pengukuran;
pengedaran penunjuk harus hampir normal;
penunjuk mesti memenuhi keperluan "kestabilan", yang bermaksud ketiadaan pengaruh pada nilai mereka oleh faktor rawak;
sampel hendaklah homogen, tidak mengandungi "outliers".

Anda boleh mendapatkan penerangan tentang dua keperluan asas untuk data - keseragaman dan kesempurnaan:

Kehomogenan memerlukan semua entiti yang diwakili dalam jadual mempunyai sifat yang sama. Keperluan untuk kesempurnaan ialah set saya Dan J membentangkan penerangan lengkap tentang manifestasi fenomena yang sedang dipertimbangkan. Jika kita mempertimbangkan jadual di mana saya adalah koleksi, dan J- set pembolehubah yang menerangkan populasi ini, maka ia harus menjadi sampel yang mewakili daripada populasi yang dikaji, dan sistem ciri J harus memberikan representasi vektor yang memuaskan bagi individu i dari sudut pandangan penyelidik.

Jika analisis kelompok didahului oleh analisis faktor, maka sampel tidak perlu "dibaiki" - keperluan yang dinyatakan dilakukan secara automatik oleh prosedur pemodelan faktor itu sendiri (terdapat kelebihan lain - penyeragaman z tanpa akibat negatif untuk sampel; jika ia dijalankan secara langsung untuk analisis kluster, ia boleh mengakibatkan penurunan kejelasan pemisahan kumpulan). Jika tidak, sampel mesti diselaraskan.

Tipologi masalah pengelompokan

Jenis Input

Dalam sains moden, beberapa algoritma untuk memproses data input digunakan. Analisis dengan membandingkan objek berdasarkan ciri (paling biasa dalam sains biologi) dipanggil Q- jenis analisis, dan dalam kes perbandingan ciri, berdasarkan objek - R- jenis analisis. Terdapat percubaan untuk menggunakan jenis analisis hibrid (contohnya, RQ analisis), tetapi metodologi ini belum dibangunkan dengan betul.

Matlamat pengelompokan

Memahami data dengan mengenal pasti struktur kluster. Membahagikan sampel kepada kumpulan objek yang serupa memungkinkan untuk memudahkan pemprosesan data selanjutnya dan membuat keputusan dengan menggunakan kaedah analisisnya sendiri untuk setiap kelompok (strategi "bahagi dan takluk").
Pemampatan data. Jika sampel awal terlalu besar, maka ia boleh dikurangkan, meninggalkan salah satu wakil yang paling tipikal dari setiap kelompok.
pengesanan kebaharuan. pengesanan kebaharuan). Objek atipikal dipilih yang tidak boleh dilampirkan pada mana-mana kelompok.

Dalam semua kes ini, pengelompokan hierarki boleh digunakan, apabila gugusan besar dibahagikan kepada yang lebih kecil, yang seterusnya, dipecah lebih kecil lagi, dsb. Tugas sedemikian dipanggil tugas taksonomi. Hasil taksonomi ialah struktur hierarki seperti pokok. Di samping itu, setiap objek dicirikan oleh penghitungan semua kelompok yang mana ia tergolong, biasanya dari besar ke kecil.

Kaedah pengelompokan

Tiada klasifikasi kaedah pengelompokan yang diterima umum, tetapi percubaan kukuh oleh V. S. Berikov dan G. S. Lbov boleh diperhatikan. Jika kita umumkan pelbagai klasifikasi kaedah pengelompokan, kita boleh membezakan beberapa kumpulan (beberapa kaedah boleh dikaitkan dengan beberapa kumpulan sekaligus, dan oleh itu adalah dicadangkan untuk mempertimbangkan penaip ini sebagai beberapa anggaran kepada klasifikasi sebenar kaedah pengelompokan):

Pendekatan kebarangkalian. Diandaikan bahawa setiap objek yang dipertimbangkan adalah milik salah satu kelas k. Sesetengah pengarang (contohnya, A. I. Orlov) percaya bahawa kumpulan ini tidak tergolong dalam kelompok sama sekali dan menentangnya di bawah nama "diskriminasi", iaitu, pilihan untuk memberikan objek kepada salah satu kumpulan yang diketahui (sampel latihan).
Pendekatan berdasarkan sistem kecerdasan buatan. Kumpulan yang sangat bersyarat, kerana terdapat banyak kaedah AI dan secara kaedah ia sangat berbeza.
pendekatan logik. Pembinaan dendrogram dijalankan menggunakan pokok keputusan.
Pendekatan graf-teoretik.
- Algoritma pengelompokan graf
Pendekatan hierarki. Kehadiran kumpulan bersarang (kelompok pesanan berbeza) diandaikan. Algoritma pula dibahagikan kepada aglomeratif (penyatuan) dan pembahagian (memisahkan). Mengikut bilangan ciri, kaedah klasifikasi monotetik dan politetik kadangkala dibezakan.
- Pengelompokan atau taksonomi pembahagian hierarki. Masalah pengelompokan dipertimbangkan dalam taksonomi kuantitatif.
Kaedah Lain. Tidak termasuk dalam kumpulan sebelumnya.
- Algoritma pengelompokan statistik
- Ensemble of clusterers
- Algoritma keluarga KRAB
- Algoritma berdasarkan kaedah penapisan
- DBSCAN dll.

Pendekatan 4 dan 5 kadangkala digabungkan di bawah nama pendekatan struktur atau geometri, yang mempunyai konsep kedekatan yang lebih formal. Walaupun terdapat perbezaan yang ketara antara kaedah yang disenaraikan, mereka semua bergantung pada yang asal " hipotesis kekompakan»: dalam ruang objek, semua objek rapat mesti tergolong dalam kelompok yang sama, dan semua objek yang berbeza, masing-masing, mesti berada dalam kelompok yang berbeza.

Pernyataan Formal Masalah Pengelompokan

Pengelompokan (pembelajaran tanpa pengawasan) berbeza daripada pengelasan (pembelajaran diselia) kerana label objek asal tidak ditetapkan pada mulanya, dan set itu sendiri mungkin tidak diketahui.

Penyelesaian masalah pengelompokan pada asasnya tidak jelas, dan terdapat beberapa sebab untuk ini (menurut beberapa pengarang):

tiada kriteria terbaik yang unik untuk kualiti pengelompokan. Beberapa kriteria heuristik diketahui, serta beberapa algoritma yang tidak mempunyai kriteria yang jelas, tetapi menjalankan pengelompokan yang agak munasabah "mengikut pembinaan". Kesemua mereka boleh memberikan hasil yang berbeza. Oleh itu, untuk menentukan kualiti kluster, pakar dalam bidang subjek diperlukan, yang boleh menilai kebermaknaan pemilihan kluster.
bilangan kelompok biasanya tidak diketahui terlebih dahulu dan ditetapkan mengikut beberapa kriteria subjektif. Ini benar hanya untuk kaedah diskriminasi, kerana dalam kaedah pengelompokan, kelompok dipilih menggunakan pendekatan formal berdasarkan ukuran kedekatan.
hasil pengelompokan sangat bergantung pada metrik, pilihan yang, sebagai peraturan, juga subjektif dan ditentukan oleh pakar. Tetapi perlu diperhatikan bahawa terdapat beberapa cadangan untuk memilih langkah kedekatan untuk pelbagai tugas.

Permohonan

Dalam biologi

Dalam biologi, pengelompokan mempunyai banyak aplikasi dalam pelbagai bidang. Sebagai contoh, dalam bioinformatik, ia digunakan untuk menganalisis rangkaian kompleks gen yang berinteraksi, kadangkala terdiri daripada ratusan atau bahkan ribuan elemen. Analisis kelompok membolehkan anda mengenal pasti subnet, kesesakan, hab dan sifat tersembunyi lain sistem yang dikaji, yang akhirnya membolehkan anda mengetahui sumbangan setiap gen kepada pembentukan fenomena yang dikaji.

Dalam bidang ekologi, ia digunakan secara meluas untuk mengenal pasti kumpulan organisma, komuniti dan lain-lain yang homogen dari segi ruang. Lebih jarang, kaedah analisis kelompok digunakan untuk mengkaji komuniti dari semasa ke semasa. Kepelbagaian struktur komuniti membawa kepada kemunculan kaedah analisis kelompok yang tidak remeh (contohnya, kaedah Czekanowski).

Secara umum, perlu diperhatikan bahawa dari segi sejarah, ukuran persamaan lebih kerap digunakan sebagai ukuran kedekatan dalam biologi, dan bukannya ukuran perbezaan (jarak).

Dalam sosiologi

Apabila menganalisis hasil penyelidikan sosiologi, adalah disyorkan untuk menjalankan analisis menggunakan kaedah keluarga aglomeratif hierarki, iaitu kaedah Ward, di mana penyebaran minimum dioptimumkan dalam kelompok, akibatnya, kelompok dengan saiz yang lebih kurang sama. dicipta. Kaedah Ward adalah yang paling berjaya untuk analisis data sosiologi. Sebagai ukuran perbezaan, jarak Euclidean kuadratik adalah lebih baik, yang menyumbang kepada peningkatan kontras kelompok. Hasil utama analisis kelompok hierarki ialah dendrogram atau "icicle diagram". Apabila mentafsirkannya, penyelidik berhadapan dengan masalah yang sama seperti tafsiran hasil analisis faktor - kekurangan kriteria yang tidak jelas untuk mengenal pasti kelompok. Adalah disyorkan untuk menggunakan dua kaedah sebagai kaedah utama - analisis visual dendrogram dan perbandingan hasil pengelompokan yang dilakukan oleh kaedah yang berbeza.

Analisis visual dendrogram melibatkan "memotong" pokok pada tahap kesamaan optimum elemen sampel. "Cawangan anggur" (terminologi Oldenderfer M.S. dan Blashfield R.K.) harus "dipotong" pada sekitar 5 pada skala Gabungan Kluster Jarak Terskala Semula, sekali gus mencapai tahap persamaan 80%. Jika pemilihan gugusan mengikut label ini sukar (beberapa gugusan kecil bergabung menjadi satu gugusan besar di atasnya), maka anda boleh memilih label lain. Teknik ini dicadangkan oleh Oldenderfer dan Blashfield.

Kini persoalan kestabilan penyelesaian kluster yang diterima pakai timbul. Malah, menyemak kestabilan pengelompokan adalah untuk memeriksa kebolehpercayaannya. Terdapat peraturan praktikal di sini - tipologi yang stabil dikekalkan apabila kaedah pengelompokan berubah. Keputusan analisis kelompok hierarki boleh disahkan dengan analisis k-means cluster berulang. Sekiranya klasifikasi kumpulan responden yang dibandingkan mempunyai bahagian kebetulan lebih daripada 70% (lebih daripada 2/3 kebetulan), maka keputusan kelompok dibuat.

Adalah mustahil untuk menyemak kecukupan penyelesaian tanpa menggunakan jenis analisis lain. Sekurang-kurangnya secara teori, masalah ini belum selesai. Analisis Kluster klasik Oldenderfer dan Blashfield menghuraikan dan akhirnya menolak lima kaedah ujian kekukuhan tambahan:

Dalam sains komputer

Mengelompokkan hasil carian - digunakan untuk pengumpulan hasil "pintar" apabila mencari fail, tapak web, objek lain, membolehkan pengguna menavigasi dengan cepat, pilih subset yang jelas lebih berkaitan dan tidak termasuk yang diketahui kurang relevan - yang boleh meningkatkan kebolehgunaan antara muka berbanding dengan keluaran dalam bentuk ringkas disusun mengikut senarai perkaitan.
- Clusty - Enjin carian pengelompokan Vivísimo
- Nigma - Enjin carian Rusia dengan pengelompokan hasil automatik
- Quintura - pengelompokan visual dalam bentuk awan kata kunci
Pembahagian imej pembahagian imej) - Pengelompokan boleh digunakan untuk memecahkan imej digital kepada kawasan yang berbeza untuk tujuan pengesanan tepi. pengesanan tepi) atau pengecaman objek.
Perlombongan data perlombongan data)- Pengelompokan dalam Perlombongan Data menjadi berharga apabila ia bertindak sebagai salah satu peringkat analisis data, membina penyelesaian analisis yang lengkap. Selalunya lebih mudah bagi penganalisis untuk mengenal pasti kumpulan objek yang serupa, mengkaji ciri mereka dan membina model berasingan untuk setiap kumpulan daripada mencipta satu model umum untuk semua data. Teknik ini sentiasa digunakan dalam pemasaran, menonjolkan kumpulan pelanggan, pembeli, barangan dan membangunkan strategi yang berasingan untuk setiap daripada mereka.

lihat juga

Nota

Pautan

Dalam bahasa Rusia

www.MachineLearning.ru - sumber wiki profesional khusus untuk pembelajaran mesin dan perlombongan data

Dalam Bahasa Inggeris

COMPACT - Pakej Perbandingan untuk Penilaian Pengelompokan. Pakej Matlab percuma, 2006.
P. Berkhin, Tinjauan Teknik Perlombongan Data Pengelompokan, Perisian Accrue, 2002.
Jain, Murty dan Flynn: Pengelompokan Data: Satu Tinjauan, ACM Comp. Surv., 1999.
untuk pembentangan lain bagi hierarki, k-means dan fuzzy c-means lihat pengenalan kepada pengelompokan ini. Juga mempunyai penjelasan tentang campuran Gaussians.
david dowe, Halaman Pemodelan Campuran- pautan model pengelompokan dan campuran lain.
tutorial tentang pengelompokan
Buku teks dalam talian: Teori Maklumat, Inferens, dan Algoritma Pembelajaran, oleh David J.C. MacKay merangkumi bab tentang pengelompokan k-means, pengelompokan k-means lembut, dan terbitan termasuk algoritma E-M dan pandangan variasi bagi algoritma E-M.
"The Self-Organized Gene", tutorial menerangkan pengelompokan melalui pembelajaran kompetitif dan peta penyusunan diri.
kernlab - Pakej R untuk pembelajaran mesin berasaskan kernel (termasuk pelaksanaan pengelompokan spektrum)
Tutorial - Tutorial dengan pengenalan Algoritma Pengelompokan (k-means, fuzzy-c-means, hierarki, campuran gaussians) + beberapa demo interaktif (java applets)
Perisian Perlombongan Data - Perisian perlombongan data kerap menggunakan teknik pengelompokan.
Aplikasi Pembelajaran Java Competitve Satu set Rangkaian Neural Tanpa Selia untuk pengelompokan. Ditulis dalam bahasa Jawa. Lengkap dengan semua kod sumber.
Perisian Pembelajaran Mesin - Juga mengandungi banyak perisian pengelompokan.

Kita tahu bahawa Bumi adalah salah satu daripada 8 planet yang beredar mengelilingi Matahari. Matahari hanyalah bintang di antara kira-kira 200 bilion bintang di galaksi Bima Sakti. Amat sukar untuk memahami nombor ini. Mengetahui perkara ini, seseorang boleh membuat andaian tentang bilangan bintang di alam semesta - kira-kira 4X10^22. Kita boleh melihat kira-kira sejuta bintang di langit, walaupun ini hanya sebahagian kecil daripada bilangan sebenar bintang. Jadi kami mempunyai dua soalan:

Apakah galaksi?
Dan apakah kaitan antara galaksi dan topik artikel (analisis kelompok)

Galaksi ialah himpunan bintang, gas, habuk, planet, dan awan antara bintang. Biasanya galaksi menyerupai bentuk lingkaran atau oedeptic. Di angkasa, galaksi dipisahkan antara satu sama lain. Lubang hitam yang besar selalunya merupakan pusat kebanyakan galaksi.

Seperti yang akan kita bincangkan dalam bahagian seterusnya, terdapat banyak persamaan antara galaksi dan analisis kelompok. Galaksi wujud dalam ruang tiga dimensi, analisis kelompok adalah analisis multidimensi yang dijalankan dalam ruang n-dimensi.

nota itu: Lubang hitam adalah pusat galaksi. Kami akan menggunakan idea yang sama untuk centroid untuk analisis kelompok.

analisis kelompok

Katakan anda ketua pemasaran dan perhubungan pelanggan di syarikat telekomunikasi. Anda memahami bahawa semua pelanggan adalah berbeza dan anda memerlukan strategi yang berbeza untuk menjangkau pelanggan yang berbeza. Anda akan menghargai kuasa alat seperti pembahagian pelanggan untuk mengoptimumkan kos. Untuk menyempurnakan pengetahuan anda tentang analisis kelompok, pertimbangkan contoh berikut, yang menggambarkan 8 pelanggan dan purata tempoh perbualan mereka (tempatan dan antarabangsa). Di bawah adalah data:

Untuk persepsi yang lebih baik, mari kita lukis graf di mana paksi-x ialah purata tempoh panggilan antarabangsa, dan paksi-y - purata tempoh panggilan tempatan. Di bawah ialah carta:

nota itu: Ini sama seperti menganalisis kedudukan bintang di langit malam (di sini bintang digantikan oleh pengguna). Di samping itu, bukannya ruang 3D, kami mempunyai ruang 2D, yang ditakrifkan mengikut tempoh panggilan tempatan dan antarabangsa, sebagai paksi x dan y.
Sekarang, bercakap dari segi galaksi, masalahnya dirumuskan seperti berikut - untuk mencari kedudukan lubang hitam; dalam analisis kelompok ia dipanggil centroids. Untuk mengesan centroid, kita akan mulakan dengan mengambil titik sewenang-wenangnya sebagai kedudukan centroid.

Jarak Euclidean untuk Mencari Centroid untuk Kluster

Dalam kes kami, kami akan secara rawak meletakkan dua centroid (C1 dan C2) pada titik dengan koordinat (1, 1) dan (3, 4). Mengapa kita memilih kedua-dua centroid ini? Paparan visual mata pada graf menunjukkan kepada kita bahawa terdapat dua kelompok yang akan kita analisis. Walau bagaimanapun, kita akan melihat kemudian bahawa jawapan kepada soalan ini tidak akan begitu mudah untuk set data yang besar.
Seterusnya, kita akan mengukur jarak antara centroid (C1 dan C2) dan semua titik pada graf menggunakan formula Euclid untuk mencari jarak antara dua titik.

Nota: Jarak juga boleh dikira menggunakan formula lain, contohnya,

segi empat sama jarak Euclidean - untuk memberi berat kepada objek yang lebih jauh antara satu sama lain
Jarak Manhattan - untuk mengurangkan kesan pelepasan
jarak kuasa - untuk menambah / mengurangkan pengaruh pada koordinat tertentu
peratus ketidaksetujuan - untuk data kategori
dan lain-lain.

Lajur 3 dan 4 (Jarak dari C1 dan C2) ialah jarak yang dikira menggunakan formula ini. Sebagai contoh, untuk pengguna pertama

Kepunyaan centroids (lajur terakhir) dikira mengikut prinsip kedekatan dengan centroid (C1 dan C2). Pengguna pertama lebih hampir kepada centroid #1 (1.41 berbanding 2.24) oleh itu tergolong dalam kelompok dengan centroid C1.

Di bawah ialah graf yang menggambarkan centroid C1 dan C2 (digambarkan sebagai berlian biru dan oren). Pengguna ditunjukkan dalam warna centroid yang sepadan yang diberikan kepada mereka.

Oleh kerana kita telah memilih centroid secara sewenang-wenangnya, langkah kedua ialah menjadikan pilihan ini berulang. Kedudukan baru centroid dipilih sebagai purata untuk titik gugusan yang sepadan. Jadi, sebagai contoh, untuk centroid pertama (ini adalah pengguna 1, 2 dan 3). Oleh itu, koordinat-x baharu bagi centroid C1 ialah purata koordinat-x pengguna ini (2+1+1)/3 = 1.33. Kami akan mendapat koordinat baharu untuk C1 (1.33, 2.33) dan C2 (4.4, 4.2). Plot baharu adalah di bawah:

Akhir sekali, kami akan meletakkan centroid di tengah kelompok masing-masing. Carta di bawah:

Kedudukan lubang hitam kami (pusat kluster) dalam contoh kami ialah C1 (1.75, 2.25) dan C2 (4.75, 4.75). Dua gugusan di atas adalah seperti dua galaksi yang dipisahkan di angkasa antara satu sama lain.

Jadi, mari kita lihat contoh lebih lanjut. Marilah kita menghadapi tugas membahagikan pengguna mengikut dua parameter: umur dan pendapatan. Katakan kita mempunyai 2 pengguna berumur 37 dan 44 dengan pendapatan masing-masing $90,000 dan $62,000. Jika kita ingin mengukur jarak Euclidean antara titik (37, 90000) dan (44, 62000), kita akan melihat bahawa dalam kes ini pembolehubah pendapatan "menguasai" pembolehubah umur dan perubahannya sangat mempengaruhi jarak. Kami memerlukan beberapa jenis strategi untuk menyelesaikan masalah ini, jika tidak analisis kami akan memberikan hasil yang salah. Penyelesaian kepada masalah ini adalah untuk membawa nilai kita kepada skala yang setanding. Normalisasi adalah penyelesaian kepada masalah kami.

Normalisasi data

Terdapat banyak pendekatan untuk menormalkan data. Contohnya, normalisasi minimum-maksimum. Untuk normalisasi ini, formula berikut digunakan

dalam kes ini, X* ialah nilai ternormal, min dan maks ialah koordinat minimum dan maksimum bagi keseluruhan set X
(Nota, formula ini meletakkan semua koordinat pada segmen )
Pertimbangkan contoh kami, biarkan pendapatan maksimum ialah $130,000 dan minimum ialah $45,000. Nilai normal pendapatan bagi pengguna A ialah

Kami akan melakukan latihan ini untuk semua mata bagi setiap pembolehubah (koordinat). Pendapatan untuk pengguna kedua (62000) akan menjadi 0.2 selepas prosedur normalisasi. Selain itu, biarkan umur minimum dan maksimum masing-masing 23 dan 58. Selepas penormalan, umur dua pengguna kami ialah 0.4 dan 0.6.

Sangat mudah untuk melihat bahawa kini semua data kami adalah antara 0 dan 1. Oleh itu, kami kini mempunyai set data ternormal pada skala yang setanding.

Ingat, sebelum prosedur analisis kelompok, perlu melakukan normalisasi.

Jenis Input

Penerangan indikatif objek. Setiap objek diterangkan oleh satu set ciri-cirinya, dipanggil tanda-tanda. Ciri boleh berbentuk angka atau bukan angka.
Matriks jarak antara objek. Setiap objek diterangkan mengikut jarak ke semua objek lain dalam sampel latihan.

Matriks jarak boleh dikira daripada matriks perihalan ciri objek dalam bilangan cara yang tidak terhingga, bergantung pada cara memperkenalkan fungsi jarak (metrik) antara penerangan ciri. Metrik Euclidean sering digunakan, tetapi pilihan ini dalam kebanyakan kes adalah heuristik dan hanya disebabkan oleh pertimbangan kemudahan.

Masalah songsang - pemulihan perihalan ciri oleh matriks jarak berpasangan antara objek - dalam kes umum tidak mempunyai penyelesaian, dan penyelesaian anggaran tidak unik dan mungkin mempunyai ralat yang ketara. Masalah ini diselesaikan dengan kaedah penskalaan multidimensi.

Justeru, perumusan masalah pengelompokan oleh matriks jarak adalah lebih umum. Sebaliknya, dengan adanya penerangan ciri, selalunya mungkin untuk membina kaedah pengelompokan yang lebih cekap.

Matlamat pengelompokan

Memahami data dengan mengenal pasti struktur kluster. Membahagikan sampel kepada kumpulan objek yang serupa memungkinkan untuk memudahkan pemprosesan data selanjutnya dan membuat keputusan dengan menggunakan kaedah analisisnya sendiri untuk setiap kelompok (strategi "bahagi dan takluk").
Pemampatan data. Jika sampel awal terlalu besar, maka ia boleh dikurangkan, meninggalkan salah satu wakil yang paling tipikal dari setiap kelompok.
Pengesanan kebaharuan. Objek atipikal dipilih yang tidak boleh dilampirkan pada mana-mana kelompok.

Dalam kes pertama, mereka cuba menjadikan bilangan kluster lebih kecil. Dalam kes kedua, adalah lebih penting untuk memastikan tahap persamaan objek yang tinggi (atau tetap) dalam setiap gugusan, dan boleh terdapat sebarang bilangan gugusan. Dalam kes ketiga, objek individu yang tidak sesuai dengan mana-mana kelompok adalah yang paling diminati.

Hasil taksonomi ialah struktur hierarki seperti pokok. Di samping itu, setiap objek dicirikan oleh penghitungan semua kelompok yang mana ia tergolong, biasanya dari besar ke kecil. Secara visual, taksonomi diwakili sebagai graf yang dipanggil dendrogram.

Contoh klasik taksonomi berdasarkan persamaan ialah nomenklatur binomial makhluk hidup dicadangkan oleh Carl Linnaeus pada pertengahan abad ke-18. Sistematisasi yang serupa dibina dalam banyak bidang pengetahuan untuk menyusun maklumat tentang sejumlah besar objek.

Fungsi jarak

Kaedah pengelompokan

Algoritma pengelompokan statistik
Pengelompokan hierarki atau taksonomi

Pernyataan Formal Masalah Pengelompokan

Pengelompokan (pembelajaran tanpa pengawasan) berbeza daripada pengelasan (pembelajaran diselia) kerana label objek asal tidak ditetapkan pada mulanya, dan set itu sendiri mungkin tidak diketahui.

Penyelesaian masalah pengelompokan pada asasnya tidak jelas, dan terdapat beberapa sebab untuk ini:

Tiada kriteria terbaik yang unik untuk kualiti pengelompokan. Beberapa kriteria heuristik diketahui, serta beberapa algoritma yang tidak mempunyai kriteria yang jelas, tetapi menjalankan pengelompokan yang agak munasabah "mengikut pembinaan". Kesemua mereka boleh memberikan hasil yang berbeza.
Bilangan kelompok biasanya tidak diketahui terlebih dahulu dan ditetapkan mengikut beberapa kriteria subjektif.
Hasil pengelompokan sangat bergantung pada metrik, pilihannya, sebagai peraturan, juga subjektif dan ditentukan oleh pakar.

Pautan

Vorontsov K.V. Kaedah Pengajaran Matematik mengikut Terdahulu. Institut Fizik dan Teknologi Moscow (2004), VMiK MSU (2007).
Sergei Nikolenko. Slaid kuliah "Mengkelompokkan Algoritma 1" dan "Mengkelompokkan Algoritma 2". Kursus "Sistem pembelajaran kendiri".

kesusasteraan

Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Statistik Gunaan: Pengelasan dan Pengurangan Dimensi. - M.: Kewangan dan perangkaan, 1989.
Zhuravlev Yu. I., Ryazanov V. V., Senko O. V."Pengiktirafan". Kaedah matematik. Sistem perisian. Aplikasi praktikal. - M.: Fazis, 2006. .
Zagoruiko N. G. Kaedah gunaan data dan analisis pengetahuan. - Novosibirsk: IM SO RAN, 1999. .
Mandel I. D. analisis kelompok. - M.: Kewangan dan perangkaan, 1988. .
Shlesinger M., Glavach V. Sepuluh kuliah mengenai pengiktirafan statistik dan struktur. - Kyiv: Naukova Dumka, 2004. .
Hastie T., Tibshirani R., Friedman J. Elemen Pembelajaran Statistik. - Springer, 2001. .