[논문]그룹특징기반 슬라이딩 윈도우 클러스터링에서의 k-means와 k-medoids 비교 평가

양주연; 심준호

doi:10.7838/jsebs.2018.23.3.225

[국내논문] 그룹특징기반 슬라이딩 윈도우 클러스터링에서의 k-means와 k-medoids 비교 평가
Comparison between k-means and k-medoids Algorithms for a Group-Feature based Sliding Window Clustering 원문보기

한국전자거래학회지 = The Journal of Society for e-Business Studies, v.23 no.3, 2018년, pp.225 - 237

양주연 (Dept of Computer Science, Sookmyung Women's University) , 심준호 (Dept of Computer Science, Sookmyung Women's University)

초록
AI-Helper

대용량 데이터의 발생과 처리가 대중화되면서 대용량 데이터 스트림 처리에 대한 수요가 급격하게 증가하고 있다. 이 수요에 따라 다양한 대용량 데이터 처리 기술이 개발되고 있다. 한 분야로 주목받고 있는 방식은 슬라이딩 윈도우를 사용한 데이터 스트림 클러스터링이다. 슬라이딩 윈도우를 사용한 데이터 스트림 클러스터링은 윈도우가 이동할 때마다 새로운 클러스터를 생성한다. 기존의 슬라이딩 윈도우 상의 클러스터링 기법은 코어셋(Coreset)을 기반으로 데이터 스트림 클러스터링을 구현하고 있다. 이 연구에서는 코어셋을 활용한 그룹특징을 이용한 알고리즘 내에서 이용하는 클러스터링 알고리즘을 변경하였다. 그리고 이를 통해 제안 알고리즘과 기존 알고리즘의 파라미터 값 변화에 따른 성능 비교 실험을 진행하였다. 개선된 사항에 대해 논하여 두 알고리즘을 비교하고 실험자에게 파라미터에 따른 이용 방향을 제시한다.

Abstract ▼ AI-Helper

The demand for processing large data streams is growing rapidly as the generation and processing of large volumes of data become more popular. A variety of large data processing technologies are being developed to suit the increasing demand. One of the technologies that researchers have particularly observed is the data stream clustering with sliding windows. Data stream clustering with sliding windows may create a new set of clusters whenever the window moves. Previous data stream clustering techniques with sliding windows exploit the coresets, also known as group features that summarize the data. In this paper, we present some reformable elements of a group-feature based algorithm, and propose our algorithm that modified the clustering algorithm of the original one. We conduct a performance comparison between two algorithms by using different parameter values. Finally, we provide some guideline for the selective use of those algorithms with regard to the parameter values and their impacts on the performance.

Keyword

표/그림 (12)

그림 Sliding Window Process
그림 Clustering based on Group Features
그림 Process for K-Means and K-Medoids
그림 Performance Comparison Procedure
그림 How to Process TSV Files as K-Means
그림 How to Process TSV Files as K-Medoids
그림 SSQ of the Dataset ‘knews.tsv’(Comparative group: K)
그림 SSQ of the Dataset ‘covtype.tsv’(Comparative group: K)
그림 SSQ of the Dataset ‘syn1k30d40.tsv’(Comparative group: K)
그림 Process Time of the Dataset ‘knews.tsv’(Comparative group: K)
그림 Process Time of the Dataset ‘covtype.tsv’(Comparative group: K)
그림 Process Time of the Dataset ‘syn1k30d40.tsv’(Comparative group: K)

AI 본문요약
AI-Helper

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

문제 정의

본 연구에서는 대형 데이터 스트림을 실시간으로 처리하는 클러스터링 기법 중 실시간 처리에 중점을 두는 알고리즘에 대해 이야기하고자 한다. 데이터 값을 그룹화[2]하고 클러스터링을 진행하는 과정을 구분하는 두 단계로 진행하는 클러스터링 방식[9]을 기반으로 하여 그룹화 하는 과정에서 사용하는 클러스터링 기법의 변화가 데이터 클러스터링 결과에 어떠한 영향을 미치는 지 확인하였다.
또한 데이터의 모든 정보의 가중치를 동일하다고 계산하여 데이터의 실질 분별에 있어서 신뢰도가 낮다는 단점을 가지고 있다. 따라서 k-means 알고리즘의 단점을 보강하기 위해 제시된 k-medoids 알고리즘을 적용하여 최종 클러스터링 값에 미치는 영향을 파악하고 개선 방향을 제시해보고자 한다.
그럼에도 k-means 알고리즘이 이상 값에 크게 반응한다는 단점을 해결하기 위해서 가장우선적으로 k-medoids 알고리즘을 대체하고자 한다. 데이터셋의 형태를 따라 k-means 알고리즘을 적용한 클러스터링과 k-medoids 알고리즘을 적용한 클러스터링의 결과 값을 비교하여 클러스터링 성능과 시간 성능을 개선하는 알고리즘의 기반을 제시하고자 한다.

