[논문]Fuzzy Utility를 활용한 연관규칙 마이닝 시스템을 위한 알고리즘의 구현에 관한 연구

박인규; 최규석

doi:10.7236/jiibc.2020.20.1.19

Fuzzy Utility를 활용한 연관규칙 마이닝 시스템을 위한 알고리즘의 구현에 관한 연구
A Study on the Implementation of an optimized Algorithm for association rule mining system using Fuzzy Utility 원문보기

The journal of the institute of internet, broadcasting and communication : JIIBC, v.20 no.1, 2020년, pp.19 - 25

박인규 (중부대학교 게임소프트웨어공학과) , 최규석 (청운대학교 컴퓨터공학과)

초록
AI-Helper

빈발 패턴 마이닝에서 각 패턴이 가지는 불확실한 정보로 인하여 정보의 손실을 수반하기 마련이다. 또한 실제적인 환경에서는 패턴들의 중요도가 시간에 따라서 변하기 때문에 이러한 요구에 부합하기 위하여 퍼지논리를 적용하고 패턴이 가지는 중요도의 동적특성을 고려하여야 한다. 본 논문에서는 웹 로그 데이터베이스에서 퍼지 유틸리티 기반 웹페이지 집합 마이닝을 통해 웹 로그 데이터베이스에서 빈발 웹 페이지 집합의 추출을 위한 퍼지 유틸리티 마이닝 기법을 제안한다. 여기서 퍼지 집합의 하향 폐쇄 특성은 최소 퍼지 유틸리티 임계 값(MFUTV) 및 사용자 정의 백분위 수(UDP)에 의해 넓은 공간을 제거하기 위해 적용된다. 여러 실험을 통하여 제안하는 기법은 매우 효과이며 확장성이 좋은 것임을 보인다.

Abstract ▼ AI-Helper

In frequent pattern mining, the uncertainty of each item is accompanied by a loss of information. AAlso, in real environment, the importance of patterns changes with time, so fuzzy logic must be applied to meet these requirements and the dynamic characteristics of the importance of patterns should be considered. In this paper, we propose a fuzzy utility mining technique for extracting frequent web page sets from web log databases through fuzzy utility-based web page set mining. Here, the downward closure characteristic of the fuzzy set is applied to remove a large space by the minimum fuzzy utility threshold (MFUT)and the user-defined percentile(UDP). Extensive performance analyses show that our algorithm is very efficient and scalable for Fuzzy Utility Mining using dynamic weights.

주제어

표/그림 (11)

그림 그림 1. 퍼지 분할 Fig. 1. Fuzzy Partition
표 표 1. 각 속성의 정의된 외부 유틸리티 Table 1. Predefined external utility of each attribute
표 표 2. 속성의 내부 유틸리티를 갖는 트랜잭션 Table 2. Transactions with internal utility of attributes
표 표 3. 각 속성의 퍼지 영역에 대한 퍼지 유틸리티 Table 3. Fuzzy utilities of fuzzy region of each attribute
표 표 4. 최대 트랜잭션 퍼지 유틸리티 Table 4. Maximum transaction fuzzy utility
표 표 5. FTWU를 가지는 2-웹 페이지 집합 Table 5. 2-webpage ses with FTWU
그림 그림 3. 실행시간 대 웹 트랜잭션 수 Fig. 3. Running time vs number of web transactions
그림 그림 4. 실행시간 대 최소 임계값 Fig. 4. Running time vs min_threshhold
그림 그림 2. 제안된 알고리즘 Fig. 2. The proposed algorithm
그림 그림 5. 빈발 웹 페이지 집합 패턴 대 최소 임계값 Fig. 5. Frequent webpage sets vs minimum threshhold
그림 그림 6. 빈발 웹 페이지 집합 대 트랜잭션 수 Fig. 6. Frequent webpage sets vs number of transactions

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

그림 5은 서로 다른 MFUT 백분율 값에서 생성된 웹 페이지 집합의 여러 가지 빈발 패턴을 나타낸다. 고정 된 웹 트랜잭션 수를 유지하면서 여러 MFUT 값에서 생성되는 웹 페이지의 빈발 패턴 수를 관찰하기 위해 수행되었다. IHUP와 UP-Growth는 가장 많은 수의 웹 페이지 집합 패턴을 생성한다.
본 논문에서는 웹 로그 데이터베이스에서 퍼지 유틸리티를 기반으로 웹 페이지의 빈발집합을 추출하는 웹 페이지를 마이닝 기법을 제안하였다. FCM과 엔트로피 개념을 사용하여 속성들의 초기분할을 수행하고, 새로운 퍼지 유틸리티 기능을 도입하고 퍼지 집합의 하향 폐쇄 특성이 최소 퍼지 유틸리티 임계 값 (MFUT) 및 사용자 정의 백분위 수 (UDP) 접근 방식으로 넓은 공간을 제거하는 데 적용되었다.

