Pemilihan fitur mirip pohon dengan panjang keputusan tetap untuk meminimalkan kinerja pencarian rata-rata

Saya memiliki query kompleks yang digunakan untuk mencari dataset S untuk menemukan H exact = { s ∈ S ∣ di mana  Q ( s )  bernilai True } . Setiap kueri mengambil waktu rata-rata t sehingga waktu keseluruhan dalam pencarian linear adalah t ⋅ | S | . Saya dapat mematahkan query ke dalam sederhana sub-query q_i dan menemukan H kira-kira = { s ∈ S | ∀ q j ( s ) Benar $Q$$S$$H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$$t$$t\cdot |S|$$H_\text{approx} = \{s\in S \mid \forall q_j(s) \text {is True}\}$ dan di mana . Setiap subquery q i adalah lebih cepat untuk menghitung, sehingga secara keseluruhan itu lebih cepat untuk menemukan H kira-kira dan kemudian menggunakan Q untuk menemukan H tepat .$H_\text{exact}\subseteq H_\text{approx}$$q_i$$H_\text{approx}$$Q$$H_\text{exact}$

Setiap memiliki banyak q i . Tumpang tindih antara Q berbeda adalah tinggi. Saya sedang mencari cara untuk menentukan serangkaian pertanyaan tetap seperti-pohon q j yang meminimalkan waktu rata-rata untuk menemukan H_exact, berdasarkan sampel besar kueri penelusuran.$Q$$q_i$$Q$$q_j$

Untuk membuat ini lebih konkret, anggap kumpulan data berisi 7 miliar orang di dunia, dan pertanyaan kompleks adalah hal-hal seperti "wanita yang tinggal di rumah merah di sudut ke-5 dan Lexington di kota yang dimulai dengan B."

Solusi yang jelas adalah memeriksa setiap orang di dunia dan melihat siapa yang cocok dengan kueri. Mungkin ada lebih dari satu orang seperti itu. Metode ini membutuhkan waktu lama.

Saya dapat melakukan pre-compute query ini dengan tepat, dalam hal ini akan sangat cepat .. tetapi hanya untuk pertanyaan ini. Namun, saya tahu bahwa pertanyaan lain adalah untuk wanita yang tinggal di rumah biru di sudut yang sama, pria yang tinggal di sudut yang sama, pertanyaan yang sama tetapi di kota yang dimulai dengan C, atau sesuatu yang sama sekali berbeda, seperti 'the raja Swedia. '

Sebagai gantinya, saya dapat memecah pertanyaan kompleks menjadi satu set yang lebih mudah tetapi lebih umum. Misalnya, semua pertanyaan di atas memiliki kueri berbasis peran jender, jadi saya dapat melakukan precompute terhadap semua orang di dunia yang menganggap diri mereka 'wanita'. Sub-query ini pada dasarnya tidak membutuhkan waktu, sehingga waktu pencarian keseluruhan berkurang sekitar 1/2. (Dengan asumsi bahwa dengan pengetahuan lain kita tahu bahwa "raja" Swedia tidak bisa menjadi "wanita." Hatshepsut adalah seorang wanita Mesir yang menjadi raja.)

Namun, terkadang ada pertanyaan yang tidak berbasis gender, seperti "orang yang tinggal di 8th street di rumah merah di kota yang dimulai dengan A." Saya dapat melihat bahwa subquery "tinggal di rumah merah" adalah umum, dan pra-menghitung daftar semua orang yang tinggal di rumah merah.

Ini memberi saya pohon keputusan. Dalam kasus biasa, setiap cabang dari pohon keputusan berisi pertanyaan yang berbeda, dan metode untuk memilih istilah yang optimal untuk pohon keputusan sudah diketahui. Namun, saya membangun sistem yang ada yang mengharuskan semua cabang harus mengajukan pertanyaan yang sama.

Berikut adalah contoh dari set keputusan akhir yang mungkin: pertanyaan 1 adalah 'apakah orang itu seorang wanita?', Pertanyaan 2 adalah 'apakah orang tersebut tinggal di rumah merah?', Pertanyaan 3 adalah 'apakah orang tersebut tinggal di kota yang dimulai dengan A atau apakah orang tersebut tinggal di kota yang dimulai dengan B? ', Dan pertanyaan 4 adalah' apakah orang tersebut tinggal di jalan bernomor? '.

$Q$$q_i$$q_j$$Q$

$Q$$H_\text{approx}$$H_\text{approx}$

$q_j$$q_j$

Apa penelitian yang ada yang harus saya cari ide?

Solusi yang saya temukan (saya ajukan pertanyaan) adalah menggunakan pengkodean yang dilapiskan, dan lebih khusus lagi, varian Zatocoding yang memiliki dukungan yang lebih baik untuk deskriptor hierarkis.

Metode yang saya gunakan berasal dari 'Desain yang Efisien untuk Pencarian Struktur Kimia. I. Layar ', Alfred Feldman dan Louis Hodes, J. Chem. Inf. Komputasi. Sci., 1975, 15 (3), hlm 147–152.

$s_i=-log_2(f_i)$$f_i$$0<$$D$$D=\sum(s_i f_i)/M_c$$M_c$$log_e 2$$s_i$

$s_i=-log_2(f_i)$$s_i=-log_2(f_i/g_i)$$g_i$

Masih ada masalah tentang bagaimana membuat deskriptor yang tepat, tetapi itu akan menjadi spesifik domain.