제안 방법

본 연구에서는 대형 데이터 스트림을 실시간으로 처리하는 클러스터링 기법 중 실시간 처리에 중점을 두는 알고리즘에 대해 이야기하고자 한다. 데이터 값을 그룹화[2]하고 클러스터링을 진행하는 과정을 구분하는 두 단계로 진행하는 클러스터링 방식[9]을 기반으로 하여 그룹화 하는 과정에서 사용하는 클러스터링 기법의 변화가 데이터 클러스터링 결과에 어떠한 영향을 미치는 지 확인하였다.
기존에 이미 제안된 알고리즘에서는 k-means 알고리즘을 이용하여 그룹화 한 데이터를 클러스터링 하였으나 제안 알고리즘에는 k-medoids알고리즘을 적용하여 기존 알고리즘과 제안 알고리즘의 성능 차이와 데이터 셋에 따른 추이를 비교하였다. 그리고 이를 통해 파라미터에 따른 두 알고리즘의 선택 방향에 대해서 제안하였다.
기존에 이미 제안된 알고리즘에서는 k-means 알고리즘을 이용하여 그룹화 한 데이터를 클러스터링 하였으나 제안 알고리즘에는 k-medoids알고리즘을 적용하여 기존 알고리즘과 제안 알고리즘의 성능 차이와 데이터 셋에 따른 추이를 비교하였다. 그리고 이를 통해 파라미터에 따른 두 알고리즘의 선택 방향에 대해서 제안하였다.
각 단계는 슬라이딩 윈도우와 LSH 알고리즘을 이용하여 클러스터링을 진행하여 시놉시스, 즉 그룹특징을 생성하는 부분과 그룹특징을 활용하여 클러스터링을 진행하는 부분으로 나뉜다. 하지만 이 연구에서 중점적으로 보기 위한 부분은 그룹특징을 활용하여 클러스터링을 진행하는 두 번째 부분의 그룹화 클러스터링 알고리즘을 수정하고 성능을 비교하였다. 따라서 두 단계로 진행되는 알고리즘의 기본 원리와 중점적으로 사용되는 슬라이딩 윈도우에 대한 정의, 그리고 기존에 사용된 그룹화 클러스터링 알고리즘에 대해 기술하였다.
하지만 이 연구에서 중점적으로 보기 위한 부분은 그룹특징을 활용하여 클러스터링을 진행하는 두 번째 부분의 그룹화 클러스터링 알고리즘을 수정하고 성능을 비교하였다. 따라서 두 단계로 진행되는 알고리즘의 기본 원리와 중점적으로 사용되는 슬라이딩 윈도우에 대한 정의, 그리고 기존에 사용된 그룹화 클러스터링 알고리즘에 대해 기술하였다.
그럼에도 k-means 알고리즘이 이상 값에 크게 반응한다는 단점을 해결하기 위해서 가장우선적으로 k-medoids 알고리즘을 대체하고자 한다. 데이터셋의 형태를 따라 k-means 알고리즘을 적용한 클러스터링과 k-medoids 알고리즘을 적용한 클러스터링의 결과 값을 비교하여 클러스터링 성능과 시간 성능을 개선하는 알고리즘의 기반을 제시하고자 한다.
제곱거리의 합은 Σ∥ S_i - C_i∥²로 계산이 가능하다. 제곱거리의 합 성능은 그룹특징마다 값이 모두 다르므로 K개의 그룹특징 값의 평균 제곱거리의 합 성능 값을 비교하여 해당 알고리즘의 성능을 평가한다.
k-means 알고리즘의 경우 유클리드 거리를 계산하는 함수를 이용하여 처리되며, k-medoids알고리즘은 대중적으로 맨해튼 거리를 계산하는 PAM(Partitioning Around Medoids) 함수로 처리되게끔 설정하였다. 두 함수는 JSAT[7]에서 제공하는 오픈 라이브러리를 수정하여 사용하였다. 차이는 [Figure 5]와 [Figure 6]을 통하여 알 수 있다.
이때 사용되는 k-means 알고리즘과 k-medoids알고리즘에서 초기 무작위 중심점, 중간 점을 설정하는 방식은 모두 최대한 멀리에 존재하는 값들이 우선 지정되게 설정하였으며 이를 통해 보다 효과적인 알고리즘 구현을 진행하였다.
R값과 L값은 증가하면 증가할수록 데이터처리 속도가 급격하게 증가하는 사안을 이유로 실험환경에서 최상의 상태를 유지할 수 있는 값을 채택하였다. 따라서 R값은 500, L값은 100으로 설정한 뒤 K값을 조정하며 k-means 알고리즘과 k-medoids 알고리즘의 성능 상태를 확인하였다. 예를 들어 제 2장 관련 연구에서 나타난 [Figure 1]에서, R, L, K는 각각 1,000, 100,3의 값을 나타내고 있다.
k-means 알고리즘과 k-medoids 알고리즘은 성능이 클러스터의 수인 K값에 가장 영향을 많이 받기 때문에 위와 같은 환경에서 비교하는 것을 중점으로 실험을 진행하였다.
실험은 K를 변경하는 것을 기반으로 진행하였다. K값에 대한 실험을 진행한 결과 값을 표로 그려 성능 비교를 진행하였다.

