1. 전통적 Skyline Query

Skyline query는 다속성 데이터에서 지배관계를 기반으로 지배되지 않는 후보군을 추출하는 대표적인 다기준 의사결정 기법이다(Börzsönyi et al., 2001). 사용자가 속성별 가중치를 입력하지 않아도 각 속성 간의 상대적 우위를 기준으로 효율적인 대안 필터링이 가능하다는 장점이 있다.

지배관계는 객체 p가 객체 q를 지배한다고 할 때, 수식 (1)과 같이 정의된다. 이때, 작은 값이 큰 값을 지배한다.

Skyline query에서는 어떤 객체가 모든 속성에서 같거나 더 우수하고, 최소 하나의 속성에서는 더 우수할 때 다른 객체를 지배한다고 한다. Skyline 연산은 지배관계를 기준으로 지배되지 않는 객체들만을 결과로 추출한다. 전통적인 필터링 기법과 비교하여 해석이 직관적이고 여러 속성을 지배관계에 의해 균형 있게 고려하는 장점이 있다(Tzitzikas and Papadakos, 2013).

Figure 1에서 H8이 최종 skyline 객체에 포함된 것은 가격과 거리라는 두 속성 모두에서 다른 객체에 의해 지배되지 않았기 때문이다. H9, H7의 경우 H8보다 가격이 비싸기 때문에 skyline 객체에서 제외되었다. 이는 skyline query가 단일 속성의 우수성보다는 다중 속성 간의 균형을 중심으로 객체를 평가한다는 것을 보여준다. H9는 거리는 같지만 가격에서 H8에 열위이므로, 전통적인 지배관계 정의에 따라 skyline 후보군에서 제외된다. 이는 거리가 유사하더라도 다차원 속성 비교 시 하나 이상의 속성에서 열위에 있다면 지배당한 것으로 간주된다는 skyline 필터링의 엄격한 원칙을 보여주는 사례이다.

Figure 1.

Skyline query

제안 기법에서 사용되는 유사도를 위한 거리 계산은 객체 간 선호 특성의 근접도를 정량화하는 보조 수단이므로 필터링 자체는 여전히 2차원 속성 벡터에 기반한 지배관계 연산을 통해 수행된다. 따라서 유사도가 높다고 H2, H3, H5, H7, H9와 같은 객체들이 동일한 그룹으로 묶이거나 선택되는 구조는 아니다. 유사도는 다차원 선호 속성을 통합한 단일 비교 척도로 활용되며 skyline 지배관계에 의해 우선 배제된 객체들은 최종 추천 대상에서 제외된다. 이와 같이 본 연구에서는 지배되지 않는 객체를 선별하는 skyline 구조를 유지하면서 사용자 선호 반영의 정량성과 직관성을 확보하기 위해 유사도 기반 비교 구조를 도입하였다.

기존 skyline은 사용자 선호의 상대적 강도나 우선순위 차이를 반영하지 못하는 구조적 한계가 있다. 모든 속성을 동등한 중요도로 처리하며 속성 간 가중치나 개인화된 선호도를 반영하지 못해 실제 사용자 만족도와 다른 결과가 나올 수 있다.

최근 연구들은 skyline의 구조적 특징을 분석하고 확장하는 다양한 시도를 하고 있다. 예를 들어, skyline 연산의 복잡성과 필터링 효과를 개선하기 위한 알고리즘 최적화 및 다차원 확장 기법들이 제안되고 있으며(Nagendra and Candan, 2012), 고차원 환경에서 skyline 객체 분포에 대한 수치적 분석도 활발히 이루어지고 있다(Gao et al., 2014).

2. 사용자 선호 반영을 위한 Skyline Query

Preference-aware skyline은 사용자로부터 속성 간 중요도와 선호 순위를 명시적으로 입력받아 선호 방향을 반영한 필터링을 수행한다(Tzitzikas and Papadakos, 2013). 이는 사용자 중심의 결과를 제공하지만, 사용자에게 과도한 입력을 요구하고 다차원 비교의 복잡성이 증가하는 한계가 있다.

유사도 기반 skyline query는 사용자 선호 속성을 기준점 벡터로 설정하고 각 객체와의 거리 기반 유사도를 계산하여 다속성 비교를 간결하게 수행한다(Levandoski et al., 2013; Lyu et al., 2019). 유사도 기법은 사용자 선호도를 정량적으로 수치화하고 기존의 지배관계 기반 비교와 통합할 수 있다.

