Apa yang diketahui, aplikasi praktis teori chaos yang ada dalam penambangan data?

13

Sambil membaca dengan santai beberapa karya pasar massal tentang teori chaos selama beberapa tahun terakhir, saya mulai bertanya-tanya bagaimana berbagai aspeknya dapat diterapkan pada data mining dan bidang terkait, seperti jaring saraf, pengenalan pola, manajemen ketidakpastian, dll. Sampai saat ini, saya Saya telah menemukan begitu sedikit contoh aplikasi seperti itu dalam penelitian yang diterbitkan sehingga saya bertanya-tanya apakah a) mereka benar-benar telah dipraktekkan dalam percobaan dan proyek yang diketahui dan dipublikasikan dan b) jika tidak, mengapa mereka menggunakan sangat sedikit dalam hal yang saling terkait ini ladang?

Sebagian besar diskusi tentang teori chaos yang saya lihat sampai saat ini berkisar pada aplikasi ilmiah yang sepenuhnya berguna, tetapi tidak ada hubungannya dengan penambangan data dan bidang terkait seperti pengenalan pola; salah satu contoh arketipikal adalah Masalah Tiga-Tubuh dari fisika. Saya ingin melupakan diskusi tentang aplikasi ilmiah biasa seperti ini dan membatasi pertanyaan semata-mata untuk aplikasi yang jelas relevan dengan data mining dan bidang terkait, yang tampaknya sedikit dan jauh di antara literatur. Daftar aplikasi potensial di bawah ini dapat digunakan sebagai titik awal pencarian untuk penelitian yang dipublikasikan, tetapi saya hanya tertarik pada aplikasi yang sebenarnya telah dipraktikkan, jika ada. Apa yang saya cari adalah implementasi yang dikenal dari teori chaos untuk data mining, bertentangan dengan daftar aplikasi potensial, yang jauh lebih luas. Berikut ini adalah contoh kecil dari ide-ide luar biasa untuk aplikasi penambangan data yang terjadi pada saya saat membaca; mungkin tidak ada dari mereka yang pragmatis, mungkin beberapa digunakan secara praktis saat kita berbicara, tetapi menuruti ketentuan yang belum saya kenal:

  1. Mengidentifikasi struktur yang mirip dengan diri sendiri dalam pengenalan pola, seperti yang dilakukan Mandelbrot secara praktis dalam kasus semburan kesalahan pada saluran telepon analog beberapa dekade yang lalu.
  2. Menghadapi Konstan Feigenbaum dalam hasil penambangan (mungkin dengan cara yang mirip dengan bagaimana para ahli teori dikejutkan untuk melihat Persamaan Maxwell muncul di tempat-tempat tak terduga selama penelitian mereka).
  3. Mengidentifikasi kedalaman bit optimal untuk bobot neural net dan berbagai uji penambangan. Saya bertanya-tanya tentang hal ini karena skala numerik yang semakin kecil di mana kepekaan terhadap kondisi awal ikut berperan, yang sebagian bertanggung jawab atas ketidakpastian fungsi terkait kekacauan.
  4. Menggunakan gagasan dimensi fraksional dengan cara lain tidak selalu terkait dengan keingintahuan fraktal yang menarik, seperti Menger Sponges, Koch Curves atau Sierpinski Carpets. Mungkin konsep tersebut dapat diterapkan pada dimensi model penambangan dengan cara yang menguntungkan, dengan memperlakukannya sebagai pecahan?
  5. Turunkan hukum kekuasaan seperti yang berlaku dalam fraktal.
  6. Karena fungsi yang ditemui dalam fraktal adalah nonlinier, saya ingin tahu apakah ada beberapa aplikasi praktis untuk regresi nonlinier.
  7. Teori chaos memiliki beberapa hubungan tangensial (dan terkadang dilebih-lebihkan) dengan entropi, jadi saya bertanya-tanya apakah ada beberapa cara untuk menghitung Entropi Shannon (atau batasannya dan kerabatnya) dari fungsi yang digunakan dalam teori chaos, atau sebaliknya.
  8. Mengidentifikasi perilaku penggandaan periode dalam data.
  9. Mengidentifikasi struktur optimal untuk jaring saraf dengan cerdas memilih yang paling mungkin "mengatur diri sendiri" dengan cara yang bermanfaat.
  10. Kekacauan dan fraktal dll juga secara tangensial terkait dengan kompleksitas komputasi, jadi saya bertanya-tanya apakah kompleksitas dapat digunakan untuk mengidentifikasi struktur yang kacau, atau sebaliknya.
  11. Saya pertama kali mendengar tentang eksponen Lyapunov dalam hal teori chaos dan telah memperhatikannya beberapa kali sejak itu dalam resep untuk jaring saraf khusus dan diskusi tentang entropi.

