인포리언스

클릭 >> Hello, world !! (from ShadowEgo)

1. (1)편 (http://222.114.71.21:10100/2017/07/31/codipintro1/)%EC%97%90 이어서…
2. 본 포스팅의 세부 요소 기술들은 모두 특허로 보호되고 있습니다. (http://222.114.71.21:10100/2018/05/24/patent2017july/

데이터를 수집했다. 그러나.

데이터를 수집하고 처리하는 시스템을 만드는 가장 기본적인 이유는 데이터에서 가치를 뽑아내고 활용하는 것이다. 그럼에도 불구하고, 많은 데이터 분석 관련 프로젝트들이 데이터를 수집하고 저장하는 시스템이나 플랫폼을 만드는 것에만 초점을 맞추고, 정작 데이터를 활용할 구체적인 방안을 만드는 데에는 소홀한 경우가 많다. 이러한 현상이 발생하는 대표적인 이유는, 데이터에서 가치를 뽑아내는 과정에는 소프트웨어 개발자나 데이터 분석 전문가들의 기술적 역량만으로 해결할 수 없는 문제들이 포함되어 있기 때문이다. 지난 (1)편에서도 언급한 바와 같이, 데이터에서 가치를 뽑아내려면, 데이터를 생성하는 주체의 특성과 상태, 생성 환경에 대한 개별적 지식과 경험이 어떻게든 활용되어야 한다.

프로그래머이면서 IoT 에 관심이 많은 김인포씨는 시중에서 판매하는 센서 세트를 구입하여 자신이 살고 있는 집의 곳곳에 센서를 설치했다. 출입문, 냉장고 문, 화장실 문 등에는 가속도 센서를, 부엌에는 온습도 센서를, 거실과 화장실에는 조도 센서를, 그리고 창문 근처에는 먼지 센서를 설치했다. 그리고 각 센서 데이터가 서버에 저장되도록 설정까지 마쳤다. 그리고는 모니터 화면에 나타나는 그래프를 보며 완벽한 IoT 환경을 만들었다는 생각을 하며 미소를 지었다. 내친 김에 김인포씨는 금융과 주식 정보를 받아오는 스크립트를 작성해서 수치를 확인할 수 있도록 dashboard 를 구성하는 작업까지 마쳤다. 김인포씨는 이제부터 매우 지능적인 생활을 할 수 있을 거라는 생각에 친구들에게 자랑을 했다.

그런데 친구인 최지능씨가 김인포씨의 자랑을 듣고는 이런 말을 했다.

“오, 멋진데, 그럼 이제 가만히 있기만 해도 중요한 정보를 다 알 수 있게 된거야?”

김인포씨가 그렇다고 대답을 하자, 최지능씨는 또 물었다.

“그럼 밖에서 일하고 있다가도 중요한 상황이 되면 실시간으로 정보를 받아볼 수도 있겠네?”

이 질문을 받고는 김인포씨는 잠시 갸우뚱했다. 데이터를 수집할 수도 있고, 그래프로 확인하는 것도 가능한데, 정작 어느 타이밍에 어떤 상황을 파악해야 하는지는 알 수 없을 것 같았다. 김인포씨는 검색을 통해 이러한 용도로 사용할 수 있는 소프트웨어나 서비스를 찾아봤지만 쉽게 찾을 수 없었다.

데이터에서 패턴을 탐지할 수 있게

CoDIP의 가장 기본적인 기능은 지속적으로 수집되는 수치 데이터에 포함된 동적 패턴(dynamic pattern)을 탐지하는 것이다. 위의 사례에서 김인포씨가 수집한 데이터들이 CoDIP에 업로드되면, 데이터에서 특정 패턴이 탐지될 때 해당 패턴의 특성과 의미를 출력할 수 있다. 따라서 김인포씨는 자신이 집을 비운 낮시간에도 낯선 사람이 집에 출입했음을 통보받을 수 있으며, 부엌의 온도가 1분 동안 5도 이상 증가했을 때 화재의 가능성을 통보받을 수 있다. 또한 화장실의 출입 회수가 지난 주에 비해 30% 이상 늘어났을 때 혈액 검사를 받아보라는 통보를 받을 수 있게 된다. 더 나아가 1주일 동안 자신이 투자한 회사의 주가가 10% 이상 오를 경우 주식을 매수할 시기임을 통보받을 수 있게 된다. (이 상황들은 모두 만들어진 예시이며, 가상의 시나리오이다.)

자, 그렇다면 이제 의문이 생긴다. “어떠한 패턴을 탐지해야 할 지, 그리고 그 패턴은 어떤 의미인지 CoDIP 은 어떻게 알아낼 수 있는 것일까?” 여기까지 꼼꼼히 읽어온 사람이라면, 왠지 어떠한 데이터던 간에 연결만 하면 알아서 척척 중요한 패턴을 탐지해서 그 의미를 알려주는 기능이 CoDIP에 포함되어 있을 것이라고 기대할 지도 모르겠다. 그렇다면 조금은 실망스러울 수도 있겠으나, CoDIP을 사용하면 할 수록, CoDIP을 점점 지능적으로 만들어갈 수 있으며, 자신이 CoDIP을 똑똑하게 만드는 과정에 직접 참여할 수도 있다는 사실을 확인하면서 실망감을 줄일 수 있을 것이다. 그리고, 사실, 매우 똑똑한 CoDIP이 개발완료되는 것이 아주 먼 미래의 일도 아니다. (사실은 Inforience 의 최종 목표는 이것이다…)

Visual Analysis in CoDIP

그림 #1. Visual Analysis (VA) 의 개념

Visual Analysis (VA) 는 CoDIP 의 여러가지 활용 모드들 중에서 가장 기본적인 모드이다. 사용자는 과거부터 현재까지 긴 시간동안 수집된, 또는 실시간으로 수집되고 있는 수치 데이터의 그래프를 직접 눈으로 확인하면서 특정 패턴이 나타난 타이밍 또는 구간을 선택하고 해당 패턴에 대한 해석과 의견을 직접 붙일 수 있다. 이렇게 붙인 내용들은 다른 사용자들과도 공유할 수 있으며, 같은 패턴에 대해 다른 사용자가 추가한 다른 관점의 해석과 의견도 수집할 수 있다. 이러한 과정을 거치게 되면 자신의 경험과 지식을 공유할 수 있을 뿐만 아니라, 이후의 분석과정에서 주목해야 할 패턴의 존재와 타이밍, 그리고 해당 패턴의 의미나 중요도를 수집할 수 있게 된다. 예를 들어, 1900년대 초반부터 현재까지의 인구변화 그래프에서 인구가 급격하게 늘어난 구간을 설정하고 인구가 늘어나게 된 원인이나 영향에 대해 적어넣을 수 있고, 다른 사용자가 그 내용을 확인할 수 있게 되는 것이다. 또는 유리 온실에 배치된 온도 센서 데이터의 그래프에서 갑자기 온도가 급격하게 하강한 구간이 난방 시스템의 고장에 의해 나타난 패턴임을 기록할 수 있다. 이렇게 기록된 결과는 해당 구간의 데이터 패턴을 “난방 시스템의 고장”이라는 그룹으로 분류하여 탐지하도록 하는 모델을 만드는 과정에서 활용될 수 있다. (뒤에서 설명할 Query Analysis 모드 또는 Machine Learning 모드에서 활용)

Query Analysis in CoDIP

VA 과정을 통해 찾아낸 데이터 패턴이 다른 구간에서도 나타나는지 탐색하고자 하거나, 존재할 것으로 생각되는 흥미로운 패턴이 데이터 내에 실제로 존재하는지, 존재한다면 어느 타이밍에 나타났으며 그 통계적인 특성은 어떠한지를 직접 분석하고자 할 때에는 Query Analysis (QA) 모드를 활용할 수 있다. 사용자는 자신이 찾고자 하는 패턴을 설정하고 입력한 뒤 탐색 기능을 동작시키게 되는데, 이를 위해 CoDIP은 다양한 패턴 설정 방법을 제공한다. 패턴 설정 과정은 자신이 찾고자 하는 패턴을 query 로 입력하는 과정이다.

그림 #2. 데이터의 y 값의 범위 지정

그림 #2는 특정 범위의 값을 나타내는 데이터의 위치를 query 로 입력하여 탐색하는 과정을 나타낸다. 사용자가 데이터 값을 지정하거나 데이터 값의 구간을 마우스로 드래그하여 설정하면 CoDIP은 해당 값을 만족시키는 구간들을 모두 탐색하여 결과를 보여준다. 더 나아가, 그러한 구간이 나타난 전체 회수와 주기성 등과 같은 부가정보를 제공하기도 한다. 사용자는 이렇게 출력된 결과에 해석과 의견을 붙여서 다른 사용자와 공유할 수 있다. 또한 이러한 결과를 실시간 query 로 등록하게 되면, CoDIP은 새롭게 입력되는 데이터에서 이와 동일한 패턴이 나타나는지 지속적으로 모니터링하게 되며, 해당 패턴이 탐지될 경우 패턴에 대한 정보와 해석을 출력한다. 패턴에 대한 정보와 해석은 사용자들이 입력한 해석과 의견을 바탕으로 만들어진다. 이렇게 출력된 결과들은 외부 서비스에 제공될 수 있다.

그림 #3. 패턴을 그려서 지정

그림 #3은 자신이 찾고자 하는 패턴을 직접 그려서 query 로 입력하여 탐색하는 과정을 나타낸다. 사용자는 상승 또는 하강하거나 특정 값이 유지되는 패턴 등을 직접 그려서 입력할 수 있는데, query 로 입력할 패턴의 길이, 각도, 높이 등을 자유자재로 설정하여 입력할 수 있다. CoDIP은 이렇게 입력된 패턴과 유사한 패턴이 나타나는 구간을 모두 찾아낸다. 패턴 탐색 결과에 해석과 의견을 붙여 공유하거나 실시간 query 로 등록하여 활용할 수 있는 것은 앞에서 설명한 y값의 범위를 지정하는 query 의 경우와 동일하다.

그림 #4. 실제로 나타났던 패턴의 구간을 선택해서 지정

데이터를 관찰하다 보면, 흥미로운 패턴이 나타난 구간을 확인하게 되는 경우가 있는데, 눈으로 확인하고 해석과 의견을 붙이는 VA 과정에서 더 나아가, 그 패턴을 query 로 설정하여 입력할 수도 있다. 그림 #4 에서 나타낸 바와 같이, 사용자가 특정 구간을 마우스로 드래그하여 실제로 나타났던 데이터 패턴의 구간을 query 로 지정하면 전체 데이터 내에서 그와 비슷한 패턴이 나타난 구간을 모두 찾을 수 있다. 해석을 붙이고 공유하거나, 실시간 query 로 등록하여 활용하는 과정은 다른 query들과 모두 동일하다.

그림 #5. 복합 query 지정

CoDIP은 여러 개의 패턴을 동시에 query로 입력하여 탐색할 수 있게 하는 기능을 제공한다. (복합 query) 이러한 복합 query 의 개념을 활용하면, 그림 #5 에서 볼 수 있는 바와 같이, 사용자는 하나의 데이터에 여러 개의 패턴을 입력하여 패턴들의 특징을 모두 만족시키는 구간을 탐색하거나, 서로 다른 데이터에 각각 개별 패턴을 query 로 입력하여 query 들이 동시에 만족하는 구간을 탐색할 수 있다. 복합 query 역시 탐색 결과에 해석을 붙이고 공유하거나, 실시간 query 로 등록하여 활용할 수 있다.

그림 #6. 패턴 간 관련성 분석

여러 개의 패턴을 query 로 입력하는 경우에는, 각 패턴이 나타나는 타이밍 사이에 규칙적인 관련성이 존재하는 지의 여부를 확인할 필요가 있다. 예를 들자면, 데이터 A에서 급격한 상승 패턴이 나타난 후 1일 이내에 데이터 B에서 하강 패턴이 나타나는 경우가 규칙적으로 반복해서 나타날 수 있는 것이다. (이런 경우, 데이터 A와 데이터 B의 사이에는 특별한 관계가 있을 가능성이 높다.) 이러한 패턴을 찾아내는 것은 어쩌면 개별 패턴을 탐색하는 것보다 더 중요한 의미를 지닐 수도 있으므로, CoDIP 에서는 각 개별 패턴의 탐지 결과들 사이의 관련성을 찾는 기능을 제공한다. 사용자가 각 개별 패턴의 탐색 결과를 생성한 뒤, 패턴 간 관련성을 찾는 기능을 실행하면 두 패턴 간의 관련성을 찾을 수 있게 된다.

Machine Learning in CoDIP

그림 #7. Machine Learning 의 적용과 활용

지금까지 모두 읽어온 독자라면, VA와 QA 과정은 눈으로 확인하고 구분할 수 있는 패턴들을 대상으로 한다는 점을 파악했을 것이다. 그러나, 초당 샘플링 수가 매우 높거나, 고차원의 데이터이거나, 변화의 패턴을 눈으로 확인하기 어려운 데이터를 대상으로 할 경우에는 VA나 QA만으로는 충분하지 않을 수 있다. 이러한 데이터를 다루는 작업은 상당한 수준의 기술적인 역량을 필요로 하는데, 그림 #7에서 확인할 수 있는 것과 같이, CoDIP에서는 특정 데이터 구간들을 모아서 특성을 추출하여 Machine Learning 모델을 학습시키고 활용할 수 있는 인터페이스를 제공한다. (Hidden Markov Model 및 Recurrent Neural Network 계열의 모델을 활용) CoDIP의 Machine Learning 모드와 관련된 자세한 내용은 추후에 이어질 포스팅에서 계속 소개할 예정이다.

VA-QA-ML

그림 #8. VA-QA-ML 사이의 관계

그림 #8은 CoDIP 의 다양한 활용 모드 사이의 관계 및 각 모드를 활용할 사용자 그룹을 나타낸다. CoDIP 은 경험적이고 주관적인 데이터 활용에서부터 기술적이고 전문적인 데이터 핸들링까지 모두 지원하며, 다양한 기술수준과 배경지식을 가진 사람들 사이에서 협업을 할 수 있도록 한다. 또한 모든 작업의 결과가 축적되어 적절히 활용될 수 있도록 한다. 다음에 소개할 CoDIP 의 특성들은 (1)편에서 언급했던 내용인데, 본 포스팅을 여기까지 읽은 후에 다시 접하게 되면 각 의미가 새롭게 다가올 것이다.

• 일부 전문가에 의해서만 수행되어 온 데이터 마이닝 작업을 일반 사용자들도 일정 수준까지 직접 수행할 수 있도록 하여 자신들의 데이터에 어떠한 패턴이 포함되어 있을지 미리 스스로 탐색해볼 수 있게 한다.
• 전문적인 데이터 마이닝 알고리즘 뿐만 아니라 사용자가 자신의 데이터에 대해 알고 있는 경험적 지식을 분석 과정에 반영할 수 있게 한다.
  • 경험적 지식의 예
    • 주변 온도가 28도 이상이고, 소음이 레벨 4 이상인 상태가 30분 이상 지속되면 기계의 동작을 멈추고 상태를 점검해야 한다.
    • 환율이 상승하고, 재고가 40% 이상이고, 지난 한 달간 비용이 30% 상승하면 관심 상태로 상황을 주시해야 한다.
    • 가속도 센서의 변동 값이 없는 상태에서 심장 박동이 30% 이상 급상승하는 경우가 1주일에 3번 이상 발견될 경우 의사의 진찰을 받아야 한다.
• 데이터 분석 인프라나 서비스를 본격적으로 도입하기 전에 데이터에 대한 초기 단계의 분석을 사전에 수행하여 데이터 분석의 효과 및 데이터 분석에 필요한 예산 규모나 투자 규모를 미리 평가해볼 수 있다.
• 자신의 개인 데이터 분석을 직접 수행해 보고 그 결과를 활용할 수 있으며, 이 과정에서 데이터 분석에 대한 지식과 경험을 쌓을 수 있다.
• 정적인 데이터 분석 뿐만 아니라 시계열과 같은 동적 데이터 패턴에 대한 분석이 가능하다.
• 동일한 데이터에 대해 여러 사용자가 함께 분석 및 해석 과정에 참여할 수 있으므로, 협업을 통해 객관적이고 신뢰성 있는 결과를 도출할 수 있다. 
• 데이터 분석 기술을 보유한 Mining expert 들과, 분석 기술은 보유하고 있지 않으나 데이터에 대한 경험적 지식을 가진 Domain expert 들의 효율적인 협업이 필요한 데이터 마이닝 과정에서, CoDIP 은 Mining expert 의 역할을 수행한다. 이를 통해, Mining expert 들이 없는 상황에서도 Domain expert 들이 최대한으로 자신만의 분석 및 해석 결과를 얻을 수 있도록 한다.

Applying CoDIP

그림 #9. 데이터에서 추출되는 지식들

그림 #9는 완성된 CoDIP이 동작하는 모습을 개념적으로 표현한 것인데, 다양한 수치 시계열 데이터가 지속적으로 입력되는 가운데, 기술적인 요소 뿐만 아니라 경험적이고 직관적인 배경지식들이 한데 어우러져서 데이터로부터 유용한 지식들이 출력되는 과정이 CoDIP 에 의해 실현될 수 있는 것이다.

CoDIP is still developing

CoDIP은 다양한 방향으로 여전히 진화하고 있다.

• 첫째, 데이터의 특정 구간에 해석을 입력하거나 query 를 입력하는 과정을 좀 더 쉽고 효율적으로 수행할 수 있게 하기 위하여 사용자 인터페이스를 계속 발전시키고 있다.
• 둘째, CoDIP 개발팀은 다양한 데이터 및 활용 케이스를 획득하고 전체적인 성능을 높이기 위한 노력을 기울이고 있다.
• 셋째, 탐지와 해석 뿐만 아니라 적절한 수준의 예측 기능을 탑재하기 위한 연구를 진행하고 있다.
• 마지막으로, 사용자의 개입이 없어도 중요한 패턴을 스스로 탐지하는 모델을 개발하기 위한 노력을 기울이고 있다. 각 방향으로의 진화의 과정과 결과는 추후의 포스팅에서 계속 소개할 예정이다.

다음의 그림들은 CoDIP 이 개발하고 있는 자동패턴 탐지 기능들의 개념을 나타낸 것인데, 사용자의 개입이 없어도 흥미로운 패턴을 스스로 찾아주는 기능이다.

그림 #10. 특이한 패턴 탐지

그림 #11. 특정 패턴의 발생 회수 및 주기성 탐지

그림 #12. 패턴의 시간적 배열 특성 탐지

그림 #13. 패턴 간 상관관계 및 인과관계 탐지 (예: 패턴 1이 발생한 후 1시간 이내에 패턴 2가 발생할 확률이 85%)

그림 #14. 데이터 간 관련성 변화 탐지 (앞에서는 두 데이터가 서로 음의 상관관계를 나타냈었는데 갑자기 바뀌는…?)

클릭 >> Hello, world !! (from ShadowEgo)

동적 데이터 패턴의 예와 중요성

바야흐로 데이터 활용의 시대다. 활용할 수 있게 된 데이터의 종류와 양이 폭증했을 뿐 아니라, 데이터를 생산하는 주체도 다양해졌으며, 이에 따라 데이터를 저장하고 분석하는 기술도 발전하고 있다. 또한 소수의 전문가들에 의해서만 데이터가 분석되었던 시대를 지나, 이제는 누구나 직접 데이터를 수집, 분석, 활용할 수 있는 시대로 나아가고 있다. 활용 대상이 될 수 있는 데이터의 종류와 양은, 한 명의 사용자가 착용한 웨어러블 장치가 수집하는 소량의 센서 데이터에서부터, 수백만명의 사용자들이 활동하는 온라인 사이트에 쌓인 엄청난 양의 컨텐츠와 로그 데이터에 이르기까지, 우리가 상상할 수 있는 것 이상이다.

데이터는 지속적으로 수집된다. 따라서, 시간에 따라 어떻게 변화했는가를 파악하는 것이 매우 중요하다. 환율이나 주식 관련 데이터들은 날마다 계속적으로 쌓이고 있으며, 개인의 카드 사용 내역도 계속해서 차곡차곡 기록된다. 일반적으로 우리는 일정한 기간 동안 쌓인 데이터에 나타난 통계적인 수치를 파악하는 것에 관심이 많지만, 그에 못지 않게 그 데이터가 시간에 따라 어떠한 변화 패턴을 보였는지, 그 변화 패턴은 무엇에 의해 비롯되었는지 등을 알고 싶어한다. 특히 모바일 헬스케어, 사물 인터넷, 핀테크 등과 같은 새로운 기술 트렌드의 등장에 의해 수집될 수 있게 된 환경, 행동, 생체, 소셜 미디어, 금융 거래 데이터 등과 같이 지속적으로 생산, 유입되는 데이터들에 포함된 동적인 특성 – 예) 시간에 따른 데이터의 추세변화 또는 여러 데이터간 상관 관계의 변화 등 – 을 신속하게 발굴하고 활용해야 할 필요성이 커지고 있다.

그림 #1. 데이터는 살아 움직인다.

위의 그림은 우리가 쉽게 접할 수 있는 데이터들의 그래프이다. 우리는 주식시장의 주요 수치 데이터가 어떻게 변화하는지, 우리가 살고 있는 곳의 날씨는 과거에 비해 얼마나 빨리 더워지고 있는지, 나의 몸에 부착한 웨어러블 센서의 데이터는 어떠한 패턴을 그리는지, 뉴스 포털에 올라오는 기사의 이슈들은 시간에 따라 어떻게 바뀌는지 등을 궁금해 한다. 더 나아가, 데이터로부터 뚜렷한 변화 패턴을 관찰하게 되면, 그러한 패턴을 발생시킨 원인을 찾고 싶어한다.

하나의 데이터에는 다양한 형태의 변화 패턴이 포함될 수 있다. 수치가 갑자기 상승하거나 하강할 수 있으며, 일정 기간동안 변화없이 특정 값을 유지할 수도 있다. 눈에 띄는 패턴이 주기적으로 발생할 수도 있으며, 여러 개의 패턴들이 복합적으로 나열되는 형태를 보일 수도 있다. 서로 다른 두 데이터가 높은 상관관계(Correlation)를 나타낼 수 있으며, 두 데이터 사이에 높은 인과관계(Causality)가 존재할 수도 있다. 따라서, 데이터에 포함된 다양한 동적 패턴들을 탐색, 발굴하고, 해당 패턴들의 원인을 고민하거나 패턴의 의미를 추출하여 적절히 활용하는 것은, 데이터 분석에 있어 가장 기본적이면서도 중요한 작업이다.  

데이터 패턴의 탐색, 해석과 협업의 필요성

그림 #2. 공간에 배치한 센서의 위치가 바뀌기만 해도 데이터 패턴은 완전히 달라지게 되어, 새롭게 다시 관찰, 분석해야 한다.

데이터는 데이터를 생성해내는 주체의 특성과 상태를 표현한다. 데이터에 포함된 패턴은 때로는 매우 무질서해 보일 수 있으며, 그 존재 여부를 미리 예측하기가 어렵다. 데이터의 특성과 상태는 해당 주체의 내재적 특성에 의해 변화할 뿐만 아니라, 외부 요소의 영향에 의해서도 변화할 수 있다. 또한 변화를 일으키는 원인이 무엇인가에 따라 다양한 패턴을 보일 수 있다. 따라서, 데이터를 생산하는 주체에 대한 지식과 경험을 바탕으로 데이터에 포함되어 있을 법한 패턴에 대한 가설을 세우고, 해당 패턴의 존재 여부를 검증해야 한다.

데이터에 포함된 패턴을 탐색하는 방법에는 여러가지가 있을 수 있다. 가장 대표적인 방법은, 데이터마이닝 또는 머신러닝 등과 같은 분야에서 개발되어 온 알고리즘들을 적용하는 것이다. 이와 같은 방법을 적용할 때에는, 알고리즘을 적용하는데 필요한 다양한 파라메터들을 사용자가 직접 결정해야 할 수도 있으며, 이렇게 결정된 파라메터들의 내용에 따라 알고리즘의 동작 방식이나 탐색 가능한 결과들이 달라지게 된다. 또 다른 방법은, 데이터에 포함되어 있을 법한 패턴에 대한 표현(metric, indicator, 또는 query  등)을 사용자가 직접 만들어 낸 후, 해당 패턴이 실제로 데이터에 포함되어 있는지 검증하는 방법이다. 전자의 방법은 데이터마이닝 또는 기계학습 알고리즘과 파라메터에 대한 지식을 필요로 한다는 특성이 있는데 반해, 후자의 방법은 일반적인 사용자들도 자신의 경험과 지식을 기반으로 탐색 작업에 직접 참여할 수 있다는 장점이 있다. 

데이터 패턴 탐색에 활용할 좋은 표현(metric, indicator, 또는 query  등)을 디자인하는 것은 매우 중요한 일이다. 또한 그러한 표현들을 누구나 쉽게 디자인하고 활용할 수 있게 하는 것도 그렇다. 세이버매트릭스(http://sabr.org/sabermetrics)는 야구 데이터에서 주요한 정보를 추출하기 위하여 다양한 지표를 디자인하고 활용하는 분야인데, 널리 활용되고 있는 중요한 지표들 중에는 전문가가 아닌, 그저 야구를 좋아하는 팬들에 의해 만들어진 것들도 많다. 결과적으로, 좋은 표현을 누구나 쉽게 만들 수 있게 되면, 다양하고 풍부한 지표가 만들어지고 활용될 수 있게 되어, 데이터의 가치가 크게 올라갈 수 있다.

데이터마이닝, 기계학습 또는 사용자에 의해 만들어진 표현 등에 의해 탐색된 패턴은 데이터를 활용하는 과정에서 매우 중요한 역할을 한다. 그러나 패턴 자체만으로는 활용성이 높지 않으며, 데이터가 나타낸 패턴에 대한 해석이 중요하다. 아무리 통계적으로 유의미한 (statistically significant) 패턴이라고 하더라도, 그 패턴이 무엇을 의미하는가를 이해하지 못하면 데이터 분석의 의미가 없어지게 된다. 

데이터가 나타낸 패턴을 해석하고 의미를 부여하는 작업은 (적어도 현재까지는) 자동적으로 이루어질 수 없으므로, 데이터 분석자의 경험과 지식을 직접 반영할 수 있도록 해야 한다. 따라서, 이와 같은 작업을 적절히 수행할 수 있도록 하는 사용자 인터페이스를 제공하는 것도 역시 중요하다. 더 나아가, 분석자의 경험과 지식은 주관적이고 편향적일 수 있으므로, 다양한 시각으로부터 해석을 수집하여 활용할 수 있도록 협업 환경을 제공할 필요도 있다.

CoDIP

그림 #3. CoDIP 을 어떤 일에 써야 좋을까?

인포리언스는 다음과 같은 특성들을 모두 만족시키는 데이터 마이닝 플랫폼 (CoDIP) 을 개발하였고, 지속적으로 각 세부 기능을 발전시키고 있다.

• 수치 시계열 데이터에 포함된 동적 패턴을 쉽게 탐색할 수 있는 데이터 마이닝 플랫폼
• 전문적 알고리즘을 활용할 수 있을 뿐만 아니라, 데이터 내용에 대한 사용자의 경험적 지식을 query 에 반영하여 분석 작업에 활용할 수 있게 하는 데이터 마이닝 플랫폼
• 탐색된 패턴에 대한 해석을 저장, 활용할 수 있는 플랫폼
• 패턴의 탐색과 해석 작업을 여러 사용자와 함께 수행할 수 있는 협업형 플랫폼
• 저장된 패턴에 대한 실시간 탐지 기능을 활용할 수 있는 플랫폼

CoDIP 의 활용 과정은 다음과 같이 요약할 수 있다.

1. 데이터 연결 : API 를 통해 CoDIP 에 데이터를 업로드한다.
2. 데이터 확인 및 핸들링: CoDIP 이 제공하는 인터페이스를 통해 자신의 데이터를 확인하고 play 해본다.
3. 원하는 패턴의 탐색: 자신이 원하는 패턴을 query 형태로 입력하여 해당 패턴의 존재와 통계적 특성을 알아낸다.
4. 패턴의 해석과 기록: 발견된 패턴에 대한 주관적인 해석을 기록, 저장한다.
5. 전문적인 분석 알고리즘의 활용: 머신러닝 및 데이터 마이닝 알고리즘을 데이터에 적용해 본다.
6. 분석 결과의 공유: 자신의 분석 결과를 타 사용자 또는 전문가와 공유하거나, 다른 사용자의 분석 과정에 참여한다.
7. 최종 결과의 활용: 분석 결과로 생성된 패턴 템플릿이나 머신러닝 모델을 실제적인 서비스에 적용한다.

CoDIP은 다음과 같은 독창적인 특성을 가지게 된다. (전 세계적으로, 다음과 같은 특성을 모두 만족시키는 소프트웨어나 서비스는 아직 출시된 바 없다)

• 일부 전문가에 의해서만 수행되어 온 데이터 마이닝 작업을 일반 사용자들도 일정 수준까지 직접 수행할 수 있도록 하여 자신들의 데이터에 어떠한 패턴이 포함되어 있을지 미리 스스로 탐색해볼 수 있게 한다.
• 전문적인 데이터 마이닝 알고리즘 뿐만 아니라 사용자가 자신의 데이터에 대해 알고 있는 경험적 지식을 분석 과정에 반영할 수 있게 한다.
  • 경험적 지식의 예
    • 주변 온도가 28도 이상이고, 소음이 레벨 4 이상인 상태가 30분 이상 지속되면 기계의 동작을 멈추고 상태를 점검해야 한다.
    • 환율이 상승하고, 재고가 40% 이상이고, 지난 한 달간 비용이 30% 상승하면 관심 상태로 상황을 주시해야 한다.
    • 가속도 센서의 변동 값이 없는 상태에서 심장 박동이 30% 이상 급상승하는 경우가 1주일에 3번 이상 발견될 경우 의사의 진찰을 받아야 한다.
• 데이터 분석 인프라나 서비스를 본격적으로 도입하기 전에 데이터에 대한 초기 단계의 분석을 사전에 수행하여 데이터 분석의 효과 및 데이터 분석에 필요한 예산 규모나 투자 규모를 미리 평가해볼 수 있다.
• 자신의 개인 데이터 분석을 직접 수행해 보고 그 결과를 활용할 수 있으며, 이 과정에서 데이터 분석에 대한 지식과 경험을 쌓을 수 있다.
• 정적인 데이터 분석 뿐만 아니라 시계열과 같은 동적 데이터 패턴에 대한 분석이 가능하다.
• 동일한 데이터에 대해 여러 사용자가 함께 분석 및 해석 과정에 참여할 수 있으므로, 협업을 통해 객관적이고 신뢰성 있는 결과를 도출할 수 있다. 
• 데이터 분석 기술을 보유한 Mining expert 들과, 분석 기술은 보유하고 있지 않으나 데이터에 대한 경험적 지식을 가진 Domain expert 들의 효율적인 협업이 필요한 데이터 마이닝 과정에서, CoDIP 은 Mining expert 의 역할을 수행한다. 이를 통해, Mining expert 들이 없는 상황에서도 Domain expert 들이 최대한으로 자신만의 분석 및 해석 결과를 얻을 수 있도록 한다.

그림 #4. CoDIP 의 다양한 활용 모드

CoDIP 은 다양한 사람들이 자신의 지식 수준과 활용 목적에 맞게 선택적으로 활용할 수 있도록 다양한 활용 모드 – Visual Analysis, Query Analysis, Machine Learning, 자동 패턴 탐지 – 를 제공한다. Visual Analysis 는 누구나 직접 데이터를 확인하면서 유의미한 특성이 나타나는 곳에 해당 특성에 대한 자신의 생각과 의견을 적어넣고 다른 사용자들과 공유할 수 있게 하는 모드이다. Query Analysis 는 사용자가 직접 자신이 탐색하고자 하는 데이터 패턴을 query 형태로 만들어 입력하여 해당 패턴을 탐색하고 해석과 의견을 입력하는 모드이며, Machine Learning 모드는 데이터의 특성을 학습한 Machine Learning 모델을 학습시키고 활용하는 모드이다. 이와 더불어, 자동 패턴 탐지 모드는 새롭게 입력되는 데이터에서 유의미해 보이는 패턴의 후보들을 자동적으로 찾아내어 분석자 또는 응용 서비스에게 제공하는 작업을 수행한다.

각 모드의 개념과 자세한 활용 과정은 (2)편에서부터 소개하도록 한다.

Abstract

The first goal of this paper is to design good implicit indicators applicable to client side Web usage mining, especially to find high interest content pages removing navigational pages and uninteresting content pages from a user’s Web visit history. To achieve the goal, a field study to explore real data is conducted. Based on visit patterns as well as various interaction patterns, several reliable implicit indicators are designed. The second goal is to develop a new framework for client side Web usage mining based on the indicators and to show that the framework provides good performance. The framework is designed to find high interest content pages using a normalization process, a transformation process, and a classification process. The performance of the framework is evaluated to show that the framework works well in terms of filtering out unnecessary pages from the visit history to find the user’s topics of interest accurately.

1. Introduction
The World Wide Web (the Web) today plays a key role as an information source and a communication tool, replacing traditional media, magazines, books, and even telephones. Search engines help users find information easily and news sites allow users to keep track of various current issues transpiring all over the world. Users communicate with each other using e-mail, social network services, community sites, and so on. Some commercial websites also provide total information services where users can choose various types of Web services.

While using the Web, users choose preferred websites to visit. In the websites, they also choose Web pages. Users may click on hyperlinks that are provided by portal sites. They also can choose Web pages to view among lists that are retrieved by search engines responding to input queries. The provided and retrieved hyperlink lists are usually classified by topics or sorted by relevance to the input queries. Users choose Web pages considering the keywords on the hyperlinks or snippets that may represent topics of the pages. By virtue of the fact that users choose or search Web pages independently, some valuable patterns that reflect their preferences of interests will be included implicitly in log data that are collectable at Web servers or Web browsers.

Many researchers, especially in the field of Web usage mining (WUM), have focused on analysis of Web usage data to detect noticeable patterns [4, 8, 21, 22, 24, 26, 30].WUM is essential to find users’ favorite content and to construct interest models. To find favorite contents, WUM analyzes data such as Web visit patterns, interaction patterns with Web pages, queries that are input to search engines, and so on. WUM consists of several tasks such as data collection and preprocessing, pattern analysis, content analysis, and user model construction. Among the tasks, the tasks of data collection and preprocessing are important because the accuracy of a constructed interest model is dependent on the results of these tasks.

Users have various interests and so they visit multiple websites. In order to comprehensively identify the various interests of a user, we should therefore analyze the log data that are collectable at the client side rather than at the server side, because it is impossible to find the total interests from content provided by a specific website. However, most WUM studies have focused on the analysis of server side data, and numerous systematic and effective methods have been suggested [2, 5, 6, 20, 21, 23, 26, 29; 33, 34]. On the other hand, client side analyses have not received full attention thus far. We believe that the lack of attention is due to the several inherent difficulties of a client side analysis. One of the difficulties is that we cannot apply prior knowledge about the content or structure of the websites at the client side [22]. The collectable data are limited relatively to a server side analysis and it is not easy to formulate a general method to apply to multiple users’ data as there may be individual differences in the data patterns.

There are several requirements to be considered we attempting to develop a method of client side WUM. First, all possible implicit indicators that may be useful to find a user’s interests should be carefully identified. The values of indicators will be obtained from several data such as viewing time, number of visits, mouse movement, mouse clicks, keyboard typing, scrolling, and so on [7]. Second, the identification process should be performed based on real data that are collected in the user’s natural environments over a long period of time to ensure reliability of the indicators. The last requirement is that a framework of client side WUM should be constructed based on the indicators, and the framework should be as generally applicable for every user as possible.

In the user’s visit history, there are some pages that are not useful to find the user’s interests. Contrary to content pages, navigational pages – the front pages of portal sites, home pages of news sites, and any hub-styled pages – are designed only to help users find their target pages rather than providing content directly. The navigational pages are useful in that they provide opportunities to find interesting pages; however, the navigational pages themselves are not useful to find the user’s interests because users may not click all of the hyperlinks on them. This means that the accuracy of the constructed interest model will be degraded unless we apply a process of removing these pages from the visit history. To date, there have been some attempts to identify and remove navigational pages. In [8, 9], the types of Web pages are classified based on their physical characteristics. The same classification has been accomplished using the number of links in a Web page [11]. However, the previous attempts are not applicable in the current Web environment because various new types of services are being continuously provided and hence we cannot expect consistency in the physical characteristics of the pages contained in such various types of services. In addition to navigational pages, content pages that are not of interest – uninteresting content pages – should be removed. Users will access the content pages by choosing some of the hyperlinks on well-designed navigational pages; nevertheless, it is not unusual for users to have no interest in some of the pages. This means that the accuracy of the constructed interest model will also be deteriorated in the absence of a process to remove uninteresting content pages.

In this paper, we introduce the research process we have taken to develop a new and reliable framework for retrieval of a user’s high interest content pages removing navigational pages and uninteresting content pages from the visit history based only on the log data collectable at the client side. We collect a user’s real interaction logs as well as visit patterns in a natural environment over a long period of time. We carefully analyze the collected data to define new and simple indicators and show that we are able to remove navigational pages and uninteresting content pages from the visit history using these indicators. We develop a new processing framework and evaluate the performance of the framework.

2. Literature Review

2.1 Web Usage Mining

The importance of WUM has been emphasized continuously since the Web was popularized to be used in everyday life. Accordingly, numerous research papers have introduced a general idea of WUM [4, 8, 21, 22, 24, 26, 30]. Among these papers, Cooley et al. [8] defined WUM as the process of applying data mining techniques to the discovery of usage patterns from Web data and suggested that WUM is important for applications such as personalization, system improvement, website modification, business intelligence, and usage characterization. This paper classified WUM tasks into 3 categories – data collection and preprocessing, pattern discovery, and pattern analysis – and introduced required techniques of the tasks. The data collection and preprocessing methods are different according to where the usage data can be collected. The usage data can be collected at the server side, client side, and proxy side but the papers focused mostly on WUM processing on the server side. Server side WUM utilizes various data such as content data, structural information, Web page meta-information (file size, last modified time), and so on as well as usage data.

Mobasher et al. [22] has provided useful surveys of WUM. Similarly to Cooley’s papers, his papers not only explained the concepts of WUM but also additionally emphasized user profile construction and recommendation based on the results of WUM. He claimed that WUM can reduce the need for obtaining subjective user ratings or registration-based personal preferences. Structural characteristics of the site or prior domain knowledge should be used importantly in the recommendation processes. For example, certain page types (content vs. navigational), product categories, and link distances can be used. He also focused on how to process usage data, content data, structure data, and user data that can be collected at the server side. The client side data have been regarded as supplementary resources.

Pierrakos et al. [24] discussed WUM for personalization. WUM provides approaches to preprocess usage data and the results of the preprocessing can be used to construct models representing a user’s behaviors and interests without the intervention of a human expert. In particular, this paper emphasizes that a flexible data elaboration process is required to construct personalization systems, because it is important to separate noise from relevant data, correlate and evaluate the data, and finally format the data so as to be ready for personalization.

Román et al. [26] introduced the latest methods and algorithms for pattern extraction from Web user browsing behaviors, but the basic purpose of the paper is same with the above papers. WUM has been applied to many research problems. Nasraoui et al. [23] suggested a method to construct dynamic user profiles. The proposed method effectively tracks users’ characteristics that evolve over time. In addition, WUM is being applied to find users’ evaluations of the performance of search engines, to extract rules from Web usage logs, to track long-term temporal property in Web usage evolution, and so on [2, 20, 29, 33, 34].

2.2 Client Side Web Usage Mining

Some researchers have paid attention to client side WUM. For the purpose of personalization, most studies have attempted to develop intelligent methods with which user preferences or interests can be inferred. The methods mostly have relied on repetitive visit patterns and dwell time on Web pages, as it is not easy for client side WUM to use structural characteristics of Web sites or prior domain knowledge, unlike server side WUM.

Seo & Zhang [28] and Zhang & Seo [35] regarded several data such as bookmarking, time for reading, following up the HTML document, and scrolling as good implicit interest indicators. They collected visit histories from 10 users and tried to estimate explicit user interest feedback with a multi-layer neural network. They also developed an agent that constructs user profiles intelligently based on reinforcement learning techniques.

Claypool et al. [7] have developed a custom Web browser to observe users in a less well controlled experimental setting. They analyzed the statistical relationships between explicit interest rating and several implicit interest indicators – the time on a page, the time spent moving the mouse, the number of mouse clicks, and the time spent scrolling. They found that the time on a page, the time spent moving the mouse, and the time spent scrolling are good indicators of interest among the considered implicit interest indicators.

Douglas & Jinmook [10] emphasized that information filtering based on implicit feedback is essential to build a recommendation system. They also provided a framework in which various observable behaviors such as view, print, copy-and-paste, bookmark, and save are classified into several categories according to the purpose of the behaviors. As an extension of this work, Kelly & Teevan [17] also provided a brief overview of implicit feedback techniques that are applicable for information retrieval.

Badi et al. [1] observed 16 users and analyzed how well reading activities and organizing activities reflect document usefulness. They developed a statistical model that predicts user interests on documents. In particular, they considered various reading activities – time spent on a document, number of mouse clicks, number of text selections, number of scrolls, number of scrolling direction changes, time spent scrolling, scroll offset, total number of scroll groups, and number of document accesses – and concluded that reading activities as well as organizing activity are useful to assess document usefulness.

Among various candidate implicit interest indicators, time spent on a Web page has received considerable attention. The basic idea is that users have a tendency to remain on high interest pages for longer time than other pages. Sugiyama, Hatano, & Yoshikawa [32] selects important pages from a browsing history that was recorded by search engine users according to time spent reading to build user profiles. Halabi, Kubat, & Tapia [12] and Hofgesang [13] also claimed that time spent on a web page is the most important indicator to infer user interests.

On the other hand, some researchers have taken a cautious stance regarding the usefulness of time spent on a Web page as an implicit interest indicator. Kelly & Belkin [16] developed specialized logging software that operates “in stealth mode”. They observed 7 users for 14 weeks, providing subjects with an opportunity to engage in multiple information-seeking episodes with tasks that were germane to their personal interests, in familiar environments. From the results they concluded that the display time is not suitable to infer the user’s preferences, because there is a large variation between display time and interest according to users and also large differences according to tasks at hand. This means that using display times averaged over a group of users as a measure of usefulness is unlikely to be effectual. In addition, using mean display time for a single user without taking account of contextual factors is also unlikely to work well. Kellar, Watters, Duffy, & Shepherd [15] investigated the usefulness of time spent as a measure of user interest. They found that participants spent more time reading relevant documents than non-relevant documents on average but this difference was not statistically significant. Based on the results, they concluded that when users read an article to judge how relevant it is, they do not spend more time on an article that they ultimately judged as relevant.

Reviewing previous WUM research, we found some client side studies, but there are several weaknesses in their research methods or the environments in which the experiments were conducted. Some studies only used a specific indicator – e.g. time spent on a Web page – rather than considering the use of all possible indicators together despite that there may be other reliable indicators that reflect the user’s interests such as mouse movement, mouse clicks, visit frequencies, and so on. Some works observed users and collected log data in a short period while users performed a small set of specific given experimental tasks rather than collecting the data in the users’ natural and familiar environments over a long period. We cannot be assured of the applicability of systems that are constructed based on such impractical data. Most of all, none of the studies suggested a method with which navigational pages can be identified intelligently at the client side even though navigational content may decrease the accuracy of users’ interest models.

3. Research Goals and Approach

Encouraged by the assertion that client side data is more reliable to build personalized systems than server or proxy side data [24], we decided to revisit the field of client side WUM. The first goal of our research is to design implicit indicators with which not only navigational pages but also uninteresting content pages can be identified to remove. We set up a hypothesis that the value of useful implicit indicators will be different among the page types and also different according to interest levels and thus the indicators will be useful for the purpose of the identification. In order to verify the reliability of the indicators, we design the indicators based on the results of a long time field study conducted in the user’s natural browsing environment. During the study, we collect as much available data as possible in order not to miss any patterns that may be useful to design the indicators.

The second goal is to develop a framework that is useful to find high interest content pages from the visit history and also make the framework robust to variances from individual differences such that it is applicable to multiple users. We transform each visited page into a multi-dimensional vector in which each element represents an indicator value that is normalized according to each user. We then apply a classification algorithm to identify those pages. We include the normalization process, the transformation process, and the classification process in our framework. We evaluate the framework in terms of the accuracy of topics of interest that are extracted from remaining high interest content pages.

Our research consists of several phases. The first phase is a field study in which raw data are collected. The second phase is analysis of the collected raw data. In the second phase, we design our implicit indicators. The usefulness of the designed indicators is analyzed in the third phase. The fourth phase entails design of a practical framework. The performance of the framework is evaluated in the last phase.

4. Experimental Data

4.1 Web Usage Mining

We developed a Browser Monitoring Module (BMM) to store all visited Web pages and to collect users’ interaction patterns, visit histories, and their feedbacks. The BMM consists of four components – a hooker, data aggregator, data recorder, and feedback window. The hooker catches every message passed within the operating system and then filters out the messages from other unfocused windows in order to count the number of messages that are invoked for only the currently focused browser window. The data aggregator also aggregates all data from these multiple components. The data recorder stores not only all visited Web pages in the local disk but also stores the aggregated data in a human-readable XML format for future analysis. Using the feedback window, users review and give feedback about all of their visited Web pages.

The BMM was installed in the users’ PCs and collected temporal information of each visited Web page and URL information. It collected several interaction logs, for example, the viewing time, the amount of scroll movement and mouse wheeling, the amount of keyboard typing, mouse clicks, and so on while a user focuses on a Web page in a browser tab. The viewing time is the time during which the user remains on a particular Web page. The amounts of mouse wheeling, clicks, and keyboard typing are measured by hooking Windows system messages. The location of the scroll bar is periodically updated so that the total displacement of the scrollbar can be estimated. We have chosen these logs because they can be measured without much effort. We did not record some of the behaviors that have been considered by other researchers – bookmarking, saving, printing, and coping, and pasting –because users do not always show those behaviors on every valuable Web page, and hence their records do not suit our purposes. For additional analyses, we also counted the number of hyperlinks in a downloaded Web page. Among visited Web pages, there were some pages that indicate an excessively long (over 15 min.) or short (less than 2 sec.) viewing time because the experiment was conducted in the users’ personal and natural environments. Therefore, as Claypool et al. [7] did, we excluded such pages from the analysis.

Table 1. User Information

For experimental purposes, we have also collected user feedbacks – interest levels on content pages as well as page types (navigational or contents) of visited Web pages. Eighteen experienced Web users (Table 1) visited about 58,353 pages during a 2 week period from their own residences. Using a feedback window, users can review the visited Web pages and choose radio buttons that ask about several types of assessments about the contents of each Web page. The users have tagged all visit logs with page type information – navigational page or content page – and also indicated their interest levels of the content pages on a 5-point scale based on subjective decisions. (1- “no interest at all”, 2-“no interest”, 3-“neutral”, 4-“a little interest” and 5-“high interest”). The feedback results for a Web page are aggregated with the interaction logs and visit history. Users gave feedback on all of their visited Web pages at least once a day. If the users do not want to answer questions regarding some of the Web pages, they can remove the records easily. We paid the participants 80 dollars to 160 dollars according to the feedback rate. During the data collection, the users visited some websites with their own special structures such as Facebook, Twitter, Google+, and so on but we excluded such websites from our analysis for future study in the belief that user interaction patterns on such websites are quite different from those on other websites.

4.2. Data Characteristics

Figure 1. Statistics of the collected data

Figure 1 presents statistics of the collected data. It shows that only parts of visited pages are useful for extraction of a user’s topics of interest. About half of all visited Web pages were classified into navigational pages by users. This result appears natural considering that various types of portal sites, news sites, and search engines have been provided to help users find target pages efficiently. We may expect that users will show high interest levels for most of their visited pages, because most target pages that users wish to access can be reached via well-designed services; however, the number of uninteresting pages was also high, contrary to our expectation.

Figure 2. (a) The average number of outlinks and (b) the average number of visits in a day

In some previous studies, there were several attempts to discriminate content pages from navigational pages using the number of outlinks contained in the pages [7, 9, 11]. The main idea is that there will be a larger number of outlinks on navigational pages than on content pages. We also initially thought that this idea is acceptable and hence counted the average numbers of contained outlinks in both navigational pages and content pages. However, as we can see in Figure 2-(a), the average number of outlinks on a navigational page was not significantly different from that on content pages in our results.

We found some interesting visit patterns from the collected data. Because most target pages that users wish to access can be reached via portal sites, news sites, search engines, and so on, the front pages of these sites and hub pages within the sites appeared in the visited URLs history more frequently than others. We believe that the cause of this pattern lies in users’ tendency to visit navigational pages to see the list of content pages prior to selecting pages to access and they also tend to return to the navigational pages to access other pages. This pattern may be repeated while users browse the Web. On the contrary, there is relatively less need to repeatedly see the same contents in content pages. As we can see in Figure 2-(b), users visited navigational pages more frequently than content pages.

Figure 3. : The positive correlations between interaction logs and interest levels

We normalized the number of interaction logs using min-max normalization according to each subject. We included this normalization procedure because there would be variances in the amount of usage logs due to users’ individual differences of reading skill, carefulness, interaction styles, and so on. As we can see in Figure 3, all users’ normalized viewing time shows a positive correlation with the interest level and, according to t-test, the difference between the viewing times of high interest levels (level 4 and 5) and the viewing times of low interest levels (level 1, level 2, and level 3) is statistically significant. The normalized amount of other interaction logs in Web pages also increased with the interest levels in general. On the contrary, we could not find any clear patterns in non-normalized data, similarly to the previous results of Kelly and Belkin’s work [16].

5. Implicit Indicators

Visit patterns have mostly been used thus far by researchers to find user’s browsing styles [8], to reorganize websites’ structures [11], to infer user’s next pages to probably visit [19], and so on. Only a few works have considered visit patterns as an interest indicator, but they simply count the number of visits [1]. On the other hand, interaction patterns on each Web page have been mostly used as an implicit indicator. However, we believe that there is no clear evidence that any one of the various types of possible indicators can be ignored. In this regard, we decided to make use of both visit patterns and interaction patterns as possible implicit interest indicators and thereupon designed two types of indicators.

5.1. Visit Pattern Indicators

Based on visit patterns that we found in our data, we designed several indicators. The definitions of visit pattern indicators are extensions of well-known Tf-idf [27]. Document frequency of a term counts the number of documents in a collection in which a term occurs. A term with lower document frequency is regarded as more specific. On the other hand, term frequency is simply the number of times a given term appears in a document. Term frequency gives a measure of the importance of a term within the particular document. Analogous to the definition of term frequency and document frequency, importance or specificity of a visited page can be understood by visit frequencies. If a user visits a Web page frequently during a unit time, the page may be important to the user. Moreover, if the user shows a repeated and also periodical visit pattern to a Web page, we may also expect that the user visits the page for a navigational purpose.

In order to apply the concept of visit frequencies, we should determine the length of unit time to calculate the frequencies. We chose two unit times – day and session – because we believe that Web browsing is a daily activity that consists of multiple separate sessions. A session is generally defined as a sequence of visits by a single user during a single visit to a server [21]. For example, total session duration may not exceed a threshold (30 min.) and total time spent on a page may not exceed a threshold (10 min.). However, for the present work, we need a different definition that is suitable to a client side analysis. In this study, we assign two successive visits in a same session if the difference in visit time between the visits is not greater than 20 minutes. Based on the time units, day and session, we designed 4 visit pattern indicators.

Day Frequency (DF)
Day frequency (DF) is obtained by dividing the number of days containing a URL in the visit history by the number of all days under consideration. The DF value of each visited URL can be calculated using the following equation:

In this equation, |D| is the total number of days under consideration, d_j is the URL collection of the j-th day, and |{d_j:〖Url〗_i∈d_j}| denotes the number of days where the i-th URL appears. If a URL exhibits a high DF value in a user’s visit logs, it means that the user visits the website almost every day.

Visit number in a day (VnD)
Visit number in a day (VnD) is obtained by dividing the number of visits to a URL in a day by the total number of visits in a day.

where n_ij is the number of occurrences of the considered i-th URL in the j-th day, and the denominator is the sum of the number of occurrences of all URLs in the j-th day. Therefore, 〖VnD〗_ij is the visit ratio of the i-th URL in the j-th day.

Session frequency (SF)
Session frequency (SF) is obtained by dividing the number of sessions containing a URL by the number of all sessions under consideration. The SF value of each visited URL can be calculated using the following equation:

In this equation, |S| is the total number of sessions under consideration, s_j is the URL collection of the j-th sessions, and |{s_j:〖Url〗_i∈s_j}| denotes the number of sessions where the i-th URL appears. If a URL exhibits a high SF value in a user’s visit logs, it means that the user visits the website almost every session. In this study, the total number of sessions is counted for each day to which a session belongs.

Visit number in a session (VnS)
Visit number in a session (VnS) is obtained by dividing the number of visits to a URL in a session by the total number of visits in a session.

where m_ij is the number of occurrences of the considered i-th URL in the j-th session, and the denominator is the sum of the number of occurrences of all URLs in the j-th session. Therefore, 〖VnS〗_ij is the visit ratio of the i-th URL in the j-th session.

5.2. Interaction Pattern Indicators

Table 2. The indicators of interaction logs

In addition to these visit pattern indicators, we also designed some indicators based on the amounts of several interaction logs. Because Web users may visit a Web page repeatedly in a day and even in a session, we set the values of interaction pattern indicators to the averaged amount of each interaction log for a day or a session. The interaction pattern indicators that we used in this study are presented in Table 2.

6. Indicator Analysis

We analyzed our data to determine whether there are noticeable patterns in the indicator values according to page types and interest levels. The DF value was obtained based on the total visit logs of all days in the experiment. The SF value was obtained based on the total visit logs of all sessions in a day. The other values are means of normalized amounts of logs according to each user.

Figure 4. Variation of visit pattern indicators values (N: navigational page / C1~C5: content pages according to interest levels

Figure 4 shows that DF, SF, VnD, and VnS can be used as indicators to find high interest content pages. The leftmost values of the figures are means of the indicator values of navigational pages and the other values are the means of content pages according to interest levels. As we expected, DF and SF are much higher on navigational pages than on content pages. VnD and VnS increased according to interest levels and the values of navigational pages are similar to the highest interest content pages. Higher DF and SF of navigational pages indicate that, in general, users traverse the Web to find content pages via navigational pages, and therefore visit logs of a navigational page can be found in a greater number of days and sessions. Contrary to our expectation that there would be relatively less need to view the same content repeatedly in content pages, there were higher VnD and VnS in high interest content pages. This indicates that users tend to visit high interest content pages more frequently than others. We believe that this pattern may be shown partly due to dynamic characteristics of some websites such as blogs and community sites in which users can find new content even when they visit the same URL as before. Those URLs appear frequently in the visit history but are regarded as content pages.

Figure 5. Variation of interaction pattern indicator values

Figure 5 shows how the day means and session means of interaction pattern indicators varied according to page types and interest levels. We found that the values also increased according to interest levels among the content pages. This means that users generally interacted more intensively with high interest content pages. One interesting pattern we found in this figure is that KtD and KtS of navigational pages are significantly higher than those of content pages. This pattern may be the result of typing queries to search engines or typing user ids and passwords when users enter websites.

Figure 6. Variation of interaction pattern indicators values (without normalization)

Figure 6 shows the trends of the day means of interaction pattern indicators that we obtained without a normalization process. We could not find any clear trends from the non-normalized data. This shows that a normalization process may be required to make use of the indicators to build a common procedure that can handle all users’ data.

Observing the trends of values of the indicators, we concluded that our indicators are highly applicable not only to determine page types but also to infer interest levels. This means that we can build a framework in which navigational pages and uninteresting content pages can be removed using the indicators.

7. WUM Framework Design and Evaluation

Figure 7. The concept of the data preprocessing framework

Figure 7 shows the concepts of two data preprocessing frameworks that we designed. The first model was designed initially and changed into the second model according to our experimental results. We included the normalization process, the transformation process, and classification process in our framework. VnD, VnS, and the values of interaction pattern indicators for a visited Web page will be normalized according to each user’s scale of the day at the end of each day and each page will be transformed into a multi-dimensional vector in which each element represents an indicator value. The classifiers will judge the page types or interest level of each vector. For the classification process, we trained a classifier and tested its general performance to handle variances of indicator values that may be caused by multiple users’ individual differences and noise. All of the visit frequencies except VnS and the day means of interaction logs are measured at the end of each day. The session means of interaction logs and VnS are measured at the end of each session. We maintained the visit histories of 5 previous days to measure DF values in order to define how many days are to be considered as a unit time. Among various types of classifiers, we have chosen the Decision Tree (C4.5) algorithm, as it can select good features independently and there is a pruning process in its induction process [25].

7.1. The First Model

As an initial model (Figure 7- (a)), using all indicator values, 18 individual classifiers were trained and evaluated respectively using each user’s data. (10-fold cross validation) Content pages were grouped into 2 groups according to the interest levels. We merged interest levels 1, 2, and 3 into a low-interest group and interest levels 4 and 5 into a high-interest group. We labeled high interest content pages as 1 and other pages – navigational pages and low interest content pages – as 0 for binary classification.

Figure 8. The performances of the first models. ((a) black: initial, gray: page type classification, white: interest level inference (b) black: using only visit pattern indicators, white: using only interaction pattern indicators)

Figure 8-(a) shows the performance of the individual classifiers. The individual classifiers showed high error rates, contrary to what we expected (‘initial’ in Figure 8-(a)). We thought that the high error derives from the trend that users showed similar visit patterns and interaction patterns in some of the navigational pages and high interest content pages. For example, as seen in Figure 4, VnD and VnS may be useful to infer interest levels among content pages but they are not useful to find navigational pages because they were high not only in high interest content pages but also in navigational pages.

In this regard, we concluded that the navigational pages should be filtered out prior to inferring interest levels of content pages, because clear increasing tendencies of visit pattern indicators are observed only among content pages. We constructed and evaluated two classifiers separately. The first classifier is for the task of finding content pages from the visit history – page type classification – and the second classifier is for inferring interest level among the content pages – interest level inference. To train and evaluate the first classifier, we labeled each content page as 0 and each navigational page as 1 for binary classification. For inference of interest levels, only the logs of content pages were included in the data.

As can be seen in Figure 8-(a) (‘page type classification’ and ‘interest level inference’), the classifiers showed good performances in their respective tasks. The classifiers also showed better performances than classifiers that were trained using only visit pattern indicators and using only interaction pattern indicators in the task of page type classification. (See Figure 8-(b))

7.2. The Second Model

In order to design a more practical framework, we built a second model in which the two classifiers work in series (Figure 7- (b)). In this case, the errors of the first classifier – navigational pages that survived from the first classifier – also may be included in input data for the second classifier.

Table 3. The information gains of indicators

We built and tested two forms of the second model. The first form was trained and tested using all indicators (All indicator form). We used only the top-10 useful indicators for the second form (Useful indicator form). To select useful indicators, we measured the Information Gain (IG) [25] of each indicator. The IG of each indicator shows how much information an indicator gives for the current classification task. In Table 3, the IG of each indicator is shown. Notice that both some of the visit pattern indicators and some of interaction pattern indicators were included in the top-10 useful indicators.

Figure 9. The performances of the second models (black: individual type, gray: all indicator form of general type, white: useful indicator form of general type)

In order to check the applicability of the second model to general users (general type), we built and tested the model with a ‘leave-one-out cross validation’. We trained the model using all user data excluding one set of user data and tested the model by the excluded user data. Figure 9 shows that the overall performances of the general types were slightly lower than the performance of the individual type in which the classifiers were trained and evaluated respectively using each user’s data. However, the overall performances of the general types were still impressive. Notice that all indicator form of the general type showed slightly better performance than useful indicator form.

8. WUM Framework Design and Evaluation

Jin, Zhou, & Mobasher [14] argued that a probabilistic latent semantic analysis can be used for WUM. In addition, Pierrakos et al. [24] also mentioned that analyzing the content of Web pages based on traditional Tf-idf vectorization or a latent semantic analysis is important to model a user’s topics of interest. Among several candidate semantic analysis methods, Latent Dirichlet Allocation (LDA) [31] models topics in a set of documents based on statistical modeling of a distribution of words. As a generative model, LDA samples a multinomial distribution over a topic from a Dirichlet with the parameter α for a document. A topic is chosen from the topic distribution. A word is generated from a topic-specific multinomial distribution. A topic-specific multinomial distribution is sampled from a Dirichlet with the parameter β. Based on these procedures, the likelihood of a document can be obtained. Currently, LDA is being widely used for the purpose of modeling topics in various types of document sets [3].

We therefore chose LDA in order to verify the performance of the second model in terms of finding interesting topics. We conducted topic modeling tasks with three data sets – a raw data set that includes all visited Web pages (raw topics), processed data sets that are outputs of the second model (processed topics), and a target data set that includes only high interest (interest level over 4) content pages (target topics). We extracted plain body text from each visited Web page and refined the text using a morpheme analyzer to retain only tokens of nouns. We identified 166,585 unique tokens (including Korean and English) from all of our data sets.

After preprocessing the Web pages, we extracted 50 topics from each data set using basic LDA (α = 0.1 and β = 0.01, as commonly used in the past [18]) and measured the similarity of the extracted topics. We applied Jensen-Shannon Divergence (JS Divergence) to measure the topic similarity between individual topics [18, 31],

where KL is Kullback-Leibler Divergence and M is the average distribution of ∅_i and ∅_j

Based on JS divergence, the error of an individual raw (or processed) topic i is measured as follows:

where

The total error of the raw (or processed) topics is the number of the topics whose individual error exceeds a threshold value. We set the threshold value to 0.4 referring to [18].

Figure 10. The performance of topic modeling (black: raw topics, gray: processed topics by all indicator form, white: processed topics by useful indicator form)

As we can see in Figure 10, the mean number of errors in raw topics was over 24 out of 50. This means that the raw data were quite different from the target data in terms of topics. On the contrary, the number of errors in the processed data set decreased to 4 (all indicator form, general type of the second model) and 10.3 (useful indicator form, general type of the second model). This shows that although outputs of the general type of the second model contain some classification errors while finding high interest content pages, the model works well in terms of filtering out unnecessary pages from the visit history to find the user’s topics of interest accurately.

9. Long History based Day Frequency

Figure 11. The performances of page type classification vs. the numbers of days for DF calculation

Thus far, we have calculated the DF value based on 5 previous days. However, we anticipated that if we obtain the DF value based on longer histories, the overall performance will increase. We repeated the same experiments varying the numbers of days for the DF calculation. Figure 11 shows the variation of the average performance of page type classification according to different numbers of days for the DF calculation. We begin to use the DF indicator from the 5th day and thus the first 4 values of the figure are the performance of the experiment in which the DF indicator was not used. Notice that as we apply a n-day history, the amount of experimental data decreased, because the data in n-oldest days should be excluded. As we can see in Figure 11, when we use the DF, the performances were higher and there was an increasing trend as we used longer histories for the DF calculation. In practical situations, we can collect data for a long time and thereby maintain a longer history for the DF calculation. However, as we apply longer histories, greater storage and calculation will accordingly be required.

10. Conclusion
One of the goals of this paper is to find good indicators applicable to client side WUM, especially indicators that can be used to remove navigational pages and uninteresting content pages from a user’s visit history. From the results of our experiment, we showed that visit pattern indicators as well as interaction pattern indicators can be used for our purpose. Another goal is to develop a new framework for client side WUM based on the indicators and to show that the framework provides good performance. The proposed framework has several new features that other approaches have not considered. The most distinctive feature is that it finds high interest content pages efficiently using only data that can be collected easily at the client side. The framework transforms each visit URL into indicator vectors. Both visit pattern indicators and interaction pattern indicators are used in the framework. The framework is also quite different from others in that it finds high interest content pages using two classifiers in series. To find pages of interest, the navigational pages are removed by the first classifier and then the uninteresting content pages are removed from the remaining content pages by the second classifier. The classifiers were built using a Decision Tree algorithm and thus they showed good generalization power even though there may be variances in input data according to users’ individual differences and noise.

From our research processes and the final results, we showed that it is possible to build a general framework for client side WUM. The extracted user interest models based on our framework are essential to build an intelligent system that will play crucial roles to find users’ interests and track change patterns. Furthermore, an accurate interest model that is constructed based on the output of the framework can be used to deliver personalized content in a proactive manner. In the near future, we will develop several intelligent systems based on this framework.

References
1. Badi, R., Bae, S., Moore, J.M., Meintanis, K., Zacchi, A., Hsieh, H., et al. (2006). Recognizing user interest and document value from reading and organizing activities in document triage, Proceedings of the 11th international conference on Intelligent user interfaces (pp. 218-225). Sydney, Australia: ACM.
2. Bayir, M.A., Toroslu, I.H., Cosar, A., & Fidan, G. (2009). Smart Miner: a new framework for mining large scale web usage data, Proceedings of the 18th international conference on World wide web (pp. 161-170). Madrid, Spain: ACM.
3. Blei, D.M. (2012). Probabilistic topic models. Commun. ACM, 55(4), 77-84.
4. Brusilovsky, P., Kobsa, A., & Nejdl, W. (Eds.). (2007). The Adaptive Web, Methods and Strategies of Web Personalization (Vol. 4321): Springer.
5. Cho, Y.H., & Kim, J.K. (2004). Application of Web usage mining and product taxonomy to collaborative recommendations in e-commerce. Expert Systems with Applications, 26(2), 233-246.
6. Cho, Y.H., Kim, J.K., & Kim, S.H. (2002). A personalized recommender system based on web usage mining and decision tree induction. Expert Systems with Applications, 23(3), 329-342.
7. Claypool, M., Le, P., Wased, M., & Brown, D. (2001). Implicit interest indicators, Proceedings of the 6th international conference on Intelligent user interfaces (pp. 33-40). Santa Fe, New Mexico, United States: ACM.
8. Cooley, R., Mobasher, B., & Srivastava, J. (1999). Data Preparation for Mining World Wide Web Browsing Patterns. Knowledge and Information Systems, 1(1), 5-32.
9. Domenech, J.M., & Lorenzo, J. (2007). A Tool for Web Usage Mining Lecture Notes in Computer Science, 4881, 695-704.
10. Douglas, W.O., & Jinmook, K. (2007). 1 Modeling Information Content Using Observable Behavior.
11. Fu, Y., Creado, M., & Ju, C. (2001). Reorganizing web sites based on user access patterns, Proceedings of the tenth international conference on Information and knowledge management (pp. 583-585). Atlanta, Georgia, USA: ACM.
12. Al halabi, W.S.A., Kubat, M., & Tapia, M. (2007). Time spent on a web page is sufficient to infer a user’s interest, IASTED European Conference on Proceedings of the IASTED European Conference: internet and multimedia systems and applications (pp. 41-46). Chamonix, France: ACTA Press.
13. Hofgesang, P.I. (2006). Peter I. Hofgesang. Workshop on Web Mining and Web Usage Analysis. The 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2006).
14. Jin, X., Zhou, Y., & Mobasher, B. (2004). Web usage mining based on probabilistic latent semantic analysis, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 197-205). Seattle, WA, USA: ACM.
15. Kellar, M., Watters, C., Duffy, J., & Shepherd, M. (2004). Effect of task on time spent reading as an implicit measure of interest. Proceedings of the American Society for Information Science and Technology, 41(1), 168-175.
16. Kelly, D., & Belkin, N.J. (2004). Display time as implicit feedback: understanding task effects, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 377-384). Sheffield, United Kingdom: ACM.
17. Kelly, D., & Teevan, J. (2003). Implicit feedback for inferring user preference: a bibliography. SIGIR Forum, 37(2), 18-28.
18. Kim, D., & Oh, A. (2011). Topic chains for understanding a news corpus, Proceedings of the 12th international conference on Computational linguistics and intelligent text processing – Volume Part II (pp. 163-176). Tokyo, Japan: Springer-Verlag.
19. Liu, H., Kešelj, V., (2007). Combined mining of Web server logs and web contents for classifying user navigation patterns and predicting users’ future requests. Data Knowl. Eng., 61(2), 304-330.
20. Masseglia, F., Poncelet, P., Teisseire, M., & Marascu, A. (2008). Web usage mining: extracting unexpected periods from web logs. Data Min. Knowl. Discov., 16(1), 39-65.
21. Mobasher, B. (2007). Web Usage Mining In B. Liu (Ed.), Web Data Mining Springer.
22. Mobasher, B., Cooley, R., & Srivastava, J. (2000). Automatic personalization based on Web usage mining. Commun. ACM, 43(8), 142-151.
23. Nasraoui, O., Soliman, M., Saka, E., Badia, A., & Germain, R. (2008). A Web Usage Mining Framework for Mining Evolving User Profiles in Dynamic Web Sites. IEEE Trans. on Knowl. and Data Eng., 20(2), 202-215.
24. Pierrakos, D., Paliouras, G., Papatheodorou, C., & Spyropoulos, C.D. (2003). Web Usage Mining as a Tool for Personalization: A Survey. User Modeling and User-Adapted Interaction, 13(4), 311-372.
25. Quinlan, J.R. (1993). C4.5: programs for machine learning: Morgan Kaufmann Publishers Inc.
26. Román, P.E., L’Huillier, G., & Velásquez, J.D. (2010). Web Usage Mining. In J.D. Velásquez & L.C. Jain (Eds.), Advanced Techniques in Web Intelligence – I (Vol. 311/2010, pp. 143-165): Springer Berlin / Heidelberg.
27. Salton, G., & McGill, M.J. (1986). Introduction to Modern Information Retrieval: McGraw-Hill, Inc.
28. Seo, Y.-W., & Zhang, B.-T. (2000). Learning user’s preferences by analyzing Web-browsing behaviors, Proceedings of the fourth international conference on Autonomous agents (pp. 381-387). Barcelona, Spain: ACM.
29. Sharma, H., & Jansen, B.J. (2005). Automated evaluation of search engine performance via implicit user feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 649-650). Salvador, Brazil: ACM.
30. Srivastava, J., Cooley, R., Deshpande, M., & Tan, P.-N. (2000). Web usage mining: discovery and applications of usage patterns from Web data. SIGKDD Explor. Newsl., 1(2), 12-23.
31. Steyvers, M., & Griffiths, T. (2007). Probabilistic Topic Models. In T. Landauer, D. McNamara, S. Dennis & W. Kintsch (Eds.), Handbook of Latent Semantic Analysis: Lawrence Erlbaum Associates.
32. Sugiyama, K., Hatano, K., & Yoshikawa, M. (2004). Adaptive web search based on user profile constructed without any effort from users, Proceedings of the 13th international conference on World Wide Web (pp. 675-684). New York, NY, USA: ACM.
33. Tao, Y.-H., Hong, T.-P., & Su, Y.-M. (2008). Web usage mining with intentional browsing data. Expert Syst. Appl., 34(3), 1893-1904.
34. Tseng, V.S., Lin, K.W., & Chang, J.-C. (2007). Prediction of user navigation patterns by mining the temporal web usage evolution. Soft Comput., 12(2), 157-163.
35. Zhang, B.-T., & Seo, Y.-W. (2001). Personalized web-document filtering using reinforcement learning. Applied Artificial Intelligence, 15(7), 665-685.