Bagaimana cara membuat diagram venn dengan 50 lingkaran? Visualisasi set dan sejarah proyek Python open source saya

Hai semuanya, nama saya Fedor Indukaev, saya bekerja sebagai analis di Yandex. Rute. Hari ini saya ingin memberi tahu Anda tentang tugas memvisualisasikan set berpotongan dan tentang paket open source Python yang saya buat untuk menyelesaikannya. Dalam prosesnya, kita akan belajar bagaimana diagram Venn dan Euler berbeda, berkenalan dengan layanan distribusi pesanan dan secara langsung menyentuh bidang ilmu pengetahuan seperti bioinformatika. Kami akan beralih dari yang sederhana ke yang lebih kompleks. Pergilah!

Tentang apa dan mengapa itu dibutuhkan?

Hampir setiap orang yang terlibat dalam analisis data eksplorasi harus mencari jawaban untuk pertanyaan jenis ini setidaknya sekali:

• Ada dataset dengan beberapa variabel biner independen. Yang mana dari mereka yang sering ditemukan bersama?
• Ada beberapa tabel dengan objek yang sifatnya sama yang memiliki ID. Bagaimana hubungan set ID dari tabel yang berbeda - apakah masing-masing tabel memiliki ID sendiri, atau sama di semua tabel, atau set berbeda, tetapi hanya sedikit?
• Ada beberapa spesies. Organisme mana yang memiliki gen atau protein yang mirip?
• Bagaimana cara menggambar bagan pie jika kategori tumpang tindih? (Benar, ini tidak menjadi masalah bagi semua orang: lihat persentase pada gambar di bawah ini.)

Semua pertanyaan ini dapat direduksi menjadi kata-kata yang sama. Kedengarannya seperti ini: beberapa set terbatas diberikan, mungkin berpotongan satu sama lain, dan kita perlu mengevaluasi posisi relatif mereka - yaitu, untuk memahami bagaimana tepatnya mereka berpotongan.

Kami akan fokus pada visualisasi dan perangkat lunak untuk membantu menyelesaikan masalah ini.

Diagram Venn

Gambar seperti itu dengan dua atau tiga lingkaran, saya pikir, sudah biasa bagi semua orang dan tidak memerlukan penjelasan:



Fitur diagram Venn adalah statis. Angka-angka di atasnya sama dan terletak secara simetris. Gambar tersebut menunjukkan semua persimpangan yang mungkin, bahkan jika sebagian besar dari mereka benar-benar kosong. Diagram seperti itu cocok untuk menggambarkan konsep atau set abstrak yang dimensi pastinya tidak diketahui atau tidak penting. Informasi dasar di sini tidak terkandung dalam jadwal, tetapi dalam tanda tangan.

Itulah bagaimana mereka dikandung oleh John Venn, seorang ahli matematika dan filsuf Inggris. Dalam artikelnya tahun 1880ia mengusulkan diagram untuk menampilkan proposisi logis secara grafis. Misalnya, pernyataan "X mana pun adalah Y atau Z" memberikan diagram di sebelah kanan (ilustrasi diambil dari artikel asli). Area yang tidak memenuhi pernyataan diarsir dengan warna hitam: X yang bukan Y atau Z. Pesan utama dari artikel ini adalah bahwa gambar statis tanpa memvariasikan bentuk dan susunan gambar lebih cocok untuk keperluan logika daripada diagram Euler dinamis, yang dibahas akan pergi di bawah ini.

Jelas bahwa dalam analisis data, ruang lingkup diagram Venn terbatas. Mereka hanya memberikan informasi kualitatif, tetapi tidak kuantitatif dan tidak mencerminkan ukuran atau bahkan kekosongan persimpangan. Jika ini tidak menghentikan Anda, Anda dapat menggunakan paket venn , yang membuat diagram seperti itu$$$N = 2, 3, 4, 5, 6$ set. Untuk setiap$$$N$ ada satu atau dua gambar khas, dan hanya tanda tangan yang akan berbeda:



Jika kami menginginkan sesuatu yang lebih tergantung secara dinamis pada data, Anda harus memperhatikan pendekatan lain: Diagram Euler.

Grafik Euler