Mungkin ada lusinan hubungan lain yang belum saya sebutkan di sini; semua ini keluar dari kepala saya. Saya tidak terlalu tertarik pada jawaban spesifik untuk spekulasi khusus ini, tetapi saya hanya membuangnya di luar sana sebagai contoh jenis aplikasi yang mungkin ada di alam liar. Saya ingin melihat balasan yang memiliki contoh-contoh penelitian saat ini dan implementasi ide-ide seperti ini, selama aplikasi secara khusus berlaku untuk data mining.

Mungkin ada implementasi lain yang masih belum saya sadari, bahkan di area yang lebih saya kenal (seperti teori informasi, set fuzzy, dan jaring saraf) dan lainnya yang saya punya kompetensi lebih sedikit, seperti regresi, jadi lebih banyak input sama-sama Tujuan praktis saya di sini adalah untuk menentukan apakah atau tidak untuk berinvestasi lebih banyak dalam belajar tentang aspek-aspek tertentu dari teori chaos, yang saya akan pakai di belakang kompor jika saya tidak dapat menemukan utilitas yang jelas.

Saya melakukan pencarian CrossValidated tetapi tidak melihat topik yang secara langsung membahas aplikasi utilitarian dari teori chaos untuk data mining dll. Yang paling dekat saya bisa datang adalah teori Chaos thread , pemodelan persamaan-bebas dan statistik non-parametrik , yang berkaitan dengan subset tertentu.

SQLServerSteve
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
whuber

Jawaban:

7

Penambangan data (DM) sebagai pendekatan praktis tampaknya hampir saling melengkapi dengan pendekatan pemodelan matematika (MM), dan bahkan bertentangan dengan teori chaos (CT). Pertama saya akan berbicara tentang DM dan MM umum, kemudian fokus pada CT.

Pemodelan matematika

Dalam pemodelan ekonomi, DM hingga saat ini dianggap hampir tabu, peretasan untuk mencari korelasi daripada belajar tentang sebab-akibat dan hubungan, lihat posting ini di blog SAS. Sikapnya berubah, tetapi ada banyak jebakan terkait dengan hubungan palsu , pengerukan data , peretasan dll.

Dalam beberapa kasus, DM tampaknya menjadi pendekatan yang sah bahkan dalam bidang dengan praktik MM yang telah mapan. Sebagai contoh, DM dapat digunakan untuk mencari interaksi partikel dalam eksperimen fisik yang menghasilkan banyak data, pikirkan penghancur partikel. Dalam hal ini fisikawan mungkin memiliki gagasan tentang bagaimana bentuk partikel, dan mencari pola dalam dataset.

Teori Kekacauan

