Классификатор kNN

[overmes]

спасибо за статью
хочу узнать ваше мнение по следующему вопросу:
делаю небольшой свой рекомендательный сервис, в статье на Википедии одним из алгоритмов для этого является kNN

Первоначальную разбивку на группы собираюсь делать методом к-средних, тк нет первоначальных групп
Чем лучше определять принадлежность к данной группе? Методом kNN или Расстоянием до центра элипсойда, который получается при k-means? или я делаю какую-то ерунду?

[0x0FFF]

Чаще всего в рекомендательных системах используется алгоритм коллаборативной фильтрации, я рекомендую для начала ознакомиться с ним (википедия). В качестве меры сходства можно начать с косинусной меры:


В данном случае kNN — это просто способ отфильтровать k пользователей с наиболее похожими вкусами, чтобы применять алгоритм коллаборативной фильтрации только к ним

k-Means в данном случае может быть использован для предварительного сегментирования пользователей, в том случае, если производительность системы не позволяет для каждой из рекомендаций рассчитывать меру сходства со всеми пользователями: можно будет ограничиться одним кластером

Итого, ваш алгоритм может выглядеть следующим образом: регулярно (раз в день / N дней) производится кластеризация пользователей. При необходимости вычисления рекомендации производится вычисление косинусной меры сходства только с пользователями, находящимися в том же кластере, что и рассматриваемый. Из получившихся мер сходства выбирается k лучших, для них и применяется коллаборативная фильтрация.
При такой реализации нужно обратить внимание на количество кластеров и размер k — эти параметры отвечают за баланс между скоростью работы и точностью рекомендации.
Также можно хранить предрасчитанные стандартные рекомендации для новых пользователей, а для пользователей, которые уже имеют покупки, но не участвовали в кластеризации, можно расчитать сначала меру сходства с центроидами, полученными в ходе k-means, таким образом определив их кластер

За примерами стоит обратиться к книге из п.5 списка литературы к статье

[overmes]

да, пользователей порядка 500к
спасибо, то что нужно

[overmes]

попробовал косинусную метрику:

для пользователя 6309

__Id_|__Косинусная метрика_|_Евклидово расстояние
(11382, (0.9945617655513243, 6.0))
(25881, (0.9946889722415817, 10.44030650891055))
(32657, (0.9948579893001871, 4.58257569495584))
(11642, (0.9949290831814581, 4.898979485566356))
(29796, (0.9950464316093013, 5.656854249492381))
(31417, (0.9951124675317691, 6.782329983125268))
(40530, (0.9952102629001573, 4.58257569495584))
(8311, (0.9952136477352348, 5.830951894845301))
(37772, (0.995641393209143, 4.47213595499958))
(11087, (0.9964597867088298, 4.795831523312719))
(9641, (0.996734136199907, 3.7416573867739413))
(9651, (0.9969863072847556, 30.04995840263344))
(22462, (0.9972173920027746, 3.3166247903554))
(6309, (0.9999999999999999, 0.0))

Почему-то появился объект 9651(третий с конца) хотя у него оценки сильно разнятся
возможно я ошибся в коде:

[overmes]

миссклик

код

def getSimilarity(userA, userB):
    if len(userA) < len(userB):
        lessList = userA
        moreList = userB
    else:
        lessList = userB
        moreList = userA
    mulSum = 0
    quadSum1 = 0
    quadSum2 = 0
    count = 0
    for key, val1 in lessList.items():
        if key in moreList:
            val1 = int(val1)
            val2 = int(moreList[key])
            mulSum += val1 * val2
            quadSum1 += val1 * val1
            quadSum2 += val2 * val2
            count += 1
    res = 0
    if mulSum and count > 20:
        res = mulSum / (math.sqrt(quadSum1) * math.sqrt(quadSum2))
    return res

Главный вопрос зачем пользоваться косинусной метрикой, если Евклидово расстояние показывает тоже самое?

[0x0FFF]

ваш код при вычислении длины вектора учитывает только те компоненты, которые являются общими для векторов userA и userB
Как оптимизация для расчета, длину векторов можно вычислить заранее, так как меняется она только при совершении покупки (или просмотра, в зависимости от того, как работает ваша система)

[overmes]

спасибо, я так сделал потому что на википедии сказано:
where Ixy is the set of items rated by both user x and user y
возможно у них ошибка

Попробую с полной длиной, тогда разница с евклидовым расстоянием будет яснее

[0x0FFF]

Там ошибка. Косинусная метрика — это косинус угла между векторами, и в знаменателе должны стоять полные длины
По поводу использования метрик: предположим, у нас есть три вектора (10, 10, 1), (1, 1, 0) и (0, 0, 1). Согласно евклидовому расстоянию наиболее близки вектора 2 и 3, а по косинусной метрике — 1 и 2, что более корректно.
Выбор метрики обусловлен конкретной задачей

[Pastafarianist]

Можно вместо

stat = [0 for i in range(numberOfClasses)]

писать

stat = [0] * numberOfClasses