Разработка функции отображения похожести для слабоструктурированных объектов

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

Данный подход должен удовлетворять следующим критериям:

· не накладывать ограничения в ал­горитме вычисления схоже­сти;

· учитывать связи между объек­тами;

· быть гибким (легко адаптироваться под различные предметные области).

Пусть производится сравнение неких объектов системы А и В.

Баллами близости будем называть неотрицательную числовую характеристику, которая отражает степень сходства двух объектов в смысле, при этом с ростом сходства двух объектов данная величина растет. Поскольку данный подход зависим от конкретной предметной области, определим также понятие критерия близости. Критерием близости будем называть совокупность критерия отбора и упорядоченный и взвешенный набор полей (список полей), по которому проводится сравнение. Критерий отбора - это ограничение на поля объекта В, в случае не выполнения которого величина баллов близости объекта А и объекта В в смысле критерия близости С равняется нулю.

Рассмотрим процедуру вычисления величины баллов близости объекта А и объекта В в смысле критерия близости С. Обозначим величину баллов близости как D, вес каждой связи между объектами как d. Данная процедура выполняется, только если объект B соответствует критерию отбора, в обратном случае баллы близости для данного объекта и данного критерия близости принимаются равными нулю и процедура завершается.

Шаги процедуры:

1. Для каждого поля из списка полей критерия близости производится определение сходства значений у объектов А и В. Величина степени сходства, умноженная на величину весового коэффициента поля, прибавляется к текущему значению D. Процедура вычисления численной степени сходства различных полей будет описана далее.

2. Если существует связь между объектами A и B, то значение D дополнительно увеличивается на величину d, умноженную на количество таких связей.

Псевдокод процедуры:

D = 0;

if S(B) == True:

for (field, weight) in F:

D += compare(A, B, field) * weight;

D += number_of_links_between(A, B)*d;

где compare(A, B, field) - функция сходства для вычисления степени сходства значений полей А и В.

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

1. Критерий близости C;

a. Критерий отбора S;

b. Набор взвешенных полей F;

2. Баллы близости за каждую связь между объектами d;

3. Алгоритм сравнения полей объектов compare(A, B, field).

Алгоритм сравнения полей определяется пользователем подхода исходя из конкретной задачи и предметной области. Единственное ограничение на данную функцию заключается в том, что она должна отображать сходство значений полей в рамках баллов близости – значение функции должно быть неотрицательным и прямо пропорциональным степени сходства значений полей.

Достоинствами описанного подхода являются:

1) гибкость - манипулируя критериями отбора, составом и весовыми коэффициентами списков полей критерия можно получить критерий близости, отражающий связь между объектами по различным параметрам, не накладывая при этом ограничений на предметную область использования;

2) учет не только структуры объектов, но и связей между ними;

3) отсутствие ограничений в алгоритме вычисления схожести;

4) универсальность – поля разного типа учитываются единообразно при построении рекомендаций.

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

3. Информационная система «Открытая Карелия»

Дата добавления: 2015-10-16