Tidak seperti diagram Venn, bentuk dan posisi gambar pada bidang di sini dipilih untuk menunjukkan hubungan set atau konsep. Jika beberapa persimpangan kosong, maka angka-angka juga tidak tumpang tindih bila memungkinkan, seperti pada gambar tentang tanaman dan hewan.

Harap dicatat bahwa gambar tentang pertanyaan di ceramah berbeda dari dua lainnya. Penting tidak hanya posisi figur, tetapi juga ukuran persimpangan - semua humor terlampir di dalamnya.

Ide ini bisa digunakan untuk tugas kita. Ambil dua atau tiga set dan gambar lingkaran dengan area yang sebanding dengan ukuran set ini. Dan kemudian kita akan mencoba untuk mengatur lingkaran di pesawat sehingga area yang tumpang tindih juga sebanding dengan ukuran persimpangan.

Inilah yang dilakukan paket (terlepas dari namanya)matplotlib-venn : Menggambar



dua set dengan proporsi yang tepat itu mudah. Tapi sudah jam tiga, metode ini mungkin gagal. Biarkan, misalnya, salah satu dari tiga set persis persimpangan dari dua lainnya:



Gambar tidak terlihat bagus, area aneh muncul dengan angka 0. Tapi tidak ada yang mengejutkan, karena persimpangan dua lingkaran tidak dapat direpresentasikan sebagai lingkaran.

Dan inilah contoh yang lebih menyedihkan: dua set dan perbedaan simetrisnya (persilangan minus persimpangan):



Ternyata menjadi sesuatu yang benar-benar aneh: perhatikan berapa banyak nol yang ada!

Contoh pertama masih bisa disimpan jika kita mengambil persegi panjang alih-alih lingkaran (persimpangan persegi panjang juga persegi panjang), sedangkan yang kedua membutuhkan setidaknya bentuk non-cembung. Nah, lebih dari tiga set, paket ini pada prinsipnya tidak mendukung.

Saya tidak tahu alat publik lain untuk Python yang mengembangkan pendekatan Euler-Venn, dan sejarah percobaan saya sendiri akan lebih jauh. Tetapi sebelum melanjutkan, saya akan membuat sedikit penyimpangan untuk menjelaskan mengapa saya bahkan mengambil tugas memvisualisasikan set.

Beberapa kata tentang API untuk membangun rute optimal

Seperti yang saya katakan, departemen kami melakukan Yandex.routing. Salah satu layanan kami membantu toko online, layanan pengiriman, dan perusahaan mana pun yang bisnisnya mencakup logistik untuk membangun rute optimal untuk transportasi.

Klien berinteraksi dengan layanan dengan mengirimkan permintaan API. Setiap permintaan berisi daftar pesanan (titik pengiriman) dengan koordinat, interval pengiriman, dll., Serta daftar mesin yang perlu mengirimkan pesanan. Algoritma kami mencerna semua data ini dan menghasilkan rute yang optimal dengan memperhitungkan kemacetan lalu lintas, kapasitas mobil, dan banyak lagi lainnya.

Kami memiliki ratusan, bukan jutaan pelanggan, seperti layanan Yandex B2C yang populer. Oleh karena itu, kebahagiaan setiap klien sangat penting bagi kami, di samping itu, adalah mungkin untuk memberinya perhatian lebih dan menyelam lebih dalam ke tugasnya. Untuk ini, khususnya, penting untuk memiliki alat untuk membantu Anda memahami permintaan apa yang klien kirimkan kepada kami.

Saya akan memberi contoh. Misalkan, dalam satu hari, 24 permintaan diterima dari Romashka. Ini dapat berarti bahwa:

• Mereka bekerja di seluruh negeri dan telah membangun 24 set rute untuk 24 gudang.
• Hanya ada satu gudang, tetapi pelanggan terus menerima pesanan baru. Untuk memperhitungkannya, Anda perlu memperbarui rute setiap jam.
• Permintaan dari klien dibentuk dengan kesalahan karena ia tidak bisa mendapatkan solusi yang baik untuk satu tugas 24 kali berturut-turut.