최근에는 속성 정규화와 거리 기반 선호 통합을 활용하여 일부 속성을 유사도 점수로 변환하고 나머지 속성과 함께 2차원 또는 저차원에서 skyline query를 수행하는 연구가 활발히 진행되고 있다(Zhang et al., 2013). Adomavicius and Kwon (2011)은 속성별 선호 함수를 통해 다속성 객체 간 비교를 정량화하는 구조를 제안했으며, Gulzar et al. (2017)은 사용자 맞춤형 속성 가중치를 반영하는 확장 가능한 skyline 프레임워크를 제시했다. 최근 연구들은 정규화, 선호 함수, 거리 기반 유사도를 통해 기존 skyline의 다차원 지배관계 비교 문제를 개선하고, 사용자 중심의 효율적 추천 모델 구현에 기여하고 있다(Shambour and Abualhaj, 2023).

본 연구는 최근의 연구 흐름을 바탕으로, 사용자 선호 속성을 유사도로 정량화하고 비선호 속성과 결합하여 2차원 skyline query를 수행함으로써 기존의 한계를 보완한다.

1. 연산 효율성 가설

다속성 비교에서 차원 수가 증가할수록 객체 간 지배관계가 성립할 확률이 낮아지고 연산 복잡도는 기하급수적으로 증가하는 문제가 보고되었다(Gao et al., 2014).

사용자는 호텔을 선택할 때 숙박 요금이 다소 높더라도 해변과 가까운 위치를 선호하거나, 후기 평점과 서비스 등급을 더 중시할 수 있다. 복합적 선호는 단일 속성이나 가중치 기반 평가 방식으로는 충분히 반영하기 어렵기 때문에 상대적 중요도와 상호작용을 정량화할 수 있는 다차원 비교가 요구된다.

본 연구는 다차원 비교의 복잡도를 해결하기 위해 일부 사용자 선호 속성을 유사도로 축소하고 나머지 독립 속성과 결합하여 2차원 형태의 skyline query를 수행한다. 유사도는 정규화된 속성값과 선호 기준점 간의 유클리드 거리를 기반으로 계산되며 복잡한 다차원 비교를 단일 거리 연산으로 변환한다.

가 설 : 유사도 기반 skyline query는 기존 기법 대비 연산 효율이 향상된다.

다중 속성 중 사용자 선호 속성을 유사도 값으로 통합한 후, 독립 속성과 결합하여 2차원 skyline query를 수행하는 것은 기존의 고차원 skyline query 보다 비교 연산 횟수를 효과적으로 감소시켜 신속한 선호객체 서비스를 제공한다.

Table 1은 본 연구에서 사용한 호텔 속성과 각 속성이 선택에 미치는 영향을 요약한 것이다. 이들 속성은 서로 다른 단위와 범위를 가지므로 비교를 위한 정규화와 선호 방향 일치가 필요하다.

Table 1.

Hotel attributes (four dimensions)

2. 속성 벡터 전처리

본 연구에서는 호텔 선택에 사용되는 네 개의 주요 속성을 기준으로 전처리를 수행하였다. 거리, 평점, 등급은 사용자 선호 속성으로 간주되며 정규화된다. 이때, 선호 방향에 따라 정규화 방식이 달라지는데, 예를 들어 거리는 값이 작을수록 선호되므로 정방향 정규화를 적용하며, 평점이나 등급처럼 값이 클수록 선호되는 속성에는 역방향 정규화를 적용한다. 속성 간 단위 불일치와 선호 방향의 차이를 보정하기 위한 정규화는 다속성 추천 시스템에서 필수적인 전처리 단계로 간주된다(Adomavicius and Kwon, 2011).

정규화된 선호 속성값은 사용자 선호 기준점과의 유클리드 거리를 계산하여 하나의 유사도 값으로 통합된다. 가격은 사용자 선호와 독립된 속성으로 간주되어 정규화 없이 그대로 유지된다. 2차원 속성 벡터(가격, 유사도)는, 이후 skyline query에 입력으로 사용되며 복잡한 다차원 비교를 간결하고 효율적으로 대체할 수 있는 기반이 된다.

[정의 1] 사용자 선호 벡터

사용자가 각 속성에 대해 선호하는 이상적인 값을 구성한 벡터로써 유사도 계산의 기준점이 된다. 정규화된 형태로 표현되며 수식 (2)와 같다. 각 oi 는 정규화된 선호 속성의 목표값이며 일반적으로는 1에 가까운 값이다.

[정의 2] 속성 정규화

