Algoritma Pencocokan Preferensi

Ada proyek sampingan yang sedang saya kerjakan di mana saya perlu menyusun solusi untuk masalah berikut.

Saya memiliki dua kelompok orang (klien). Grup Abermaksud untuk membeli dan grup Bbermaksud untuk menjual produk yang ditentukan X. Produk ini memiliki serangkaian atribut x_i, dan tujuan saya adalah untuk memfasilitasi transaksi antara Adan Bdengan mencocokkan preferensi mereka. Gagasan utamanya adalah untuk menunjukkan kepada masing-masing anggota Akoresponden di Bmana produknya lebih sesuai dengan kebutuhannya, dan sebaliknya.

Beberapa aspek masalah yang menyulitkan:

1. Daftar atribut tidak terbatas. Pembeli mungkin tertarik pada karakteristik yang sangat khusus atau semacam desain, yang jarang di antara populasi dan saya tidak dapat memprediksi. Tidak dapat sebelumnya mencantumkan semua atribut;

2. Atribut mungkin kontinu, biner, atau tidak dapat diukur (mis: harga, fungsionalitas, desain);

Adakah saran tentang cara mendekati masalah ini dan menyelesaikannya dengan cara otomatis?

Saya juga akan menghargai beberapa referensi untuk masalah serupa lainnya jika memungkinkan.

Saran bagus! Banyak kesamaan dalam cara saya berpikir mendekati masalah.

Masalah utama pada pemetaan atribut adalah bahwa tingkat detail yang harus dijelaskan produk tergantung pada masing-masing pembeli. Mari kita ambil contoh sebuah mobil. Produk "mobil" memiliki banyak atribut yang berkisar dari kinerjanya, struktur mekanik, harga dll.

Misalkan saya hanya menginginkan mobil murah, atau mobil listrik. Oke, mudah dipetakan karena mewakili fitur utama dari produk ini. Tetapi katakanlah, misalnya, bahwa saya menginginkan mobil dengan transmisi Dual-Clutch atau lampu depan Xenon. Yah mungkin ada banyak mobil di pangkalan data dengan atribut ini, tetapi saya tidak akan meminta penjual untuk mengisi tingkat detail produk mereka sebelum informasi bahwa ada seseorang yang melihatnya. Prosedur seperti itu akan mengharuskan setiap penjual mengisi formulir yang kompleks, sangat terperinci, hanya mencoba menjual mobilnya di peron. Tidak akan berhasil.

Tapi tetap saja, tantangan saya adalah mencoba sedetail yang diperlukan dalam pencarian untuk membuat pasangan yang baik. Jadi cara saya berpikir adalah memetakan aspek-aspek utama dari produk, yang mungkin relevan bagi semua orang, untuk mempersempit kelompok penjual potensial.

Langkah selanjutnya adalah "pencarian yang disempurnakan". Untuk menghindari membuat formulir yang terlalu rinci saya bisa meminta pembeli dan penjual untuk menulis teks gratis dari spesifikasi mereka. Dan kemudian gunakan beberapa algoritma pencocokan kata untuk menemukan kemungkinan kecocokan. Meskipun saya mengerti bahwa ini bukan solusi yang tepat untuk masalah karena penjual tidak dapat "menebak" apa yang dibutuhkan pembeli. Tetapi mungkin membuat saya dekat.

Kriteria bobot yang disarankan sangat bagus. Ini memungkinkan saya untuk mengukur tingkat yang cocok dengan kebutuhan pembeli. Bagian penskalaan mungkin menjadi masalah, karena pentingnya setiap atribut bervariasi dari klien ke klien. Saya sedang berpikir untuk menggunakan semacam pengenalan pola atau hanya meminta de pembeli untuk memasukkan tingkat kepentingan setiap atribut.

Saran pertama saya adalah memetakan atribut yang tidak dapat diukur ke kuantitas dengan bantuan fungsi pemetaan yang sesuai. Kalau tidak, tinggalkan saja.