Sistem chaotic mungkin sangat tahan terhadap analisis dengan teknik DM. Pertimbangkan metode linear congruental ( LCG ) yang biasa digunakan dalam generator nomor psudo-acak yang umum . Ini pada dasarnya adalah sistem yang kacau . Itulah mengapa ini digunakan untuk angka acak "palsu". Generator yang baik tidak dapat dibedakan dari urutan nomor acak. Ini berarti bahwa Anda tidak akan dapat menentukan apakah itu acak atau tidak dengan menggunakan metode statistik. Saya akan menyertakan data mining di sini juga. Cobalah untuk menemukan pola dalam urutan RAND () yang dihasilkan dengan penambangan data! Namun, sekali lagi ini adalah urutan yang sepenuhnya deterministik seperti yang Anda tahu, dan persamaannya juga sangat sederhana.

Teori chaos bukan tentang mencari pola kesamaan secara acak. Teori chaos melibatkan pembelajaran tentang proses dan hubungan dinamis sedemikian rupa sehingga gangguan kecil menguat dalam sistem menciptakan perilaku yang tidak stabil, sementara entah bagaimana dalam kekacauan ini pola stabil muncul. Semua hal keren ini terjadi karena properti persamaan itu sendiri. Para peneliti kemudian mempelajari persamaan ini dan sistem mereka. Ini sangat berbeda dari pola pikir dari penggalian data yang diterapkan.

Misalnya, Anda dapat berbicara tentang pola kesamaan diri saat mempelajari sistem yang kacau, dan perhatikan bahwa penambang data berbicara tentang pencarian pola juga. Namun, ini menangani konsep "pola" yang sangat berbeda. Sistem chaotic akan menghasilkan pola-pola ini dari persamaan. Mereka mungkin mencoba untuk membuat set persamaan mereka dengan mengamati sistem aktual dll, tetapi mereka selalu berurusan dengan persamaan di beberapa titik. Penambang data akan datang dari sisi lain, dan tidak mengetahui atau menebak banyak tentang struktur internal sistem, akan mencoba mencari pola. Saya tidak berpikir bahwa kedua kelompok ini pernah melihat sistem aktual atau kumpulan data yang sama.

Contoh lain adalah peta logistik paling sederhana yang bekerja dengan Feigenbaum untuk menciptakan periode bifurkasi penggandaannya yang terkenal.

masukkan deskripsi gambar di sini

Persamaannya sangat sederhana:

xn+1=rxn(1-xn)
Namun, saya tidak melihat bagaimana orang akan menemukannya dengan teknik data mining.

Aksakal
sumber
(+1). Saya akan menambahkan bahwa ketika Anda dapat menentukan dengan tepat persamaan yang menentukan perilaku sistem yang kacau, Anda dapat memprediksi perilaku itu sepenuhnya, atau mendekati itu. Kami jarang dapat memperoleh R-squared even> .5 dalam penambangan data / pemodelan prediktif.
rolando2
+1 ini jelas melengkapi jawaban yang telah saya siapkan untuk sementara waktu, yang akan saya posting dalam beberapa jam.
SQLServerSteve
4

