Apakah ada algoritma mirip pohon keputusan untuk pengelompokan tanpa pengawasan?

20

Saya memiliki dataset yang terdiri dari 5 fitur: A, B, C, D, E. Mereka semua adalah nilai numerik. Alih-alih melakukan pengelompokan berbasis kepadatan, apa yang ingin saya lakukan adalah mengelompokkan data dengan cara seperti pohon keputusan.

Pendekatan yang saya maksud adalah sesuatu seperti ini:

Algoritme dapat membagi data ke dalam kelompok awal X berdasarkan fitur C, yaitu kelompok X mungkin memiliki nilai C kecil, sedang, C besar dan nilai C sangat besar dll. Selanjutnya, di bawah masing-masing simpul kelompok X, algoritma selanjutnya membagi data ke dalam cluster Y berdasarkan fitur A. Algoritma berlanjut sampai semua fitur digunakan.

Algoritma yang saya jelaskan di atas seperti algoritma pohon keputusan. Tapi saya membutuhkannya untuk pengelompokan tanpa pengawasan, bukan klasifikasi terawasi.

Pertanyaan saya adalah sebagai berikut:

  1. Apakah algoritma seperti itu sudah ada? Apa nama yang tepat untuk algoritma tersebut
  2. Apakah ada paket / pustaka R / python yang memiliki implementasi algoritma semacam ini?
nan
sumber
3
But I need it for unsupervised clustering, instead of supervised classificationFrasa kunci ini saja terlalu singkat dan tidak menjelaskan dengan jelas apa yang Anda inginkan. Di atas itu Anda menggambarkan apa yang menurut saya merupakan pohon keputusan. Dapatkah Anda sekarang memberikan bagian yang serupa tentang algo yang Anda inginkan?
ttnphns
1
@ttnphns Hai, seperti yang Anda tahu, pohon keputusan adalah metode yang diawasi. Anda memberi label setiap vektor fitur sebagai Class1 atau Class2. Algoritma menentukan ambang batas untuk setiap fitur berdasarkan label yang dikenal. Namun, saya menghadapi masalah pengelompokan. Saya tidak tahu label yang benar dari setiap vektor fitur. Saya ingin menemukan algoritma yang secara otomatis menentukan ambang batas untuk setiap fitur untuk membangun pohon. Dengan cara ini, pengelompokan yang dihasilkan dapat dengan mudah diartikan sebagai misalnya Cluster 1: Tinggi A-Rendah B- Sedang C- Tinggi D - Rendah E, Cluster 2 sebagai Rendah A - Tinggi B- Sedang C- Sedang D - Rendah E.
nan
Tidak cukup mengerti Anda. Ambil CHAIDpohon, misalnya. Anda harus memilih variabel dependen. Biarlah A. Algoritme memilih antara B, C, D, E variabel yang paling berkorelasi dengan A dan binn bahwa variabel (katakanlah, itu, prediktor, menjadi D) menjadi dua atau lebih kategori "optimal" - sehingga korelasi (antara variabel D yang dikategorikan dan variabel A dimaksimalkan. Katakanlah, ia meninggalkan 3 grup, D1, D2, D3. Selanjutnya, prosedur yang sama diulang dalam setiap kategori (grup) D secara terpisah, dan prediktor terbaik di antara B, C , E dicari di bawah binning itu. Dll. Apa sebenarnya yang tidak cocok untuk Anda di sini?
ttnphns
2
@ttnphns Saya baru saja menemukan makalah ini, saya pikir mereka melakukan apa yang saya maksud. ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/…
nan
1
@ apakah Anda sudah menemukan implementasi pohon seperti itu? Mereka tidak menyediakan tautan ke kode di artikel
Alleo

Jawaban:

12

Anda mungkin ingin mempertimbangkan pendekatan berikut:

  • Gunakan algoritma pengelompokan apa pun yang memadai untuk data Anda
  • Asumsikan cluster yang dihasilkan adalah kelas
  • Latih pohon keputusan di kelompok

Ini akan memungkinkan Anda untuk mencoba algoritma pengelompokan yang berbeda, tetapi Anda akan mendapatkan pendekatan pohon keputusan untuk masing-masing algoritma tersebut.

Anony-Mousse -Reinstate Monica
sumber
1
setuju bahwa ini "tepat", tetapi orang tentu saja harus selalu ingat bahwa membuat label dari algoritma pengelompokan bukan fitur "aktual" dari pengamatan. Bergantung pada kualitas & jenis pengelompokan, bias yang diperkenalkan akan ada pada tingkat yang lebih besar atau lebih kecil.
NiuBiBang
Bisakah Anda mengarahkan saya ke makalah yang membahas strategi ini?
nCessity
2

Makalah pertama yang muncul dalam pikiran adalah ini: Clustering Via Decision Tree Konstruksi https://pdfs.semanticscholar.org/8996/148e8f0b34308e2d22f78ff89bf1f038d1d6.pdf

Seperti yang disebutkan lain, "hierarkis" (atas ke bawah) dan "aglomerasi hierarkis" (bawah ke atas) adalah teknik yang dikenal baik yang dirancang menggunakan pohon untuk melakukan pengelompokan. Scipy punya ini.

Jika Anda setuju dengan kode khusus karena saya tidak tahu ada perpustakaan, ada dua teknik yang bisa saya rekomendasikan. Berhati-hatilah karena ini bukan pengelompokan secara teknis karena mekanisme yang mereka andalkan. Anda mungkin menyebut pengelompokan semu ini.

1) Dibimbing: Ini agak mirip dengan kertas (layak dibaca). Bangun model pohon keputusan tunggal untuk mempelajari beberapa target (Anda memutuskan apa yang masuk akal). Targetnya bisa berupa kolom yang dibuat secara acak (membutuhkan pengulangan dan mengevaluasi iterasi yang terbaik, lihat di bawah). Tetapkan setiap path lengkap pohon sebagai "cluster" karena titik-titik yang jatuh melalui serangkaian cabang secara teknis serupa dalam hal target. Ini hanya berfungsi dengan baik pada beberapa masalah, tetapi efisien dalam skala besar. Anda berakhir dengan K cluster (lihat di bawah).