대상 데이터

실험은 총 세 가지의 데이터 셋을 중심으로 진행되었다. 첫 번째로는 국내 포털 사이트에서 제공되는 뉴스 정보 값을 임의로 추출하여 생성한 ‘knews.
8에서 진행하였다. 데이터 셋은 위에서 언급한 세 가지의 각각의 특징을 가진 데이터를 사용하였다. [Figure 1]을 참조하면 K는 그룹특성, 곧 클러스터 설정 수, R은 윈도우전체 범위의 수, L은 윈도우 슬라이드의 수를 지칭한다.

데이터처리

실험은 K를 변경하는 것을 기반으로 진행하였다. K값에 대한 실험을 진행한 결과 값을 표로 그려 성능 비교를 진행하였다. 성능은 평균 제곱거리의 합과 수행 시간을 비교하였으며 평균 제곱거리의 합의 비교 결과로는 얼마나 효율적인 클러스터링이 진행되었는지를 확인할 수 있다.

이론/모형

본 연구에서는 슬라이딩 윈도우 모델을 기반으로 하여 데이터 스트림을 처리하는 알고리즘을 활용하였다. 해당 알고리즘의 수행 과정은 두 단계로 나누어 진행된다.
윈도우 슬라이드에 들어간 데이터들은 LSH함수를 통해 그룹특징을 생성한다. 그리고 그 그룹특징을 클러스터링 단위로 삼아 k-means 알고리즘, 또는 k-medoids 알고리즘을 이용하여 클러스터링을 진행한다.

성능/효과