A priori itu benar-benar tidak jelas apa yang sebenarnya terjadi. Tetapi jika kita dapat dengan cepat membandingkan 24 set ID pesanan, situasinya akan segera menjadi jelas. Jika mereka tidak berpotongan sama sekali - ini adalah kasus pertama (24 gudang). Jika set mengalir dari satu ke yang lain, yang kedua (pembaruan rute terjadwal). Nah, 24 set yang hampir identik adalah tanda yang mungkin bahwa klien membutuhkan bantuan.

Sederhanakan tugas: dari lingkaran ke garis-garis

Untuk beberapa waktu saya menggunakan paket matplotlib-venn, tetapi pembatasan set "dua setengah", tentu saja, membuat frustrasi. Merefleksikan pendekatan yang berbeda untuk masalah ini, saya memutuskan untuk mencoba beralih dari lingkaran dan umumnya dua dimensi primitif ke satu dimensi - garis horizontal. Persimpangan kemudian dapat digambarkan secara vertikal ditindih seperti ini:



Dimensi linear dirasakan oleh mata lebih baik daripada kuadrat, trigonometri kompleks tidak diperlukan untuk konstruksi, dan menempatkan jarak di sepanjang sumbu Y membuat grafik lebih sedikit kelebihan beban. Selain itu, contoh pertama gagal kami (dua set dan persimpangan mereka sebagai yang ketiga) membaik dengan sendirinya:



Masalah dengan perbedaan simetris masih ada di sini. Tetapi kita akan menanganinya sebagai Alexander yang Agung dengan simpul Gordian: mari kita, jika perlu, potong salah satu set menjadi dua bagian:



Himpunan merah digambarkan dalam dua garis bukannya satu, tetapi tidak ada yang salah dengan itu. Keduanya memiliki ketinggian yang sama dan memiliki warna yang sama, sehingga kesatuan mereka secara visual dapat dibaca dengan baik.

Sangat mudah untuk memverifikasi bahwa dengan cara ini, dengan ketelitian proporsi, tiga set dapat digambarkan. Jadi, masalah untuk$$$N$ sama dengan 2 atau 3 dapat dianggap diselesaikan.

Kelebihan lain dari pendekatan ini adalah mudah untuk diterapkan ke sejumlah set, yang akan kami lakukan segera. Yang diperlukan hanyalah menyelesaikan bukan hanya satu, tetapi sejumlah baris putus-putus. Tapi pertama-tama, sedikit kombinasi sederhana.

Sedikit aritmatika

Mari kita lihat diagram Venn dengan tiga lingkaran dan hitung berapa banyak area yang dibagi lingkaran:



Setiap area ditentukan oleh apakah itu terletak di dalam atau di luar masing-masing dari tiga lingkaran, tetapi area eksternal berlebihan. Total yang kita dapatkan$$$2^3-1=7$ . Lokasi lain dari tiga lingkaran dapat memberikan area lebih sedikit hingga 1, ketika semua lingkaran bertepatan.

Mentransfer argumen ini dari lingkaran ke set, kami mendapatkannya$$$N$ set saling mematahkan tidak lebih dari$$$2^N-1$ bagian dasar tersebut. Adalah penting bahwa masing-masing bagian ini dimasukkan seluruhnya atau tidak seluruhnya termasuk dalam set ini. Dalam diagram baru kami, kolom adalah bagian dasar.

Lebih banyak set!

Jadi, kami ingin menggeneralisasi skema ini untuk kasus ini $$$N > 3$:



Untuk $$$N$set kita dapatkan grid$$$N$ baris dan$$$M ≤ 2^N − 1$ kolom, seperti yang baru saja kita hitung. Masih harus melalui setiap baris dan mengisi sel-sel yang sesuai dengan bagian-bagian dasar yang termasuk dalam set ini.

Untuk menggambarkan, ambil contoh model lima set:

programming_languages = {'python', 'r', 'c', 'c++', 'java', 'julia'}
geographic_places = {'java', 'buffalo', 'turkey', 'moscow'}
letters = {'a', 'r', 'c', 'i', 'z'}
human_names = {'robin', 'julia', 'alice', 'bob', 'conrad'}
animals = {'python', 'buffalo', 'turkey', 'cat', 'dog', 'robin'}