가설 설정

마이닝에서 사용되는 외부 유틸리티 값은 표 1처럼 1에서 10까지로 항목의 가중치로 가정하고. 데이터베이스의 트랜잭션은 내부 유틸리티로서 표 2와 같이 항목이 가지는 빈도수로 구성된다.

제안 방법

본 논문에서는 웹 로그 데이터베이스에서 퍼지 유틸리티를 기반으로 웹 페이지의 빈발집합을 추출하는 웹 페이지를 마이닝 기법을 제안하였다. FCM과 엔트로피 개념을 사용하여 속성들의 초기분할을 수행하고, 새로운 퍼지 유틸리티 기능을 도입하고 퍼지 집합의 하향 폐쇄 특성이 최소 퍼지 유틸리티 임계 값 (MFUT) 및 사용자 정의 백분위 수 (UDP) 접근 방식으로 넓은 공간을 제거하는 데 적용되었다. 실험 결과는 제안한 방법이 실행 시간 및 웹 로그 데이터베이스에서 높은 유틸리티 웹 페이지 집합 추출 측면에서 기존의 알고리즘보다 양호함을 보였다.
유틸리티 값을 모두 계산하고 정규화해 준다. 그리고 그 정규화한 값을 지정된 임계값을 기준으로 그 이하의 값을 가지는 항목들을 필터링한다. ur은 0과 1 사이로 지정한 0.
이러한 이유로 양적 데이터베이스에서 퍼지 규칙을 효율적으로 찾는 것이 매우 중요한 문제로 대두된다. 빈발패턴을 추출하기 위해 거의 모든 기존 알고리즘이 먼저 후보 패턴 집합을 생성 한 다음 각 후보의 정확한 유틸리티를 계산하여 빈발패턴을 식별하고, 웹 로그 데이터베이스에서 퍼지 유틸리티 웹 페이지를 추출하는 기법을 제안한다. 이 기법에서는 집합의 각 멤버에 적절한 값을 할당하기 위해 새로운 퍼지 집합 멤버쉽 기능이 정의되었다.
이로 인해 트랜잭션 데이터베이스에서 유틸리티를 기반으로 하는 마이닝이 생겼다. 상한(Upper) 모델을 사용하여 데이터베이스의 최대 가중치(이익) 값을 각 트랜잭션의 가중치 상한으로 채택한 새로운 하향 폐쇄 특성을 제안했다. IHUP^[4]기법은 다중 데이터베이스 스캔을 피함으로써 마이닝의 성능을 향상 시켰고, UP-Growth은 UP-Tree에서 높은 유틸리티 패턴 집합을 효율적으로 얻을 수 있지만 두 번의 스캔으로 시간적인 문제가 있다^[5].
세 번째 단계는 웹 로그 데이터베이스에서 IU 및 할당된 EU 값을 사용하여 T_d에 속하는 모든 웹 페이지(a_i) 에 대하여 MFTU를 계산하고, MFTU를 이용하여 FTWU 값을 계산한다. 표 5에서 T₁ 트랜잭션의 최대 퍼지 거래 유틸리티 (MFTU)는 다음과 같이 계산된다.
알고리즘의 성능을 알아보기 위하여 실행시간을 측정하였다. 제안된 방법의 검증을 위하여 기존의 IHUP(UP-Growth) 및 HUIMiner(FHM 알고리즘)와 비교하였다.
그림 4는 서로 다른 최대 퍼지 유틸리티 임계값인 MFUT에서 기존의 방법인 IHUP, FHM, HUI-Miner, UP-Growth 및 제안된 기법과의 소요 된 시간을 비교한 것이다. 웹 트랜잭션 수만 건에 대해 MFUT를 백분율로 변경하여 실험을 수행하였다. MFUT가 증가함에 따라 많은 수의 낮은 퍼지 유틸리티 웹 페이지 제거로 인해 실행 시간이 실질적으로 감소함을 보여준다.
제안된 방법의 검증을 위하여 기존의 IHUP(UP-Growth) 및 HUIMiner(FHM 알고리즘)와 비교하였다. 일관성을 위하여 최소 퍼지 유틸리티 임계값 (MFUT)을 15로 유지하면서 실험하였다^[14,15,16].
FHM은 후보 생성 및 유틸리티 계산 수를 줄여서 실행 시간을 단축하였다. 제안된 기법은 이러한 전체 알고리즘 중에서 가장 짧은 시간에 빈발 항목을 추출하였다. 그 이유는 후보 항목 집합을 생성하지 않고 오히려 퍼지 항목만 저장하고 바람직하지 않은 항목 집합을 제거하기 때문이다.

데이터처리