호텔의 다차원 속성을 벡터 p = (p₁, p₂,..., p_d)로 정의한다. 각 속성 pi는 가격, 거리, 후기 별점, 서비스 등급처럼 서로 다른 단위와 값의 범위를 가지므로, 속성 간 공정한 비교를 위해 Min-Max 정규화로 모든 값을 [0,1] 구간으로 변환한다. 이때 L은 가격, 거리와 같이 값이 낮을수록 선호되는 속성들의 집합이고, H는 별점, 등급처럼 값이 높을수록 선호되는 속성들의 집합이다. 정규화된 값는 수식 (3)과 같이 정의되며 p_i,min, p_i,max는 속성에서 최소값과 최대값이다.

Min-Max 정규화는 거리 기반 추천 시스템, 클러스터링, 분류 등의 다차원 데이터 처리에서 널리 활용되는 전처리 기법으로, 스케일 왜곡 방지와 비교 구조의 단순화 측면에서 효과성이 입증되었다(Han et al., 2011).

[정의 3] 유사도 계산

사용자 선호 벡터를 o=(o₁, o₂, ..., o_d)라고 하면 정의 2에서 객체의 정규화된 속성 벡터 p~=(p~1, p~2, ..., p~d)에 대한 유클리드 거리의 유사도(similarity) S(p)는 수식 (4)와 같이 정의된다. 이때 선호 기준에 대한 유사도는 값이 작을수록 사용자의 선호에 근접한 것이다.

기준점 o는 각 속성에서 사용자가 가장 선호하는 이상적인 값을 의미하며 정규화된 공간에서는 속성에 대해 o_i = 1이므로 o = (1,1,...,1)이다. 즉, 각 객체는 이상적인 조건으로부터 얼마나 가까운지를 유클리드 거리로 평가받는다.

3. 유사도 기반 2차원 Skyline Query

기존 skyline query는 고차원 속성 간 지배 관계가 드물게 성립하고 차원 수가 증가할수록 연산량이 급증하는 한계가 있다. 본 연구에서는 기존의 문제를 해결하기 위해 정규화된 사용자 선호 속성을 기준점과의 유클리드 거리를 계산하여 하나의 유사도 값으로 통합하고 가격과 함께 2차원 속성 벡터로 구성하였다. 복잡한 다차원 비교를 간결한 2차원 비교로 대체함으로써 연산 효율성과 직관성을 동시에 확보할 수 있다. 다음은 2차원 속성 벡터와 지배관계에 대한 새로운 정의이다.

[정의 4] 2차원 속성 벡터

호텔의 다차원 속성 벡터 p는 수식 (5)와 같이 사용자 선호 기반 유사도 값 S(p)와 독립 속성 c를 결합한 2차원 속성 벡터 p' 로 표현된다. c는 비교 기준으로 사용되는 독립 속성(예: 가격)이며 S(p)는 사용자 선호 벡터 o와 정규화된 객체 속성 p 간의 유클리드 거리로 계산된 유사도 값이다.

[정의 5] 2차원 지배 관계

호텔과 사용자의 2차원 벡터 p´=(c1, s1), q´=(c2, s2)에 대해, 수식 (6)의 조건이 성립하면 p' 는 q' 를 지배한다.

이와 같이 각 호텔 객체는 (가격, 유사도) 형태의 2차원 벡터로 표현되며 전통적인 skyline 알고리즘을 적용한다. 유사도와 가격은 값이 작을수록 선호되므로 지배되지 않는 객체를 추출하여 사용자 선호에 부합하는 추천 후보군을 도출할 수 있다.

1. 실험환경 및 데이터셋 구성

본 연구는 유사도 기반 2차원 skyline query의 성능을 검증하기 위해 Python 환경에서 알고리즘을 구현하고 실험을 수행하였다. 실험은 정규화, 유사도 계산, skyline 연산을 포함하며 이에 대한 환경 정보는 Table 2와 같다.

Table 2.

Experimental setup

실험에는 호텔에 대한 200개의 가상 데이터셋이 사용되었다. 각 객체는 총 4개의 속성을 가지며 이 중 거리, 평점, 등급은 선호 속성으로 분류되어 유클리드 거리 기반의 유사도 계산에 활용된다. 가격은 일반적인 비교 기준 속성으로 간주되어 유사도 값과 함께 2차원 벡터로 구성된다.

