비 트랜잭션 데이터를 대상으로 연관 규칙을 도출하기 위해서, 데이터의 속성들을 구간화하는 기법들이 활발하게 연구되었다. 이러한 기존의 연구들은 구간화 단계에서 구간 범위의 변화에 따른 연관 규칙의 신뢰도 변화를 반영하지 않고, 구간화 단계와 연관 규칙을 도출하는 단계들을 독립적으로 수행하였다. 이로 인해 속성들의 구간이 부적절하게 설정되고, 이 결과 높은 신뢰도를 갖는 연관 규칙들이 최종 결과에서 누락된다. 따라서 본 논문에서는 속성들을 구간화하는 단계와 연관 규칙들을 도출하는 단계를 병합하여 동시에 수행함으로써, 가장 신뢰도가 높은 연관규칙들을 도출할 수 있는 구간을 설정하는 방안을 제안한다. 이를 위해서 연관 규칙의 우변의 속성들을 대상으로 계층적 클러스터링을 수행하고, 각 클러스터들에 대해서 특성 분석을 수행한다. 실험 결과, 제안하는 기법은 기존의 기법들에 비해서 높은 신뢰도를 갖는 연관 규칙들을 발견하는 것으로 나타났다.
비 트랜잭션 데이터를 대상으로 연관 규칙을 도출하기 위해서, 데이터의 속성들을 구간화하는 기법들이 활발하게 연구되었다. 이러한 기존의 연구들은 구간화 단계에서 구간 범위의 변화에 따른 연관 규칙의 신뢰도 변화를 반영하지 않고, 구간화 단계와 연관 규칙을 도출하는 단계들을 독립적으로 수행하였다. 이로 인해 속성들의 구간이 부적절하게 설정되고, 이 결과 높은 신뢰도를 갖는 연관 규칙들이 최종 결과에서 누락된다. 따라서 본 논문에서는 속성들을 구간화하는 단계와 연관 규칙들을 도출하는 단계를 병합하여 동시에 수행함으로써, 가장 신뢰도가 높은 연관규칙들을 도출할 수 있는 구간을 설정하는 방안을 제안한다. 이를 위해서 연관 규칙의 우변의 속성들을 대상으로 계층적 클러스터링을 수행하고, 각 클러스터들에 대해서 특성 분석을 수행한다. 실험 결과, 제안하는 기법은 기존의 기법들에 비해서 높은 신뢰도를 갖는 연관 규칙들을 발견하는 것으로 나타났다.
To discover association rules from nontransactional data, there have been many studies on discretization of attribute values. These studies do not reflect the change of discovered rules' confidence according to the change of the ranges of the discretized attributes, and perform the discretization st...
To discover association rules from nontransactional data, there have been many studies on discretization of attribute values. These studies do not reflect the change of discovered rules' confidence according to the change of the ranges of the discretized attributes, and perform the discretization stage and the rule discovery stage independently. This causes the ranges of attributes not properly discretized, thereby making the rules having high confidence excluded in the result set. To solve this problem, we propose a novel method that performs the discretization and rule discovery stages simultaneously in order to discretize ranges of attributes in such a way that the rules having high confidence are discovered well. To the end, we perform hierarchical clustering on the attributes in the right hand side of rules, then do characterization on every cluster thus obtained. The experimental result demonstrates that our method discovers the rules having high confidence better than existing methods.
To discover association rules from nontransactional data, there have been many studies on discretization of attribute values. These studies do not reflect the change of discovered rules' confidence according to the change of the ranges of the discretized attributes, and perform the discretization stage and the rule discovery stage independently. This causes the ranges of attributes not properly discretized, thereby making the rules having high confidence excluded in the result set. To solve this problem, we propose a novel method that performs the discretization and rule discovery stages simultaneously in order to discretize ranges of attributes in such a way that the rules having high confidence are discovered well. To the end, we perform hierarchical clustering on the attributes in the right hand side of rules, then do characterization on every cluster thus obtained. The experimental result demonstrates that our method discovers the rules having high confidence better than existing methods.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
3] 의 경우, 후자가 보다 많은 경우를 포함하고 있으므로, 전자에 비해서 유용한 연관 규칙임을 알 수 있다. 따라서 본 논문에서는 계층적 클러스터링의 병합 과정에 따른 클러스터들의 특성 변화를 살펴보면서, 신뢰도의 손실이 없는 경우, 가급적 넓은 범위를 갖도록 속성들의 구간들을 설정하는 기법을 제안한다.
따라서 본 논문에서는 연관 규칙 도출 작업과 속성들의 값을 구간화 하는 작업을 동시에 수행하면서, 상호작용을 통해서 높은 신뢰도를 갖는 연관 규칙들을 도출하는 방법을 제안한다. 또한, 제안하는 기법의 구간 설정 방법을 통해서 기존의 기법들에서는 발견할 수 없었던 의미 있는 연관 규칙들을 도출할 수 있음을 정량적으로 검증한다.
또한, 본 논문에서는 속성들의 구간을 결정하는 과정과, 연관 규칙을 도출하는 과정을 동시에 수행하고자 한다. 이러한 상호작용을 통하여 높은 신뢰도를 갖는 연관규칙들을 도출할 수 있으며, 기존의 연구에서 부적절하게 설정된 속성들의 구간으로 인해 발견하지 못했던 연관 규칙들을 도출할 수 있다.
우변은 n개의 속성들의 구간들로 구성되고, Bm"는 우변에 해당하는 속성 Bm의 w번째 구간을 의미한다. 본 논문에서는 계층적 클러스터링 기법을 이용하여 연관 규칙을 도출하는데, 이 과정에서 다수의 클러스터들이 생성된다. 이러한 클러스터들 중에서 식별자가 [인 클러스터를 G로 나타낸다.
본 논문에서는 분석 대상이 특정 속성의 변화에 따라서 다른 속성들이 어떠한 변화를 빈번하게 보이는지를 연관 규칙의 형태로 도출하고자 한다. 이를 위해서 본 논문에서 도출하는 연관 규칙은 좌변은 단일 속성, 우변은 다企의 속성들로 표현된다.
본 논문에서는 비 트랜젝션 데이터를 대상으로 속성들을 구간화하여, 연관 규칙을 도출하는 방안에 대하여 논의하였다. 기존의 연구들은 속성들을 구간화하는 단계와 연관 규칙을 도출하는 단계를 분리하여 독립적으로 수행하였다.
본 실험에서는 속성 RM, AGE, MEDV의 조합들을 우변으로 갖고, 그 외의 속성들을 각각 좌변으로 갖는 연관 규칙을 도출 한다. 이는 어떤 속성이 방의 개수, 집의 나이, 집의 가격에 영향을 미치는지를 분석하는 것이다. 본 논문에서는 우변의 속성 RM, AGE, MEDV를 각각 Bl, B2, B3로 나타낸다.
이에 본 논문에서는 속성들의 구간의 범위를 결정하는 과정과 연관 규칙을 도출하는 과정을 병합하여 수행함으로써, 가장 높은 신뢰도를 갖는 연관 규칙들을 도출할 수 있는 구간 범위를 설정하는 방법을 제안하였다. 이를 위해서 연관 규칙의 우변의 속성들을 대상으로 계층적 클러스터링을 수행하여, 각 클러스터마다 특성 분석을 수행하였다.
따라서 이러한 기법들은 신뢰도가 높은 연관 규칙들을 결과에서 누락할 수 있는 가능성을 갖고있다. 이에 본 논문에서는 속성들의 구간화 단계와 연관규칙 도출 단계를 동시에 수행하여, 신뢰도가 높은 연관규칙들이 도출되도록 속성들의 구간을 설정하는 방법을제안한다.
된다. 이에 본 연구에서는 다수의 속성으로 표현되는 우변을갖는 연관규칙을 도출하는 방안을 제안한다.
제안 방법
" Br„를 나타낼 수 있다. 각 클러스터들은 최대 좌변 속성의 구간들의 개수만큼의 연관 규칙들을 나타낼 수 있는데, 본 논문에서는 분석가가 설정한 임계값이상의 신뢰도를 갖는 연관 규칙들만을 인정하는 것으로 한다.
본 논문에서는 두 가지 종류의 실험을 수행하였다. 실험 1에서는 세 가지 기법들을 이용해서 도출한 연관 규칙의 개수, 평균 신뢰도를 비교하였고, 실험 2에서는 규칙들이 포괄하는 평균 면적, 평균 신뢰도/면적을 비교하였다.
이는 어떤 속성이 방의 개수, 집의 나이, 집의 가격에 영향을 미치는지를 분석하는 것이다. 본 논문에서는 우변의 속성 RM, AGE, MEDV를 각각 Bl, B2, B3로 나타낸다. 따라서 본 실험에서 도출하는연관 규칙들의 우변은 Bl, B2, B3의 가능한 조합들인 Bl, B2, B3, B1&B2, B1&B3, B2&B3, B1&B2&B3의총 7가지의 경우로 구성된다.
이를 이용하여 연관 규칙을 도출한다. 본 실험에서는 속성 RM, AGE, MEDV의 조합들을 우변으로 갖고, 그 외의 속성들을 각각 좌변으로 갖는 연관 규칙을 도출 한다. 이는 어떤 속성이 방의 개수, 집의 나이, 집의 가격에 영향을 미치는지를 분석하는 것이다.
실험 1에서는 세 가지 기법들을 이용해서 도출한 연관 규칙의 개수, 평균 신뢰도를 비교하였고, 실험 2에서는 규칙들이 포괄하는 평균 면적, 평균 신뢰도/면적을 비교하였다. 실험 1에서는 기법 RMUC, 기법 Clustering, 기법 Equi-depth를 통하여 Bl, B2, B3의 구간들을 설정하고, 이를 통해서 도출된 연관 규칙들의 개수, 규칙들이 갖는 신뢰도의 평균값을 비교하였다. 그림 1과 그림 2는 각각 도출된 연관 규칙의 개수, 평균 신뢰도를 그래프의 형태로 보인 것이다.
실험 1에서는 세 가지 기법들을 이용해서 도출한 연관 규칙의 개수, 평균 신뢰도를 비교하였고, 실험 2에서는 규칙들이 포괄하는 평균 면적, 평균 신뢰도/면적을 비교하였다. 실험 1에서는 기법 RMUC, 기법 Clustering, 기법 Equi-depth를 통하여 Bl, B2, B3의 구간들을 설정하고, 이를 통해서 도출된 연관 규칙들의 개수, 규칙들이 갖는 신뢰도의 평균값을 비교하였다.
이를 통해서, 기법 RMUC가 다수의 속성들을 우변으로 갖는 연관 규칙을 도출하는 데에 적당한 기법임을 알 수 있다. 실험 2에서는 기법 RMUC, 기법 Clustering, 기법 Equi-depth를 통하여 Bl, B2, B3의 구간들을 설정하고, 이를.통해서 도출된 연관 규칙들이 포괄하는 면적의 평균, 평균 신뢰도/면적의 값을 비교하였다.
그 과정은 다음과 같다. 우선, 데이터들이 갖고 있는 속성들에 대하여 각 속성들을 기준으로 클러스터링을 수행한다. 이 단계에서 각 속성마다 데이터들의 클러스터들이 생성된다.
위의 세 가지 기법들을 통해서 우변 속성들의 구간을설정하고, 이를 이용하여 연관 규칙을 도출한다. 본 실험에서는 속성 RM, AGE, MEDV의 조합들을 우변으로 갖고, 그 외의 속성들을 각각 좌변으로 갖는 연관 규칙을 도출 한다.
규칙의 형태로 도출하고자 한다. 이를 위해서 본 논문에서 도출하는 연관 규칙은 좌변은 단일 속성, 우변은 다企의 속성들로 표현된다. 우변에 다수의 속성들을 포함함으로써 특정 속성의 변화에 따른 분석 대상의 변화를 세밀하게 표현할 수 있다.
구간 범위를 설정하는 방법을 제안하였다. 이를 위해서 연관 규칙의 우변의 속성들을 대상으로 계층적 클러스터링을 수행하여, 각 클러스터마다 특성 분석을 수행하였다. 클러스터의 특성은 해당 클러스터가 만족하는 연관 규칙의 신뢰도를 의미한다.
진행한다. 클러스터 간의 거리를 측정하는 방법에는 최소, 최대, 평균, 중심 거리를 이용하는 방법들이 있으며, 본 논문에서는 그 중에서 가장 널리 사용되는 최소 거리 기법을 이용하였다. 최소 거리 기법은 두 클러스터에 각각 속해 있는 데이터들의 쌍의 거리 값들 중에서 최소 값을 두 클러스터 간의 거리로 부여하는 방법이다[5, 6].
실험 2에서는 기법 RMUC, 기법 Clustering, 기법 Equi-depth를 통하여 Bl, B2, B3의 구간들을 설정하고, 이를.통해서 도출된 연관 규칙들이 포괄하는 면적의 평균, 평균 신뢰도/면적의 값을 비교하였다.
대상 데이터
본 논문에서는 우변의 속성 RM, AGE, MEDV를 각각 Bl, B2, B3로 나타낸다. 따라서 본 실험에서 도출하는연관 규칙들의 우변은 Bl, B2, B3의 가능한 조합들인 Bl, B2, B3, B1&B2, B1&B3, B2&B3, B1&B2&B3의총 7가지의 경우로 구성된다.
본 논문에서는 성능 분석을 위하여 보스턴시의 집 가격과 관련된 데이터를 사용하였다. 이는 1997년 7월에 수집된 것으로서 506개의 레코드, 14가지의 속성들로 구성되어 있다[7].
이론/모형
우변의 속성들을 가장 의미 있는 구간들로 분할하기 위해서는 유사한속성 값을 갖는 데이터 집합들의 식별이 선행되어야 한다. 본 논문에서는 이를 위해서 계층적 클러스터링 기법을 이용한다.
본 연구에서 성능 평가의 대상으로 선정한 속성의 구간화 기법들은 본 논문에서 제안하는 기법인 RMUC (Rule Mining Using Clustering), 클러스터링을 이용하는 기법인 Clustering, 포함하는 데이터의 개수가 동일하도록 구간을 설정하는 기법인 Equi-depth로 총 세 가지이다. 기법 Clustering과 기법 Equi-depth는 참고문헌 [2]에서 성능 분석을 위해서 사용된 기법들이다.
성능/효과
실험 결과, 제안하는 기법인 RMUC가 기법 Clustering, 기법 Equie depth에 비하여 우변에 다수의 속성들이 포함된 경우에, 우수한 성능을 보이는 것으로 나타났다. B1&B2의 경우, 기법 RMUC가 기법 Clustering과 기법 Equi-depth에비하여 평균 신뢰도/면적의 값으로서 각각 6.32배, 4.78 배 높은 값을 보였고, B1&B3의 경우, 각각 5.57배, 459 배, B2&B3의 경우, 각각 6.36배, 2.88배, B1&B2&B3의경우, 각각 1.72배, 1.85배 높은 값을 보였다.
기법 RMUC는 기법 Clustering에 비해서 평균 신뢰도는 유사한 반면에, 도출된 규칙의 수는 1.7배 가량 증가하였는데, 이는 기법 RMUC7} 기법 Clustering 이 도출하지 못한 높은 신뢰도를 갖는 연관 규칙들을 도출하였음을 의미한다. 또한, 기법 RMUC 는 기법 E* qui depth에 비해서 도출되는 규칙의 수는 유사한 반면에, 평균 신뢰도는 0.
기법 RMUC는 연관 규칙의 우변에 다수의 속성들이 포함되는 경우인 B1&B2&B3에 기법 Clustering, 기법 Equi-depth에 비해서 우수한 성능을 보였다. 이를 통해서, 기법 RMUC가 다수의 속성들을 우변으로 갖는 연관 규칙을 도출하는 데에 적당한 기법임을 알 수 있다.
기법 RMUC는 총 276개, 평균 39.43개, 평균 신뢰도 0.757554를 갖는 규칙들을 도출한 반면에, 기법 Clus- teringe 총 162개, 평균 23.14개, 평균 신뢰도 0.756102 를 갖는 규칙들을 도출하였다. 또한, 기법 Equi-depth는총 254개, 평균 36.
7배 가량 증가하였는데, 이는 기법 RMUC7} 기법 Clustering 이 도출하지 못한 높은 신뢰도를 갖는 연관 규칙들을 도출하였음을 의미한다. 또한, 기법 RMUC 는 기법 E* qui depth에 비해서 도출되는 규칙의 수는 유사한 반면에, 평균 신뢰도는 0.033 가량 높은 값을 보이는데, 이는 기법 RMUC가 기법 Equi-depth에 비해서 우변 속성들에보다 의미 있는 구간 범위가 설정되었음을 의미한다.
033 가량 향상된 것으로 나타났다. 또한, 제안하는 기법은 기존의 기법들에 비해서, 다수의속성들을 우변으로 갖는 연관 규칙을 도출하는 데에 우수한 성능을 보이는 것으로 나타났다.
방법을 제안한다. 또한, 제안하는 기법의 구간 설정 방법을 통해서 기존의 기법들에서는 발견할 수 없었던 의미 있는 연관 규칙들을 도출할 수 있음을 정량적으로 검증한다.
실험 1과 실험 2의 결과를 통해서, 제안하는 기법이 기존의 기법들에 비해서, 다수의 속성들을 우변으로 갖는연관 규칙을 도출하는 데에 유용한 기법임을 알 수 있다.
실험 1의 결과, 제안하는 기법인 RMUC가 기법 Clustering, 기법 Equi-depth에 비하여 전체적으로 많은 연관 규칙들을 도출하고, 이들의 신뢰도도 높은 것으로 나타났다.
실험 결과, 제안하는 기법은 기존의 클러스터링을 이용한 기법에 비해서 1.7배 가량 많은 연관 규칙들을 도출하는 것으로 나타났는데, 이는 제안하는 기법이 클러스터링 기법에서 누락되었던 연관 규칙들을 도출할 수있음을 의미한다. 제안하는 기법은 데이터의 개수가 동일하도록 속성의 구간을 설정한 기법에 비해서, 연관 규칙의 신뢰도가 0.
그림 3은 실험 2의 결과를 보인 것이다. 실험 결과, 제안하는 기법인 RMUC가 기법 Clustering, 기법 Equie depth에 비하여 우변에 다수의 속성들이 포함된 경우에, 우수한 성능을 보이는 것으로 나타났다. B1&B2의 경우, 기법 RMUC가 기법 Clustering과 기법 Equi-depth에비하여 평균 신뢰도/면적의 값으로서 각각 6.
7배 가량 많은 연관 규칙들을 도출하는 것으로 나타났는데, 이는 제안하는 기법이 클러스터링 기법에서 누락되었던 연관 규칙들을 도출할 수있음을 의미한다. 제안하는 기법은 데이터의 개수가 동일하도록 속성의 구간을 설정한 기법에 비해서, 연관 규칙의 신뢰도가 0.033 가량 향상된 것으로 나타났다. 또한, 제안하는 기법은 기존의 기법들에 비해서, 다수의속성들을 우변으로 갖는 연관 규칙을 도출하는 데에 우수한 성능을 보이는 것으로 나타났다.
참고문헌 (7)
B. Lent, A. Swami, and J. Widom, "Clustering Association Rules," In Proc. IEEE Int'l. Conf. on Data Engineering, IEEE ICDE, pp.220-231, 1997.
R. J. Miller and Y. Yang, "Association Rules Over Interval Data," In Proc. ACM Int'l. Conf. on Management of Data, ACM SIGMOD, pp.452-461, 1997.
R. Povinelli, Identifying Temporal Patterns for Characterization and Prediction of Financial Time Series Events, Springer Berlin, 2001.
M. Kamber, J. Han, and J. Chiang, "Metarule-Guided Mining of Multi-Dimensional Association Rules Using Data Cubes," In Proc. ACM Int'l. Conf. on Knowledge Discovery and Data Mining, ACM SIGKDD, pp.207-210, 1997.
T. Zhang, R. Ramakrishnan, and M. Livny, "BIRCH: An Efficient Data Clustering Method for Very Large Databases," In Proc. ACM Int'l. Conf. on Management of Data, ACM SIGMOD, pp. 103-114, 1996.
T. Zhang, R. Ramakrishnan, and M. Livny, "Data Clustering System BIRCH and Its Applications," Data Mining and Knowledge Discovery, vol.1, no.2, pp.141-182, 1997.
D. Harrison and D. L. Rubinfeld, "Hedonic Housing Prices and the Demand for Clean Air," Journal of Environmental Economics and Management, vol.5, pp.81-102, 1978.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.