2) Semisupervised (semacam tidak diawasi, tetapi diawasi secara mekanis), menggunakan # 1: Anda dapat mencoba membangun pohon untuk memprediksi kolom dengan pola tinggalkan satu. yaitu jika skemanya adalah [A, B, C], buat 3 model [A, B] -> C, [A, C] -> B, [B, C] -> A. Anda mendapatkan kelompok KN (lihat di bawah). N = len (skema). Jika beberapa fitur ini tidak menarik atau tidak seimbang (dalam hal kategori), jangan gunakan sebagai target.

Rangkuman: Model akan memilih fitur berdasarkan informasi atau kemurnian dan kluster akan didasarkan hanya pada beberapa fitur daripada semua. Tidak ada konsep jarak dalam kelompok-kelompok ini, tetapi Anda tentu bisa merancang satu berdasarkan pusat.

Kelebihan: mudah dimengerti dan dijelaskan, pelatihan cepat dan inferensi, bekerja dengan baik dengan beberapa fitur kuat, bekerja dengan kategori. Ketika fitur Anda pada dasarnya heterogen dan Anda memiliki banyak fitur, Anda tidak perlu menghabiskan banyak waktu untuk memutuskan mana yang akan digunakan dalam fungsi jarak.

Cons: tidak standar, harus ditulis, bias naif, collinearity dengan target menyebabkan hasil yang buruk, memiliki 1000 fitur yang sama pentingnya tidak akan bekerja dengan baik (KMeans dengan jarak Euclidean lebih baik di sini).

Berapa banyak cluster yang Anda dapatkan? Anda harus, benar-benar harus membatasi model DT agar tidak tumbuh terlalu banyak. mis. Tetapkan sampel min per daun, simpul daun maks (lebih disukai), atau kedalaman maks. Secara opsional, atur kemurnian atau batasan entropi. Anda harus memeriksa berapa banyak klaster yang diberikan dan mengevaluasi jika metode ini lebih baik daripada pengelompokan nyata.

Apakah teknik dan parameternya bekerja dengan baik untuk Anda? Mana yang terbaik? Untuk mengetahuinya, Anda perlu melakukan evaluasi klaster: Metrik kinerja untuk mengevaluasi pembelajaran tanpa pengawasan

ldmtwo
sumber
2

Apa yang Anda cari adalah algoritma pengelompokan yang memecah belah.

Algoritma yang paling umum adalah aglomeratif, yang mengelompokkan data secara bottom-up - setiap pengamatan dimulai saat cluster dan clusternya sendiri digabungkan. Cluster yang memecah belah adalah top down - pengamatan dimulai dalam satu cluster yang secara bertahap dibagi.

Keinginan untuk terlihat seperti pohon keputusan membatasi pilihan karena sebagian besar algoritma beroperasi pada jarak dalam ruang data yang lengkap daripada memisahkan satu variabel pada suatu waktu.

DIANA adalah satu-satunya algoritma pengelompokan memecah belah yang saya tahu, dan saya pikir itu terstruktur seperti pohon keputusan. Saya akan kagum jika tidak ada orang lain di luar sana.

Anda bisa menggunakan algoritma pohon keputusan standar jika Anda memodifikasi aturan pemisahan ke metrik yang tidak mempertimbangkan variabel dependen yang ditentukan, melainkan menggunakan metrik kebaikan klaster.

KirkD_CO
sumber
0

Satu ide untuk dipertimbangkan adalah anggaplah Anda memiliki fitur k dan n poin. Anda dapat membangun pohon acak menggunakan fitur (k-1) dan 1 fitur sebagai variabel dependen. Y. Anda dapat memilih ketinggian h dan setelah itu Anda akan memiliki titik data di root. Anda dapat memilih jenis pohon yang berbeda. Hanya pemikiran saja.

Ankit Swarnkar
sumber