ML-Блиц: разбор задач первого квалификационного раунда
В реализации я буду использовать метод Уэлфорда, т.к. он нравится мне больше, чем вычисления по «стандартным» формулам. Кроме того, я не буду использовать numpy и какие-либо другие библиотеки, чтобы продемонстрировать, что для получения решения достаточно знания элементарных конструкций языка python.
Итак, нам понадобится уметь инкрементально вычислять среднее и сумму квадратов отклонений. Для этого опишем два класса:
class MeanCalculator:
def __init__(self):
self.Count = 0.
self.Mean = 0.
def Add(self, value, weight = 1.):
self.Count += weight
self.Mean += weight * (value - self.Mean) / self.Count
def Remove(self, value, weight = 1.):
self.Add(value, -weight)
class SumSquaredErrorsCalculator:
def __init__(self):
self.MeanCalculator = MeanCalculator()
self.SSE = 0.
def Add(self, value, weight = 1.):
curDiff = value - self.MeanCalculator.Mean
self.MeanCalculator.Add(value, weight)
self.SSE += weight * curDiff * (value - self.MeanCalculator.Mean)
def Remove(self, value, weight = 1.):
self.Add(value, -weight)
Теперь нужен класс для хранения и обработки обучающей выборки. Для начала опишем его поля и метод ввода:
class Instances:
def __init__(self):
self.Items = []
self.OverAllSSE = SumSquaredErrorsCalculator()
def Read(self):
fin = open('stump.in')
for line in fin.readlines()[1:]:
x, y = map(float, line.strip().split())
self.Items.append([x, y])
self.OverAllSSE.Add(y)
self.Items.sort()
Одновременно с вводом данных мы сразу формируем структуру SumSquaredErrorsCalculator для всех объектов выборки. После загрузки всей выборки мы сортируем её по неубыванию значений признаков.
Теперь самое интересное: метод для нахождения оптимальных значений параметров.
Начнём с инициализации. В начальном состоянии все объекты находятся в правой подвыборке. Тогда параметр 
может быть равен чему угодно, параметр 
равен средней величине ответов во всей выборке, а параметр 
таков, чтобы все объекты выборки находились правее него.
Кроме того, инициализируем переменные left и right — они будут хранить статистики для левой и правой подвыборок, соответственно.
left = SumSquaredErrorsCalculator()
right = self.OverAllSSE
bestA = 0
bestB = right.MeanCalculator.Mean
bestC = self.Items[0][0]
bestQ = right.SSE
Теперь переходим к инкрементальному алгоритму. Будем обрабатывать элементы выборки по одному. Каждый элемент переносится в левое подмножество. Затем нужно проверить, что соответствующее разбиение действительно существует — то есть, значение признака отличается от значения признака следующего объекта.
for i in range(len(self.Items) - 1):
item = self.Items[i]
nextItem = self.Items[i + 1]
left.Add(item[1])
right.Remove(item[1])
if item[0] == nextItem[0]:
continue
a = left.MeanCalculator.Mean
b = right.MeanCalculator.Mean
c = (item[0] + nextItem[0]) / 2
q = left.SSE + right.SSE
if q < bestQ:
bestA = a
bestB = b
bestC = c
bestQ = q
Теперь осталось только скомпоновать код для получения решения:
instances = Instances()
instances.Read()
a, b, c = instances.BestSplit()
print >> open('stump.out', 'w'), a, b, c
Замечу, что представленное решение на python действительно принимается системой, но оно подходит к верхней границе по времени решения: самые большие тесты требует порядка 800 миллисекунд на исполнение. Конечно, с использованием дополнительных библиотек можно добиться намного более впечатляющей производительности.
Поэтому я также реализовал предложенный алгоритм на C++. Это решение затратило в худшем случае 60 миллисекунд на один из тестов.
