http://pkolt.ru/pages/168/
Определить на сколько отличаются(похожи) объекты
Практическое применение:
Рассмотрим 2 алгоритма для определения похожести Эвклидово расстояние и коэффициент корреляции Пирсона.
Результат работы функции число от 0 до 1, чем больше число тем больше общего между Гвидо и Ларри.
- списки продуктов, каталоги товаров(поиск схожих товаров)
- профили пользователей, сайты знакомств(поиск близких по критериям людей)
Рассмотрим 2 алгоритма для определения похожести Эвклидово расстояние и коэффициент корреляции Пирсона.
Эвклидово расстояние
В примере дается список людей и их оценки разным языкам программирования, по шкале от 0 до 5. Причем понятно что Гвидо больше нравится Python, а Ларри - Perl. Просто потому что каждый из них автор этого языка.Результат работы функции число от 0 до 1, чем больше число тем больше общего между Гвидо и Ларри.
01 | from math import sqrt |
02 |
03 | values = { |
04 | 'Guido van Rossum': {'python': 5.0, 'php': 1.2, 'ruby': 4.0, 'perl': 2.8}, |
05 | 'Larry Wall': {'python': 5.0, 'php': 1.2, 'ruby': 4.0, 'perl': 5.0}, |
06 | } |
07 |
08 |
09 | def euclidean_distance(values, obj1, obj2): |
10 | """ |
11 | Эвклидово расстояние, |
12 | дианазон значений результата от 0 до 1 |
13 | """ |
14 | if isinstance(values, dict) and values.has_key(obj1) andvalues.has_key(obj2): |
15 | signs = {} # признаки оценки |
16 | # отбор признаков, присутствующих у обоих |
17 | for key, value in values[obj1].items(): |
18 | if key in values[obj2]: |
19 | signs[key] = (values[obj1][key], values[obj2][key]) |
20 | # если признаков нет, вернуть 0 |
21 | return 0 if not signs else 1/(1+sqrt(sum([pow(v1-v2, 2) for (v1,v2) insigns.values()]))) |
22 | else: |
23 | raise ValueError |
24 |
25 | print euclidean_distance(values, 'Guido van Rossum', 'Larry Wall') |
26 | # 0.3125 |
Коэффициент корреляции Пирсона
01 | from math import sqrt |
02 |
03 | values = { |
04 | 'Guido van Rossum': {'python': 5.0, 'php': 1.2, 'ruby': 4.0, 'perl': 2.8}, |
05 | 'Larry Wall': {'python': 5.0, 'php': 1.2, 'ruby': 4.0, 'perl': 5.0}, |
06 | } |
07 |
08 | def pearsons_correlation_coefficient(values, obj1, obj2): |
09 | """ |
10 | Коэффициент корреляции Пирсона |
11 | диапазон значений результата от -1 до 1 |
12 | """ |
13 | if isinstance(values, dict) and values.has_key(obj1) andvalues.has_key(obj2): |
14 | signs = [] # признаки оценки |
15 | # отбор признаков, присутствующих у обоих |
16 | for key, value in values[obj1].items(): |
17 | if key in values[obj2]: |
18 | signs.append(key) |
19 | # если признаков нет, вернуть 0 |
20 | if not signs: return 0 |
21 | # количество признаков |
22 | n = len(signs) |
23 | # сумма знач.всех признаков |
24 | sum1 = sum([values[obj1][s] for s in signs]) |
25 | sum2 = sum([values[obj2][s] for s in signs]) |
26 | # сумма квадратов знач.всех признаков |
27 | sum1Sq = sum([pow(values[obj1][s],2) for s in signs]) |
28 | sum2Sq = sum([pow(values[obj2][s],2) for s in signs]) |
29 | # сумма произведений знач.всех признаков |
30 | pSum = sum([values[obj1][s]*values[obj2][s] for s in signs]) |
31 | # Коэффициент Пирсона |
32 | num = pSum-(sum1*sum2/n) |
33 | den = sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n)) |
34 | if den == 0: return 0 |
35 | r = num/den |
36 | return r |
37 | else: |
38 | raise ValueError |
39 |
40 | print pearsons_correlation_coefficient(values, 'Guido van Rossum', 'Larry Wall') |
41 | # 0.79850420561 |
Как видно из примера коэффициент Пирсона дает более объективный результат, но существуют и другие математические формулы.
No comments:
Post a Comment