알고리즘의 성능을 알아보기 위하여 실행시간을 측정하였다. 제안된 방법의 검증을 위하여 기존의 IHUP(UP-Growth) 및 HUIMiner(FHM 알고리즘)와 비교하였다. 일관성을 위하여 최소 퍼지 유틸리티 임계값 (MFUT)을 15로 유지하면서 실험하였다^[14,15,16].

이론/모형

이 문제를 해결하기 위해 퍼지 집합의 언어적 변수를 이용하여 표현되는 양의 선명한 경계를 부드럽게 처리하여 정보의 손실을 막을 수 있다. 따라서 선명한 경계 문제와 물리적 측정의 부정확성을 보다 잘 처리하기 위하여 퍼지 유틸리티 마이닝(fuzzy utility mining)을 활용하고자 한다.

성능/효과

IHUP은 웹 페이지의 빈발집합을 많이 생성하지만 웹 페이지 빈발집합이 높은 유용성을 보장하지는 않는다. 결국 제안된 방법은 높은 유틸리티를 가지는 웹 페이지 빈발집합을 추출하는 측면에서 기존의 알고리즘보다 양호하다.
MFUT 4 % 이후부터 퍼지 낮은 유틸리티를 가지는 웹 피이지는 제거되므로 실행 시간이 더 빠르다. 따라서 제안된 방법의 실행 시간이 양호하여 퍼지 유틸리티 기반의 웹 페이지 집합 마이닝의 효율성이 높아졌다고 볼 수 있다.
FCM과 엔트로피 개념을 사용하여 속성들의 초기분할을 수행하고, 새로운 퍼지 유틸리티 기능을 도입하고 퍼지 집합의 하향 폐쇄 특성이 최소 퍼지 유틸리티 임계 값 (MFUT) 및 사용자 정의 백분위 수 (UDP) 접근 방식으로 넓은 공간을 제거하는 데 적용되었다. 실험 결과는 제안한 방법이 실행 시간 및 웹 로그 데이터베이스에서 높은 유틸리티 웹 페이지 집합 추출 측면에서 기존의 알고리즘보다 양호함을 보였다. 기존의 알고리즘보다 약 20∼ 35 % 더 효율적이다.
또한 웹 데이터베이스에서 하나의 스캔만 필요하기 때문에 전체적으로 계산 시간을 단축시켜 마이닝 속도를 향상시킨다. 제안된 기법은 실행 시간에서 IHUP (Incremental High Utility Pattern), UP-Growth, HUI-Miner (High Utility Itemset Miner) 및 FHM (Faster High-Utility Itemset Mining)의 기존 알고리즘보다 양호하다는 것을 보이고자 한다.
그림 6은 웹 트랜잭션 수에 대해 생성 된 웹 페이지 집합의 여러 가지 패턴을 보여준다. 제안된 방법은 적은 수의 빈발웹 페이지 집합을 생성하지만 퍼지 유틸리티가 높다. IHUP은 웹 페이지의 빈발집합을 많이 생성하지만 웹 페이지 빈발집합이 높은 유용성을 보장하지는 않는다.

후속연구

기존의 알고리즘보다 약 20∼ 35 % 더 효율적이다. 따라서 이러한 접근 방식(제한된 방식)을 통해 얻은 결론은 인공지능형 검색엔진 내부에 지식 베이스를 추가하여 지능형 검색에 활용될 수 있을 것으로 사료된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	웹 사용 마이닝은 어디에 사용되고 있는가?	웹 사용 마이닝은 웹 마이닝 범주 중 하나로서 방문자가 웹 사이트를 서핑 할 때 웹 서버의 로그 파일에 기록된 사용자 활동에서 시간에 따라서 변하는 유용한 패턴을 마케팅 전략에 활용되고 있다. 예를 들어, 웹상의 데이터와 지식은 부정확하고 불완전하며 불확실한 데이터로 구성되어 진다.
	부정확하고 불완전하며 불확실한 데이터를 처리하는데 쓰이는 개념은?	예를 들어, 웹상의 데이터와 지식은 부정확하고 불완전하며 불확실한 데이터로 구성되어 진다. 퍼지 개념은 종종 이러한 데이터를 처리하는 데 사용되므로, 퍼지 및 언어 지식을 밝히기 위한 여러 가지 퍼지 웹 마이닝 기법이 존재한다[1].
	퍼지 집합의 하향 폐쇄 특성의 용도는?	본 논문에서는 웹 로그 데이터베이스에서 퍼지 유틸리티 기반 웹페이지 집합 마이닝을 통해 웹 로그 데이터베이스에서 빈발 웹 페이지 집합의 추출을 위한 퍼지 유틸리티 마이닝 기법을 제안한다. 여기서 퍼지 집합의 하향 폐쇄 특성은 최소 퍼지 유틸리티 임계 값(MFUTV) 및 사용자 정의 백분위 수(UDP)에 의해 넓은 공간을 제거하기 위해 적용된다. 여러 실험을 통하여 제안하는 기법은 매우 효과이며 확장성이 좋은 것임을 보인다.

