Latar belakang
Sekitar 15 tahun yang lalu, saya belajar tentang keberadaan
jalur mendasar - kelompok yang dapat membedakan ruang topologi dengan konektivitas. Selebihnya bukan tentang mereka, tetapi mereka datang dengan ide regressor dan classifier - tanpa optimasi berdasarkan penyimpanan sampel.
Rincian lebih lanjut.
Gagasan dan dugaan
Karena jalur mendasar adalah loop dari titik yang dipilih, dan kesetaraan pada mereka, lalu bagaimana loop tersebut dapat ditemukan dalam data? Dan apakah itu perlu?
Gagasan ini datang dengan analogi dengan algoritma KNN dan SVM - "analog". Bagaimana jika loop diganti dengan "pipa", sebuah silinder dari satu titik data ke titik data lainnya, dan apa yang jatuh ke dalam pipa ditetapkan ke kelas yang sama dengan dua titik jalur ini (tidak lagi mendasar)? "Pipa" harus memiliki lebar sedemikian untuk mengklasifikasikan kelas dengan benar ... dan dalam batas itu adalah garis lurus. Jarak ke titik baru yang tidak diketahui harus minimal di sepanjang jalan, maka kita dapat menghubungkannya ke kelas yang sama dengan jalur.
Regressor dapat dibangun dengan memproyeksikan titik pada garis lurus antara titik data, dan menginterpolasi nilai target yang terkait dengan titik data dengan rasio yang sama di mana proyeksi membagi jalur.
Metode konstruksi ini mengingat seluruh sampel dan memberikan prediksi yang akurat pada set pelatihan.
Implementasi primitif
Bagaimana cara membangun jalan? Saya mengambil elemen maksimum sesuai dengan norma, dan mulai mencari yang paling dekat dengannya, menghubungkan jalur yang diterima. Pada akhirnya - ditutup dengan permulaan (tentu saja bisa diperdebatkan, tapi seperti itu).
PengukurIni adalah versi kode yang paling pertama, lihat buku catatan yang diperbarui di bawah ini.class PathMachine(BaseEstimator): def __init__(self, norm=np.linalg.norm, classify=False): self.norm = norm self.classify = classify def find_start(self, X): index_max = None value_max = -np.inf for index, x in enumerate(X): value = self.norm(x) if value > value_max: index_max = index value_max = value return index_max def find_next(self, point, target, X, y): index_min = None value_min = np.inf for index, x in enumerate(X): if self.classify and (y[index] != target): continue value = self.norm(x - point) if value < value_min: index_min = index value_min = value return index_min def fit(self, X, y): X = np.copy(X) y = np.copy(y).flatten() self.paths = {} if self.classify else [] start_index = self.find_start(X) start_value = X[start_index] start_target = y[start_index] X = np.delete(X, start_index, axis=0) y = np.delete(y, start_index, axis=0) while len(X) > 0: next_index = self.find_next(start_value, start_target, X, y) if self.classify and next_index is None: start_index = self.find_start(X) start_value = X[start_index] start_target = y[start_index] continue next_target = y[next_index] if self.classify: if not next_target in self.paths: self.paths[next_target] = [] self.paths[next_target].append({ 'start': start_value, 'next': X[next_index] }) else: self.paths.append({ 'start': start_value, 'next': X[next_index], 'value': start_target, 'target': next_target }) start_value = X[next_index] start_target = y[next_index] X = np.delete(X, next_index, axis=0) y = np.delete(y, next_index, axis=0) if self.classify: self.paths[start_target].append({ 'start': start_value, 'next': self.paths[start_target][0]['start'] }) else: self.paths.append({ 'start': start_value, 'next': self.paths[0]['start'], 'value': start_target, 'target': self.paths[0]['target'] }) return self def predict(self, X): result = [] for x in X: if self.classify: predicted = None min_distance = np.inf for target in self.paths: for path in self.paths[target]: point = x - path['start'] line = path['next'] - path['start'] if np.allclose(self.norm(line), 0): continue direction = line / self.norm(line) product = np.dot(point, direction) projection = product * direction distance = self.norm(projection - point) if distance < min_distance: predicted = target min_distance = distance result.append(predicted) else: predicted = None min_distance = np.inf for path in self.paths: point = x - path['start'] line = path['next'] - path['start'] if np.allclose(self.norm(line), 0): continue direction = line / self.norm(line) product = np.dot(point, direction) projection = product * direction parameter = np.sign(product) * self.norm(projection) /\ self.norm(line) distance = self.norm(projection - point) if distance < min_distance: predicted = (1 - parameter) * path['value'] +\ parameter * path['target'] min_distance = distance result.append(predicted) return np.array(result) def score(self, X, y): if self.classify: return f1_score(y.flatten(), self.predict(X), average='micro') else: return r2_score(y.flatten(), self.predict(X))
Secara teoritis (dan secara teknis), dimungkinkan untuk membuat predict_proba dengan cara yang sama - seperti 1 - jarak dinormalisasi. Tapi saya tidak datang dengan kesempatan untuk benar-benar menguji probabilitas, jadi ...
Beberapa tes
Saya mulai dengan Boston Housing and Iris yang klasik, dan untuk baseline saya memilih Ridge dan LogisticRegression. Nah, bagaimana, bagaimana jika.
Secara umum, saya sarankan melihat
notebook jupyter .
Singkatnya: regressor bekerja lebih buruk, classifier bekerja lebih baik.
pembaruan: setelah StandardScaler, regressor bekerja lebih baik.Saya juga mengendarai set data sintetis. Secara umum ada sesuatu di hutan, yaitu kayu bakar.
Tapi ini diperhatikan:
- Regressor bekerja dengan baik di ruang dimensi kecil,
- Baik regressor dan classifier peka terhadap noise, mulai dari ambang tertentu,
- Regressor, tidak seperti garis, diduga multimodality (di Boston Housing),
- Dengan konstruksi, classifier bekerja dengan baik (terbaik dari semua ... :)) pada satu set bulan yang tidak terpisahkan secara linear.
Kesimpulan, Pro, Kontra, dan Penerapan
Saya pribadi tidak melihat keuntungan apa pun dalam implementasi saat ini. Baik secara teknis maupun matematis. Mungkin ini dapat dimodifikasi menjadi sesuatu yang lebih masuk akal. Karena itu, saya juga tidak melihat penerapan tertentu. Apakah mungkin untuk bekerja dengan data yang sangat kecil tanpa preprocessing ...
Ada banyak kelemahan: diperlukan untuk menyimpan seluruh dataset dalam memori, kemampuan generalisasi dibangun di atas ekstrapolasi, hyperparameter utama dan satu-satunya - norma - tidak dapat menerima seleksi-enumerasi khusus.
Tetapi, bagi saya, yang diterima adalah kejutan, yang saya putuskan untuk dibagikan di sini.