ПРИБЛИЖЕНИЕ ПОЛЬЗОВАТЕЛЬСКИХ ПРЕДПОЧТЕНИЙ В СИСТЕМАХ ОНЛАЙН МАГАЗИНОВ
Во многих онлайн-системах покупатели обычно поражены огромным количеством результатов и вариантов выбора. Однако на практике их обычно интересуют только некоторые из этих вариантов. Хотя эти системы онлайн-покупок позволяют пользователям предоставлять некоторые ключевые слова и другую информацию, чтобы фильтровать и получать только то, что им нужно, последние считают, что то, что они получают, не обязательно соответствует их удовлетворению.
В этой статье мы предлагаем новую систему покупок, которая позволяет покупателям выражать то, что они хотят, при покупке продукта в Интернете. Точнее, пользователям предоставляется возможность предоставить свои требования и желания в дружественной и интерактивной форме. Затем система предоставит список предложений, отвечающих требованиям пользователей и максимально удовлетворяющих их желания. Требования и желания управляются в уникальной модели, соответственно, как набор жестких ограничений и предпочтений, где последние могут быть количественными (числовыми), качественными (порядковыми) или обоими. Затем применяется метод ветвления и привязки, чтобы предоставить пользователям список лучших результатов.
Многие онлайн-системы предполагают некоторое взаимодействие с пользователями, чтобы понять и удовлетворить их потребности. Чтобы добиться успеха, эти системы должны максимизировать взаимодействие с системой. Максимальное удовлетворение пользователя может быть достигнуто путем учета его / ее желаний / предпочтений, когда он / она ищет данный предмет. Это приведет к тому, что система станет более популярной и заработает больше репутации среди клиентов. Для того чтобы системы могли обрабатывать желания пользователей, они должны иметь надлежащий способ представления, выявления и оценки пользовательских предпочтений. Таким образом, рассуждение о предпочтениях является основной концепцией для систем, в которых задействовано относительно большое пространство взаимодействия с пользователем. Более того, многие из этих систем существуют в стесненных условиях. Например, в онлайновой системе конфигурации ПК пользователь не может выбирать две разные части, которые несовместимы друг с другом. Поэтому мы должны рассмотреть ситуацию, когда ограничения и предпочтения сосуществуют вместе. В нынешних системах покупок покупателям может быть трудно найти подходящий продукт среди огромного набора возможностей.
Более того, у них сложилось впечатление, что их предпочтения и потребности не учитываются системой. Это побудило нас к разработке системы онлайн-покупок, учитывающей требования проблемы и максимально увеличивающей желания пользователей. Требования и желания управляются в уникальной модели, соответственно, посредством набора жестких ограничений и предпочтений, где последние могут быть количественными (числовыми), качественными (порядковыми) или обоими. Жесткие ограничения соответствуют здесь как требованиям пользователя, так и требованиям к проблеме, и управляются с помощью инфраструктуры проблемы удовлетворенности (CSP) [1]. Мы используем C-полукольцо [2] и CP-сеть [3, 4] для представления набора количественных и качественных предпочтений соответственно. Затем применяется метод ветвления и привязки, чтобы предоставить пользователям список результатов, удовлетворяющих жестким ограничениям и оптимизирующих предпочтения. Насколько нам известно, не существует существующих требований к интерактивной системе для обработки проблем, а также пользовательских предпочтений, выраженных как в качественном, так и в количественном отношении. Более того, наша система является первой реальной попыткой справиться и использовать как C-semires, так и CP-net в одной и той же интерактивной системе.
Сеть условных предпочтений (CP-net) [3, 4] представляет собой графическую модель для представления качественных утверждений о предпочтениях, включая условные предпочтения, такие как: «Я предпочитаю от А до В, когда Х держит». CP-сеть работает, используя понятие преференциальной независимости, основанное на предположении при прочих равных условиях (со всеми остальными вещами без изменений). Предположение при прочих равных условиях (CP) дает нам четкий способ интерпретации предпочтений пользователя. Например, я предпочитаю A больше, чем B, значит, я предпочитаю A больше, чем B, если не было изменений в основных свойствах объектов. Сеть CP может быть представлена ориентированным графом, где узлы представляют объекты (или переменные) вместе с их возможными значениями (доменами переменных), а дуги представляют независимые предпочтения среди объектов. Каждая переменная X связана с таблицей при прочих равных условиях (обозначается как CPT (X)), выражающей ранжирование порядка по различным значениям X с учетом набора родителей Pa (X). Результатом для CP-сети является присвоение каждой переменной из ее домена. Учитывая CP-сеть, пользователи обычно имеют несколько запросов о представленных наборах предпочтений. Одним из основных запросов является лучший результат с учетом набора предпочтений. Мы говорим, что исход o i лучше, чем исход oj, если есть последовательность ухудшающихся сальто, переходящих от oi к oj [6]. Ухудшение сальто — это изменение значения переменной на менее предпочтительное значение в соответствии с CPT переменной.
Проблема удовлетворения ограничений (CSP) [1] является хорошо известной основой для задач ограничений. Более формально, CSP состоит из набора переменных, каждая из которых определена в наборе возможных значений (область переменных), и набора отношений, ограничивающих значения, которые может принимать каждая переменная. Решением для CSP является полное присвоение значений переменным таким образом, чтобы все ограничения были выполнены. В отличие от жестких ограничений, мягкие ограничения связаны со степенью удовлетворенности [7], и цель состоит в том, чтобы найти оптимальный результат или решение. В мягких CSP (SCSP) [2] исследуется задача оптимизации, где оптимальным решением является одно решение с наилучшей целевой функцией в соответствии с мягкими ограничениями. SCSP является обобщением классического CSP, где ограничения имеют несколько уровней выполнимости, которые полностью или частично упорядочены в соответствии со структурой C-полукольца [2]. C-полукольцо — это математическая модель, основанная на формализме полукольца, с помощью которой обрабатываются различные задачи и расширения мягких ограничений. Используя c-semiring, можно представить различные проблемы ограничений в единой структуре. Более формально, Csemiring — это кортеж (A, +, x, 0, 1), где [8]: A — это множество, а 0, 1 — это элементы A. + — дополнительная операция, определенная над набором элементов из A и 0 — это единичный элемент. х — операция умножения, 1 — единичный элемент, а 0 — поглощающий элемент. + это идемпотентная операция. Это + + = а, и это может быть использовано, чтобы найти частичный порядок над A. Частичный порядок над A может быть найден как a <b, если b лучше, чем a (то есть a + b = b). Используя определение C-полукольца, различные расширения CSP могут быть представлены в единой структуре, предоставляя разную семантику операциям сложения и умножения [9]. Взвешенный CSP (WCSP) является экземпляром C-полукольца, где соответствующее значение для каждого кортежа представляет стоимость этого кортежа в окончательном решении. Следовательно, оптимальным решением в WCSP является решение, в котором соответствующее значение является минимальным, а конечная цель состоит в том, чтобы минимизировать глобальную стоимость проблемы. При добавлении двух ограничений WCSP принимает ограничение с минимальным значением кортежа, и общая стоимость может стать больше 1. При наличии CP-net N его можно аппроксимировать к проблеме мягких ограничений SCSP [5]. Это приближение является благоприятным во многих областях, особенно в тех областях, где существует интенсивное взаимодействие с пользователем, как в случае проблем онлайн-конфигурации [5]. Другим преимуществом приближения CP-сети к SCSP является преодоление сложности рассуждения с помощью CP-сетей. Цель аппроксимации — преобразовать операторы предпочтений в CP-сети в мягкие ограничения и отразить порядок для каждого оператора, придав более высокое значение предпочтительным экземплярам для кортежей. Известно, что тестирование доминирования («данный результат лучше, чем другой») является сложным в вычислительном отношении в CP-сетях. Тем не менее, SCSP обеспечивает линейное время в ответ на тестирование доминирования между двумя исходами [8, 5].
Основной характеристикой, с помощью которой можно различать различные приближения для конкретной CP-сети, является свойство сохранения информации [10]. Сохранение информации просто означает, что то, что уже является предпочтительным в сети CP, также должно быть предпочтительным в приближенном SCSP. Процесс аппроксимации может быть выполнен в два этапа путем создания графа ограничений и вычисления значений предпочтений для каждой переменной в графе ограничений. Последний шаг, который необходимо выполнить, чтобы сделать приближенный SCSP совместимым с каркасом C-полукольца, — это отразить веса переменных в кортежах ограничений. Это может быть просто сделано путем умножения веса для каждой переменной X на набор ограничений, где упоминается X.
Использованные источники
[1] Rina Dechter, Constraint processing, Elsevier Morgan Kaufmann, 2003.
[2] Stefano Bistarelli, Ugo Montanari, and Francesca Rossi, “Semiring-based constraint satisfaction and optimization,” JOURNAL OF THE ACM, vol. 44, no. 2, pp. 201–236, 1997.
[3] Craig Boutilier, Ronen I. Brafman, Carmel Domshlak, Holger H. Hoos, and David Poole, “Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements,” J. Artif. Intell. Res. (JAIR), vol. 21, pp. 135–191, 2004.
[4] Ronen I. Brafman and Yannis Dimopoulos, “A new look at the semantics and optimization methods of cpnetworks,” in IJCAI, 2003, pp. 1033–1038.
[5] Carmel Domshlak, Steven David Prestwich, Francesca Rossi, Kristen Brent Venable, and Toby Walsh, “Hard and soft constraints for reasoning about qualitative conditional preferences,” J. Heuristics, vol. 12, no. 4-5, pp. 263–285, 2006.
[6] Steve Prestwich, Francesca Rossi, Kristen Brent Venable, and Toby Walsh, “Constrained cpnets,” in in Proceedings of CSCLP04, 2004.
[7] Francesca Rossi, Kristen Brent Venable, and Toby Walsh, “Preferences in constraint satisfaction and optimization,” AI Magazine, vol. 29, no. 4, pp. 58–68, 2008.
[8] Stefano Bistarelli and Francesca Rossi, “Semiringbased soft constraints,” in Concurrency, Graphs and Models, 2008, pp. 155–173.
[9] S. Bistarelli, U. Montanari, F. Rossi, T. Schiex, G. Verfaillie, and H. Fargier, “Semiring-based csps and valued csps: Frameworks, properties, and comparison,” Constraints, vol. 4, 1999.
[10] S. Prestwich, F. Rossi, K. B. Venable, and T. Walsh, “Constraint-based preferential optimization,” in Proceedings of the 20th national conference on Artificial intelligence Volume 1. 2005, pp. 461–466, AAAI Press.
APPROXIMATING USER PREFERENCES IN ONLINE STORE SYSTEMS
Malek Mouhoub, Bandar Mohammed, Eisa Alanazi