Tantangan
Dalam artikel ini, kami ingin berbicara tentang bagaimana kami menciptakan solusi untuk mengklasifikasikan nama produk dari tanda terima dalam aplikasi untuk mencatat pengeluaran untuk cek dan asisten belanja. Kami ingin memberi pengguna kesempatan untuk melihat statistik pembelian, dikumpulkan secara otomatis berdasarkan tanda terima yang dipindai, yaitu untuk mendistribusikan semua barang yang dibeli oleh pengguna berdasarkan kategori. Karena memaksa pengguna untuk secara mandiri mengelompokkan produk sudah abad terakhir. Ada beberapa pendekatan untuk menyelesaikan masalah ini: Anda dapat mencoba menerapkan algoritma pengelompokan dengan berbagai cara representasi vektor kata atau algoritma klasifikasi klasik. Kami belum menemukan sesuatu yang baru, dan dalam artikel ini kami hanya ingin berbagi panduan kecil tentang kemungkinan solusi untuk masalah tersebut, contoh bagaimana tidak melakukan ini, analisis mengapa metode lain tidak berhasil dan masalah apa yang mungkin Anda temui dalam proses.
Clustering
Salah satu masalah adalah bahwa nama barang yang kita dapatkan dari cek tidak selalu mudah diuraikan, bahkan untuk seseorang. Kecil kemungkinan Anda akan tahu produk seperti apa dengan nama
"UTRUSTA krnsht" yang dibeli di salah satu toko Rusia? Penikmat sejati desain Swedia pasti akan menjawab kami segera: Bracket untuk oven Utrust, tetapi menjaga spesialis seperti itu di markas cukup mahal. Selain itu, kami tidak memiliki sampel berlabel siap pakai yang sesuai untuk data kami, yang dapat digunakan untuk melatih model. Oleh karena itu, pertama kita akan berbicara tentang bagaimana, dengan tidak adanya data untuk pelatihan, kami menerapkan algoritma pengelompokan dan mengapa kami tidak menyukainya.
Algoritma tersebut didasarkan pada pengukuran jarak antara objek, yang membutuhkan representasi vektor atau penggunaan metrik untuk mengukur kemiripan kata-kata (misalnya, jarak Levenshtein). Pada langkah ini, kesulitannya terletak pada representasi vektor yang bermakna dari nama-nama tersebut. Merupakan masalah untuk mengekstrak properti dari nama-nama yang akan secara lengkap dan komprehensif menggambarkan produk dan hubungannya dengan produk lain.
Opsi termudah adalah menggunakan Tf-Idf, tetapi dalam hal ini dimensi ruang vektor cukup besar, dan ruang itu sendiri jarang. Selain itu, pendekatan ini tidak mengekstraksi informasi tambahan apa pun dari namanya. Dengan demikian, dalam satu kelompok dapat terdapat banyak produk dari kategori yang berbeda, disatukan oleh kata yang sama, seperti, misalnya, "kentang" atau "salad":
Kami juga tidak dapat mengontrol kelompok mana yang akan dirakit. Satu-satunya hal yang dapat diindikasikan adalah jumlah cluster (jika algoritma berdasarkan puncak non-kepadatan di ruang digunakan). Tetapi jika Anda menentukan jumlah yang terlalu kecil, maka satu cluster besar terbentuk, yang akan berisi semua nama yang tidak dapat masuk ke dalam cluster lain. Jika Anda menentukan yang cukup besar, maka setelah algoritme berfungsi, kita harus melihat melalui ratusan cluster dan menggabungkannya ke dalam kategori semantik dengan tangan.
Tabel di bawah ini memberikan informasi tentang cluster menggunakan algoritma KMeans dan Tf-Idf untuk representasi vektor. Dari tabel ini kita melihat bahwa jarak antara pusat-pusat cluster kurang dari jarak rata-rata antara objek dan pusat-pusat cluster di mana mereka berada. Data tersebut dapat dijelaskan oleh fakta bahwa dalam ruang vektor tidak ada puncak kepadatan yang jelas dan pusat cluster terletak pada lingkaran, di mana sebagian besar objek berada di luar lingkaran ini. Selain itu, satu cluster terbentuk, yang berisi sebagian besar vektor. Kemungkinan besar dalam klaster ini adalah nama-nama yang mengandung kata-kata yang lebih sering ditemukan daripada yang lain di antara semua produk dari kategori yang berbeda.
Tabel 1. Jarak antar cluster.| Cluster | C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 |
|---|
| C1 | 0,0 | 0,502 | 0,354 | 0,475 | 0,481 | 0,527 | 0,498 | 0,501 | 0,524 |
|---|
| C2 | 0,502 | 0,0 | 0,614 | 0,685 | 0,696 | 0,728 | 0,706 | 0,709 | 0,725 |
|---|
| C3 | 0,354 | 0,614 | 0,0 | 0,590 | 0,597 | 0,635 | 0,610 | 0,613 | 0,632 |
|---|
| C4 | 0,475 | 0,685 | 0,590 | 0,0 | 0,673 | 0,709 | 0,683 | 0,687 | 0,699 |
|---|
| C5 | 0,481 | 0,696 | 0,597 | 0,673 | 0,0 | 0,715 | 0,692 | 0,694 | 0,711 |
|---|
| C6 | 0,527 | 0,727 | 0,635 | 0,709 | 0,715 | 0,0 | 0,726 | 0,728 | 0,741 |
|---|
| C7 | 0,498 | 0,706 | 0,610 | 0,683 | 0,692 | 0,725 | 0,0 | 0,707 | 0,714 |
|---|
| C8 | 0,501 | 0,709 | 0,612 | 0,687 | 0,694 | 0,728 | 0,707 | 0,0 | 0,725 |
|---|
| C9 | 0,524 | 0,725 | 0,632 | 0,699 | 0,711 | 0,741 | 0,714 | 0,725 | 0,0 |
|---|
Tabel 2. Informasi singkat tentang kluster| Cluster | Jumlah objek | Jarak rata-rata | Jarak minimum | Jarak maksimum |
|---|
| C1 | 62530 | 0,999 | 0,041 | 1,001 |
|---|
| C2 | 2159 | 0,864 | 0,527 | 0,964 |
|---|
| C3 | 1099 | 0,934 | 0,756 | 0,993 |
|---|
| C4 | 1292 | 0,879 | 0,733 | 0,980 |
|---|
| C5 | 746 | 0,875 | 0,731 | 0,965 |
|---|
| C6 | 2451 | 0,847 | 0,719 | 0,994 |
|---|
| C7 | 1133 | 0,866 | 0,724 | 0,986 |
|---|
| C8 | 876 | 0,863 | 0,704 | 0,999 |
|---|
| C9 | 1879 | 0,849 | 0,526 | 0,981 |
|---|
Tetapi di beberapa tempat, kluster-kluster itu ternyata cukup baik, seperti, misalnya, pada gambar di bawah ini - di sana, hampir semua produk adalah makanan kucing.
Doc2Vec adalah salah satu dari algoritma yang memungkinkan Anda untuk mewakili teks dalam bentuk vektor. Dengan menggunakan pendekatan ini, setiap nama akan dideskripsikan dengan vektor berdimensi lebih kecil daripada menggunakan Tf-Idf. Dalam ruang vektor yang dihasilkan, teks yang mirip akan dekat satu sama lain, dan yang berbeda jauh.
Pendekatan ini dapat menyelesaikan masalah dimensi besar dan ruang kosong yang diperoleh dengan metode Tf-Idf. Untuk algoritme ini, kami menggunakan opsi tokenization yang paling sederhana: kami memecah nama menjadi kata-kata yang terpisah dan mengambil bentuk awalnya. Dia dilatih tentang data dengan cara ini:
max_epochs = 100 vec_size = 20 alpha = 0.025 model = doc2vec.Doc2Vec(vector_size=vec_size, alpha=alpha, min_alpha=0.00025, min_count=1, dm =1) model.build_vocab(train_corpus) for epoch in range(max_epochs): print('iteration {0}'.format(epoch)) model.train(train_corpus, total_examples=model.corpus_count, epochs=model.iter)
Tetapi dengan pendekatan ini, kami mendapat vektor yang tidak membawa informasi tentang nama - dengan kesuksesan yang sama Anda dapat menggunakan nilai acak. Berikut adalah salah satu contoh pengoperasian algoritma: gambar menunjukkan produk yang serupa menurut pendapat algoritme dengan “Roti Borodino dalam bentuk n pn 0.45k”.
Mungkin masalahnya ada pada panjang dan konteks nama: pas di nama "__ klub. Pisang 200ml" bisa berupa yogurt, jus, atau sekaleng krim besar. Anda dapat mencapai hasil yang lebih baik menggunakan pendekatan yang berbeda untuk tokenization nama. Kami tidak memiliki pengalaman menggunakan metode ini, dan pada saat upaya pertama gagal, kami sudah menemukan beberapa set yang ditandai dengan nama produk, jadi kami memutuskan untuk meninggalkan sementara metode ini dan beralih ke algoritma klasifikasi.
Klasifikasi
Pra-pemrosesan data
Nama-nama barang dari cek datang kepada kita dengan cara yang tidak selalu jelas: Latin dan Cyrillic dicampur dalam kata-kata. Misalnya, huruf "a" dapat diganti dengan "a" Latin, dan ini menambah jumlah nama unik - misalnya, kata "susu" dan "susu" akan dianggap berbeda. Nama-nama itu juga mengandung banyak kesalahan ketik dan singkatan lainnya.
Kami memeriksa basis data kami dan menemukan kesalahan khas pada namanya. Pada tahap ini, kami mengeluarkan ekspresi reguler, dengan bantuan yang kami membersihkan nama dan membawanya ke pandangan umum tertentu. Dengan menggunakan pendekatan ini, hasilnya meningkat sekitar 7%. Bersama dengan opsi SGD Classifier sederhana berdasarkan pada fungsi Huber loss dengan parameter twisted, kami mendapatkan akurasi 81% untuk F1 (akurasi rata-rata untuk semua kategori produk).
sgd_model = SGDClassifier() parameters_sgd = { 'max_iter':[100], 'loss':['modified_huber'], 'class_weight':['balanced'], 'penalty':['l2'], 'alpha':[0.0001] } sgd_cv = GridSearchCV(sgd_model, parameters_sgd,n_jobs=-1) sgd_cv.fit(tf_idf_data, prod_cat) sgd_cv.best_score_, sgd_cv.best_params_
Juga, jangan lupa bahwa beberapa kategori orang membeli lebih sering daripada yang lain: misalnya, "Teh dan permen" dan "Sayuran dan buah-buahan" jauh lebih populer daripada "Layanan" dan "Kosmetik". Dengan distribusi data seperti itu, lebih baik menggunakan algoritma yang memungkinkan Anda untuk mengatur bobot (tingkat kepentingan) untuk setiap kelas. Berat kelas dapat ditentukan secara terbalik dengan nilai yang sama dengan rasio jumlah produk di kelas terhadap jumlah total produk. Tetapi Anda tidak perlu memikirkannya, karena dalam penerapan algoritme ini, dimungkinkan untuk menentukan bobot kategori secara otomatis.
Memperoleh data baru untuk pelatihan
Aplikasi kami membutuhkan kategori yang sedikit berbeda dari yang digunakan dalam kompetisi, dan nama-nama produk dari database kami sangat berbeda dari yang disajikan dalam kontes. Oleh karena itu, kami perlu menandai barang dari tanda terima kami. Kami mencoba melakukan ini sendiri, tetapi kami menyadari bahwa meskipun kami menghubungkan seluruh tim kami, itu akan memakan waktu yang sangat lama. Oleh karena itu, kami memutuskan untuk menggunakan
"Toloka" Yandex .
Di sana kami menggunakan bentuk penugasan ini:
- di setiap sel kami menyajikan produk, kategori yang harus ditentukan
- kategori hipotetisnya ditentukan oleh salah satu model kami sebelumnya
- bidang respons (jika kategori yang diajukan salah)
Kami membuat instruksi terperinci dengan contoh-contoh yang menjelaskan fitur masing-masing kategori, dan juga menggunakan metode kontrol kualitas: satu set dengan jawaban standar yang ditunjukkan bersama dengan tugas-tugas biasa (kami menerapkan jawaban standar sendiri, menandai beberapa ratus produk). Menurut hasil jawaban untuk tugas-tugas ini, pengguna yang salah menandai data disaring. Namun, untuk keseluruhan proyek, kami melarang hanya tiga pengguna dari 600+.
Dengan data baru, kami mendapatkan model yang lebih sesuai dengan data kami, dan akurasi meningkat sedikit lebih banyak (~ 11%) dan sudah mendapatkan 92%.
Model akhir
Kami memulai proses klasifikasi dengan kombinasi data dari beberapa dataset dengan Kaggle - 74%, setelah itu kami meningkatkan preprocessing - 81%, mengumpulkan set data baru - 92% dan akhirnya memperbaiki proses klasifikasi: awalnya, dengan menggunakan regresi logistik kami mendapatkan probabilitas awal barang yang dimiliki SGD memberikan akurasi yang lebih besar untuk kategori berdasarkan nama produk, tetapi masih memiliki nilai besar pada fungsi kerugian, yang sangat mempengaruhi hasil klasifikasi akhir. Selanjutnya, kami menggabungkan data yang diperoleh dengan data lain pada produk (harga produk, toko tempat pembelian, statistik di toko, cek dan informasi meta lainnya), dan XGBoost dilatih pada semua volume data ini, yang memberikan akurasi 98% (peningkatan 6% lainnya). Ternyata, kontribusi terbesar dibuat oleh kualitas sampel pelatihan.
Berjalan di server
Untuk mempercepat penyebaran, kami mengangkat server sederhana di Flask ke Docker. Ada satu metode yang menerima barang dari server yang perlu dikategorikan dan mengembalikan barang dengan kategori sudah. Dengan demikian, kami dengan mudah diintegrasikan ke dalam sistem yang ada, yang pusatnya adalah Tomcat, dan kami tidak perlu membuat perubahan pada arsitektur - kami hanya menambahkan satu blok lagi ke dalamnya.
Tanggal rilis
Beberapa minggu yang lalu kami memposting rilis kategorisasi di Google Play (akan muncul di App Store setelah beberapa saat). Ternyata seperti ini:
Dalam rilis mendatang, kami berencana untuk menambahkan kemampuan untuk memperbaiki kategori, yang akan memungkinkan kami untuk dengan cepat mengumpulkan kesalahan kategorisasi dan melatih kembali model kategorisasi (sementara kami melakukannya sendiri).
Kompetisi yang disebutkan di Kaggle:
www.kaggle.com/c/receipt-categorisationwww.kaggle.com/c/market-basket-analysiswww.kaggle.com/c/prod-price-prediction