Kedua, saya tidak berpikir Anda perlu berasumsi bahwa daftar atribut tidak terbatas. Pendekatan standar dan intuitif adalah untuk mewakili setiap atribut sebagai dimensi individu dalam ruang vektor. Setiap produk kemudian hanya titik di ruang ini. Dalam hal ini, jika Anda ingin menambahkan lebih banyak atribut secara dinamis, Anda hanya perlu memetakan kembali vektor produk ke dalam ruang fitur baru (dengan dimensi tambahan).

Dengan representasi ini, penjual adalah titik di ruang fitur dengan atribut produk dan pembeli adalah titik di ruang fitur yang sama dengan atribut preferensi. Tugasnya adalah untuk menemukan titik pembeli yang paling mirip untuk titik penjual yang diberikan.

Jika dataset Anda (yaitu jumlah pembeli / penjual) tidak terlalu besar, Anda dapat menyelesaikan ini dengan pendekatan tetangga terdekat diimplementasikan dengan bantuan pohon kd.

Untuk data berukuran sangat besar, Anda dapat mengambil pendekatan IR. Indeks sekumpulan penjual (yaitu atribut produk) dengan memperlakukan setiap atribut sebagai istilah terpisah dengan term-weight diatur ke nilai atribut. Kueri dalam hal ini adalah pembeli yang juga dikodekan dalam ruang istilah sebagai vektor kueri dengan bobot istilah yang sesuai. Langkah pengambilan akan mengembalikan daftar kecocokan K paling atas kepada Anda.

Seperti yang disarankan, menjadi liar . Pertama-tama, koreksi saya jika saya salah:

• Hanya ada beberapa fitur untuk setiap produk unik;
• Tidak ada daftar fitur utama, dan klien dapat menambahkan fitur baru ke produk mereka.

Jika demikian, membangun tabel fitur produk lengkap bisa jadi mahal komputasi. Dan tabel data akhir akan sangat jarang.

Langkah pertama adalah mempersempit daftar pelanggan (produk) untuk pencocokan. Mari kita membangun grafik bipartit, di mana penjual akan menjadi simpul tipe-1, dan pembeli akan menjadi simpul tipe-2. Buat keunggulan antara penjual dan pembeli setiap kali mereka mereferensikan fitur produk serupa, seperti dalam sketsa berikut:

Dengan menggunakan grafik di atas, untuk setiap produk penjual unik, Anda dapat memilih hanya pembeli yang tertarik pada fitur yang cocok dengan produk (dimungkinkan untuk memfilter setidaknya satu fitur umum, cocok dengan set lengkap fitur, atau mengatur level ambang batas). Namun yang pasti, itu tidak cukup. Langkah selanjutnya adalah membandingkan nilai fitur, seperti yang dijelaskan oleh penjual dan pembeli. Ada banyak varian (mis. K-Nearest-Neighbors). Tetapi mengapa tidak mencoba menyelesaikan pertanyaan ini menggunakan grafik yang ada? Mari kita tambahkan bobot ke tepinya:

• untuk fitur berkelanjutan (mis., harga):

  

• untuk fitur biner dan non-kuantitatif - hanya bikondisional logis:

  

Gagasan utama di sini adalah untuk skala setiap fitur ke interval [0, 1]. Selain itu, kami dapat menggunakan koefisien fitur untuk menentukan fitur yang paling penting. Misalnya, dengan asumsi harga dua kali lebih penting dari ketersediaan beberapa fungsi langka:

Salah satu langkah terakhir adalah menyederhanakan struktur grafik dan mengurangi banyak sisi menjadi satu sisi dengan bobot sama dengan jumlah bobot masing-masing fitur yang dihitung sebelumnya. Dengan struktur yang dikurangi, setiap pasangan pelanggan / produk hanya dapat memiliki satu sisi (tidak ada sisi paralel). Jadi, untuk menemukan penawaran terbaik untuk penjual yang tepat, Anda hanya perlu memilih pembeli yang terhubung dengan batas maksimal.

Tantangan di masa depan: memperkenalkan metode murah untuk menimbang tepi pada langkah pertama :)