Hal paling aneh yang saya temukan ketika membaca tentang teori chaos untuk menjawab pertanyaan ini adalah kelangkaan penelitian yang dipublikasikan yang mengejutkan di mana penambangan data dan kerabatnya memanfaatkan teori chaos. Ini terlepas dari upaya bersama untuk menemukan mereka, dengan berkonsultasi dengan sumber-sumber seperti Teori Kekacauan Diterapkan ABambel AB: Paradigma untuk Kompleksitas dan Alligood, dkk. Kekacauan: Pengantar Sistem Dinamik (yang terakhir sangat berguna sebagai buku sumber untuk topik ini) dan merampok bibliografi mereka. Setelah semua itu, saya hanya membuat satu studi yang mungkin memenuhi syarat dan saya harus meregangkan batasan "data mining" hanya untuk memasukkan kasus tepi ini: sebuah tim di University of Texas melakukan penelitian tentang reaksi Belousov-Zhabotinsky (BZ) (yang sudah diketahui rentan terhadap aperiodisitas) secara tidak sengaja menemukan perbedaan dalam asam malonat yang digunakan dalam percobaan mereka karena pola kacau, mendorong mereka untuk mencari yang baru pemasok. [1] Mungkin ada yang lain - saya bukan spesialis dalam teori chaos dan hampir tidak bisa memberikan evaluasi literatur yang lengkap - tetapi tidak proporsional dengan penggunaan ilmiah biasa seperti Masalah Tiga-Tubuh dari fisika tidak akan banyak berubah jika kita menyebutkan semuanya. Bahkan, untuk sementara ketika pertanyaan ini ditutup, Saya mempertimbangkan untuk menulis ulang dengan judul "Mengapa ada Beberapa Implementasi Teori Kekacauan dalam Penambangan Data dan Bidang Terkait?" Ini tidak sesuai dengan sentimen yang tidak jelas namun tersebar luas bahwa seharusnya ada banyak aplikasi dalam penambangan data dan bidang terkait, seperti jaring saraf, pengenalan pola, manajemen ketidakpastian, set fuzzy, dll.; Lagi pula, teori chaos juga merupakan topik paling mutakhir dengan banyak aplikasi berguna. Saya harus berpikir panjang dan keras tentang di mana tepatnya batas antara bidang-bidang ini terletak untuk memahami mengapa pencarian saya tidak membuahkan hasil dan kesan saya salah.

Jawaban; tldr

Penjelasan singkat untuk ketidakseimbangan yang mencolok ini dalam jumlah studi dan penyimpangan dari harapan dapat dikaitkan dengan fakta bahwa teori chaos dan data mining dll menjawab dua kelas pertanyaan yang terpisah; dikotomi tajam di antara mereka jelas sekali ditunjukkan, namun begitu mendasar sehingga tidak diperhatikan, seperti melihat hidung sendiri. Mungkin ada beberapa pembenaran untuk keyakinan bahwa kebaruan relatif teori chaos dan bidang-bidang seperti data mining menjelaskan beberapa kelangkaan implementasi, tetapi kita dapat mengharapkan ketidakseimbangan relatif untuk bertahan bahkan ketika bidang ini matang karena mereka hanya membahas sisi berbeda dari koin yang sama. Hampir semua implementasi sampai saat ini telah dalam studi fungsi yang dikenal dengan output yang jelas yang terjadi untuk menunjukkan beberapa penyimpangan kacau membingungkan, sedangkan penambangan data dan teknik individu seperti jaring saraf dan pohon keputusan semuanya melibatkan penentuan fungsi yang tidak diketahui atau didefinisikan dengan buruk. Bidang terkait seperti pengenalan pola dan himpunan fuzzy juga dapat dilihat sebagai organisasi dari hasil fungsi yang juga sering tidak diketahui atau tidak didefinisikan dengan baik, ketika sarana organisasi itu tidak mudah terlihat juga. Ini menciptakan jurang praktis yang tidak dapat diatasi yang hanya dapat dilintasi dalam keadaan langka tertentu - tetapi bahkan ini dapat dikelompokkan bersama di bawah rubrik kasus penggunaan tunggal: mencegah gangguan aperiodik dengan algoritma penambangan data. Bidang terkait seperti pengenalan pola dan himpunan fuzzy juga dapat dilihat sebagai organisasi dari hasil fungsi yang juga sering tidak diketahui atau tidak didefinisikan dengan baik, ketika sarana organisasi itu tidak mudah terlihat juga. Ini menciptakan jurang praktis yang tidak dapat diatasi yang hanya dapat dilintasi dalam keadaan langka tertentu - tetapi bahkan ini dapat dikelompokkan bersama di bawah rubrik kasus penggunaan tunggal: mencegah gangguan aperiodik dengan algoritma penambangan data. Bidang terkait seperti pengenalan pola dan himpunan fuzzy juga dapat dilihat sebagai organisasi dari hasil fungsi yang juga sering tidak diketahui atau tidak didefinisikan dengan baik, ketika sarana organisasi itu tidak mudah terlihat juga. Ini menciptakan jurang praktis yang tidak dapat diatasi yang hanya dapat dilintasi dalam keadaan langka tertentu - tetapi bahkan ini dapat dikelompokkan bersama di bawah rubrik kasus penggunaan tunggal: mencegah gangguan aperiodik dengan algoritma penambangan data.

