マラソンマッチというのは10日間ぐらいの期間で問題を分析しコードを書いてスコアを競う競技です。
今回ので3回めのマラソンマッチ参加。
序盤は上位にいられたのですが、終盤は失速してしまいましたorz
順位表
問題の説明
問題の内容は与えられたデータ点(\(x, y\)の2次元の値)の6つのラベルへの分類でした。
与えられたデータ点はいくつかのマップごとに与えられています。
ラベルは'0'、'0 or 1'、'1'、'1 or 2'、'2'、'>2'となっていて、マップ内のデータ点は\(z = x - y\)の値の昇順に6つのラベルに分けられています。
問題文にも書いてあるのですが、マップごとに大きく値とラベルの傾向が異なっています。
また問題文にはラベル'2'の時の\(z\)の値はラベル'1'の\(z\)に\(\log 2\)を足したもの(ただし誤差あり)、などというような関係式が書かれていましたが、私はこの情報はまったく使いませんでした。
使った手法
分類の手法としては\(k\)近傍法を使いました。
\(k\)近傍法は予測したいデータと距離の小さい(類似度の高い)トレーニングデータ\(k\)個のラベルの多数決で予測を行います。
他の機械学習の手法と比較するとあまり性能はよくありませんが、データ同士の距離が定義できれば簡単に使える手法で、非線形な多クラス分類が扱えて、必要なパラメータの数も多くありません。
今回のタスクでは、2段階の\(k\)近傍法を用いました。
マップごとに大きく値の傾向が異なっているため、まずマップに対して\(k\)近傍法を行い、次にそれらのマップの一番近いデータ点について\(k\)近傍法を行いました。
マップの距離を求める際に使ったマップごとのベクトルは、マップ内のデータ点の値の範囲(\(z\)の1次元)を適当に区切ってその頻度に怪しげなチューニングをして用いました。
感想
マラソンマッチで上位の方に行けたのは初めてだったので嬉しかったです
重い学習をしようと思うと途端に時間が足りなくなって困りました
やっぱりPythonでは速度的につらいんですかね
色々と実験している最中は関数に分けずにいじくり回していたので、途中から「もっと早く関数化しておくべきだった」と後悔しながらの作業になってしまいました。
マップ同士の距離を求める部分で距離学習やスコアを直接的に回帰などで学習してどうにかならないかなと思ったのですが、あまりうまくいきませんでした。
マラソンマッチは1つのファイルで提出しないといけないため、既存のライブラリなどを使うのが非常にめんどくさくて諦めました。
ソースコード
import sys import collections import math import heapq import bisect def euclid(v1, v2): denominator1 = math.sqrt(sum([v * v for v in v1.values()])) denominator2 = math.sqrt(sum([v * v for v in v2.values()])) if denominator1 == 0: denominator1 = 1 if denominator2 == 0: denominator2 = 1 key = set(v1.keys()) key.update(v2.keys()) return math.sqrt(sum([(v1[c] / denominator1 - v2[c] / denominator2) ** 2 for c in key])) class AlleleClassifier(object): def readTrain(self, train): data_train = collections.defaultdict(list) data_raw = [] for line in train: line = line.strip() sp = line.split(',') z = float(sp[2]) - float(sp[3]) label = sp[4] data_train[sp[0]].append((z, label)) data_raw.append(z) for k in data_train: data_train[k].sort() return (data_train, data_raw) def getThreshold(self, data_raw, D): data_raw.sort() L_raw = len(data_raw) threshold = [data_raw[i * (L_raw / D)] for i in xrange(1, D)] return threshold def getFeatureOfTrain(self, data_train, RAT, threshold): freq_train = collections.defaultdict(collections.Counter) for m_data in data_train: for z, label in data_train[m_data]: freq_train[m_data]['int' + str(int(z))] += 1 freq_train[m_data]['int' + str(int(z + 0.3))] += 1 index = bisect.bisect_right(threshold, z) freq_train[m_data][index] += 1 * RAT freq_train[m_data][index + 1] += 0.35 * RAT freq_train[m_data][index - 1] += 0.35 * RAT freq_train[m_data][index + 2] += 0.05 * RAT freq_train[m_data][index - 2] += 0.05 * RAT return freq_train def getFeatureOfTest(self, test, RAT, threshold): data_test = [] freq_test = collections.defaultdict(collections.Counter) maps = set() for line in test: line = line.strip() sp = line.split(',') maps.add(sp[0]) z = float(sp[2]) - float(sp[3]) data_test.append((sp[0], z)) freq_test[sp[0]]['int' + str(int(z))] += 1 freq_test[sp[0]]['int' + str(int(z + 0.3))] += 1 index = bisect.bisect_right(threshold, z) freq_test[sp[0]][index] += 1 * RAT freq_test[sp[0]][index + 1] += 0.35 * RAT freq_test[sp[0]][index - 1] += 0.35 * RAT freq_test[sp[0]][index + 2] += 0.05 * RAT freq_test[sp[0]][index - 2] += 0.05 * RAT return (data_test, freq_test, maps) def getNearestMap(self, n, freq_train, freq_test, maps, func): nearest = {} for k in maps: rank = [] for kk in freq_train: rank.append((func(freq_test[k], freq_train[kk]), kk)) nearest[k] = heapq.nsmallest(n, rank) return nearest def predict(self, target, inst, data_train, data_test, nearest): est = collections.Counter() candidate_whole = [] for sim, m in nearest[target]: ind = bisect.bisect_left(data_train[m], (inst, 0)) candidate = data_train[m][max(0, ind - 2): min(len(data_train[m]), ind + 3)] diff = map(lambda x: (abs(inst - x[0]), x[1]), candidate) diff.sort() for z in diff[:1]: candidate_whole.append(z) candidate_whole.sort() for z in candidate_whole[:5]: est[z[1]] += 1 temp = '0' m_v = -1 for eee in sorted(est): if m_v <= est[eee]: m_v = est[eee] temp = eee if m_v == est['0']: temp = '0' return temp def classify(self, train, test): data_train, data_raw = self.readTrain(train) threshold = self.getThreshold(data_raw, 20) RAT = 1.2 freq_train = self.getFeatureOfTrain(data_train, RAT, threshold) data_test, freq_test, maps = self.getFeatureOfTest(test, RAT, threshold) nearest = self.getNearestMap(7, freq_train, freq_test, maps, euclid) result = [] for k, inst in data_test: result.append(self.predict(k, inst, data_train, data_test, nearest)) return tuple(result)
