Типизация (определение свойств) объекта руками пользователей сайта

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

Итак, дано: на сайте есть готовый набор объектов, свойства для которых определены и проверены. И добавляется новый объект, о котором мы ничего не знаем, но посетители сайта могут судить. Задача: сделать так, чтобы администратору не надо было добавлять вручную требуемые свойства, а все делалось само, руками посетителей сайта.

Для наглядности, будем считать, что у нас – сайт, посвященный сотовым телефонам. На сайте (для простоты) – 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 – верное свойство
)

Возможные улучшения

Первое улучшение – это устранение погрешностей. Имея достаточное количество сравнений, мы можем исключить результаты, которые не вписываются в общую массу, и тем самым можем повысить точность.

Второе улучшение: изменение веса голоса у пользователей.
Пользователи, чьи ответы совпадают с ответом большинства, получают больший вес собственного голоса. Соответственно, при последующих голосованиях за «похожесть», голос такого пользователя будет иметь больший вес, что тоже должно уменьшить разброс.

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

Буду рад вопросам, предложениям и просто комментариям.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 16

    0
    А на практике проверялось?
      +1
      Скоро будет проверено на практике. Пишу универсальный «движок» для сравнения фильмов, а-ля «фильм наподобие ___». Планирую выложить его на bitbucket для всех желающих.
        0
        Я добавил фичу вычисляющую реальную среднюю ошибку пользователей. То есть подсосывать время от времени объекты с известными атрибутами и сравнивать насколько оценка пользовталей коррелирует.
          +1
          Да, так можно и вычислять пользователей, которые голосуют неправильно, и скорректировать вес их голоса.
          В итоге может получиться динамическая самоорганизующаяся экспертная система.
            0
            Или пользователи будут ставить метку похожие на два телефона потому что оба телефона красного цвета а не потому что у обоих есть фонарик.
              0
              И такое тоже будет, согласен с вами, и пользователи тут правы — оба телефона красные, и этим они тоже похожи. И кто-то же должен определить что этот телефон — красный, задача администратора — импортировать набор товаров на сайт, он может это делать не глядя, просто проверив что все данные, включая фотографии и начальные описания импортировались верно.

              И если уж обобщать, то все телефона — телефоны, следовательно, между всеми объектами есть нечто общее.

              Однако, я верю в коллективный разум, и в то, что люди определяют похожие свойства не только по внешним параметрам, но и по функциональности.
      0
      Хм, выявим о товаре необходимые свойства по похожести, а кто их заполнит значениями? Как с помощью сравнения о фильме будет заполнена информация об актерах, наградах, сборах, трейлер? Можно ещё примеры практического применения?
        0
        Актеры, сборы, трейлеры — тут вы правы, такая информация нуждается в предварительном заполнении. Но метки- классификаторы содержимого вполне могут проставляться автоматически.

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

        Чем больше меток проставлено изначально для известных объектов, тем точнее типизация.

        Логика тут простая: если объект X похож на объект A и объект B, и не похож на объект C, то, вычисляя пересечения этих объектов, мы получаем подмножество, в которое входит некоторое количество общих свойств. Собственно, это и есть то, что мы вычисляем.
          0
          То есть практичность только в классификации (категоризации)?
          Из первых абзацев статьи складывается картина, что администратор совсем не понимает, что за нечто добавляет на сайт. Может, только название или картинку этого нечто знает, а далее пользователи через сравнения определят, что это нечто автомобиль с турбонадувом X78 и болтиком с криволинейной резьбой в фиксаторе магнитных ускорителей. Ну и сотню других свойств :) Вот и задумался, как же через сравнения о товаре будет добавлена исчерпывающая информация, как будут добавлены уникальные свойства?
            0
            Часть свойств, сами понимаете, невозможно так добавить. Но вот вычислить похожие объекты без муторного забивания их свойств — да, возможно.
            Есть еще, кстати, возможность определять свойства объектов на основе отношения пользователя к ним.
            Например: та же база фильмов. Зарегистрированные пользователи нажимают «нравится». Для каждого пользователя формируется перечень меток фильмов, которые ему нравятся, тем же методом пересечения. Теперь, если пользователь отметил неизвестный нам фильм, мы с некоторой вероятностью можем судить о его содержании и метках. Чем больше пользователей — тем больше точность.
              0
              Думаю вероятность эта будет несильно велика. Более-менее правомерно сделать предположение что если из двух объектов с сильно пересекающимся набором свойств один понравился, то понравится и другой, но вот делать выводу о свойствах одного по тому что понравился другой, очень опрометчиво. Как минимум нужно иметь значительный набор объектов, который понравился одному пользователю, выделить статистически значимое подмножество нравящихся значений свойств для него лично, и уже потом сравнивать оцениваемый объект с этим подмножеством.
                0
                Вы правы, нужен достаточно большой объем данных, и несколько пользователей, поставивших несколько «лайков»
                Чем больше объем информации, тем точнее будет прогноз.

                Про пересечение свойств в «лайках» одного пользователя: я исхожу из того, что у каждого человека есть свой набор предпочтений в, например, фильмах. Если такой человек «лайкнул» штук 20 фильмов, для которых у нас есть хороший набор меток (не просто, например «фантастика», а более подробный, типа: «роботы», «искусственный интеллект», «космос», «андроиды», «путешествия во времени» и т.п.), то мы сможем вычислить набор его предпочтений. Конечно, не все метки будут повторяться, но мы сможем вычислить их наличие и веса.

                Далее, как только несколько пользователей «лайкнут» неизвестный нам фильм, мы сможем пересечь их предпочтения, где-то да они совпадут, вот 100% гарантия.

                Надо только выяснить необходимый порог для этого, чьи голоса учитывать (какой минимальный порог «лайков» для каждого пользователя).
                  +1
                  я исхожу из того, что у каждого человека есть свой набор предпочтений в, например, фильмах.

                  Ложное предположение. Вернее как, человеку могут нравится разные фильмы. Вот есть у него 100 лайкнутых «роботов» и 100 лайкнутых «ниндзя» (причем ни одного «робоы-ниндзя» для простоты) — лайкнул он 201 фильм — это роботы или ниндзя?
                    0
                    Если метки будут скудными, то конечно, мы никак не поймем что человеку нравится. Поэтому я и говорю, что нужен хороший набор меток. Вот, если интересно, на Чобиты (AniDB), типичное описание:
                    Скрытый текст
                    Android
                    Angst
                    Asia
                    College
                    Comedy
                    Conspiracy
                    Earth
                    Ecchi
                    Japan
                    Lingerie
                    Nopan
                    Nosebleed
                    Nudity
                    Original Work: Manga
                    Pantsu
                    Plot Continuity
                    Romance
                    School Life
                    Sci-Fi
                    Seinen
                    Slapstick
                    Sudden Girlfriend
                    Appearance Teacher x Student
                    Time: Future
                    Virtual Reality
                    artificial intelligence
                    beach episode
                    boy meets girl
                    broadcast
                    cropped to 4-3
                    character that only says own name
                    computer
                    Do Androids Dream of Electric Sheep?
                    drama
                    forbidden love
                    grail in the garbage
                    gynoid
                    head
                    patting
                    human-android relations
                    ideal woman
                    male protagonist
                    multiple couples
                    overly cute catchphrase
                    philosophical
                    robofetish-kun
                    RPG elements
                    sentou episode
                    symbolism


                    я их скопировал как есть, сорри за «кашу». Вот что я имел в виду, говоря «хороший набор меток». Это — пример неплохого набора меток. Я бы его увеличил еще на 30-50%, но и этого достаточно.
                    И, кстати, для понимания пристрастий пользователя нужно считать не просто пересечения и вычитать несовпадения, а назначать каждой метке ее вес.

                    Да, это большой объем данных. Это — минус. Плюс состоит в том, что мы экономим время живого человека, которому, например нужно платить деньги за то, чтобы он посмотрел кино и вбил какое-то количество тегов — и не факт что набор будет верным. Опять же, подобные вычисления делаются не в рил-тайме, это может быть некий фоновый процесс, на slave-базе.
                      0
                      Могу сказать про себя: мне нравятся разные фильмы. я люблю и «Кошмар на улице вязов», и «Титаник» и «Искусственный интеллект», «Зеленый слоник», например тоже мне понравился, и массу разных других направлений и жанров, которые вроде бы никак друг с другом не связаны. Но, тем не менее, если собрать все фильмы, которые мне понравились, то можно найти некоторые закономерности и перевесы в определенных метках. Более чем уверен, что на основе моих «лайков» можно узнать мои предпочтения, какие именно аспекты мне лично нравятся.

                      Соответственно, пересекая мои интересы с интересами других людей, которым тоже понравился неизвестный (неопределенный в нашей системе) фильм, мы можем найти точки пересечения, просто потому что они будут. А если их нет — значит, у нас был плохой набор меток, и его надо расширять. Хорошая новость в том, что данное решение может работать «постфактум», то есть, если мы понимаем что пересечений нет, то добавляем метки и снова делаем расчет.
            0
            Еще примеры практического применения: сравнение музыкальных композиций.
            Или книги, похожие на фильмы.
            Или сравнение авторов (кто из писателей похож по стилю на, например, Стивена Кинга).

          Only users with full accounts can post comments. Log in, please.