Dalam hal ini kami akan mencoba memahami di mana seseorang tidak boleh menggunakan algoritma KNN dalam format Tanya Jawab
T. Apa asumsi dasar KNN?
Jawab. Diasumsikan bahwa tetangga terdekat mempunyai label serupa
Jadi di manakah sesuatu akan rusak? — ketika asumsinya tidak terpenuhi, yaitu tidak ada tetangga terdekat pada suatu titik tertentu.
T. Bagaimana hal itu bisa terjadi?
Itu bisa terjadi ketika setiap titik saling berjauhan?
T. Oke, kapan hal itu akan terjadi?
Kami akan mencoba menjawab pertanyaan ini dengan mengkorelasikan kedekatan dengan jarak dalam hypercube imajiner di bawah.
Bayangkan kita memiliki n titik data yang terdistribusi secara merata di seluruh unit hiperkubus dengan dimensi d . Sekarang, mari kita ambil sebuah kubus kecil dengan panjang l di dalam kubus satuan ini & asumsikan bahwa kubus tersebut berisi k poin. Kami berasumsi bahwa k titik tersebut berada di dekatnya. Kita akan menganalisis kasus dimana k titik pada hiperkubus kecil dengan sisi lakan lebih jauh
Q. Berapakah volume kubus yang panjang sisinya l dalam dimensi d?
Untuk kubus tiga dimensi maka akan menjadi l kubus. Demikian pula untuk hiperkubus dengan panjang sisi l& dalam dimensi d, volume hiperkubus tersebut adalah l pangkat d
Q. Volume ini setara dengan apa?
Karena n titik terdistribusi secara merata di seluruh unit hiperkubus, & karena kita berasumsi bahwa hiperkubus yang lebih kecil ini berisi k titik, volumenya harus setara dengan k/n
T. Jika kita ingin mendapatkan 10 tetangga terdekat dalam kumpulan data dengan 1000 poin, apa dampak dimensi yang berbeda?
Ketika jumlah dimensi bertambah, panjang sisi hiperkubus bertambah & mendekati satuan panjang, yaitu kubus satuan dimensi yang berisi n titik data.
T. Jadi apa masalahnya?
Artinya seiring bertambahnya dimensi, 10 poin yang kita mulai, hampir didistribusikan ke seluruh hyper cube. Jadi saat ini tidak ada gagasan tentang kedekatan & mematahkan asumsi algoritma
T. Bisakah kita meningkatkan ukuran kumpulan data untuk mengatasi masalah ini?
Di sini ukuran data yang dipertimbangkan adalah 1000 titik data & tetangga terdekat sebanyak 10, misalkan kita menetapkan panjang sisi tertentu l sebagai 0,1 maka jumlah titik yang diperlukan untuk mempertahankan l tersebut. Kemudian ukuran data harus ditingkatkan pangkat 10, yang tumbuh terlalu cepat & praktis tidak mungkin menemukan kumpulan data sebesar itu
Kesimpulan : Karena dimensi tinggi mematahkan asumsi KNN, kita tidak boleh menggunakan KNN untuk kumpulan data berdimensi tinggi
Referensi:
Saya sangat berterima kasih kepada Kilian Weinberger atas ceramahnya yang luar biasa tentang ML. Pemikiran yang disajikan di sini merupakan rangkuman dari apa yang saya pahami dari salah satu kuliah »di KNN