R값과 L값은 증가하면 증가할수록 데이터처리 속도가 급격하게 증가하는 사안을 이유로 실험환경에서 최상의 상태를 유지할 수 있는 값을 채택하였다. 따라서 R값은 500, L값은 100으로 설정한 뒤 K값을 조정하며 k-means 알고리즘과 k-medoids 알고리즘의 성능 상태를 확인하였다.
K값에 대한 실험을 진행한 결과 값을 표로 그려 성능 비교를 진행하였다. 성능은 평균 제곱거리의 합과 수행 시간을 비교하였으며 평균 제곱거리의 합의 비교 결과로는 얼마나 효율적인 클러스터링이 진행되었는지를 확인할 수 있다. 그리고 수행 시간의 비교 결과로는 어떤 알고리즘이 더욱 시간을 적게 소요하여 효율적인 성능을 냈는지를 확인할 수 있다.
성능은 평균 제곱거리의 합과 수행 시간을 비교하였으며 평균 제곱거리의 합의 비교 결과로는 얼마나 효율적인 클러스터링이 진행되었는지를 확인할 수 있다. 그리고 수행 시간의 비교 결과로는 어떤 알고리즘이 더욱 시간을 적게 소요하여 효율적인 성능을 냈는지를 확인할 수 있다.
위의 세 그래프 모두를 비교하면 k-means 알고리즘이 k-medoids 알고리즘에 비해 상대적으로 클러스터링 결과가 확실한 형태를 보인다. K값이 증가함에 따라 두 알고리즘 간의 격차가 줄어드는 것은 클러스터링 알고리즘의 특성에 의한 것이므로 제할 수 있다.
수행 시간 비교에서는 평균 제곱거리의 합의 값을 비교했을 때와 정 반대의 양상이 나타났다. k-medoids 알고리즘의 속도가 평균적으로 추측이 가능한 추이를 나타내며 k-means 알고리즘보다 좋은 성능을 냈음을 알 수 있다.
k-means 알고리즘의 경우 ‘평균 제곱거리의 합’ 측면에서 훨씬 좋은 성능을 나타냈고 kmedoids알고리즘의 경우 ‘수행 시간’ 측면에서보다 더 좋은 성능을 나타냈다. 따라서 해당 클러스터링을 진행할 때, 어떠한 파라미터를 우선순위로 두고 클러스터링을 진행하는지에 따라 둘 중 어느 알고리즘을 선택하는 지에 결정적인 역할을 하게 될 것이라는 것을 알 수 있었다.
더불어 본 연구에서는 실험 과정을 통해 클러스터 값을 어떻게 설정하는지에 따라 평균 제곱거리의 합 측면에서 차이를 나타낼 수 있음을 알 수 있다. 따라서 이에 대한 추가적인 실험을 통해 k-means 알고리즘과 k-medoids알고리즘의 알고리즘 사용 방향성을 찾아낼 수 있다는 것을 알았다.
더불어 본 연구에서는 실험 과정을 통해 클러스터 값을 어떻게 설정하는지에 따라 평균 제곱거리의 합 측면에서 차이를 나타낼 수 있음을 알 수 있다. 따라서 이에 대한 추가적인 실험을 통해 k-means 알고리즘과 k-medoids알고리즘의 알고리즘 사용 방향성을 찾아낼 수 있다는 것을 알았다. 이는 추가적인 실험의 지속과정을 통해 정확한 수치와 비교 분석이 필요하며, 이를 통해 현장에서 이용하는 방향에 K, L, R과 같은 파라미터 측면에서 조금 더 명확한 가이드라인을 제시해 줄 수 있을 것이다.

후속연구

따라서 이에 대한 추가적인 실험을 통해 k-means 알고리즘과 k-medoids알고리즘의 알고리즘 사용 방향성을 찾아낼 수 있다는 것을 알았다. 이는 추가적인 실험의 지속과정을 통해 정확한 수치와 비교 분석이 필요하며, 이를 통해 현장에서 이용하는 방향에 K, L, R과 같은 파라미터 측면에서 조금 더 명확한 가이드라인을 제시해 줄 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	빅데이터를 활용하기 위해 대형 데이터 스트림의 처리가 필수적인 이유는 무엇인가?	빅데이터에서 사용되는 대용량 데이터는 실시간으로 수집되는 정보를 기반으로 한다. 따라서 빅데이터를 제대로 활용하기 위해서는 대형 데이터 스트림의 처리가 필수적이다.
	빅데이터는 무엇인가?	빅데이터[6, 8]는 정보, 기술, 효과, 방법론의 총 집합체로서 정보 기술의 최신 동향으로 주시되고 있다. 빅데이터는 이름 그대로 대용량데이터를 처리하고 이를 통해 추출한 정보를 이용하여 기술적, 혹은 사회적 적용을 하는 것까지 포함하는 매우 포괄적인 정의를 가진다.
	데이터 스트림을 실시간으로 클러스터링 처리하는 기법이 제시되는 이유는 무엇인가?	대형 데이터 스트림을 처리하는 방식에는 다양한 방식이 존재한다[11]. 데이터 스트림은 실시간으로 정보 값이 변화하는 특수성을 가지고 있고, 이를 통해 변화하는 추이를 확인하기 위해야 한다는 특수성을 가지고 있기 때문에 데이터 스트림을 실시간으로 클러스터링 처리하는 기법이 제시된다.

저자의 다른 논문 :

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: 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

연합인증