Table 3은 실험에 사용된 호텔 데이터의 속성과 범위를 나타낸다. 각 속성은 호텔 예약 시 일반적으로 고려되는 주요 기준(가격, 해변까지 거리, 후기 평점, 서비스 등급)을 반영하여 설정하였다. 가격은 비용 민감도를 평가할 수 있는 대표 속성이며 해변까지의 거리는 접근성, 후기 평점은 사회적 검증 요소, 호텔 등급은 객관적 서비스 수준을 반영한다. 값의 범위는 실제 온라인 호텔 예약 플랫폼(예: Booking.com, Agoda 등)의 검색 결과를 참고하여 한국 및 아시아 주요 관광지 호텔에서 자주 나타나는 범위로 구성하였다. 실험의 일반성과 직관성을 확보하기 위해 각 속성은 현실에서 관측 가능한 값으로 설정되었으며 선호 방향 또한 사용자 일반 경향(예: 가격은 낮을수록, 평점은 높을수록)을 기반으로 정의하였다.

Table 3.

Attribute type and value ranges

2. 사용자 선호 시나리오 설계

본 연구는 다양한 사용자 선호 상황을 반영하기 위해 세 가지 선호 속성에 대해 기대 수준을 설정하고 이를 기반으로 사용자 선호 벡터를 구성하였다. 속성 간 단위와 범위 차이는 Min-Max 정규화를 통해 변환되었으며, 낮을수록 선호되는 속성은 역방향 정규화를 적용하였다.

사용자 기대값(raw preference value)은 Table 4와 같이 정규화를 통해 유사도 계산의 기준점으로 활용된다. 계산된 유사도 값은 독립 속성인 가격과 함께 2차원 속성 벡터를 구성하여 skyline query에 적용된다.

Table 4.

User-defined attribute preferences

3. 실험 분석

본 절에서는 유사도 기반 2차원 skyline query의 실효성을 평가하기 위해, 기존의 다차원 skyline과 비교 실험을 수행하였다. 실험은 동일한 조건에서 두 기법의 필터링 결과를 비교함으로써 사용자 선호 반영 수준, 후보 압축률, 결과 해석 가능성, 연산 효율성 측면에서의 차이를 정량적으로 분석하는 데 목적이 있다.

기존 skyline query는 모든 속성을 동일한 중요도로 취급하며 지배관계를 평가하므로 사용자 선호의 상대적 강도를 반영하지 못하고 고차원 환경에서는 필터링 성능이 저하되는 문제가 있다. 반면, 본 연구의 제안 기법은 선호 속성을 통합한 유사도 값과 가격 속성을 결합하여 2차원 비교 구조를 형성함으로써 차원 축소에 따른 효율성과 사용자 중심의 필터링을 동시에 달성하고자 한다.

비교 대상은 기존의 4차원 skyline query과 본 연구의 2차원 유사도 기반으로 구성된다. 기존 기법은 거리, 평점, 등급, 가격 등 네 개 속성을 정규화하여 절대값 기준으로 비교하며 속성 간 중요도나 개인화된 선호 차이를 고려하지 않는다. 반면, 제안 기법은 선호 속성을 단일 유사도 값으로 변환한 후 가격과 결합하여 2차원 벡터를 구성한다.

두 기법은 동일한 정규화 데이터셋과 사용자 선호 기준점을 기반으로 비교되며 실험 평가지표로는 평균 유사도 거리, skyline 객체 수, 결과 해석 용이성 등이 사용되었다. 평균 유사도 거리는 사용자 기준에 부합하는 정도를 나타내고 객체 수는 필터링 강도를 반영한다. 또한 비교 구조에 따른 이론적 연산 복잡도를 분석하여 제안 기법의 성능 개선 효과를 평가하였다.

3.1 속성 정규화 및 유사도 계산

호텔 데이터는 서로 다른 단위와 범위를 가진 속성으로 구성되며 비교의 공정성을 위해 정규화가 필요하다. 본 연구는 Min-Max 정규화를 적용하여 각 속성을 [0,1] 구간으로 변환하고 거리 및 가격처럼 낮을수록 선호되는 속성에는 역방향 정규화를 수행하였다. 사용자 선호 벡터 또한 동일한 기준으로 정규화된다.

각 호텔 객체와 사용자 간 유사도는 정규화된 거리, 평점, 등급을 대상으로 유클리드 거리로 계산되며 가격과 함께 호텔의 2차원 속성 벡터를 형성한다. 이 벡터는 skyline query에서 사용자 중심의 skyline 객체를 탐색하는데 사용된다.

Figure 2는 위 과정을 알고리즘 형태로 정리한 것으로 정규화 기준 계산부터 유사도 거리 계산 및 최종 벡터 반환까지의 절차를 상세히 보여준다.

Figure 2.

Normalization and similarity algorithm

