Memberikan pengenalan yang tepat waktu dan penting terhadap analisis klaster fuzzy, metode dan kegunaannya. Menjelaskan secara sistematis berbagai teknik pengelompokan fuzzy sehingga pembaca dapat memilih metode yang paling cocok untuk menyelesaikan masalahnya. Terdapat tinjauan literatur yang baik dan sangat komprehensif mengenai pokok bahasan, pengenalan gambar, klasifikasi cakupan, analisis data dan derivasi aturan. Contoh-contohnya cukup ilustratif dan menyampaikan. hasilnya telah diuji.
Ini adalah buku paling rinci tentang pengelompokan fuzzy, oleh karena itu buku ini direkomendasikan untuk ilmuwan komputer, matematikawan, insinyur - siapa pun yang terlibat dalam analisis data, pemrosesan gambar. Ini juga akan berguna bagi siswa yang bekerja di bidang ilmu komputasi.
Karya ini dikhususkan untuk salah satu metode teori pengenalan pola — analisis klaster.
Ide-ide utama analisis klaster disajikan dalam bentuk ringkas dan beberapa area penerapannya dalam penelitian pertambangan ditampilkan. Metode clustering yang dijelaskan dapat digunakan dalam permasalahan nyata. Dalam algoritma, bagian komputasi dipertimbangkan dengan cukup detail.
Terlepas dari kenyataan bahwa analisis klaster adalah alat klasifikasi yang efektif dan nyaman, dan juga sangat umum dalam penelitian praktis, hanya ada sedikit publikasi tentang topik ini dalam bahasa Rusia, dan publikasi yang sudah ada tidak informatif. Brosur ini menyoroti beberapa isu mendasar analisis klaster.
Untuk para peneliti, disertasi dan spesialis yang bekerja di bidang analisis statistik multivariat.
Tag,Tema buku ini adalah tinjauan terhadap keadaan teori dan praktik penerapan “analisis klaster”. Metode ini memiliki semua kelebihan dari metode pengelompokan kombinasional, dan tidak lepas dari kelemahan utamanya - dispersi material, yang membuka prospek luas untuk penerapan metode tersebut dalam analisis statistik, dalam klasifikasi objek, dalam penelitian. hubungan, tipifikasi sampel, dll. Buku ini dibedakan berdasarkan kelengkapannya, aksesibilitasnya, dan singkatnya penyajiannya. Buku ini ditujukan bagi para ahli statistik, ekonom, serta sosiolog, demografi, biologi, dan spesialis lainnya. Direproduksi dalam ejaan penulis asli edisi 1977 (penerbit Statistica).
Tag,Topik penelitian berkisar dari analisis morfologi mumi hewan pengerat di New Guinea hingga kajian hasil pemungutan suara senator AS, dari analisis fungsi perilaku kecoa beku saat dicairkan, hingga kajian sebaran geografis. jenis lumut tertentu di Saskatchewan.
Ledakan publikasi ini berdampak besar pada pengembangan dan penerapan analisis klaster. Namun sayangnya, ada juga sisi negatifnya. Pesatnya pertumbuhan publikasi analisis klaster telah menyebabkan terbentuknya pengelompokan pengguna dan, sebagai konsekuensinya, terciptanya jargon yang hanya digunakan oleh pengelompokan yang menciptakannya (Blashfield dan Aldenderfer, 1978; Blashfield, 1980).
Terbentuknya jargon oleh para ilmuwan sosial misalnya dibuktikan dengan beragamnya terminologi yang berkaitan dengan metode Ward. "Metode lingkungan" disebut berbeda dalam literatur. Setidaknya ada empat nama lagi yang diketahui: "metode varians minimum", "metode kesalahan jumlah kuadrat", "minimalkan pengelompokan hierarki" dan "HGROUP". Dua nama pertama hanya merujuk pada kriteria yang optimumnya ditentukan dengan metode Ward, sedangkan nama ketiga terkait dengan jumlah kesalahan kuadrat, yang merupakan transformasi jejak monotonik dari matriks W, matriks kovarians intragrup. Terakhir, nama yang umum digunakan “HGROUP” adalah nama program komputer populer yang mengimplementasikan metode Ward (Veldman, 1967).
Pembentukan jargon menghambat pengembangan koneksi interdisipliner, menghalangi perbandingan efektif metodologi dan hasil penerapan analisis klaster di berbagai bidang ilmu pengetahuan, mengarah pada upaya yang tidak perlu (penemuan kembali algoritma yang sama) dan, akhirnya, tidak memberikan hal baru. pengguna pemahaman mendalam tentang metode yang mereka pilih (Blashfield dan aldenderfer, 1978). Misalnya, sebuah studi ilmu sosial (Rogers dan Linden, 1973) membandingkan tiga metode pengelompokan yang berbeda dengan menggunakan data yang sama. Mereka menyebut metode ini sebagai berikut: "pengelompokan hierarki", "pengelompokan hierarki atau HCG" dan "analisis cluster". Dan tidak satu pun dari nama-nama ini yang familier dengan metode pengelompokan. Pengguna pemula program analisis klaster akan bingung dengan semua nama yang ada dan tidak akan dapat mengaitkannya dengan deskripsi metode pengelompokan lainnya. Pengguna berpengalaman akan menemukan diri mereka dalam posisi sulit ketika membandingkan penelitian mereka dengan karya serupa. Kita mungkin bertindak ekstrem, namun jargon adalah masalah yang serius.
Dalam beberapa tahun terakhir, perkembangan analisis klaster agak melambat, dilihat dari jumlah publikasi dan jumlah disiplin ilmu yang menerapkan metode ini. Dapat dikatakan bahwa saat ini psikologi, sosiologi, biologi, statistika dan beberapa disiplin ilmu teknik sedang memasuki tahap konsolidasi terkait dengan analisis klaster.
Jumlah artikel yang memuji manfaat analisis klaster secara bertahap berkurang. Pada saat yang sama, semakin banyak karya yang membandingkan penerapan berbagai metode pengelompokan pada data kontrol. Dalam literatur, lebih banyak perhatian diberikan pada aplikasi. Banyak penelitian bertujuan untuk mengembangkan langkah-langkah praktis untuk menguji validitas hasil yang diperoleh dengan menggunakan analisis cluster. Semua ini membuktikan upaya serius untuk menciptakan teori statistik yang masuk akal tentang metode pengelompokan.
Mengirimkan karya bagus Anda ke basis pengetahuan itu sederhana. Gunakan formulir di bawah ini
Pelajar, mahasiswa pascasarjana, ilmuwan muda yang menggunakan basis pengetahuan dalam studi dan pekerjaan mereka akan sangat berterima kasih kepada Anda.
Perkenalan
1.Sejarah "analisis cluster"
2. Terminologi
2.1Objek dan fitur
2.2 Jarak antar benda (metrik)
2.3Kepadatan dan lokalitas cluster
2.4 Jarak antar cluster
3. Metode pengelompokan
3.1Fitur metode aglomerasi hierarkis
3.2Fitur metode pengelompokan berulang
4. Pengelompokan fitur
5. Stabilitas dan kualitas clustering
Bibliografi
PERKENALAN
Analisis cluster adalah seperangkat metode matematika yang dirancang untuk membentuk kelompok objek "dekat" yang relatif "jauh" satu sama lain berdasarkan informasi tentang jarak atau hubungan (ukuran kedekatan) di antara mereka. Arti serupa dengan istilah: otomatis klasifikasi, taksonomi, pengenalan pola tanpa guru." Definisi analisis klaster ini diberikan dalam Kamus Statistik edisi terbaru. Faktanya, "analisis cluster" adalah nama umum untuk sekumpulan algoritma yang cukup besar yang digunakan untuk membuat klasifikasi. Sejumlah publikasi juga menggunakan sinonim untuk analisis klaster seperti klasifikasi dan partisi. Analisis klaster banyak digunakan dalam sains sebagai sarana analisis tipologis. Dalam kegiatan ilmiah apa pun, klasifikasi merupakan salah satu komponen mendasar, yang tanpanya mustahil membangun dan menguji hipotesis dan teori ilmiah. Oleh karena itu, dalam pekerjaan saya, saya menganggap perlu untuk mempertimbangkan masalah analisis klaster (dasar analisis klaster), serta mempertimbangkan terminologinya dan memberikan beberapa contoh penggunaan metode ini dengan pemrosesan data sebagai tujuan utama saya.
1. SEJARAH “ANALISIS CLUSTER”
Analisis terhadap publikasi dalam dan luar negeri menunjukkan bahwa analisis klaster digunakan dalam berbagai bidang ilmiah: kimia, biologi, kedokteran, arkeologi, sejarah, geografi, ekonomi, filologi, dll. Buku karya VV Nalimov "Probabilistic Model of Language" menjelaskan penggunaan analisis cluster dalam studi terhadap 70 sampel analitik. Sebagian besar literatur mengenai analisis klaster telah muncul selama tiga dekade terakhir, meskipun karya pertama yang menyebutkan metode klaster muncul cukup lama. Antropolog Polandia K. Chekanowski mengemukakan gagasan "klasifikasi struktural", yang berisi gagasan utama analisis cluster - alokasi kelompok objek yang kompak.
Pada tahun 1925, ahli hidrobiologi Soviet P.V. Terentyev mengembangkan apa yang disebut "metode Pleiades Korelasi", yang dimaksudkan untuk mengelompokkan fitur-fitur yang berkorelasi. Metode ini memberi dorongan bagi berkembangnya metode pengelompokan dengan menggunakan grafik. Istilah "analisis cluster" pertama kali dikemukakan oleh Trion. Kata “cluster” diterjemahkan dari bahasa Inggris sebagai “bunch, brush, bundle, group”. Oleh karena itu, jenis analisis ini awalnya disebut “analisis cluster”. Pada awal 1950-an, publikasi oleh R. Lewis, E. Fix dan J. Hodges muncul tentang algoritma analisis cluster hierarki. Dorongan nyata untuk pengembangan penelitian analisis klaster diberikan oleh karya R. Rosenblatt tentang perangkat pengenalan (perceptron), yang meletakkan dasar bagi pengembangan teori "pengenalan pola tanpa guru".
Dorongan berkembangnya metode clustering adalah buku “Principles of Numerical Taxonomy” yang diterbitkan pada tahun 1963. dua ahli biologi - Robert Sokal dan Peter Sneath. Penulis buku ini berangkat dari fakta bahwa untuk menciptakan klasifikasi biologis yang efektif, prosedur pengelompokan harus memastikan penggunaan berbagai indikator yang mengkarakterisasi organisme yang diteliti, menilai tingkat kesamaan antara organisme tersebut, dan memastikan penempatan organisme serupa. dalam kelompok yang sama. Dalam hal ini, kelompok yang dibentuk harus cukup “lokal”, yaitu. kesamaan benda (organisme) dalam kelompok harus melebihi kesamaan kelompok satu sama lain. Analisis selanjutnya terhadap kelompok yang teridentifikasi, menurut pendapat penulis, dapat memperjelas apakah kelompok ini sesuai dengan spesies biologis yang berbeda. Dengan demikian, Sokal dan Sneath berasumsi bahwa mengungkap struktur distribusi objek ke dalam kelompok membantu menetapkan proses pembentukan struktur tersebut. Dan perbedaan serta persamaan organisme dari kelompok (kelompok) yang berbeda dapat menjadi dasar untuk memahami proses evolusi yang sedang berlangsung dan menjelaskan mekanismenya.
Pada tahun yang sama, banyak algoritma yang diusulkan oleh penulis seperti J. McKean, G. Ball dan D. Hall menggunakan metode k-means; G. Lance dan W. Williams, N. Jardine dan lainnya - tentang metode hierarki. Kontribusi signifikan terhadap pengembangan metode analisis klaster dibuat oleh ilmuwan dalam negeri - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. Khususnya, pada tahun 60-70an. Banyak algoritma yang dikembangkan oleh matematikawan Novosibirsk N.G. Zagoruiko, V.N. Elkina dan G.S. Lbov menikmati popularitas yang luar biasa. Ini adalah algoritma terkenal seperti FOREL, BIGFOR, KRAB, NTTP, DRET, TRF, dll. Berdasarkan paket ini, paket perangkat lunak OTEX khusus telah dibuat. Produk perangkat lunak PPSA dan Class-Master yang tidak kalah menarik diciptakan oleh matematikawan Moskow S.A. Aivazyan, I.S. Enyukov dan B.G. Mirkin.
Sampai batas tertentu, metode analisis klaster tersedia di sebagian besar paket statistik dalam dan luar negeri yang paling terkenal: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, COPRA-2, SITO, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS , GENSTAT, S -PLUS, dll. Tentu saja, 10 tahun setelah publikasi ulasan ini, banyak hal yang berubah, versi baru dari banyak program statistik telah muncul, dan program yang benar-benar baru telah muncul yang menggunakan algoritme baru dan daya komputasi yang sangat meningkat. Namun, sebagian besar paket statistik menggunakan algoritma yang diusulkan dan dikembangkan pada tahun 60-70an.
Menurut perkiraan kasar para ahli, jumlah publikasi tentang analisis klaster dan penerapannya di berbagai bidang pengetahuan meningkat dua kali lipat setiap tiga tahun. Apa alasan tingginya minat terhadap analisis jenis ini? Secara obyektif, ada tiga penyebab utama fenomena ini. Ini adalah munculnya teknologi komputasi yang kuat, yang tanpanya analisis klaster data nyata praktis tidak mungkin dilakukan. Alasan kedua adalah ilmu pengetahuan modern semakin mengandalkan klasifikasi dalam konstruksinya. Selain itu, proses ini semakin mendalam, karena bersamaan dengan itu terjadi peningkatan spesialisasi pengetahuan, yang tidak mungkin terjadi tanpa klasifikasi yang cukup obyektif.
Alasan ketiga - pendalaman pengetahuan khusus pasti mengarah pada peningkatan jumlah variabel yang diperhitungkan dalam analisis objek dan fenomena tertentu. Akibatnya, klasifikasi subjektif, yang sebelumnya mengandalkan sejumlah kecil fitur yang diperhitungkan, seringkali menjadi tidak dapat diandalkan. Dan klasifikasi objektif, dengan karakteristik objek yang terus meningkat, memerlukan penggunaan algoritma pengelompokan kompleks yang hanya dapat diimplementasikan berdasarkan komputer modern. Alasan-alasan inilah yang memunculkan “cluster boom”. Namun, di kalangan dokter dan ahli biologi, analisis cluster belum menjadi metode penelitian yang cukup populer dan umum.
2 TERMINOLOGI
2. 1 OBYEK DAN TANDA
Mari kita perkenalkan dulu konsep-konsep seperti objek dan tanda. Objek - dari bahasa Latin objectum - subjek. Dalam kaitannya dengan kimia dan biologi, yang dimaksud dengan objek adalah subjek penelitian tertentu yang dipelajari dengan menggunakan metode fisika, kimia, dan lainnya. Benda-benda tersebut dapat berupa sampel, tumbuhan, hewan, dan lain-lain. Sekumpulan objek tertentu yang tersedia bagi peneliti untuk dipelajari disebut sampel, atau kumpulan sampel. Banyaknya objek dalam suatu populasi biasa disebut dengan ukuran sampel. Biasanya ukuran sampel dilambangkan dengan huruf latin "n" atau "N".
Tanda (sinonim - properti, variabel, karakteristik; bahasa Inggris - variabel - variabel.) - adalah properti spesifik suatu objek. Properti ini dapat dinyatakan sebagai nilai numerik atau non-numerik. Misalnya, tekanan darah (sistolik atau diastolik) diukur dalam milimeter air raksa, berat badan dalam kilogram, tinggi badan dalam sentimeter, dll. Tanda-tanda seperti itu bersifat kuantitatif. Berbeda dengan karakteristik numerik (skala) yang kontinu ini, sejumlah fitur dapat mempunyai nilai yang diskrit dan terputus-putus. Pada gilirannya, fitur-fitur diskrit seperti itu biasanya dibagi menjadi dua kelompok.
1) Kelompok pertama adalah variabel rangking, atau disebut juga variabel ordinal (skala). Tanda-tanda seperti itu dicirikan oleh sifat mengatur nilai-nilai ini. Ini termasuk tahapan penyakit tertentu, kelompok umur, skor pengetahuan siswa, skala gempa Richter 12 poin, dll.
2) Kelompok ciri diskrit kedua tidak memiliki urutan seperti itu dan disebut nominal (dari kata "nominal" - sampel) atau ciri klasifikasi. Contoh dari tanda-tanda tersebut dapat berupa kondisi pasien - "sehat" atau "sakit", jenis kelamin pasien, periode observasi - "sebelum pengobatan" dan "setelah pengobatan", dll. Dalam kasus ini, biasanya dikatakan bahwa ciri-ciri tersebut termasuk dalam skala nama.
Konsep objek dan fitur biasanya disebut matriks "Properti objek" atau "Fitur objek". Matriksnya akan berupa tabel persegi panjang yang berisi nilai-nilai fitur yang menggambarkan sifat-sifat sampel observasi yang diteliti. Dalam konteks ini, satu observasi akan dicatat sebagai baris tersendiri yang berisi nilai-nilai fitur yang digunakan. Atribut terpisah dalam matriks data tersebut akan diwakili oleh kolom yang berisi nilai atribut ini untuk semua objek dalam sampel.
2. 2 JARAK ANTARA BENDA (METRIK)
Mari kita perkenalkan konsep "jarak antar benda". Konsep ini merupakan ukuran integral dari kemiripan suatu benda satu sama lain. Jarak antar objek dalam ruang fitur adalah suatu nilai d ij yang memenuhi aksioma berikut:
1. d ij > 0 (jarak tidak negatif)
2. d ij = d ji (simetri)
3. d ij + d jk > d ik (pertidaksamaan segitiga)
4. Jika d ij tidak sama dengan 0, maka i tidak sama dengan j (daya pembedaan benda tidak identik)
5. Jika d ij = 0, maka i = j (tidak dapat dibedakannya benda-benda yang identik)
Lebih mudah untuk menyatakan ukuran kedekatan (kesamaan) objek sebagai kebalikan dari jarak antar objek. Banyak publikasi tentang analisis klaster menjelaskan lebih dari 50 cara berbeda untuk menghitung jarak antar objek. Selain istilah "jarak", istilah lain yang sering ditemukan dalam literatur adalah "metrik", yang berarti suatu metode untuk menghitung jarak tertentu. Yang paling mudah diakses untuk persepsi dan pemahaman dalam hal fitur kuantitatif adalah apa yang disebut "jarak Euclidean" atau "metrik Euclidean". Rumus untuk menghitung jarak ini adalah:
Rumus ini menggunakan notasi berikut:
· d ij - jarak antara objek ke-i dan ke-j;
· x ik - nilai numerik variabel ke-k untuk objek ke-i;
· x jk - nilai numerik variabel ke-k untuk objek ke-j;
· v - jumlah variabel yang mendeskripsikan objek.
Jadi, untuk kasus v=2, jika kita hanya mempunyai dua tanda kuantitatif, jarak d ij akan sama dengan panjang sisi miring segitiga siku-siku yang menghubungkan dua titik pada sistem koordinat persegi panjang. Kedua titik ini akan sesuai dengan pengamatan sampel ke-i dan ke-j. Seringkali, alih-alih jarak Euclidean biasa, kuadrat d 2 ij digunakan. Selain itu, dalam beberapa kasus, jarak Euclidean "tertimbang" digunakan, dalam perhitungan yang menggunakan koefisien bobot untuk masing-masing suku. Untuk mengilustrasikan konsep metrik Euclidean, kami menggunakan contoh pelatihan sederhana. Matriks data yang ditunjukkan pada tabel di bawah ini terdiri dari 5 observasi dan dua variabel.
Tabel 1
Matriks data lima sampel observasi dan dua variabel.
Dengan menggunakan metrik Euclidean, kita menghitung matriks jarak antar objek, yang terdiri dari nilai d ij - jarak antara objek ke-i dan ke-j. Dalam kasus kita, i dan j adalah jumlah objek observasi. Karena ukuran sampel adalah 5, i dan j, masing-masing, dapat mengambil nilai dari 1 hingga 5. Jelas juga bahwa jumlah semua kemungkinan jarak berpasangan adalah 5*5=25. Memang benar, untuk objek pertama jaraknya adalah sebagai berikut: 1-1; 1-2; 1-3; 1-4; 1-5. Untuk objek 2 juga akan ada 5 kemungkinan jarak: 2-1; 2-2; 2-3; 2-4; 2-5 dll. Akan tetapi, banyaknya jarak yang berbeda akan kurang dari 25, karena sifat tidak dapat dibedakannya benda-benda yang identik harus diperhitungkan - d ij = 0 untuk i = j. Artinya jarak antara benda #1 dan benda #1 yang sama akan menjadi nol. Jarak nol yang sama akan berlaku untuk semua kasus lainnya i = j. Selain itu, sifat simetri dapat disimpulkan bahwa d ij = d ji untuk sembarang i dan j. Itu. jarak antara benda #1 dan #2 sama dengan jarak antara benda #2 dan #1.
Ekspresi jarak Euclidean sangat mirip dengan apa yang disebut jarak pangkat Minkowski yang digeneralisasi, yang menggunakan nilai lain, bukan dua pangkat. Secara umum, nilai ini dilambangkan dengan simbol "p".
Untuk p = 2 kita mendapatkan jarak Euclidean seperti biasa. Jadi ekspresi metrik Minkowski yang digeneralisasi memiliki bentuk:
Pemilihan nilai tertentu dari eksponen “p” dilakukan oleh peneliti sendiri.
Kasus khusus dari jarak Minkowski adalah apa yang disebut jarak Manhattan, atau "jarak blok kota", yang sesuai dengan p=1:
Jadi, jarak Manhattan adalah jumlah modul perbedaan fitur-fitur objek yang bersesuaian. Membiarkan p cenderung tak terhingga, kita mendapatkan metrik "dominasi", atau metrik Sup:
yang juga dapat direpresentasikan sebagai d ij = max| x ik - x jk |.
Metrik Minkowski sebenarnya adalah sekumpulan besar metrik, termasuk metrik yang paling populer. Namun, ada metode untuk menghitung jarak antar objek yang secara fundamental berbeda dari metrik Minkowski. Yang paling penting adalah apa yang disebut jarak Mahalanobis, yang memiliki sifat agak spesifik. Ekspresi untuk metrik ini:
Lewat sini X Saya Dan X J vektor kolom nilai variabel untuk objek ke-i dan ke-j ditunjukkan. Simbol T dalam ekspresi (X Saya - X J ) T menunjukkan apa yang disebut operasi transposisi vektor. Simbol S matriks varians-kovarians intra-grup yang umum ditunjukkan. Sebuah simbol -1 di atas S berarti Anda perlu membalikkan matriks S . Berbeda dengan metrik Minkowski dan metrik Euclidean, jarak Mahalanobis melalui matriks varians-kovarians S terkait dengan korelasi variabel. Jika korelasi antar variabel adalah nol, maka jarak Mahalanobis setara dengan kuadrat jarak Euclidean.
Dalam kasus penggunaan ciri kualitatif dikotomis (hanya memiliki dua nilai), jarak Hamming banyak digunakan
sama dengan jumlah ketidakcocokan nilai fitur yang sesuai untuk objek ke-i dan ke-j yang dipertimbangkan.
2. 3 KEPADATAN DAN LOKALITAS CLUSTER
Tujuan utama analisis klaster adalah menemukan kelompok objek yang serupa satu sama lain dalam sampel. Mari kita asumsikan bahwa dengan beberapa metode yang mungkin kita telah memperoleh kelompok - cluster seperti itu. Properti penting dari cluster harus diperhatikan. Salah satu properti tersebut adalah kepadatan distribusi titik, pengamatan dalam suatu cluster. Properti ini memungkinkan kita untuk mendefinisikan cluster sebagai sekelompok titik dalam ruang multidimensi yang relatif padat dibandingkan dengan wilayah lain dalam ruang ini yang tidak berisi titik sama sekali atau berisi sedikit observasi. Dengan kata lain, seberapa kompak cluster ini, atau sebaliknya, seberapa jarang cluster tersebut. Meskipun terdapat bukti yang cukup mengenai sifat ini, tidak ada cara yang pasti untuk menghitung indikator (densitas) tersebut. Indikator paling sukses yang mencirikan kekompakan, kepadatan "pengemasan" observasi multidimensi dalam suatu cluster tertentu, adalah dispersi jarak dari pusat cluster ke titik-titik individual cluster. Semakin kecil sebaran jarak tersebut, maka semakin dekat pengamatan ke pusat cluster, maka semakin besar pula kepadatan cluster tersebut. Begitu pula sebaliknya, semakin besar penyebaran jaraknya, maka semakin jarang cluster tersebut, sehingga terdapat titik-titik yang terletak dekat dengan pusat cluster dan cukup jauh dari pusat cluster.
Properti cluster berikutnya adalah ukurannya. Indikator utama ukuran sebuah cluster adalah "radius" -nya. Properti ini paling mencerminkan ukuran cluster sebenarnya jika cluster yang dipertimbangkan berbentuk bulat dan hipersfer dalam ruang multidimensi. Namun jika clusternya berbentuk memanjang, maka konsep radius atau diameter tidak lagi mencerminkan ukuran sebenarnya dari cluster tersebut.
Properti penting lainnya dari sebuah cluster adalah lokalitasnya, keterpisahannya. Ini mencirikan tingkat tumpang tindih dan keterpencilan timbal balik dari cluster satu sama lain dalam ruang multidimensi. Misalnya, perhatikan distribusi tiga cluster dalam ruang fitur baru yang terintegrasi pada gambar di bawah. Sumbu 1 dan 2 diperoleh dengan metode khusus dari 12 ciri sifat reflektif berbagai bentuk eritrosit, dipelajari menggunakan mikroskop elektron.
Gambar 1
Kita melihat bahwa cluster 1 memiliki ukuran minimum, sedangkan cluster 2 dan 3 memiliki ukuran yang kurang lebih sama. Pada saat yang sama, kita dapat mengatakan bahwa kepadatan minimum, dan karenanya dispersi jarak maksimum, merupakan karakteristik cluster 3. Selain itu, cluster 1 dipisahkan oleh ruang kosong yang cukup besar dari cluster 2 dan cluster 3. Sedangkan cluster 2 dan 3 sebagian tumpang tindih satu sama lain. Yang menarik adalah kenyataan bahwa cluster 1 memiliki perbedaan yang jauh lebih besar dari cluster ke-2 dan ke-3 di sepanjang sumbu 1 dibandingkan di sepanjang sumbu 2. Sebaliknya, cluster 2 dan 3 berbeda kira-kira sama satu sama lain baik di sepanjang sumbu 1 maupun di sepanjang sumbu 2. Jelasnya, untuk analisis visual seperti itu, semua pengamatan sampel perlu diproyeksikan ke sumbu khusus, di mana proyeksi elemen cluster akan terlihat sebagai cluster terpisah.
2. 4 JARAK ANTARA CLUSTER
Dalam pengertian yang lebih luas, objek dapat dipahami tidak hanya sebagai subjek penelitian asli, yang disajikan dalam matriks “objek-properti” sebagai garis terpisah, atau sebagai titik individual dalam ruang fitur multidimensi, tetapi juga sebagai kelompok terpisah dari titik-titik tersebut. , disatukan oleh satu algoritma atau lainnya ke dalam sebuah cluster. Dalam hal ini timbul pertanyaan bagaimana memahami jarak antara akumulasi titik (cluster) tersebut dan bagaimana cara menghitungnya. Dalam hal ini, variasi kemungkinannya bahkan lebih besar dibandingkan dengan penghitungan jarak antara dua observasi dalam ruang multidimensi. Prosedur ini diperumit oleh kenyataan bahwa, tidak seperti titik, cluster menempati sejumlah ruang multidimensi dan terdiri dari banyak titik. Dalam analisis klaster, jarak antar klaster banyak digunakan, dihitung berdasarkan prinsip tetangga terdekat (nearest neighbour), pusat gravitasi, tetangga terjauh, median. Empat metode yang paling banyak digunakan: single link, full link, average link, dan metode Ward. Pada metode single link, suatu objek akan dilampirkan pada cluster yang sudah ada jika setidaknya salah satu elemen cluster tersebut memiliki tingkat kemiripan yang sama dengan objek yang digabungkan. Untuk metode tautan lengkap, suatu objek dilampirkan ke sebuah cluster hanya jika kesamaan antara kandidat untuk dimasukkan dan salah satu elemen cluster tidak kurang dari ambang batas tertentu. Untuk metode koneksi rata-rata, terdapat beberapa modifikasi, yaitu beberapa kompromi antara koneksi tunggal dan penuh. Mereka menghitung nilai rata-rata kemiripan calon inklusi dengan seluruh objek cluster yang ada. Penempelan dilakukan ketika nilai rata-rata kesamaan yang ditemukan mencapai atau melebihi ambang batas tertentu. Yang paling umum digunakan adalah kesamaan rata-rata aritmatika antara objek cluster dan kandidat untuk dimasukkan ke dalam cluster.
Banyak metode pengelompokan yang berbeda satu sama lain karena algoritmanya pada setiap langkah menghitung berbagai fungsi kualitas partisi. Metode Ward yang populer dibangun sedemikian rupa untuk mengoptimalkan varian minimum jarak intracluster. Pada langkah pertama, setiap cluster terdiri dari satu objek, sehingga dispersi jarak intracluster sama dengan 0. Dengan metode ini, objek-objek yang memberikan pertambahan dispersi minimum digabungkan, sehingga metode ini cenderung menghasilkan cluster hipersferis.
Berbagai upaya untuk mengklasifikasikan metode analisis klaster menghasilkan lusinan atau bahkan ratusan kelas yang berbeda. Keanekaragaman tersebut dihasilkan oleh banyaknya kemungkinan cara untuk menghitung jarak antar observasi individu, tidak sedikit metode untuk menghitung jarak antar cluster individu dalam proses clustering, dan berbagai estimasi optimalitas struktur cluster akhir.
Yang paling banyak digunakan dalam paket statistik populer adalah dua kelompok algoritma analisis klaster: metode aglomerasi hierarkis dan metode pengelompokan berulang.
3. METODE PENGELOMPOKAN
3. 1 FITUR METODE AGGLOMERASI HIERARKIS
Dalam algoritma hierarki aglomeratif, yang lebih sering digunakan dalam penelitian biomedis nyata, pada awalnya semua objek (pengamatan) dianggap sebagai kelompok terpisah dan independen yang hanya terdiri dari satu elemen. Tanpa penggunaan teknologi komputer yang canggih, penerapan analisis data cluster akan sangat bermasalah.
Pilihan metrik dibuat oleh peneliti. Setelah menghitung matriks jarak, proses dimulai aglomerasi (dari bahasa Latin agglomero - saya lampirkan, kumpulkan), melewati langkah demi langkah secara berurutan. Pada langkah awal proses ini, dua buah observasi awal (monocluster) yang jarak antar keduanya paling kecil digabungkan menjadi satu cluster yang sudah terdiri dari dua objek (observasi). Jadi, alih-alih N monocluster (cluster yang terdiri dari satu objek), setelah langkah pertama, akan ada cluster N-1, yang mana satu cluster akan berisi dua objek (pengamatan), dan cluster N-2 akan tetap terdiri dari hanya satu objek. Pada langkah kedua, berbagai metode penggabungan cluster N-2 dimungkinkan. Hal ini karena salah satu cluster tersebut sudah berisi dua objek. Oleh karena itu, muncul dua pertanyaan utama:
· bagaimana menghitung koordinat sekelompok dua (dan selanjutnya lebih dari dua) objek;
· bagaimana menghitung jarak ke cluster "poli-objek" dari "monocluster" dan antara cluster "poli-objek".
Pada akhirnya, pertanyaan-pertanyaan ini menentukan struktur akhir dari cluster yang dihasilkan (struktur cluster berarti komposisi cluster individu dan posisi relatifnya dalam ruang multidimensi). Berbagai kombinasi metrik dan metode penghitungan koordinat dan jarak timbal balik klaster menimbulkan beragamnya metode analisis klaster. Pada langkah kedua, bergantung pada metode yang dipilih untuk menghitung koordinat suatu cluster yang terdiri dari beberapa objek dan metode untuk menghitung jarak antarcluster, dimungkinkan untuk menggabungkan kembali dua observasi terpisah ke dalam cluster baru, atau menggabungkan satu observasi baru. observasi ke cluster yang terdiri dari dua objek. Untuk kenyamanan, sebagian besar program metode hierarki aglomerasi di akhir pekerjaan dapat menyediakan dua grafik utama untuk dilihat. Grafik pertama disebut dendrogram (dari bahasa Yunani dendron - pohon), yang mencerminkan proses aglomerasi, penggabungan pengamatan individu menjadi satu kelompok akhir. Mari kita beri contoh dendrogram 5 observasi dalam dua variabel.
Jadwal1
Sumbu vertikal dari grafik tersebut adalah sumbu jarak antarcluster, dan jumlah objek – kasus yang digunakan dalam analisis – ditandai sepanjang sumbu horizontal. Dari dendrogram ini terlihat bahwa benda no 1 dan no 2 terlebih dahulu digabungkan menjadi satu cluster, karena jarak antar keduanya paling kecil dan sama dengan 1. Penggabungan ini ditampilkan pada grafik dengan garis horizontal yang menghubungkan vertikal segmen yang keluar dari titik bertanda C_1 dan C_2. Mari kita perhatikan fakta bahwa garis horizontal itu sendiri lewat tepat pada tingkat jarak antarcluster sama dengan 1. Selanjutnya, pada langkah kedua, objek No. 3, yang ditunjuk sebagai C_3, bergabung dengan cluster ini, yang sudah mencakup dua objek. Langkah selanjutnya adalah menggabungkan objek #4 dan #5 yang jarak keduanya sama dengan 1,41. Dan pada langkah terakhir, cluster objek 1, 2 dan 3 digabungkan dengan cluster objek 4 dan 5. Grafik menunjukkan bahwa jarak antara dua cluster kedua dari belakang (cluster terakhir mencakup kelima objek) lebih besar dari 5 , tetapi kurang dari 6, karena garis horizontal atas yang menghubungkan dua cluster kedua dari belakang melewati pada tingkat yang kira-kira sama dengan 7, dan tingkat hubungan objek 4 dan 5 adalah 1,41.
Dendrogram di bawah ini diperoleh dengan menganalisis dataset nyata yang terdiri dari 70 sampel kimia olahan yang masing-masing dikarakterisasi oleh 12 fitur.
Bagan 2
Terlihat dari grafik bahwa pada langkah terakhir, ketika dua cluster terakhir bergabung, jarak antara keduanya sekitar 200 unit. Terlihat bahwa cluster pertama memiliki objek yang jauh lebih sedikit dibandingkan cluster kedua.Di bawah ini adalah bagian dendrogram yang diperbesar dimana nomor observasi terlihat jelas, dilambangkan sebagai C_65, C_58, dst. (kiri ke kanan): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94, dst.
Bagan 3 Bagian yang diperbesar dari bagan #2 di atas
Terlihat bahwa objek 44 merupakan monocluster yang bergabung dengan cluster kanan pada langkah kedua dari belakang, kemudian pada langkah terakhir semua observasi digabungkan menjadi satu cluster.
Grafik lain yang dibangun dalam prosedur tersebut adalah grafik jarak antarcluster pada setiap langkah penyatuan. Di bawah ini adalah plot serupa untuk dendrogram di atas.
Bagan 4
Dalam sejumlah program, dimungkinkan untuk menampilkan dalam bentuk tabel hasil penggabungan objek pada setiap langkah pengelompokan. Di sebagian besar tabel ini, untuk menghindari kebingungan, terminologi yang berbeda digunakan untuk menunjuk observasi awal - monocluster, dan cluster sebenarnya yang terdiri dari dua atau lebih observasi. Dalam paket statistik berbahasa Inggris, observasi awal (baris matriks data) ditetapkan sebagai "kasus" - kasus. Untuk menunjukkan ketergantungan struktur cluster pada pilihan metrik dan pilihan algoritma cluster union, di bawah ini kami menyajikan dendrogram yang sesuai dengan algoritma koneksi lengkap. Dan di sini kita melihat bahwa objek #44 digabungkan dengan sisa pilihan pada langkah terakhir.
Bagan 5
Sekarang mari kita bandingkan dengan grafik lain yang diperoleh dengan menggunakan metode single link pada data yang sama. Berbeda dengan metode koneksi penuh, terlihat bahwa metode ini menghasilkan rantai panjang objek-objek yang saling menempel secara berurutan. Namun, dalam ketiga kasus tersebut, kita dapat mengatakan bahwa ada dua kelompok utama yang menonjol.
Bagan 6
Mari kita perhatikan juga fakta bahwa dalam ketiga kasus, objek No. 44 bergabung sebagai monokluster, meskipun pada langkah proses pengelompokan yang berbeda. Pemilihan monocluster tersebut merupakan cara yang baik untuk mendeteksi anomali observasi, yang disebut outlier. Mari kita hapus objek "mencurigakan" No. 44 ini dan lakukan pengelompokan lagi. Kami mendapatkan dendrogram berikut:
Bagan 7
Terlihat bahwa efek "rantai" tetap dipertahankan, begitu pula pembagian menjadi dua kelompok observasi lokal.
3. 2 FITUR METODE CLUSTERING ITERATIF
Di antara metode iteratif, metode yang paling populer adalah metode k-means McKean. Berbeda dengan metode hierarki, di sebagian besar implementasi metode ini, pengguna sendiri yang harus menentukan jumlah cluster akhir yang diinginkan, yang biasanya dilambangkan dengan "k". Seperti dalam metode pengelompokan hierarki, pengguna dapat memilih satu atau jenis metrik lainnya. Algoritma yang berbeda dari metode k-means juga berbeda dalam cara memilih pusat awal dari cluster yang diberikan. Dalam beberapa versi metode, pengguna sendiri dapat (atau harus) menentukan titik awal tersebut, baik dengan memilihnya dari pengamatan nyata, atau dengan menentukan koordinat titik tersebut untuk setiap variabel. Dalam implementasi lain dari metode ini, pemilihan sejumlah k titik awal dibuat secara acak, dan titik awal ini (butiran cluster) selanjutnya dapat disempurnakan dalam beberapa tahap. Ada 4 tahapan utama dari metode tersebut:
· memilih atau menetapkan k observasi yang akan menjadi pusat utama cluster;
· jika diperlukan, klaster perantara dibentuk dengan menugaskan setiap observasi ke pusat klaster terdekat yang ditentukan;
· setelah menugaskan semua pengamatan ke masing-masing klaster, pusat klaster primer digantikan oleh rata-rata klaster;
· Iterasi sebelumnya diulangi hingga perubahan koordinat pusat cluster menjadi minimal.
Dalam beberapa versi metode ini, pengguna dapat menetapkan nilai numerik dari kriteria, yang diartikan sebagai jarak minimum untuk memilih pusat cluster baru. Suatu observasi tidak akan dianggap sebagai calon pusat cluster baru apabila jaraknya terhadap pusat cluster yang digantikan melebihi angka yang ditentukan. Parameter ini disebut "radius" di beberapa program. Selain parameter ini, dimungkinkan juga untuk mengatur jumlah maksimum iterasi atau mencapai jumlah tertentu, biasanya cukup kecil, yang akan membandingkan perubahan jarak untuk semua pusat cluster. Pengaturan ini biasa disebut dengan “konvergensi” karena mencerminkan konvergensi proses pengelompokan berulang. Di bawah ini kami sajikan beberapa hasil yang diperoleh dengan menggunakan metode McKean k-means terhadap data sebelumnya. Jumlah cluster yang diinginkan awalnya ditetapkan menjadi 3 dan kemudian menjadi 2. Bagian pertama berisi hasil analisis varians satu arah, di mana nomor cluster bertindak sebagai faktor pengelompokan. Kolom pertama berisi daftar 12 variabel, diikuti jumlah kuadrat (SS) dan derajat kebebasan (df), kemudian uji F Fisher, dan pada kolom terakhir tingkat signifikansi “p” tercapai.
Tabel 2 Data McKean k-means berlaku untuk 70 sampel uji.
|
Variabel |
|||||||
Seperti terlihat dari tabel ini, hipotesis nol tentang kesetaraan mean pada ketiga kelompok ditolak. Di bawah ini adalah grafik rata-rata semua variabel untuk masing-masing cluster. Rata-rata cluster yang sama dari variabel disajikan di bawah ini dalam bentuk tabel.
Tabel 3. Tinjauan rinci data pada contoh tiga cluster.
|
Variabel |
Gugus #1 |
Gugus #2 |
Gugus #3 |
|
Bagan 8
Analisis nilai rata-rata variabel untuk setiap cluster memungkinkan kita untuk menyimpulkan bahwa menurut fitur X1, cluster 1 dan 3 memiliki nilai yang dekat, sedangkan cluster 2 memiliki nilai rata-rata yang jauh lebih rendah dibandingkan dua cluster lainnya. Sebaliknya menurut fitur X2, cluster pertama memiliki nilai terendah, sedangkan cluster ke-2 dan ke-3 memiliki nilai rata-rata yang lebih tinggi dan mendekati. Untuk sifat X3-X12, nilai mean pada cluster 1 jauh lebih tinggi dibandingkan pada cluster 2 dan 3. Tabel analisis ANOVA hasil pengelompokan menjadi dua cluster berikut juga menunjukkan perlunya menolak hipotesis nol tentang kesetaraan. rata-rata kelompok untuk hampir seluruh 12 fitur, kecuali variabel X4, yang tingkat signifikansinya ternyata lebih dari 5%.
Tabel 4. Tabel analisis sebaran hasil clustering menjadi dua cluster.
|
Variabel |
|||||||
Di bawah ini adalah grafik dan tabel mean grup untuk kasus clustering menjadi dua cluster.
Tabel 5. Tabel kasus clustering menjadi dua cluster.
|
Variabel |
Gugus #1 |
Gugus #2 |
|
Bagan 9.
Dalam hal peneliti tidak dapat menentukan terlebih dahulu jumlah cluster yang paling mungkin, ia terpaksa mengulangi perhitungan dengan menetapkan nomor yang berbeda, serupa dengan yang dilakukan di atas. Dan kemudian, membandingkan hasil yang diperoleh satu sama lain, berhenti pada salah satu opsi pengelompokan yang paling dapat diterima.
4 . PENGELOMPOKAN FITUR
Selain mengelompokkan pengamatan individu, ada juga algoritma pengelompokan fitur. Salah satu metode yang pertama adalah metode korelasi Pleiades Terentiev P.V. Gambaran primitif dari galaksi semacam itu sering kali dapat ditemukan dalam publikasi biomedis dalam bentuk lingkaran yang dihiasi dengan panah yang menghubungkan tanda-tanda yang penulis temukan korelasinya. Sejumlah program untuk mengelompokkan objek dan fitur memiliki prosedur terpisah. Misalnya, dalam paket SAS untuk pengelompokan fitur, prosedur VARCLUS (dari VARiable - variabel dan CLUSter - cluster) digunakan, sedangkan analisis observasi cluster dilakukan dengan prosedur lain - FASTCLUS dan CLUSTER. Konstruksi dendrogram dalam kedua kasus tersebut dilakukan dengan menggunakan prosedur TREE (pohon).
Dalam paket statistik lainnya, pemilihan elemen untuk pengelompokan - objek atau fitur - dilakukan dalam modul yang sama. Sebagai metrik untuk pengelompokan fitur, sering digunakan ekspresi yang menyertakan nilai koefisien tertentu yang mencerminkan kekuatan hubungan untuk sepasang fitur. Dalam hal ini, akan sangat mudah bagi tanda-tanda dengan kekuatan sambungan sama dengan satu (ketergantungan fungsional) untuk mengambil jarak antara tanda-tanda sama dengan nol. Memang, dengan koneksi fungsional, nilai suatu fitur dapat menghitung nilai fitur lainnya secara akurat. Dengan berkurangnya kekuatan hubungan antar tanda, jarak pun bertambah. Di bawah ini adalah grafik yang menunjukkan dendrogram kombinasi 12 fitur yang digunakan di atas saat mengelompokkan 70 sampel analitik.
Grafik 10. Dendrogrammengelompokkan 12 fitur.
Seperti dapat dilihat dari dendrogram ini, kita berhadapan dengan dua pengelompokan fitur lokal: X1-X10 dan X11-X12.Kelompok fitur X1-X10 dicirikan oleh nilai jarak antarkluster yang cukup kecil, tidak melebihi sekitar 100 unit. Di sini kita juga melihat beberapa subgrup berpasangan internal: X1 dan X2, X3 dan X4, X6 dan X7. Jarak antar ciri pasangan ini yang sangat mendekati nol menunjukkan hubungan pasangannya yang kuat. Sedangkan untuk pasangan X11 dan X12 nilai jarak antarclusternya jauh lebih besar yaitu sekitar 300 satuan. Terakhir, jarak yang sangat jauh antara cluster kiri (X1-X10) dan kanan (X11-X12), yaitu sekitar 1150 unit, menunjukkan bahwa hubungan antara kedua kelompok fitur ini cukup minim.
5. STABILITAS DAN KUALITAS CLUSTERING
Jelas, tidak masuk akal untuk mengajukan pertanyaan tentang seberapa absolut klasifikasi tertentu yang diperoleh dengan menggunakan metode analisis klaster. Ketika metode pengelompokan diubah, stabilitas diwujudkan dalam kenyataan bahwa dua cluster terlihat cukup jelas pada dendrogram.
Sebagai salah satu cara yang mungkin untuk memeriksa stabilitas hasil analisis cluster, dapat digunakan metode membandingkan hasil yang diperoleh dengan berbagai algoritma clustering. Cara lainnya adalah apa yang disebut metode bootstrap yang dikemukakan oleh B. Efron pada tahun 1977, metode “jackknife” dan “sliding control”. Cara paling sederhana untuk memeriksa stabilitas solusi cluster adalah dengan membagi sampel awal secara acak menjadi dua bagian yang kira-kira sama, mengelompokkan kedua bagian, dan kemudian membandingkan hasilnya. Cara yang lebih memakan waktu melibatkan pengecualian berurutan dari objek pertama di awal dan pengelompokan objek yang tersisa (N - 1). Selanjutnya, lakukan prosedur ini secara berurutan, kecuali prosedur kedua, ketiga, dan seterusnya. objek, struktur semua N cluster yang diperoleh dianalisis. Algoritme lain untuk memeriksa stabilitas melibatkan reproduksi berganda, duplikasi sampel asli N objek, kemudian menggabungkan semua sampel duplikat menjadi satu sampel besar (populasi umum semu) dan secara acak mengekstraksi sampel baru N objek dari sampel tersebut. Setelah itu dilakukan pengelompokan sampel ini, kemudian sampel acak baru diambil dan dilakukan pengelompokan kembali, dan seterusnya. Ini juga cukup padat karya.
Permasalahan yang tidak kalah pentingnya adalah ketika menilai kualitas clustering. Cukup banyak algoritma untuk mengoptimalkan solusi cluster yang diketahui. Karya pertama yang memuat rumusan kriteria minimalisasi varians intracluster dan algoritma (tipe k-means) untuk mencari solusi optimal muncul pada tahun 50-an. Pada tahun 1963 Artikel J. Ward juga menyajikan algoritma hierarki optimasi serupa. Tidak ada kriteria universal untuk mengoptimalkan solusi cluster. Semua ini menyulitkan peneliti untuk memilih solusi optimal. Dalam situasi seperti ini, cara terbaik untuk menyatakan bahwa solusi cluster yang ditemukan adalah optimal pada tahap penelitian ini hanyalah konsistensi solusi ini dengan kesimpulan yang diperoleh dengan menggunakan metode statistik multivariat lainnya.
Kesimpulan tentang optimalitas pengelompokan juga didukung oleh hasil positif dari pengecekan momen prediktif dari solusi yang diperoleh pada objek studi lain. Saat menggunakan metode analisis klaster hierarki, kami dapat merekomendasikan untuk membandingkan beberapa grafik perubahan langkah demi langkah dalam jarak antarkluster satu sama lain. Dalam hal ini, preferensi harus diberikan pada opsi di mana garis datar dari kenaikan tersebut diamati dari langkah pertama hingga beberapa langkah kedua dari belakang dengan kenaikan vertikal tajam pada grafik ini pada 1-2 langkah terakhir pengelompokan.
KESIMPULAN
Dalam pekerjaan saya, saya mencoba menunjukkan tidak hanya kompleksitas jenis analisis ini, tetapi juga kemampuan pemrosesan data yang optimal, karena seringkali untuk keakuratan hasil Anda harus menggunakan puluhan hingga ratusan sampel. Jenis analisis ini membantu mengklasifikasikan dan memproses hasil. Saya juga menganggap tidak kalah pentingnya penerimaan teknologi komputer dalam analisis ini, yang memungkinkan proses pemrosesan hasil memakan waktu lebih sedikit dan dengan demikian memungkinkan lebih banyak perhatian diberikan pada kebenaran pengambilan sampel untuk analisis.
Dalam penggunaan analisis klaster, terdapat kehalusan dan detail yang muncul dalam kasus-kasus tertentu dan tidak langsung terlihat. Misalnya, peran skala fitur mungkin minimal, dan mungkin dominan dalam beberapa kasus. Dalam kasus seperti ini, transformasi variabel perlu digunakan. Hal ini sangat efektif ketika menggunakan metode yang menghasilkan transformasi fitur non-linier yang umumnya meningkatkan tingkat korelasi antar fitur secara keseluruhan.
Ada kekhususan yang lebih besar dalam penggunaan analisis klaster dalam kaitannya dengan objek yang hanya dijelaskan oleh fitur kualitatif. Dalam hal ini, metode digitalisasi awal fitur kualitatif dan analisis klaster dengan fitur baru cukup berhasil. Dalam pekerjaan saya, saya menunjukkan bahwa analisis klaster memberikan banyak informasi baru dan orisinal baik dalam hal penerapannya dalam sistem yang cukup dipelajari, maupun dalam studi sistem dengan struktur yang tidak diketahui.
Perlu juga dicatat bahwa analisis klaster menjadi sangat diperlukan dalam penelitian evolusi, memungkinkan pembangunan pohon filogenetik yang menunjukkan jalur evolusi. Metode ini juga banyak digunakan dalam program penelitian ilmiah di bidang kimia fisik dan analitik.
BIBLIOGRAFI
1) Aivazyan S. A., Enyukov I. S., Meshalkin L. D. Tentang struktur dan isi paket perangkat lunak untuk analisis statistik terapan//Algoritma dan perangkat lunak untuk analisis statistik terapan.--M., 1980.
2) Ayvazyan S. A., Bezhaeva Z. I., Staroverov O. V. Klasifikasi observasi multidimensi.--M.: Statistics, 1974.
3) Becker V. A., Lukatskaya M. L. Tentang analisis struktur matriks koefisien kopling//Masalah pemodelan dan peramalan ekonomi dan statistik di industri.-- Novosibirsk, 1970.
4) Braverman E. M., Muchnik I. B. Metode struktural pengolahan data.--M.: Nauka, 1983.
5) Voronin Yu.A.Teori klasifikasi dan penerapannya.--Novosibirsk: Nauka, 1987.
6) Baik I. J. Botriologi botryologi // Klasifikasi dan cluster.--M.: Mir, 1980.
7) Dubrovsky S. A. Analisis statistik multivariat terapan.--M.: Keuangan dan statistik, 1982.
8) Duran N., Odell P. Analisis klaster.--M.: Statistika, 1977.
9) Eliseeva I.I., Rukavishnikov V.S.Pengelompokan, korelasi, pengenalan pola.--M.: Statistika, 1977.
10) Zagoruiko N. G. Metode pengenalan dan penerapannya.--M.: Radio Soviet, 1972.
11) Zade L. A. Himpunan fuzzy dan penerapannya dalam pengenalan pola dan analisis klaster//Klasifikasi dan klaster.--M.: Mir, 1980.
12) Kildishev G.S., Abolentsev Yu.I.Pengelompokan multidimensi.--M.: Statistik, 1978.
13) Raiskaya II, Gostilin NI, Frenkel' AA Tentang salah satu cara untuk memeriksa validitas partisi dalam analisis klaster.//Penerapan analisis statistik multivariat dalam perekonomian dan penilaian kualitas produk.--Ch. P.Tartu, 1977.
14) Shurygin A. M. Distribusi jarak dan perbedaan antar titik // Dukungan perangkat lunak dan algoritmik untuk analisis statistik multidimensi terapan.--M., 1983.
15) Eeremaa R. Teori umum merancang sistem cluster dan algoritma untuk menemukan representasi numeriknya: Prosiding Pusat Komputasi TSU.--Tartu, 1978.
16) Yastremsky B.S. Karya Terpilih.--M.: Statistika, 1964.
Dokumen Serupa
Tujuan segmentasi pasar dalam kegiatan pemasaran. Intisari analisis klaster, tahapan utama pelaksanaannya. Pilih cara mengukur jarak atau ukuran kesamaan. Metode pengelompokan hierarkis dan non-hierarki. Penilaian reliabilitas dan reliabilitas.
laporan, ditambahkan pada 02.11.2009
Indikator utama kondisi keuangan perusahaan. Krisis di perusahaan, penyebab, jenis dan konsekuensinya. Metode modern dan alat analisis klaster, fitur penggunaannya untuk evaluasi keuangan dan ekonomi suatu perusahaan.
tesis, ditambahkan 10/09/2013
Lakukan analisis klaster perusahaan menggunakan Statgraphics Plus. Konstruksi persamaan regresi linier. Perhitungan koefisien elastisitas dengan model regresi. Penilaian signifikansi statistik persamaan dan koefisien determinasi.
tugas, ditambahkan 16/03/2014
Konstruksi regresi tipologis untuk kelompok observasi individu. Data spasial dan informasi temporal. Lingkup penerapan analisis klaster. Konsep homogenitas benda, sifat matriks jarak. Melakukan regresi tipologis.
presentasi, ditambahkan 26/10/2013
Penciptaan model dan metode gabungan sebagai cara peramalan modern. Model berbasis ARIMA untuk menggambarkan deret waktu stasioner dan non stasioner dalam menyelesaikan masalah clustering. Model AR autoregresif dan penerapan korelogram.
presentasi, ditambahkan 01/05/2015
Karakteristik berbagai jenis metrik. Metode tetangga terdekat dan generalisasinya. Algoritma Tetangga Terdekat. Metode jendela Parzen. Pengklasifikasi metrik umum. Masalah memilih metrik. Jarak Manhattan dan Euclidean. ukuran kosinus.
makalah, ditambahkan 03/08/2015
Karakteristik industri konstruksi di Wilayah Krasnodar. Prakiraan perkembangan pembangunan perumahan. Metode modern dan alat analisis klaster. Metode statistik multidimensi untuk mendiagnosis keadaan ekonomi suatu perusahaan.
tesis, ditambahkan 20/07/2015
Karakteristik pinjaman hipotek pada contoh wilayah Bryansk. Tinjauan metode pengambilan keputusan matematis: evaluasi ahli, perbandingan berurutan dan berpasangan, analisis hierarki. Pengembangan program pencarian pinjaman hipotek yang optimal.
makalah, ditambahkan 29/11/2012
Bidang penerapan analisis sistem, tempatnya, peran, tujuan dan fungsinya dalam ilmu pengetahuan modern. Konsep dan isi metode analisis sistem, metode informalnya. Fitur metode penelitian heuristik dan ahli serta fitur penerapannya.
makalah, ditambahkan pada 20/05/2013
Pengembangan dan penelitian metode ekonometrik, dengan memperhatikan kekhususan data ekonomi dan sesuai dengan kebutuhan ilmu dan praktek ekonomi. Penerapan metode dan model ekonometrik untuk analisis statistik data ekonomi.
Istilah "analisis cluster" pertama kali digunakan oleh psikolog Amerika Robert Trion dalam karyanya dengan nama yang sama pada tahun 1930. Meskipun demikian, istilah "cluster" dan "cluster analysis" dianggap baru oleh penutur asli, seperti yang dicatat oleh Alexander Khrolenko, yang melakukan analisis korpus terhadap penggunaan leksem "cluster": "sebagian besar penulis menggunakan istilah ini membayar perhatian pada kebaruannya" (Khrolenko, 2016, hal. 106)
Analisis cluster mencakup banyak algoritma klasifikasi yang berbeda, yang tujuannya adalah untuk mengatur informasi ke dalam cluster. Penting untuk diingat bahwa analisis klaster itu sendiri bukanlah suatu algoritma tertentu, tetapi ada tugas yang perlu diselesaikan. Mark Ereshefsky mencatat dalam karyanya "The Scarcity of the Linear Hierarchy" bahwa analisis cluster adalah salah satu dari tiga jenis klasifikasi objek di dunia, bersama dengan esensialisme dan klasifikasi sejarah.
Dalam linguistik, prinsip deskripsi cluster mengandung arti, selain analisis unit-unit yang termasuk dalam cluster ini, juga analisis hubungan di dalamnya. Ini dapat berupa hubungan pada tingkat yang berbeda: dari hubungan logis (paradigmatis dan sintagmatik, misalnya) hingga pembentukan kata dan hubungan fonetik.
F. Brown mengidentifikasi langkah-langkah analisis klaster berikut (Brown):
- 1. Memilih suatu ukuran dan menghasilkan pengukuran, kriteria atau entitas yang diperlukan untuk diklasifikasikan
- 2. Menetapkan ukuran kemiripan
- 3. Perumusan aturan penentuan urutan pembentukan klaster
- 4. Menerapkan aturan untuk membentuk cluster
Perlu dicatat bahwa poin ketiga menimbulkan pertanyaan, karena ciri khas clustering sebagai metode klasifikasi adalah tidak adanya kelas tertentu. Pengelompokan dokumen adalah tugas pencarian informasi. Tidak seperti kategorisasi teks, ini tidak menyertakan kategori atau set pelatihan yang telah ditentukan sebelumnya. Cluster dan hubungan di antara mereka "secara otomatis diekstraksi dari dokumen, dan dokumen secara berurutan dilampirkan ke cluster ini" (Golub, hal. 52-53) Mark Ereshefsky memperkenalkan analisis cluster sebagai metode klasifikasi. Dia percaya bahwa "semua bentuk analisis cluster didasarkan pada dua asumsi: anggota kelompok taksonomi harus berbagi sekelompok sifat, dan sifat-sifat ini tidak dapat muncul pada semua atau hanya satu anggota kelompok ini." (Ereshefsky, hal. 15)
Dalam karyanya “Pendekatan Cluster dalam Analisis Linguistik” (Nurgalieva, 2013) N.Kh. Nurgalieva mengidentifikasi empat tugas utama analisis klaster:
- 1. Perkembangan tipologi atau klasifikasi
- 2. Menjelajahi skema konseptual yang berguna untuk mengelompokkan objek
- 3. Penyajian hipotesis berdasarkan data yang diteliti
- 4. Menguji hipotesis atau penelitian untuk menentukan apakah jenis (kelompok) yang diidentifikasi dengan satu atau lain cara benar-benar ada dalam data yang tersedia
Semua metode analisis klaster dapat dibagi menjadi analisis klaster yang "keras" dan jelas, ketika setiap objek termasuk dalam suatu klaster atau tidak, dan "lunak", analisis klaster fuzzy, ketika setiap objek termasuk dalam kelompok tertentu dengan tingkat probabilitas tertentu. .
Metode analisis cluster juga dibagi menjadi hierarki dan non-hierarki. Metode hierarki menyiratkan adanya kelompok bersarang, tidak seperti metode non-hierarki. Nurgaliyeva mencatat bahwa metode hierarki "tampaknya paling cocok untuk memecahkan masalah linguistik" (Nurgaliyeva, hal. 1), karena memungkinkan Anda melihat dan menganalisis struktur fenomena yang diteliti.
ANALISIS CLUSTER DALAM MASALAH PERAMALAN SOSIAL EKONOMI
Pengantar analisis klaster.
Ketika menganalisis dan meramalkan fenomena sosial-ekonomi, peneliti sering kali menemukan deskripsinya yang multidimensi. Hal ini terjadi ketika memecahkan masalah segmentasi pasar, membangun tipologi negara menurut sejumlah indikator yang cukup banyak, memprediksi situasi pasar untuk barang-barang tertentu, mempelajari dan memprediksi depresi ekonomi, dan banyak masalah lainnya.
Metode analisis multivariat adalah alat kuantitatif yang paling efektif untuk mempelajari proses sosial ekonomi yang dijelaskan oleh sejumlah besar karakteristik. Ini termasuk analisis cluster, taksonomi, pengenalan pola, dan analisis faktor.
Analisis cluster paling jelas mencerminkan fitur analisis multivariat dalam klasifikasi, analisis faktor - dalam studi komunikasi.
Terkadang pendekatan analisis klaster disebut dalam literatur sebagai taksonomi numerik, klasifikasi numerik, pengenalan pembelajaran mandiri, dll.
Analisis klaster menemukan penerapan pertamanya dalam sosiologi. Nama analisis klaster berasal dari kata bahasa Inggris cluster - kumpulan, akumulasi. Untuk pertama kalinya pada tahun 1939, subjek analisis klaster didefinisikan dan dijelaskan oleh peneliti Trion. Tujuan utama dari analisis klaster adalah untuk membagi himpunan objek dan fitur yang diteliti ke dalam kelompok atau klaster yang homogen dalam arti yang sesuai. Ini berarti bahwa masalah mengklasifikasikan data dan mengidentifikasi struktur yang sesuai di dalamnya telah terpecahkan. Metode analisis klaster dapat diterapkan dalam berbagai kasus, bahkan dalam kasus di mana kita berbicara tentang pengelompokan sederhana, yang semuanya bermuara pada pembentukan kelompok berdasarkan kesamaan kuantitatif.
Keuntungan besar dari analisis klaster adalah memungkinkan Anda mempartisi objek bukan berdasarkan satu parameter, tetapi berdasarkan keseluruhan rangkaian fitur. Selain itu, analisis klaster, tidak seperti kebanyakan metode matematika dan statistik, tidak memberlakukan batasan apa pun pada jenis objek yang dipertimbangkan, dan memungkinkan kita untuk mempertimbangkan sekumpulan data awal yang sifatnya hampir berubah-ubah. Hal ini sangat penting, misalnya, untuk peramalan konjungtur, ketika indikator mempunyai bentuk yang beragam sehingga menyulitkan penggunaan pendekatan ekonometrik tradisional.
Analisis klaster memungkinkan untuk mempertimbangkan sejumlah besar informasi dan secara drastis mengurangi, memampatkan sejumlah besar informasi sosial-ekonomi, menjadikannya kompak dan visual.
Analisis klaster sangat penting dalam kaitannya dengan rangkaian waktu yang mencirikan pembangunan ekonomi (misalnya, kondisi ekonomi dan komoditas secara umum). Di sini dimungkinkan untuk memilih periode ketika nilai indikator terkait cukup dekat, serta menentukan kelompok deret waktu, yang dinamikanya paling mirip.
Analisis klaster dapat digunakan secara siklis. Dalam hal ini penelitian dilakukan sampai tercapai hasil yang diinginkan. Pada saat yang sama, setiap siklus di sini dapat memberikan informasi yang dapat mengubah arah dan pendekatan penerapan analisis klaster lebih lanjut. Proses ini dapat direpresentasikan sebagai sistem umpan balik.
Dalam permasalahan peramalan sosial ekonomi, sangat menjanjikan untuk menggabungkan analisis klaster dengan metode kuantitatif lainnya (misalnya dengan analisis regresi).
Seperti metode lainnya, analisis klaster memiliki kelemahan dan keterbatasan tertentu: Secara khusus, komposisi dan jumlah klaster bergantung pada kriteria partisi yang dipilih. Saat mereduksi susunan data awal ke bentuk yang lebih kompak, distorsi tertentu mungkin terjadi, dan fitur individual dari objek individual juga mungkin hilang karena penggantiannya dengan karakteristik nilai umum dari parameter cluster. Saat mengklasifikasikan objek, seringkali kemungkinan tidak adanya nilai cluster dalam kumpulan yang dipertimbangkan diabaikan.
Dalam analisis klaster, dianggap bahwa:
a) karakteristik yang dipilih memungkinkan, pada prinsipnya, pengelompokan yang diinginkan;
b) satuan pengukuran (skala) dipilih dengan benar.
Pilihan skala memainkan peran besar. Biasanya, data dinormalisasi dengan mengurangkan mean dan membaginya dengan standar deviasi sehingga variansnya sama dengan satu.
Masalah analisis klaster.
Tugas analisis klaster adalah membagi himpunan objek G menjadi m (m merupakan bilangan bulat) klaster (subset) Q1, Q2,…, Qm, berdasarkan data yang terdapat pada himpunan X, sehingga setiap objek Gj milik satu dan hanya satu subset partisi dan objek-objek yang termasuk dalam cluster yang sama adalah serupa, sedangkan objek-objek yang termasuk dalam cluster yang berbeda bersifat heterogen.
Misalnya, G mencakup n negara, yang masing-masing dicirikan oleh GNP per kapita (F1), jumlah M mobil per 1.000 orang (F2), konsumsi listrik per kapita (F3), konsumsi baja per kapita (F4), dll. Kemudian X1 (vektor pengukuran) adalah sekumpulan karakteristik tertentu untuk negara pertama, X2 untuk negara kedua, X3 untuk negara ketiga, dan seterusnya. Tantangannya adalah mengelompokkan negara-negara berdasarkan tingkat pembangunannya.
Solusi dari masalah analisis klaster adalah partisi yang memenuhi kriteria optimalitas tertentu. Kriteria ini dapat berupa suatu fungsi yang menyatakan tingkat keinginan berbagai partisi dan pengelompokan, yang disebut fungsi tujuan. Misalnya, jumlah deviasi kuadrat intragrup dapat diambil sebagai fungsi tujuan:
dimana xj - mewakili pengukuran objek ke-j.
Untuk mengatasi masalah analisis cluster, perlu didefinisikan konsep kesamaan dan heterogenitas.
Jelas bahwa objek ke-i dan ke-j akan jatuh ke dalam cluster yang sama ketika jarak (jarak) antara titik Xi dan Xj cukup kecil dan akan jatuh ke dalam cluster yang berbeda ketika jarak ini cukup besar. Jadi, masuk ke dalam satu atau beberapa cluster objek ditentukan oleh konsep jarak antara Xi dan Xj dari Ep, dimana Ep adalah ruang Euclidean berdimensi p. Fungsi non-negatif d(Xi, Xj) disebut fungsi jarak (metrik) jika:
a) d(Xi , Xj) ³ 0, untuk semua Xi dan Xj dari Ep
b) d(Xi, Xj) = 0 jika dan hanya jika Xi = Xj
c) d(Xi, Xj) = d(Xj, Xi)
d) d(Xi, Xj) £ d(Xi, Xk) + d(Xk, Xj), dimana Xj; Xi dan Xk adalah tiga vektor apa pun dari Ep.
Nilai d(Xi, Xj) untuk Xi dan Xj disebut jarak antara Xi dan Xj dan ekuivalen dengan jarak antara Gi dan Gj menurut karakteristik yang dipilih (F1, F2, F3, ..., Fр).
Fungsi jarak yang paling umum digunakan adalah:
1. Jarak Euclidean d2(Хi , Хj) = 
2. l1 - norma d1(Хi , Хj) =
3. Supremum - norma d¥ (Хi , Хj) = sup
k = 1, 2, ..., hal
4. lp - norma dр(Хi , Хj) = 
Metrik Euclidean adalah yang paling populer. Metrik l1 adalah yang paling mudah untuk dihitung. Norma supremum mudah dihitung dan mencakup prosedur pengurutan, sedangkan norma lp mencakup fungsi jarak 1, 2, 3,.
Misalkan n pengukuran X1, X2,..., Xn direpresentasikan sebagai matriks data p ´n:
Maka jarak antar pasangan vektor d(Хi , Хj) dapat direpresentasikan sebagai matriks jarak simetris:
Konsep kebalikan dari jarak adalah konsep kemiripan antar benda Gi. dan Gj. Fungsi real non-negatif S(Хi ; Хj) = Sij disebut ukuran kemiripan jika:
1) 0 £ S(Xi , Xj)<1 для Хi¹ Хj
2) S(Хi , Хi) = 1
3) S(Xi, Xj) = S(Xj, Xi)
Pasangan nilai ukuran kesamaan dapat digabungkan menjadi matriks kesamaan:
Nilai Sij disebut dengan koefisien kemiripan.
1.3. Metode analisis klaster.
Saat ini ada banyak metode analisis klaster. Mari kita membahas beberapa di antaranya (metode di bawah ini biasanya disebut metode varians minimum).
Misalkan X adalah matriks pengamatan: X = (X1, X2,..., Xu) dan kuadrat jarak Euclidean antara Xi dan Xj ditentukan dengan rumus:
1) Metode koneksi lengkap.
Inti dari metode ini adalah bahwa dua benda yang termasuk dalam kelompok (cluster) yang sama mempunyai koefisien kemiripan yang lebih kecil dari suatu nilai ambang batas S. Dalam hal jarak Euclidean d, ini berarti jarak antara dua titik (benda) sebesar cluster tidak boleh melebihi nilai ambang batas tertentu h. Jadi, h menentukan diameter maksimum yang diijinkan dari suatu subset yang membentuk sebuah cluster.
2) Metode jarak lokal maksimum.
Setiap objek dianggap sebagai cluster satu titik. Objek dikelompokkan menurut aturan berikut: dua cluster digabungkan jika jarak maksimum antara titik satu cluster dan titik cluster lainnya minimal. Prosedur ini terdiri dari n - 1 langkah dan menghasilkan partisi yang cocok dengan semua kemungkinan partisi pada metode sebelumnya untuk nilai ambang batas apa pun.
3) Metode kata.
Dalam metode ini, jumlah simpangan kuadrat intragrup digunakan sebagai fungsi tujuan, yang tidak lebih dari jumlah kuadrat jarak antara setiap titik (objek) dan rata-rata cluster yang memuat objek tersebut. Pada setiap langkah, dua cluster digabungkan yang menghasilkan peningkatan minimum pada fungsi tujuan, yaitu. jumlah kuadrat intragrup. Metode ini bertujuan untuk menggabungkan cluster-cluster yang berjarak berdekatan.
4) Metode pusat.
Jarak antara dua cluster didefinisikan sebagai jarak Euclidean antara pusat (rata-rata) cluster berikut:
d2 ij = (`X – `Y)Т(`X – `Y) Pengelompokan berlangsung langkah demi langkah pada masing-masing n–1 langkah menggabungkan dua cluster G dan p yang memiliki nilai minimum d2ij Jika n1 jauh lebih besar dari n2, maka pusat penyatuan dua cluster berdekatan satu sama lain dan karakteristik cluster kedua praktis diabaikan ketika cluster digabungkan. Kadang-kadang metode ini kadang juga disebut dengan metode kelompok berbobot.
1.4 Algoritma pengelompokan sekuensial.
Anggap Ι = (Ι1, Ι2, … Ιn) sebagai himpunan cluster (Ι1), (Ι2),…(Ιn). Mari kita pilih dua di antaranya, misalnya, Ι i dan Ι j, yang dalam beberapa hal lebih dekat satu sama lain dan menggabungkannya menjadi satu cluster. Kumpulan cluster baru, yang sudah terdiri dari n-1 cluster, akan menjadi:
(Ι1), (Ι2)…, (Ι saya , Ι j), …, (Ιn).
Mengulangi proses tersebut, kita memperoleh kumpulan cluster berturut-turut yang terdiri dari (n-2), (n-3), (n-4), dst. cluster. Di akhir prosedur, Anda bisa mendapatkan cluster yang terdiri dari n objek dan bertepatan dengan himpunan awal Ι = (Ι1, Ι2, … Ιn).
Sebagai ukuran jarak, kita ambil kuadrat metrik Euclidean di j2. dan hitung matriks D = (di j2), dimana di j2 adalah kuadrat jarak antara
| Ι1 | Ι2 | Ι3 | …. | tidak | |
| Ι1 | 0 | d122 | d132 | …. | d1n2 |
| Ι2 | 0 | d232 | …. | d2n2 | |
| Ι3 | 0 | …. | d3n2 | ||
| …. | …. | …. | |||
| tidak | 0 |
Biarkan jarak antara Ι i dan Ι j menjadi minimal:
di j2 = menit (di j2, i ¹ j). Dengan bantuan Ι i dan Ι j kita membentuk cluster baru
(Ιi, Ιj). Buatlah matriks jarak ((n-1), (n-1)) baru
| (Ι saya , Ι j) | Ι1 | Ι2 | Ι3 | …. | tidak | |
| (Ι saya ; Ι j) | 0 | di j21 | di j22 | di j23 | …. | di j2n |
| Ι1 | 0 | d122 | d13 | …. | d12n | |
| Ι2 | 0 | di j21 | …. | d2n | ||
| Ι3 | 0 | …. | d3n | |||
| tidak | 0 |
(n-2) baris matriks terakhir diambil dari matriks sebelumnya, dan baris pertama dihitung ulang. Perhitungan dapat diperkecil seminimal mungkin jika di j2k,k = 1, 2,…, n dapat dinyatakan; (k ¹ i ¹ j) melalui elemen matriks asal.
Awalnya jarak yang ditentukan hanya antar cluster berelemen tunggal, namun perlu juga ditentukan jarak antar cluster yang mengandung lebih dari satu elemen. Hal ini dapat dilakukan dengan berbagai cara, dan bergantung pada metode yang dipilih, kita mendapatkan algoritma analisis cluster dengan properti berbeda. Misalnya, seseorang dapat mengatur jarak antara cluster i + j dan beberapa cluster lainnya k sama dengan rata-rata aritmatika jarak antara cluster i dan k dan cluster j dan k:
di+j,k = ½ (dik + djk).
Namun kita juga dapat mendefinisikan di+j,k sebagai jarak minimum dari dua jarak berikut:
di+j,k = menit(di k + dj k).
Dengan demikian, langkah pertama dari operasi algoritma hierarki aglomeratif dijelaskan. Langkah selanjutnya sama.
Kelas algoritma yang cukup luas dapat diperoleh jika rumus umum berikut digunakan untuk menghitung ulang jarak:
di+j,k = A(w) min(dik djk) + B(w) max(dik djk), dimana
A(w) = jika dik £djk
A(w) = jika dik > djk
B(w) = jika dik £djk
B(w) = jika dik > djk
dimana ni dan nj adalah jumlah elemen dalam cluster i dan j, dan w adalah parameter bebas, pilihannya menentukan algoritma tertentu. Misalnya, dengan w = 1, kita mendapatkan apa yang disebut algoritma “koneksi rata-rata”, yang rumus untuk menghitung ulang jarak berbentuk:
di+j,k = 
Dalam hal ini, jarak antara dua cluster pada setiap langkah algoritma ternyata sama dengan rata-rata aritmatika dari jarak antara semua pasangan elemen sedemikian rupa sehingga satu elemen dari pasangan tersebut menjadi milik satu cluster, yang lainnya milik cluster lainnya.
Arti visual dari parameter w menjadi jelas jika kita menempatkan w®¥. Rumus konversi jarak berbentuk:
di+j,k = min(di,k djk)
Ini akan menjadi apa yang disebut algoritma “tetangga terdekat”, yang memungkinkan Anda memilih cluster dengan bentuk kompleks yang sewenang-wenang, asalkan bagian-bagian berbeda dari cluster tersebut dihubungkan oleh rantai elemen yang berdekatan satu sama lain. Dalam hal ini, jarak antara dua cluster pada setiap langkah algoritma ternyata sama dengan jarak antara dua elemen terdekat milik kedua cluster tersebut.
Seringkali diasumsikan bahwa jarak awal (perbedaan) antara elemen-elemen yang dikelompokkan diberikan. Dalam beberapa kasus, hal ini benar. Namun, hanya objek dan karakteristiknya yang ditentukan, dan matriks jarak dibuat berdasarkan data tersebut. Bergantung pada apakah jarak antar objek atau antara karakteristik objek dihitung, metode yang berbeda digunakan.
Dalam kasus analisis cluster objek, ukuran perbedaan yang paling umum adalah kuadrat jarak Euclidean
(di mana xih, xjh adalah nilai atribut ke-h untuk objek ke-i dan ke-j, dan m adalah banyaknya karakteristik), atau jarak Euclidean itu sendiri. Jika fitur diberi bobot yang berbeda, maka bobot tersebut dapat diperhitungkan saat menghitung jarak
Terkadang jarak digunakan sebagai ukuran perbedaan, dihitung dengan rumus:
yang disebut: jarak "Hamming", "Manhattan" atau "blok kota".
Ukuran alami kesamaan karakteristik objek dalam banyak masalah adalah koefisien korelasi di antara keduanya
dimana mi ,mj ,di ,dj adalah deviasi mean dan akar-rata-rata-kuadrat untuk masing-masing karakteristik i dan j. Nilai 1 – r dapat dijadikan sebagai ukuran perbedaan antar karakteristik. Dalam beberapa soal, tanda koefisien korelasi tidak signifikan dan hanya bergantung pada pilihan satuan pengukuran. Dalam hal ini, ô1 - ri j ô digunakan sebagai ukuran selisih antar karakteristik
1.5 Jumlah cluster.
Masalah yang sangat penting adalah masalah pemilihan jumlah cluster yang dibutuhkan. Terkadang sejumlah m cluster dapat dipilih secara apriori. Namun, secara umum, jumlah ini ditentukan dalam proses pemisahan himpunan menjadi beberapa cluster.
Studi dilakukan oleh Fortier dan Solomon, dan ditemukan bahwa jumlah cluster harus diambil untuk mencapai probabilitas a bahwa partisi terbaik ditemukan. Jadi, jumlah partisi optimal adalah fungsi dari pecahan b tertentu dari partisi terbaik atau, dalam arti tertentu, partisi layak dalam himpunan semua partisi yang mungkin. Total hamburan akan semakin besar, semakin tinggi fraksi b dari partisi yang diperbolehkan. Fortier dan Solomon mengembangkan tabel yang dapat digunakan untuk mengetahui jumlah partisi yang dibutuhkan. S(a,b) bergantung pada a dan b (di mana a adalah probabilitas ditemukannya partisi terbaik, b adalah proporsi partisi terbaik dalam jumlah total partisi) Selain itu, sebagai ukuran heterogenitas, bukan hamburan ukuran yang digunakan, tetapi ukuran keanggotaan yang diperkenalkan oleh Holzenger dan Harman. Tabel nilai S(a,b) diberikan di bawah ini.
tabel nilai S(a,b).
| b\a | 0.20 | 0.10 | 0.05 | 0.01 | 0.001 | 0.0001 |
| 0.20 | 8 | 11 | 14 | 21 | 31 | 42 |
| 0.10 | 16 | 22 | 29 | 44 | 66 | 88 |
| 0.05 | 32 | 45 | 59 | 90 | 135 | 180 |
| 0.01 | 161 | 230 | 299 | 459 | 689 | 918 |
| 0.001 | 1626 | 2326 | 3026 | 4652 | 6977 | 9303 |
| 0.0001 | 17475 | 25000 | 32526 | 55000 | 75000 | 100000 |
Seringkali, kriteria untuk menggabungkan (jumlah cluster) adalah perubahan fungsi yang sesuai. Misalnya, jumlah deviasi kuadrat: 
Proses pengelompokan di sini harus sesuai dengan peningkatan minimum yang konsisten pada nilai kriteria E. Adanya lonjakan tajam pada nilai E dapat diartikan sebagai ciri dari jumlah cluster yang secara objektif ada pada populasi yang diteliti.
Jadi, cara kedua untuk menentukan jumlah cluster terbaik adalah dengan mengidentifikasi lompatan yang ditentukan oleh transisi fase dari keadaan objek yang berpasangan kuat ke keadaan objek yang berpasangan lemah.
1.6 Dendogram.
Metode paling terkenal untuk merepresentasikan matriks jarak atau kesamaan didasarkan pada gagasan dendogram atau diagram pohon. Dendogram dapat didefinisikan sebagai representasi grafis dari hasil proses clustering sekuensial, yang dilakukan dalam matriks jarak. Dengan bantuan dendogram, dimungkinkan untuk menggambarkan prosedur pengelompokan secara grafis atau geometris, asalkan prosedur ini hanya beroperasi dengan elemen matriks jarak atau kesamaan.
Ada banyak cara untuk membuat dendrogram. Pada dendrogram, objek letaknya vertikal di sebelah kiri, hasil clusteringnya ada di sebelah kanan. Nilai jarak atau kesamaan yang sesuai dengan struktur cluster baru ditampilkan sepanjang garis lurus horizontal di atas dendrogram.
Gambar 1 menunjukkan salah satu contoh dendogram. Gambar 1 sesuai dengan kasus enam objek (n=6) dan k karakteristik (fitur). Objek A dan C merupakan objek yang paling dekat sehingga digabungkan menjadi satu cluster pada tingkat kedekatan sebesar 0,9. Objek D dan E digabungkan pada level 0,8. Sekarang kami memiliki 4 cluster:
Jenis dendogram bergantung pada pilihan ukuran kemiripan atau jarak antara objek dengan cluster serta metode clustering. Hal yang terpenting adalah pemilihan ukuran kemiripan atau ukuran jarak antara suatu objek dengan suatu cluster.
Jumlah algoritma analisis cluster terlalu besar. Semuanya dapat dibagi menjadi hierarki dan non-hierarki.
Algoritme hierarki dikaitkan dengan konstruksi dendogram dan dibagi menjadi:
a) aglomeratif, ditandai dengan kombinasi elemen awal yang konsisten dan penurunan jumlah cluster;
b) habis dibagi (divisible), dimana jumlah cluster bertambah, dimulai dari satu, sehingga terbentuklah barisan kelompok yang membelah.
Algoritma analisis cluster saat ini memiliki implementasi perangkat lunak yang baik yang memungkinkan penyelesaian masalah dengan dimensi tertinggi.
1.7 Data
Analisis cluster dapat diterapkan pada data interval, frekuensi, data biner. Penting agar variabel-variabel tersebut berubah pada skala yang sebanding.
Heterogenitas unit pengukuran dan ketidakmungkinan ekspresi yang masuk akal dari nilai-nilai berbagai indikator pada skala yang sama mengarah pada fakta bahwa jarak antar titik, yang mencerminkan posisi objek dalam ruang propertinya, ternyata bergantung pada skala yang dipilih secara sewenang-wenang. Untuk menghilangkan heterogenitas pengukuran data awal, semua nilainya dinormalisasi terlebih dahulu, yaitu. dinyatakan melalui rasio nilai-nilai tersebut dengan nilai tertentu yang mencerminkan sifat-sifat tertentu dari indikator tersebut. Normalisasi data awal untuk analisis klaster terkadang dilakukan dengan membagi nilai awal dengan standar deviasi dari indikator yang bersangkutan. Cara lain adalah dengan menghitung apa yang disebut kontribusi standar. Ini juga disebut kontribusi Z.
Kontribusi z menunjukkan berapa banyak deviasi standar yang dipisahkan oleh observasi tertentu dari mean:
Dimana xi adalah nilai pengamatan, mean, S adalah simpangan baku.
Rata-rata kontribusi Z adalah nol dan deviasi standarnya adalah 1.
Standardisasi memungkinkan perbandingan pengamatan dari distribusi yang berbeda. Jika distribusi suatu variabel normal (atau mendekati normal) dan mean serta varians diketahui atau diperkirakan dari sampel yang besar, maka kontribusi Z dari suatu observasi memberikan informasi yang lebih spesifik tentang lokasinya.
Perhatikan bahwa metode normalisasi berarti pengakuan semua fitur sebagai setara dalam hal menjelaskan kesamaan objek yang dipertimbangkan. Telah dicatat bahwa dalam kaitannya dengan perekonomian, pengakuan terhadap kesetaraan berbagai indikator tampaknya tidak selalu dapat dibenarkan. Seiring dengan normalisasi, diharapkan untuk memberikan bobot pada masing-masing indikator yang mencerminkan signifikansinya dalam rangka menentukan persamaan dan perbedaan antar objek.
Dalam situasi ini, kita harus menggunakan metode penentuan bobot indikator individu - survei para ahli. Misalnya, ketika memecahkan masalah klasifikasi negara-negara menurut tingkat pembangunan ekonomi, kami menggunakan hasil survei terhadap 40 pakar terkemuka Moskow tentang masalah negara-negara maju pada skala sepuluh poin:
indikator umum pembangunan sosial-ekonomi - 9 poin;
indikator distribusi sektoral dari populasi yang bekerja - 7 poin;
indikator prevalensi tenaga kerja upahan - 6 poin;
indikator yang mencirikan elemen manusia dari kekuatan produktif - 6 poin;
indikator pengembangan kekuatan produktif material - 8 poin;
indikator belanja publik - 4 poin;
indikator "militer-ekonomi" - 3 poin;
indikator sosio-demografis - 4 poin.
Perkiraan para ahli relatif stabil.
Penilaian para ahli memberikan dasar yang diketahui untuk menentukan pentingnya indikator yang termasuk dalam kelompok indikator tertentu. Mengalikan nilai indikator yang dinormalisasi dengan koefisien yang sesuai dengan skor penilaian rata-rata memungkinkan untuk menghitung jarak antara titik-titik yang mencerminkan posisi negara-negara dalam ruang multidimensi, dengan mempertimbangkan bobot fitur-fiturnya yang tidak sama.
Seringkali, ketika memecahkan masalah seperti itu, bukan hanya satu, tetapi dua perhitungan yang digunakan: yang pertama, di mana semua tanda dianggap setara, yang kedua, di mana mereka diberi bobot yang berbeda sesuai dengan nilai rata-rata perkiraan ahli.
1.8. Penerapan analisis klaster.
Mari kita pertimbangkan beberapa penerapan analisis klaster.
Pembagian negara menjadi kelompok-kelompok sesuai dengan tingkat perkembangannya.
65 negara dipelajari menurut 31 indikator (pendapatan nasional per kapita, jumlah penduduk yang bekerja di industri dalam %, tabungan per kapita, jumlah penduduk yang bekerja di bidang pertanian dalam %, rata-rata harapan hidup, jumlah mobil per 1 ribu penduduk, jumlah angkatan bersenjata per 1 juta penduduk, pangsa PDB dalam industri dalam%, pangsa PDB dalam pertanian dalam%, dll.)
Masing-masing negara dalam pertimbangan ini bertindak sebagai objek yang dicirikan oleh nilai-nilai tertentu dari 31 indikator. Oleh karena itu, mereka dapat direpresentasikan sebagai titik-titik dalam ruang 31 dimensi. Ruang yang demikian biasa disebut ruang milik benda yang diteliti. Perbandingan jarak antara titik-titik ini akan mencerminkan tingkat kedekatan negara-negara yang dipertimbangkan, kesamaannya satu sama lain. Arti sosio-ekonomi dari pemahaman kesamaan ini berarti bahwa negara-negara dianggap semakin mirip, semakin kecil perbedaan antara indikator-indikator yang sama yang menggambarkannya.
Langkah pertama dalam analisis tersebut adalah mengidentifikasi pasangan perekonomian nasional yang termasuk dalam matriks kesamaan, yang jarak antar negaranya paling kecil. Ini jelas merupakan perekonomian yang paling mirip dan serupa. Dalam pertimbangan berikut ini, kedua negara ini dianggap sebagai satu kelompok, satu cluster. Oleh karena itu, matriks asli diubah sehingga elemen-elemennya adalah jarak antara semua kemungkinan pasangan bukan 65, tetapi 64 objek - 63 ekonomi dan cluster yang baru ditransformasikan - gabungan bersyarat dari dua negara yang paling mirip. Baris dan kolom yang sesuai dengan jarak dari sepasang negara yang termasuk dalam gabungan ke negara lain dibuang dari matriks kesamaan asli, tetapi ditambahkan baris dan kolom yang berisi jarak antara cluster yang diperoleh gabungan dan negara lain.
Jarak antara klaster yang baru diperoleh dan negara-negara tersebut diasumsikan sama dengan rata-rata jarak antara klaster tersebut dan kedua negara yang membentuk klaster baru. Dengan kata lain, gabungan kelompok negara diperlakukan secara keseluruhan dengan karakteristik yang kira-kira sama dengan rata-rata karakteristik negara-negara penyusunnya.
Langkah analisis kedua adalah mempertimbangkan matriks yang ditransformasikan dengan cara ini dengan 64 baris dan kolom. Sekali lagi, sepasang perekonomian diidentifikasi, yang jarak antara keduanya paling tidak penting, dan keduanya, seperti dalam kasus pertama, disatukan. Dalam hal ini, jarak terkecil dapat terjadi antara sepasang negara, dan antara negara mana pun dan gabungan negara-negara yang diperoleh pada tahap sebelumnya.
Prosedur lebih lanjut serupa dengan yang dijelaskan di atas: pada setiap tahap, matriks diubah sehingga dua kolom dan dua baris yang berisi jarak ke objek (pasangan negara atau asosiasi - cluster) yang disatukan pada tahap sebelumnya dikeluarkan darinya. ; baris dan kolom yang dikecualikan diganti dengan kolom dan baris yang berisi jarak dari gabungan baru ke fitur lainnya; selanjutnya, dalam matriks yang dimodifikasi, sepasang objek terdekat terungkap. Analisis berlanjut hingga matriksnya benar-benar habis (yaitu, hingga seluruh negara disatukan). Hasil umum dari analisis matriks dapat direpresentasikan dalam bentuk pohon kesamaan (dendogram), serupa dengan yang dijelaskan di atas, dengan satu-satunya perbedaan bahwa pohon kesamaan, yang mencerminkan kedekatan relatif dari 65 negara yang kami pertimbangkan, adalah jauh lebih rumit dibandingkan skema yang hanya menampilkan lima perekonomian nasional. Pohon ini mencakup 65 level sesuai dengan jumlah objek yang cocok. Tingkat pertama (bawah) berisi poin yang sesuai dengan masing-masing negara secara terpisah. Keterhubungan kedua titik pada tingkat kedua ini menunjukkan sepasang negara yang paling dekat dalam hal tipe umum perekonomian nasional. Pada tingkat ketiga, rasio pasangan negara yang paling mirip berikutnya dicatat (seperti yang telah disebutkan, baik pasangan negara baru, atau negara baru dan pasangan negara serupa yang sudah teridentifikasi dapat berada dalam rasio ini). Begitu seterusnya hingga tingkat terakhir, di mana semua negara yang diteliti bertindak sebagai satu kesatuan.
Dari hasil penerapan analisis klaster, diperoleh lima kelompok negara berikut:
kelompok Afro-Asia;
kelompok Latino-Asia;
kelompok Latin-Mediterania;
kelompok negara kapitalis maju (tanpa Amerika)
Pengenalan indikator baru di luar 31 indikator yang digunakan di sini, atau penggantiannya dengan indikator lain, tentu saja menyebabkan perubahan pada hasil klasifikasi negara.
2. Pembagian negara menurut kriteria kedekatan budaya.
Seperti yang Anda ketahui, pemasaran harus mempertimbangkan budaya negara (adat istiadat, tradisi, dll).
Kelompok negara berikut diperoleh melalui pengelompokan:
Arab;
Timur Tengah;
Skandinavia;
Berbicara bahasa Jerman;
Berbahasa Inggris;
Eropa Romawi;
Amerika Latin;
Timur Jauh.
3. Pengembangan perkiraan pasar seng.
Analisis klaster memainkan peran penting pada tahap reduksi model ekonomi dan matematis dari konjungtur komoditas, berkontribusi pada fasilitasi dan penyederhanaan prosedur komputasi, memastikan hasil yang diperoleh lebih kompak dengan tetap menjaga akurasi yang diperlukan. Penggunaan analisis klaster memungkinkan untuk membagi seluruh rangkaian awal indikator pasar ke dalam kelompok (cluster) sesuai dengan kriteria yang relevan, sehingga memudahkan pemilihan indikator yang paling representatif.
Analisis klaster banyak digunakan untuk memodelkan kondisi pasar. Dalam praktiknya, sebagian besar tugas peramalan didasarkan pada penggunaan analisis klaster.
Misalnya, tugas mengembangkan prakiraan pasar seng.
Awalnya, 30 indikator utama pasar seng global dipilih:
X1 - waktu
Angka produksi:
X2 - di dunia
X4 - Eropa
X5 - Kanada
X6 - Jepang
X7 - Australia
Indikator konsumsi:
X8 - di dunia
X10 - Eropa
X11 - Kanada
X12 - Jepang
X13 - Australia
Stok produsen seng:
X14 - di dunia
X16 - Eropa
X17 - negara lain
Stok seng konsumen:
X18 - di AS
X19 - di Inggris
X10 - di Jepang
Impor bijih seng dan konsentratnya (ribu ton)
X21 - di AS
X22 - di Jepang
X23 - di Jerman
Ekspor bijih seng dan konsentratnya (ribu ton)
X24 - dari Kanada
X25 - dari Australia
Impor seng (ribu ton)
X26 - di AS
X27 - ke Inggris
X28 - di Jerman
Ekspor seng (ribu ton)
X29 - dari Kanada
X30 - dari Australia
Untuk menentukan ketergantungan tertentu digunakan alat analisis korelasi dan regresi. Hubungan dianalisis berdasarkan matriks koefisien korelasi berpasangan. Di sini hipotesis distribusi normal dari indikator konjungtur yang dianalisis diterima. Jelas bahwa rij bukanlah satu-satunya indikator yang memungkinkan adanya hubungan indikator-indikator yang digunakan. Perlunya penggunaan analisis klaster dalam permasalahan ini karena jumlah indikator yang mempengaruhi harga seng sangat banyak. Terdapat kebutuhan untuk menguranginya karena beberapa alasan berikut:
a) kurangnya data statistik yang lengkap untuk seluruh variabel;
b) komplikasi tajam dari prosedur komputasi ketika sejumlah besar variabel dimasukkan ke dalam model;
c) penggunaan metode analisis regresi yang optimal memerlukan kelebihan jumlah nilai yang diamati dibandingkan jumlah variabel setidaknya 6-8 kali;
d) keinginan untuk menggunakan variabel independen secara statistik dalam model, dll.
Sangat sulit untuk melakukan analisis seperti itu secara langsung pada matriks koefisien korelasi yang relatif besar. Dengan bantuan analisis klaster, seluruh rangkaian variabel pasar dapat dibagi ke dalam kelompok-kelompok sedemikian rupa sehingga elemen-elemen dari setiap klaster berkorelasi kuat satu sama lain, dan perwakilan dari kelompok yang berbeda dicirikan oleh korelasi yang lemah.
Untuk mengatasi masalah ini, salah satu algoritma analisis cluster hierarki aglomeratif diterapkan. Pada setiap langkah, jumlah cluster berkurang satu karena optimalnya, dalam arti tertentu, penyatuan dua kelompok. Kriteria untuk bergabung adalah mengubah fungsi terkait. Sebagai fungsinya, digunakan nilai jumlah simpangan kuadrat yang dihitung dengan rumus berikut:
(j = 1, 2, …, m),
dimana j adalah nomor cluster, n adalah jumlah elemen dalam cluster.
rij - koefisien korelasi berpasangan.
Dengan demikian, proses pengelompokan harus sesuai dengan kenaikan minimum nilai kriteria E secara berurutan.
Pada tahap pertama, array data awal disajikan sebagai satu set yang terdiri dari cluster, yang masing-masing mencakup satu elemen. Proses pengelompokan dimulai dengan penyatuan sepasang cluster, yang menghasilkan peningkatan minimum dalam jumlah deviasi kuadrat. Hal ini memerlukan estimasi jumlah deviasi kuadrat untuk masing-masing kemungkinan gabungan cluster. Pada tahap selanjutnya sudah dipertimbangkan nilai jumlah simpangan kuadrat untuk cluster, dan seterusnya. Proses ini akan dihentikan pada langkah tertentu. Untuk melakukan ini, Anda perlu memantau nilai jumlah deviasi kuadrat. Mengingat urutan peningkatan nilai, seseorang dapat menangkap lompatan (satu atau lebih) dalam dinamikanya, yang dapat diartikan sebagai karakteristik jumlah kelompok yang ada secara “objektif” dalam populasi yang diteliti. Pada contoh di atas, lompatan terjadi ketika jumlah cluster adalah 7 dan 5. Selanjutnya jumlah kelompok tidak boleh dikurangi, karena hal ini menyebabkan penurunan kualitas model. Setelah memperoleh klaster, variabel-variabel yang paling penting dalam arti ekonomi dan paling erat kaitannya dengan kriteria pasar yang dipilih - dalam hal ini, kutipan London Metal Exchange untuk seng - dipilih. Pendekatan ini memungkinkan Anda untuk menyimpan sebagian besar informasi yang terkandung dalam kumpulan indikator awal konjungtur.