Ketidakcocokan dengan Workflow Ilmu Chaos

Alur kerja khas dalam "ilmu chaos" adalah untuk melakukan analisis komputasi dari output dari fungsi yang diketahui, sering bersama dengan alat bantu visual dari ruang fase, seperti diagram bifurkasi, peta Hénon, bagian Poincaré, diagram fase dan lintasan fase. Fakta bahwa para peneliti bergantung pada eksperimen komputasi menggambarkan betapa sulitnya efek kacau untuk ditemukan; itu bukan sesuatu yang biasanya dapat Anda tentukan dengan pena dan kertas. Mereka juga terjadi secara eksklusif dalam fungsi nonlinier. Alur kerja ini tidak layak kecuali kita memiliki fungsi yang diketahui untuk dikerjakan. Penambangan data dapat menghasilkan persamaan regresi, fungsi fuzzy, dan sejenisnya, tetapi semuanya memiliki batasan yang sama: semuanya hanya perkiraan umum, dengan jendela kesalahan yang jauh lebih luas. Sebaliknya, fungsi yang diketahui tunduk pada kekacauan relatif jarang terjadi, seperti rentang input yang menghasilkan pola kacau, sehingga tingkat spesifisitas yang tinggi diperlukan bahkan untuk menguji efek kacau. Setiap penarik aneh hadir dalam ruang fase fungsi yang tidak diketahui pasti akan bergeser atau menghilang sama sekali ketika definisi dan input mereka berubah, sangat menyulitkan prosedur deteksi yang digariskan oleh penulis seperti Alligood, et al.

Kekacauan sebagai Kontaminan dalam Hasil Penambangan Data

Bahkan, hubungan data mining dan kerabatnya dengan teori chaos praktis bertentangan. Ini benar-benar benar jika kita melihat cryptanalysis secara luas sebagai bentuk spesifik dari penambangan data, mengingat bahwa saya telah menjalankan setidaknya satu makalah penelitian tentang meningkatkan kekacauan dalam skema enkripsi (saya tidak dapat menemukan kutipan pada saat ini, tetapi dapat berburu itu atas permintaan). Bagi seorang penambang data, kehadiran kekacauan biasanya merupakan hal yang buruk, karena rentang nilai yang tampaknya tidak masuk akal yang dihasilkannya dapat sangat menyulitkan proses yang sulit untuk memperkirakan fungsi yang tidak diketahui. Penggunaan yang paling umum untuk kekacauan dalam penambangan data dan bidang terkait adalah untuk mengesampingkannya, yang tidak berarti prestasi. Jika ada efek kacau tetapi tidak terdeteksi, efeknya pada usaha penambangan data mungkin sulit diatasi. Pikirkan betapa mudahnya jaringan saraf biasa atau pohon keputusan dapat mengalahkan hasil yang tampaknya tidak masuk akal dari penarik yang kacau, atau bagaimana lonjakan tiba-tiba dalam nilai input tentu saja dapat mengacaukan analisis regresi dan mungkin dianggap berasal dari sampel buruk atau sumber kesalahan lainnya. Kelangkaan efek kacau di antara semua fungsi dan rentang input berarti penyelidikan ke dalamnya akan sangat diprioritaskan oleh para peneliti.

Metode Mendeteksi Kekacauan dalam Hasil Penambangan Data