1행에서는 정규화를 위해 데이터셋에 포함된 모든 속성에 대해 최소값과 최대값을 계산한다. 2행은 사용자로부터 입력된 선호 속성값을 동일한 정규화 기준으로 변환한다. 정규화된 사용자 벡터는 호텔 객체들과 같은 공간상에서 비교 가능하도록 만들어진다. 3행은 데이터셋의 각 객체(호텔)에 대해 정규화 및 유사도 계산을 위한 반복문이다. 4행은 각 객체의 4개 속성을 정규화한다. 이때 속성마다 해당 범위의 min, max값을 사용하여 0~1 범위로 조정한다. 5행과 6행은 낮을수록 선호되는 거리(distance)와 가격(price)의 정규화된 값을 각각 1 - value로 반전하여 일관된 비교가 가능하도록 한다.

호텔과 사용자 선호 벡터 사이의 유사도는 7행에서 정규화된 거리, 평점, 등급으로 유클리드 거리를 계산하여 구한다. 이 값은 사용자 기준에서 해당 객체의 상대적 선호도를 정량화한 척도이다. 최종적으로 8행에서는 한 호텔의 정규화된 가격과 유사도 값을 쌍으로 묶어 반환하고 데이터셋 D를 반복하여 처리한다.

3.2 추천 객체 수 비교

Skyline query는 객체 간 지배 관계를 바탕으로 후보를 선별하는 필터링 기법이지만, 비교 속성 수가 많아질수록 다수의 객체가 상호 지배하지 않게 되어 skyline 객체가 많아진다. 본 실험에서는 기존의 4차원 skyline과 제안된 2차원 유사도 기반의 추천 객체 수를 비교하였다. 실험은 데이터 크기를 20개에서 200개까지 단계적으로 늘리며 진행하였고 결과는 Figure 3과 같다. 기존에는 각각 12, 25, 48, 60, 110개의 객체를 추천한 반면, 제안 기법은 4, 7, 11, 13, 17개로 객체 수가 감소하였다. 결과는 고차원 비교 구조에서의 지배 관계 형성 한계를 수치적으로 보여준다. 특히 데이터 200개를 기준으로 기존에는 전체의 55%를 추천한 데 비해, 제안 기법은 약 8.5%에 불과하였다. 제안 기법은 10~15% 수준으로 후보 수를 유지하며 필터링 효과를 강화하였고 이는 사용자의 선택 효율성과 결과 해석의 명확성을 크게 개선하는 것으로 볼 수 있다.

Figure 3.

Object recommendation

3.3 시간 복잡도

Skyline query는 객체 간 지배 관계를 비교하며 O(n²)의 시간 복잡도를 가진다. 기존에는 거리, 평점, 등급, 가격의 네 개 속성을 각각 독립적으로 비교하기 때문에 전체 연산량은 O(4n²)에 이른다. 이는 속성 수가 증가할수록 연산량이 급격히 증가하는 구조적 한계를 내포하고 있다(Tan et al., 2001; Nagendra and Candan, 2012).

반면 제안 기법은 세 개의 선호 속성을 정규화한 후 유사도 거리 계산을 통해 단일 스칼라 값으로 통합하고 이를 가격과 결합하여 2차원 벡터로 변환한다. 단계별 시간 복잡도는 정규화 및 거리 계산에 O(nd), 2차원 skyline 연산에 O(n²)이 되며 전체 시간 복잡도는 O(nd + n²)로 수렴된다. 실험에서는 선호속성 수 d = 3으로 고정되어 O(n²)에 해당한다.

연산량 비교는 하드웨어 환경 영향을 배제한 연산 횟수(Operation Counts, Ops)를 기준으로 진행되었다. Ops는 알고리즘 복잡도 분석에서 일반적으로 사용되는 비교 지표로, 입력 크기에 따른 연산량을 정량화하여 하드웨어나 실행 환경의 차이를 배제한 성능 비교를 가능하게 한다(Cormen et al., 2009). Figure 4는 입력 객체 수에 따른 연산량 차이를 나타내며 데이터 200개를 기준으로 기존 기법은 약 160,000 Ops, 제안 기법은 약 40.600 Ops를 기록하였다.

Figure 4.

Operation counts

제안 기법은 차원 축소와 유사도 통합을 통해 비교 횟수를 효과적으로 감소시켜 전체 연산량을 절감하였으며 데이터 크기가 커질수록 기존 대비 연산 효율성이 더욱 뚜렷하게 나타났다. 이는 제안 기법이 대규모 데이터 환경에서 보다 효율적으로 작동함을 입증한 것으로 가설 1에 대한 정량적 타당성을 뒷받침한다.