참고문헌 (16)

M. Zdravko and T. L. Daniel, "Data Mining the Web, Uncovering Patterns In Web Content, Structure and Usage", John Wiley & sons Inc., New Jersey, USA, pp. 115-132, 2007. https://doi.org/10.18637/jss.v025.b01
C. W. Lin and T. P. Hong, "A survey of fuzzy web mining", Data Mining Knowledge Discovery, Vol.3, No. 13, pp. 190-199, 2013 https://doi.org/10.1002/widm.1091

상세보기
R. Agrawal, T. Imielinski, and A. Swami, "Mining association rules between sets of items in large databases", In: Proc. of ACM Sigmod Record, ACM. Vol. 22, pp. 207-216, 1993. https://doi.org/10.1145/170036.170072

상세보기
R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A.I. Verkamo, "Fast discovery of association rules", In: Proc. of Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, pp. 307-328, 1996. https://doi.org/10.1109/fskd.2008.332
U. Yun and J.J Leggett, "Wfim: Weighted frequent itemset mining with a weight range and a minimum weight", In: Proc. of International Conf. on Data Mining, SIAM, pp. 636-640, 2005. https://doi.org/10.1137/1.9781611972757.76
C.F. Ahmed, S.K. Tanbeer, B. S. Jeong, and Y. K. Lee, "Efficient tree structures for high utility pattern mining in incremental databases", IEEE Transactions on Knowledge and Data Engineering, Vol. 21, No. 12, pp. 1708-1721, 2009. https://doi.org/10.1109/tkde.2009.46

상세보기
S. Vincent, C. W. Tseng, B. E. Wu, Shie, and P. S. Yu, "UP-Growth: An Efficient Algorithm for High Utility Itemset Mining", In: Proc. of ACM-Knowledge Data Discovery, Washington, DC, USA, pp. 253-262, 2010. https://doi.org/10.1145/1835804.1835839
U. Yun, H. Ryang, and K.H. Ryu, "High utility itemset mining with techniques for reducing over-estimated utilities and pruning candidates", Expert Systems with Applications, Vol. 41 No. 8, pp.3861-3878, 2014. https://doi.org/10.1016/j.eswa.2013.11.038

상세보기
C. M. Wang, S. H. Chen, and Y. F. Huang, "A fuzzy approach for mining high utility quantitative itemsets", In: Proc. of Fuzzy Systems, FUZZ-IEEE International Conf. on IEEE, pp. 1909-1913, 2009. https://doi.org/10.1109/fuzzy.2009.5277408
K. K. Mohbey, "High fuzzy utility based frequent patterns mining approach for mobile web services sequences", International Journal of Engineering (IJE), TRANSACTIONS B: Applications", Vol. 30, No. 2, pp. 182-191 , 2017. https://doi.org/10.5829/idosi.ije.2017.30.02b.04
L.A. Zadeh, "The concept of a linguistic variable and its application to approximate reasoning-1", Information Science, Vol.8, pp.199-249, 1975. https://doi.org/10.1016/0020-0255(75)90017-1

상세보기
S. G. Matthews, M. A. Gongora, A. A. Hopgood, and S. Ahmadi, "Web usage mining with evolutionary extraction of temporal fuzzy association rules", Knowledge Based System, Vol. 54 pp. 66-72, 2013. https://doi.org/10.1016/j.knosys.2013.09.003

상세보기
V. Kumar, R. S. Thakur "High Fuzzy Utility Based Sets Mining from Weblog Database", Int. Journal of Intelligent Engineering & System, Vol. 16, pp. 191-200, 2017. https://doi.org/10.22266/ijies2018.0228.20

상세보기
Y. S. Im, E. Y. Kang, "MPEG-2 Video Watermarking in Quantized DCT Domain," The Journal of The Institute of Internet, Broadcasting and Communication(JIIBC), Vol. 11, No. 1, pp. 81-86, 2011. https://doi.org/10.1109/tip.2006.873476

원문보기 상세보기
I. Jeon, S. Kang, H. Yang, "Development of Security Quality Evaluate Basis and Measurement of Intrusion Prevention System," Journal of the Korea Academia-Industrial cooperation Society (JKAIS), Vol. 11, No. 1, pp. 81-86, 2010. https://doi.org/10.5762/kais.2010.11.4.1449

원문보기 상세보기
J. S. Oh, B, S. Lee, "A Study for Lifespan Prediction of Expansion by Temperature Status,", The Journal of KISTI, Vol. 19, No. 10, pp. 424-429637, 2018. http://dx.doi.org/10.5762/KAIS.2018.19.10.424

원문보기 상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증