Bertindak seperti dijelaskan di atas, kita mendapatkan gambar berikut:



Bunyinya buruk: ada terlalu banyak celah di garis, semua set dipotong menjadi kubis. Tetapi karena kita tidak suka istirahat, mengapa tidak langsung mengatur tugas untuk meminimalkannya? Bagaimanapun, urutan kolom tidak signifikan, tidak ada yang mencegah kita mengatur ulang mereka seperti yang kita inginkan. Kita sampai pada masalah ini: temukan permutasi kolom dari matriks nol yang diberikan dan yang dengan jumlah minimum kesenjangan antara unit dalam baris.

Seperti yang saya katakan kemudian, ini praktis adalah tugas dari seorang penjual keliling di metrik Hamming , ini adalah NP-complete . Jika ada beberapa kolom (katakanlah, tidak lebih dari 12), maka Anda dapat menemukan permutasi yang diperlukan dengan pencarian lengkap, jika tidak, Anda perlu menggunakan heuristik tertentu.

Kami menerapkan algoritma serakah sederhana. Mari kita sebut kesamaan dari dua kolom jumlah posisi di mana nilai-nilai dalam kolom ini bertepatan. Ambil dua kolom paling mirip, satukan. Selanjutnya, kami akan dengan bersemangat membangun urutan di kedua sisi pasangan ini. Di antara kolom-kolom yang tersisa, kami menemukan kolom yang paling mirip dengan salah satu dari keduanya, pasangkan - dan seterusnya dengan kolom-kolom lainnya.

Berikut adalah gambar sebelum dan sesudah menerapkan algoritma:



Itu menjadi jauh lebih baik. Pada tahap ini saya merasa bahwa sesuatu yang bermanfaat keluar. Setelah bereksperimen, saya perhatikan bahwa algoritma cenderung menempel pada minimum lokal. Kami berhasil memperlakukan ini dengan baik dengan pengacakan sederhana: kami membuat sedikit noise tentang kesamaan kolom, menjalankan algoritme, mengulang 1000 kali, memilih yang terbaik dari 1000 solusi.

Hasilnya sudah cukup alat yang berfungsi, tetapi Anda dapat menambahkan beberapa informasi yang lebih berguna untuk itu. Saya membuat dua grafik tambahan: ukuran set asli ditampilkan di sebelah kanan, dan yang teratas untuk setiap persimpangan menunjukkan berapa banyak set kami. Sebenarnya, ini tidak lebih dari jumlah matriks biner kami di baris (di kanan) dan di kolom (di atas):



Saya juga menambahkan opsi untuk memesan set sendiri (mis., Baris) sesuai dengan prinsip yang sama dengan kolom: dengan meminimalkan jumlah jeda. Akibatnya, set yang serupa dikelompokkan:

Aplikasi dalam pekerjaan

Secara alami, pertama-tama, saya mulai menggunakan alat baru untuk tugas yang dibuat: untuk memeriksa permintaan pelanggan untuk API kami. Hasilnya membuat saya senang. Jadi, misalnya, hari kerja salah satu klien tampak seperti. Setiap baris adalah permintaan ke API (banyak ID pesanan termasuk di dalamnya), dan tanda tangan di tengahnya adalah waktu pengiriman permintaan:



Sepanjang hari dalam tampilan penuh. Pada pukul 10:49 seorang pelanggan logistik dengan interval 23 detik mengirim dua permintaan yang identik dengan 129 pesanan. Dari 11:25 hingga 15:53 ​​ada tiga permintaan dengan 152 pesanan yang berbeda. Pada 16:43 permintaan unik ketiga tiba dengan 114 pesanan. Untuk mengatasi permintaan ini, ahli logistik kemudian menerapkan empat pengeditan manual (ini dapat dilakukan melalui UI kami).

Dan inilah yang terlihat seperti hari yang ideal: semua tugas independen diselesaikan satu kali, tidak ada koreksi atau pemilihan parameter yang diperlukan:



Dan berikut ini adalah contoh dari klien yang mengirim permintaan setiap 15-30 menit untuk memperhitungkan pesanan akun yang diterima secara real time:



Bahkan pada 50 set, algoritme dengan jelas mengungkapkan struktur yang tersembunyi dalam data. Anda dapat melihat bagaimana pesanan lama dihapus dari permintaan dan diganti dengan yang baru saat dieksekusi.

Singkatnya, saya benar-benar berhasil menutup kebutuhan kerja saya dengan alat yang dibuat.

Pisang untuk skala (tidak juga)

Ketika saya mempelajari pendekatan yang ada, saya menemukan beberapa kali gambar dari jurnal Nature , yang membandingkan genom pisang dan lima tanaman lainnya:



Perhatikan bagaimana ukuran wilayah berhubungan dengan 13 dan 149 elemen (ditunjukkan oleh panah): yang kedua beberapa kali lebih kecil. Jadi tidak ada pertanyaan tentang proporsionalitas.

Tentu saja, saya ingin mencoba tangan saya pada data tersebut, tetapi hasilnya tidak menyenangkan saya:



Grafiknya terlihat berantakan. Alasannya adalah bahwa, pertama, hampir semua persimpangan (62 dari 63 kemungkinan) adalah kosong, dan kedua, ukurannya berbeda dengan tiga urutan besarnya. Akibatnya, anotasi numerik menjadi sangat ramai.

Untuk membuat alat saya nyaman untuk data tersebut, saya menambahkan beberapa parameter. Satu memungkinkan Anda untuk menyelaraskan sebagian lebar kolom, yang lain menyembunyikan penjelasan jika lebar kolom kurang dari nilai yang ditentukan.



Pilihan ini dibaca dengan cukup baik, tetapi untuk ini saya harus mengorbankan proporsionalitas ukuran yang tepat.

Ternyata, dengan memperhatikan bidang bioinformatika, saya benar. Saya memposting posting tentang alat saya di Reddit di r / visualisasi , r / datacience dan r / bioinformatika , itu yang terakhir diterima, ulasannya sangat antusias.

Konversi Produk

Pada akhirnya, saya menyadari bahwa itu ternyata menjadi alat yang baik yang dapat bermanfaat bagi banyak orang. Oleh karena itu, lahirlah ide untuk mengubahnya menjadi paket open source lengkap. Tentu saja, persetujuan dari para pemimpin diperlukan, tetapi orang-orang tidak hanya tidak keberatan, tetapi juga mendukung saya, yang banyak terima kasih kepada mereka.

Bekerja terutama pada akhir pekan, saya mulai secara bertahap membawa kode ke pemasaran, menulis tes dan berurusan dengan sistem paket dengan Python. Ini adalah proyek pertama saya dari jenis ini, jadi butuh beberapa bulan.

Mencari nama baik juga merupakan tugas yang sulit, dan saya mengatasinya dengan buruk. Nama Terpilih (super venn) tidak dapat disebut berhasil, karena seluruh garam diagram Venn adalah sifat statis mereka, tetapi, sebaliknya, saya mencoba untuk secara akurat menunjukkan dimensi sebenarnya. Tetapi ketika saya menyadari ini, proyek sudah diterbitkan dan sudah terlambat untuk mengubah nama.

Analog

Tentu saja, saya bukan yang pertama menggunakan pendekatan ini untuk memvisualisasikan set: ide, secara umum, terletak di permukaan. Ada dua aplikasi web serupa dalam akses terbuka: RainBio dan Linear Diagram Generator , yang kedua menggunakan prinsip yang persis sama dengan tambang. (Para penulis juga menulis artikel 40 halaman , yang secara eksperimental membandingkan apa yang lebih baik dirasakan - garis horizontal atau vertikal, tipis atau tebal, dll. Bahkan menurut saya artikel itu adalah yang utama bagi mereka, dan alat itu sendiri hanyalah tambahan untuk itu. .)

Untuk membandingkan dua aplikasi ini dengan paket saya, kami kembali menggunakan contoh dengan kata-kata. Anda dapat memutuskan sendiri opsi mana yang lebih mudah dibaca dan informatif.

Rainbio


Generator Diagram Linier


Supervenn

Pendekatan lain

Kita tidak bisa tidak menyebutkan proyek UpSet , yang ada sebagai aplikasi web dan paket untuk R dan Python. Prinsip dasar dapat dipahami dengan melihat tampilan data genom pisang. Grafik dipotong ke kanan, hanya 30 persimpangan dari 62 yang ditampilkan:



