Нередки случаи, когда требуется определить набор свойств вновь созданного объекта. Например, это может касаться сайта с описаниями товаров, фильмов (и, соответственно, для каждого объекта необходим набор тегов или свойств). Вообще, это касается любого хранилища описаний любых объектов, которые предполагают наличие свойств и возможности сравнивать объекты между собой по принципу «похож или непохож».
Итак, дано: на сайте есть готовый набор объектов, свойства для которых определены и проверены. И добавляется новый объект, о котором мы ничего не знаем, но посетители сайта могут судить. Задача: сделать так, чтобы администратору не надо было добавлять вручную требуемые свойства, а все делалось само, руками посетителей сайта.
Для наглядности, будем считать, что у нас – сайт, посвященный сотовым телефонам. На сайте (для простоты) – 5 телефонов, обладающих следующими условными свойствами (свойства пронумерованы для удобства):
A> Виброзвонок (1), Радио (2), Громкая связь (3), Фонарик (4)
B> Виброзвонок (1), Громкая связь (3), MP3- плеер (5)
C> Фонарик (4), Неразборный корпус (6), MP3- плеер (5)
D> Неразборный корпус (6), TV (7)
E> MP3- плеер (5), TV (7), Радио (2)
И добавляется шестой аппарат, про который администратор сайта ничего не знает, в отличие от посетителей. Пусть это будет аппарат с Радио (2) и TV (7).
В нашем примере существует всего 7 возможных атрибутов у объекта. Новому объекту мы присваиваем все возможные свойства.
Следующим этапом мы должны определить только те свойства, которыми объект действительно обладает, для этого мы предлагаем посетителям сайта выбрать степень сходства между известным нам объектом и новым (предлагаем случайно выбранный объект). Сходство оценивается по шкале от 0 до 2х, где 0 – «не похоже», 1- «есть что-то общее» и 2- «очень похоже». Можно сделать более растянутую шкалу, но для простоты, здесь применяется именно эта.
При сравнении мы учитываем только те свойства, которые есть и у нового, и у известного нам объекта. Если пользователь выбрал степень схожести «очень похоже», то мы прибавляем 1 к «весу» пересекающихся свойств у неизвестного объекта. При «есть что-то общее» прибавляем 0.5, а если «не похожи», то вычитаем 1.
Я набросал небольшой пример на PHP, иллюстрирующий работу алгоритма.
// насколько объекты похожи на новый
$known_objects = array ('a'=>1, 'b'=>0, 'c'=>0, 'd'=>1, 'e'=>2);
//объекты и их свойства
$a = array (1,2,3,4);
$b = array (1,3,5);
$c = array (4,6,5);
$d = array (6,7);
$e = array (5,7,2);
//для каждого свойства нового объекта мы определяем вес, для начала он = 1
$new_object = array (1=>1, 2=>1, 3=>1, 4=>1, 5=>1, 6=>1, 7=>1);
//множитель, чем меньше значение, тем более плавно изменяются веса
const K_MUL = 0.1;
$s = array_keys($known_objects);
//100 итераций, сравниваем со случайно выбранным объектом
for ($i=0; $i<100; $i++) {
shuffle($s);
$new_object = cmp($new_object, $$s[0], $known_objects[$s[0]]);
}
//нормализуем веса
process($new_object);
//выводим результат
print_r($new_object);
//нормализуем веса и удаляем свойства с весом меньше 0.5
function process(&$new_object) {
$max = 0;
foreach ($new_object as $k=>$v) {
if ($v > $max) {
$max = $v;
}
}
$mv = 1.1;
if ($max > $mv) {
$div = (1 / $max);
foreach ($new_object as $k=>$v) {
$new_object[$k] *= $div;
}
}
foreach ($new_object as $k=>$v) {
if ($new_object[$k] <0.5) {
unset($new_object[$k]);
}
}
}
//сравниваем неизвестный ($a) и известный ($b) объект
function cmp($a,$b,$val) {
switch ($val) {
case 0: {
$add = -0.5;
break;
}
case 1: {
$add = 0.5;
break;
}
case 2: {
$add = 1;
break;
}
}
foreach ($a as $k=>$v) {
if (in_array($k, $b)) {
$a[$k] += $add * K_MUL;
}
}
return $a;
}
Код очень примитивный, но дает понимание работы.
На выходе мы получаем что-то вроде такого массива, где ключ- номер свойства, а значение = вычисленный вес
Array
(
[2] => 1,
[7] => 0.944444
)
Как показывают тесты, точность зависит от количества итераций, при этом, минимальное кол-во итераций = 50 (соотносится с K_MUL * 0.5, где 0.5 – минимальный шаг изменения веса).
Добавление известных объектов с разной степенью похожести улучшает определение свойств неизвестного объекта.
Человеческий фактор
Рассмотренный нами случай является идеальным. Но что делать, если, допустим, некоторый процент пользователей отвечает неточно? Для моделирования подобной ситуации можно добавить рандомизацию ответов, добавив в функцию cmp следующую строку:
If (rand(0,100) > 70) {
$val = rand(0,2);
}
Мы моделируем ситуацию, в которой каждый третий ответ является случайным (может соответствовать истине, а может, и нет).
Как показали тесты, при увеличении количества итераций в 3 раза (те самые 1/3 потенциально неправильных ответов), мы получаем все тот же массив 2 и 7, и лишь изредка появляются флуктуации, которые можно отсеять, изменив порог в функции «process»
Array (
[2] => 0.98648648648649 – верное свойство
[6] => 0.50675675675676 — флуктуация
[7] => 1 – верное свойство
)
Возможные улучшения
Первое улучшение – это устранение погрешностей. Имея достаточное количество сравнений, мы можем исключить результаты, которые не вписываются в общую массу, и тем самым можем повысить точность.
Второе улучшение: изменение веса голоса у пользователей.
Пользователи, чьи ответы совпадают с ответом большинства, получают больший вес собственного голоса. Соответственно, при последующих голосованиях за «похожесть», голос такого пользователя будет иметь больший вес, что тоже должно уменьшить разброс.
Важное дополнение: предполагается, что подобный алгоритм функционирует в дружественной среде, в которой пользователи могут ошибаться, но делают это не намеренно и не массово.
Буду рад вопросам, предложениям и просто комментариям.
Автор: Dan11aM