Langkah-langkah tertentu yang terkait dengan teori chaos berguna dalam mengidentifikasi efek aperiodik, seperti Entropi Kolmogorov dan persyaratan bahwa ruang fase menunjukkan eksponen Lyapunov yang positif. Keduanya ada dalam daftar periksa untuk pendeteksian kekacauan [2] yang disediakan dalam AB iedambel's Applied Chaos Theory, tetapi sebagian besar tidak berguna untuk fungsi yang diperkirakan, seperti eksponen Lyapunov, yang membutuhkan fungsi pasti dengan batas yang diketahui. Meskipun demikian, prosedur umum yang digariskannya mungkin berguna dalam situasi penambangan data; Sasaran Ҫambel pada akhirnya adalah program "kontrol kekacauan," yaitu penghapusan efek aperiodik yang mengganggu. [3] Metode lain seperti menghitung penghitungan kotak dan dimensi korelasi untuk mendeteksi dimensi fraksional yang menyebabkan kekacauan mungkin lebih praktis dalam aplikasi data mining daripada Lyapunov dan lainnya dalam daftar. Tanda lain dari efek kacau adalah adanya pola pengganda periode (atau tiga kali lipat dan lebih) dalam fungsi output, yang sering mendahului perilaku aperiodik (yaitu "kacau") dalam diagram fase.

Membedakan Aplikasi Tangensial

Case use primer ini harus dibedakan dari kelas aplikasi yang terpisah yang hanya berhubungan secara tangensial dengan teori chaos. Pada pemeriksaan lebih dekat, daftar "aplikasi potensial" yang saya berikan dalam pertanyaan saya sebenarnya hampir seluruhnya terdiri dari ide-ide untuk meningkatkan konsep yang bergantung pada teori chaos, tetapi yang dapat diterapkan secara independen dengan tidak adanya perilaku aperiodik (periode penggandaan dikecualikan). Baru-baru ini saya memikirkan penggunaan ceruk potenital baru, menghasilkan perilaku aperiodik untuk mengeluarkan jaring saraf dari minimum lokal, tetapi ini juga akan masuk dalam daftar aplikasi tangensial. Banyak dari mereka ditemukan atau disempurnakan sebagai hasil penelitian ke dalam ilmu kekacauan, tetapi dapat diterapkan ke bidang lain. "Aplikasi tangensial" ini hanya memiliki koneksi fuzzy satu sama lain namun membentuk kelas yang berbeda, dipisahkan oleh batas keras dari kasus penggunaan utama teori chaos dalam penambangan data; yang pertama memanfaatkan aspek-aspek tertentu dari teori chaos tanpa pola aperiodik, sementara yang terakhir dikhususkan untuk mengesampingkan kekacauan sebagai faktor yang menyulitkan dalam hasil penambangan data, mungkin dengan menggunakan prasyarat seperti kepositifan eksponen Lyapunov dan deteksi penggandaan periode . Jika kita membedakan antara teori chaos dan konsep-konsep lain yang digunakannya dengan benar, mudah untuk melihat bahwa aplikasi yang pertama secara inheren terbatas pada fungsi yang diketahui dalam studi ilmiah biasa. Benar-benar ada alasan bagus untuk bersemangat tentang aplikasi potensial dari konsep-konsep sekunder ini tanpa adanya kekacauan, tetapi juga alasan untuk khawatir tentang efek kontaminasi dari perilaku aperiodik yang tak terduga pada upaya penambangan data saat itu ada. Kesempatan seperti itu akan jarang terjadi, tetapi kelangkaan itu juga cenderung berarti bahwa mereka tidak akan terdeteksi. Metode Ҫambel mungkin berguna dalam mencegah masalah seperti itu.

[1] hlm. 143-147, Alligood, Kathleen T .; Sauer, Tim D. dan Yorke, James A., 2010, Chaos: Pengantar Sistem Dinamis, Springer: New York. [2] hlm. 208-213, Ҫambel, AB, 1993, Teori Kerusakan Terapan: Paradigma Kompleksitas, Academic Press, Inc .: Boston. [3] hal. 215, Ҫambel.

SQLServerSteve
sumber