Menariknya, jika Anda menggunakan supervenn untuk mengurutkan kolom berdasarkan lebar dan membuat kolom sama dengan menggunakan opsi penyelarasan lebar, Anda akan mendapatkan hal yang hampir sama, meskipun ini tidak segera terlihat. Yang hilang hanyalah garis-garis vertikal dengan ukuran persimpangan, alih-alih hanya ada angka di bagian bawah grafik:



Saat menulis teks ini, saya mencoba menggunakan versi Python dari UpSet, tetapi saya menemukan bahwa paket tersebut belum diperbarui sejak 2016, dokumentasi tidak menjelaskan format input dengan cara apa pun, dan test case macet dengan kesalahan. Versi web berfungsi, ia memiliki banyak fungsi tambahan yang bermanfaat, tetapi bekerja dengannya cukup sulit karena cara memasukkan data yang rumit.

Akhirnya, gambaran yang menarik dari teknik visualisasi yang diatur tersedia online . Tidak semuanya diimplementasikan sebagai alat perangkat lunak. Berikut ini beberapa gambar untuk menarik perhatian Anda:




Saya sangat tertarik dengan metode Bubble Sets (baris bawah), yang memungkinkan Anda untuk menampilkan set kecil di atas pengaturan unsur-unsur di pesawat. Ini bisa nyaman, misalnya, ketika elemen-elemen dilampirkan pada sumbu waktu (a) atau ke peta (b). Sejauh ini, metode ini telah diimplementasikan hanya di Jawa dan JavaScript (tautannya ada di halaman penulis), dan akan lebih bagus jika seseorang melakukan porting ke Python.

Saya mengirim surat dengan deskripsi singkat tentang proyek kepada penulis UpSet dan ulasannya dan menerima ulasan yang baik. Dua dari mereka bahkan berjanji untuk memasukkan supervenn dalam ceramah mereka tentang visualisasi set.

Kesimpulan

Jika Anda ingin menggunakan paket, ini tersedia di GitHub dan di PyPI: pip install supervenn . Saya akan berterima kasih atas komentar tentang kode dan penggunaan paket, untuk ide dan kritik. Saya akan sangat senang membaca rekomendasi tentang cara meningkatkan algoritma permutasi kolom untuk ukuran besar$$$N$ , dan tips tentang cara menulis tes untuk fungsi charting.

Terimakasih atas perhatiannya!

Referensi

1. John Venn. Pada representasi diagram dan mekanis dari proposisi dan penalaran . The London, Edinburgh dan Dublin Philosophical Magazine, Juli 1880.

2. J.-B. Lamy dan R. Tsopra. RainBio: Visualisasi proporsional dari set besar dalam biologi . Transaksi IEEE pada Visualisasi dan Grafik Komputer, doi: 10.1109 / TVCG.2019.2921544.

3. Peter Rodgers, Gem Stapleton dan Peter Chapman. Visualisasi Set dengan Diagram Linear . Transaksi ACM di Komputer Manusia Interaksi 22 (6) hal. 27: 1-27: 39 September 2015. doi: 10.1145 / 2810012.

4. Alexander Lex, Nils Gehlenborg, Hendrik Strobelt, Romain Vuillemot, Hanspeter Pfister
UpSet: Visualisasi Set Intersecting Set. Transaksi IEEE pada Visualisasi dan Grafik Komputer (InfoVis'14), 2014.

5. Bilal Alsallakh, Luana Micallef, Wolfgang Aigner, Helwig Hauser, Silvia Miksch dan Peter Rodgers. The-of-the-Art of Set Visualisasi . Forum Grafik Komputer. Volume 00 (2015), nomor 0 hlm. 1–27 10.1111 / cgf.12722.

6. Christopher Collins, Gerald Penn dan Sheelagh Carpendale. Bubble Sets: Mengungkap Hubungan Set dengan Isocontour atas Visualisasi yang Ada . IEEE Trans. tentang Visualisasi dan Grafik Komputer (Proc. IEEE Conf. on Visualization Information), vol. 15, iss. 6, hlm. 1009−1016, 2009.