Skip to main content

Data Mining Lab. Blog

Search This Blog

Pages

Showing posts from April, 2020

Posts

BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart

Posted by Data Mining Lab. 날짜: 4/01/2020

Data Mining Lab.

Go to DMLAB Website

본 블로그에서는 서울대학교
컴퓨터공학부 데이터마이닝

연구실에서 진행하고 있는

최신 연구를 소개합니다.

Archive

2024 10

2023 12
2022 12
2021 12
2020 12
2019 1
- December 2019 1

Show more Show less

Popular Posts

Aggregately Diversified Bundle Recommendation via Popularity Debiasing and Configuration-aware Reranking

본 문서에서는 2023년 PAKDD 학회에서 발표될 " Aggregately Diversified Bundle Recommendation via Popularity Debiasing and Configuration-aware Reranking " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Aggregately Diversified Bundle Recommendation via Popularity Debiasing and Configuration-aware Reranking Authors: Hyunsik Jeon, Jongjin Kim, Jaeri Lee, Jong-eun Lee, and U Kang Conference: PAKDD (2023) Aggregately Diversified Bundle Recommendation 추천 시스템은 온라인 플랫폼에서 매우 중요하며, 번들 추천은 사용자에게 개별 아이템 대신 아이템 묶음을 제안하는 것을 목표로 합니다. 번들 추천은 한번의 구매로 고객이 필요한 여러 아이템을 제공할 수 있는 이점 때문에 온라인 플랫폼에서 주목받고 있습니다. 그러나 전통적인 번들 추천 모델은 정확도에만 초점을 맞추어 다양성에 대한 주의를 기울이지 않았습니다. 이에 반해 집계적으로 다양한 번들 추천(aggregately diversified bundle recommendation)은 정확도 뿐만 아니라 사용자 전체에 대해 다양한 아이템을 노출시키는 데 중점을 둡니다. 사용자들에게 다양한 아이템을 노출시키는 것은 그림 1과 같이 장기적으로 플랫폼의 판매 이익을 높일 뿐 아니라, 사용자들이 새로운 아이템을 발견할 수 있게 됨으로써 궁극적으로 사용자의 만족도도 높일 수 있습니다. 그림 1. 번들 추천에서 집계적 다양성의 중요성. 본 논문에서는 이처럼 실세계에서 매우 중요한 문제인 집계적으로 다양한 번들 추천 문제를 다룹니다. 구체적인 문제 정의는 다음과 같습니다. 주어진 정보 사용자-번들 상호

D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors

본 문서에서는 ICDE 2020에서 발표된 " D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Jun-Gi Jang et al., D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors , ICDE 2020 Tucker Decomposition 동영상 (가로, 세로, 시간), 기상 데이터 (오염물질, 위치, 시간) 등과 같이 다양한 데이터들이 밀도 높은 텐서 (Dense tensor)로 표현됩니다. 터커 분해 (Tucker Decomposition) 은 텐서 데이터를 분석하는 가장 유명한 모델 중 하나이며 차원 축소, 클러스터링, 추천 시스템 등과 같이 다양한 응용들에서 활용하고 있습니다. 그림 1. 3차원 텐서에 대한 터커 분해 예시 터커 분해는 그림 1의 예시와 같이 주어진 텐서를 각 차원의 저계수 요인행렬 (low-rank factor matrix)과 관계간의 강도를 표현하는 코어 텐서 (core tensor)로 분해합니다. 터커 분해는 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와 입력 텐서간의 차이를 줄이는 방향으로 요인 행렬들과 코어 텐서를 학습합니다. ALS (Alternating Least Square) 는 터커 분해의 요인 행렬들과 코어 텐서를 학습할 때 사용하는 접근법 중 하나입니다. 해당 방법은 임의의 요인 행렬 하나를 제외한 나머지 모두를 고정시키고, 고정되지 않은 하나의 요인 행렬을 업데이트하며, 요인 행렬들을 순서대로 업데이트합니다. 그림 1의 예에서는 행렬 B와 C를 고정시키고 A를 업데이트합니다. 그 다음, A와 C를 고정시키고 B를 업데이트하며, C도 마찬가지로 A와 B를 고정시켜 업데이트합니다. 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와

Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries

본 문서에서는 데이터 마이닝 분야 학회 중 하나인 KDD 2021에서 발표될 " Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries " 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title: Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries Authors: Jun-Gi Jang and U Kang Conference: The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( KDD ), 2021 Temporal Dense Tensor 실세계에 존재하는 많은 데이터가 시간 밀도 텐서 (temporal dense tensor)로 표현될 수 있습니다. 시간 밀도 텐서는 한 차원이 시간과 관련이 있으며, 대부분의 값들이 관측된 데이터입니다. 예를 들어, 여러 위치에 설치된 센서들에서 매 시간마다 측정값들을 얻을 수 있습니다. 해당 데이터는 3차원 시간 밀도 텐서로 표현할 수 있습니다. 이 외에도, 주식 데이터, 비디오 데이터, 교통량 데이터 등도 시간 밀도 텐서로 표현할 수 있습니다. 그림 1. 시간 밀도 텐서 예시. 센서 데이터, 주식 데이터, 비디오 데이터, 교통량 데이터 등 다양한 실세계 데이터가 시간 밀도 텐서로 표현할 수 있다. 이렇듯 실세계에 존재하는 많은 데이터가 시간 밀도 텐서로 표현될 수 있으며 여러 차원을 가지는 텐서 특성상 데이터의 크기는 매우 큽니다. 그러므로, 시간 밀도 텐서를 효율적이고 효과적으로 분석하는 방법을 개발하는 것은 매우 중요합니다. Tucker Decomposition 터커 분해 (Tucker decomposition) 는 주어진 텐서를 분석할 수 있는 가장 핵심적인 도구 중 하나입니

Time-Aware Tensor Decomposition for Missing Entry Prediction

본 문에서는 Arxiv에 기재된 Time-Aware Tensor Decomposition for Missing Entry Prediction 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Time-Aware Tensor Decomposition for Missing Entry Prediction Authors: Dawon Ahn, Jun-Gi Jang, U Kang Arixv: https://arxiv.org/pdf/2012.08855.pdf CANDECOMP/PARAFAC (CP) Decomposition 그림 1. 3차원 시간 텐서의 CP 분해 다차원 배열을 의미하는 텐서는 시간에 따라 변화하는 다중적인 관계를 표현할 수 있습니다. 예를 들어, 센서에서 수집된 대기 오염 데이터는 오염 물질의 측정 값을 포함하는 3차원 시간 텐서(장소, 오염 물질, 시간)로 표현됩니다. 텐서 분해(Tensor Decomposition)는 텐서 데이터를 효과적으로 분석하는 방법으로, 클러스터링 및 이상 탐지를 포함한 다양한 응용 프로그램에서 광범위하게 활용되고 있습니다. CANDECOMP / PARAFAC (CP) 분해는 가장 대표적인 텐서 분해 모델 중 하나로, 그림 1과 같이 텐서를 각 차원의 벡터들의 외적의 합으로 나타낼 수 있습니다. 위와 같은 시간 텐서에는 대표적인 특성 2가지를 관측할 수 있습니다. 첫번째는 텐서의 시간 차원은 인접한 값들끼리는 서로 연관성이 있는 특징이 있습니다. 예를 들어, t번째 시간에서 관측된 오염 데이터는 t-1, t+1번째 시간에서 관측된 오염 데이터와 비슷한 값을 갖을 것입니다. 두번째로는 데이터를 수집하는 센서 및 기계 오류 및 고장으로 인해 텐서는 많은 결측치로 포함하고, 이는 시간 조각(Time Slice) 별로 다른 희소성(혹은 밀도)을 갖게 합니다. 그러나 표준적인 CP 분해 방법을 포함한 기존 분해 방법들은 위 두 가지 특성 모두 고려하지 않았습니다. 본 논문의 목표는 결측치 예측을 위

Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance

본 문서에서는 IROS 2019에서 발표된 Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance 논문을 소개합니다. 논문에 대한 상세 정보는 다음과 같습니다. Title: Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance [ link ] Authors: Seungcheol Park, Shuyu Wang, Hunjung Lim, and U Kang Conference: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2019 Segmentation of 3D LiDAR Point Clouds 3차원 라이다 센서 (3D LiDAR sensor)란 빛을 이용하여 주변 물체까지의 거리를 측정하여 센서 주변에 있는 물체들에 대한 위치 정보를 전달해주는 장치입니다. 라이다 센서는 실내에서 사용되는 안내 로봇부터 자율주행 차량까지 다양한 분야에서 사용되고 있습니다. 이때, 라이다 센서는 주로 주변에 물체가 있는지 없는지를 인식 (detection)하거나, 물체가 있다면 어떤 물체인지를 식별 (classification)하는 일을 주로 하게 됩니다. 특히 실내외에서 사람을 인식하는 보행자 식별 (pedestrian classification) 과정은 안전을 위해서도 중요하기 때문에 활발하게 연구되고 있는 분야입니다. 그림 1. 라이다 센서를 이용한 보행자 식별 과정의 예시 그림 1은 현관에 설치된 라이다 센서를 통해 보행자를 인식하는 예시를 보여주고 있습니다. 라이다 센서가 인식한 점 정보 (Input Data)를 전달받은 후 다음과 같은 네 단계를 통해 보행자 인식이

Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference

본 문서에서는 WSDM 2020에서 발표된 Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference 논문을 소개합니다. 논문에 대한 상세 정보는 다음과 같습니다. Title: Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference Authors: Jaemin Yoo, U Kang, Mauro Scanagatta, Giorgio Corani, and Marco Zaffalon ACM International Conference on Web Search and Data Mining (WSDM) 2020 Graph Sampling 그래프 샘플링(graph sampling)은 어떤 그래프가 주어졌을 때 해당 그래프의 특성을 보존하는 작은 서브그래프(subgraph)를 생성하는 문제입니다. 본 연구에서는 그래프 샘플링 중에서도 정점 집합을 유지하면서 간선 집합의 일부만을 선택하는 간선 샘플링(edge sampling) 문제를 다룹니다. 예를 들어 사용자간 관계를 설명하는 소셜 네트워크가 주어져 있다고 할 때, 간선 샘플링은 각 사용자의 정보는 유지한 채 사용자간 관계 정보만을 제거하여 서브그래프를 생성합니다. 간선 샘플링이 잘 이루어지면 그림 1 과 같은 결과를 생성하게 됩니다. 그림에 나타난 그래프는 여러 개의 블로그와 블로그간 하이퍼링크를 나타내는 웹 그래프로, 각 정점의 색은 블로그의 정치 성향을 나타냅니다. 이때, 그림 왼쪽의 그래프는 동일한 성향의 블로그끼리 간선을 생성하는 동종 친화성(homophily) 특성을 보이는데, 이 특성이 그림 오른쪽의 서브그래프에서도 잘 보존되는 것을 확인할 수 있습니다. 이렇게 생성된 서브그래프는 실제 그래프의 특성을 보다 효율적으로 파악하기 위해 사용될 수 있습니다. 그림 1.

Domain-Aware Data Selection for Speech Classification via Meta-Reweighting

본 문서에서는 Interspeech'24 학회에 발표된 "Domain-Aware Data Selection for Speech Classification via Meta-Reweighing" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title : Domain-Aware Data Selection for Speech Classification via Meta-Reweighting Authors: Junghun Kim, Ka Hyun Park, Hoyoung Yoon and U Kang Conference: Annual Conference of the International Speech Communication Association (Interspeech) 2024 Introduction 음성 분류 문제는 화자의 감정 분석, 화자 식별, 언어 인식, 가짜 음성 탐지와 같은 다양한 실세계 응용에 중요한 역할을 합니다. 이 과정에서 음성 데이터는 고유한 특성을 갖는 여러 도메인에 걸쳐 존재할 수 있습니다. 예를 들어, 다양한 질병을 가진 환자들의 음성 데이터를 분석하는 경우, 각 질병을 가지고 있는 환자들의 음성 특징이 다르다는 점을 고려하여 음성을 분류해야합니다. 특히, 음성 장애를 가진 환자의 의도를 파악하는 작업에서는 장애의 종류에 따라 각 환자의 발화 특성이 달라지기 때문에, 다중 도메인 데이터를 효과적으로 활용하기 위한 방안이 필요합니다. 이러한 여러 도메인이 존재하는 상황에서의 기존의 음성 분류 방식은 다음과 같이 구분해 볼 수 있습니다. 첫 번째로, 타겟 도메인의 정보만을 활용하는 방법이 있습니다. 이러한 방식을 사용하게 되면 유용한 소스 도메인의 데이터가 존재하더라도 활용하지 못하는 단점이 있습니다. 이는 실제 문제 상황에서 발생하는 문제로, 제한된 타겟 도메인 데이터를 보완하기 위해 소스 도메인 데이터를 어떻게 활용할지에 대한 전략이 필요합니다. 두 번째로, 주어진 타겟과 더불어

FreQuant: A Reinforcement-Learning based Adaptive Portfolio Optimization with Multi-frequency Decomposition

본 문서에서는 KDD 2024 학회에 발표될 "FreQuant: A Reinforcement-Learning based Adaptive Portfolio Optimization with Multi-frequency Decomposition" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title : FreQuant: A Reinforcement-Learning based Adaptive Portfolio Optimization with Multi-frequency Decomposition Authors: Jihyeong Jeon, Jiwon Park, Chanhee Park, and U Kang Conference: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) 2024 Introduction 최근 연구에서는 강화 학습 (RL) 과 딥러닝을 결합하여 자산의 시간적 패턴을 포착하고, 이를 통해 포트폴리오를 최적화하는 것의 효과가 입증되었습니다. 현존하는 대부분의 모델은 시간 도메인에서 자산의 패턴 분석을 중점으로 두었으며, 시간 축을 기준으로 변동에 대한 평준화를 진행하는 연산을 수행하였습니다. 그러나 이러한 평준화 연산은 때때로 시장 및 자산에 중대한 영향을 주는 갑작스러운 사건에 따른 급격한 가격 변동에 둔감해진다는 단점이 있습니다. 따라서, 기존 모델의 경우 시장 혹은 자산이 방향성이 있는 일관적 패턴을 보일 때 좋은 성능을 보이지만, 갑작스러운 사건에 의하여 시장이 요동칠 때는 모델이 변화를 감지하지 못하여 큰 손실을 초래하게 됩니다. 이러한 한계를 극복하려는 방법의 하나는 시간 도메인에서 주파수 도메인 분석으로 변화를 주어 자산의 패턴 분석을 진행하는 것입니다. 이를 위한 이산 푸리에 변환 (DFT) 은 시간 도메인의 신호를 주파수 도메인의 특성으로 변환함으로써 해석하기 어려운 시간적 패턴을 다양한 주기성을

Fast and Accurate Domain Adaptation for Irregular Tensor Decomposition

본 문서에서는 KDD 2024 학회에 발표될 "Fast and Accurate Domain Adaptation for Irregular Tensor Decomposition" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title : Fast and accurate domain adaptation for irregular tensor decomposition Authors: Junghun Kim, Ka Hyun Park, Jun-Gi Jang and U Kang Conference: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) 2024 Introduction 불규칙 텐서 (irregular tensor) 는 3차원 텐서에서 한 축의 길이가 다른 형태의 데이터를 의미합니다. 실세계의 여러 데이터들은 불규칙 텐서 (irregular tensor) 로 표현됩니다. 예를 들어 특정 바이러스에 감염된 환자들의 데이터는 각 환자가 하나의 슬라이스 (slice) 형태로 존재하는 불규칙 텐서로 표현됩니다. 이 때 각 슬라이스는 ("입원 기간", "의료 정보") 의 정보가 담겨있는데, 환자들에게 얻은 "의료 정보"의 종류는 동일하므로 (예를 들어 심장 박동, 맥박 등) 슬라이스들의 "의료 정보"의 길이는 동일합니다. 하지만 모든 환자들의 입원 기간이 다르기 때문에 슬라이스들의 "입원 기간" 축의 길이는 다릅니다. 이러한 불규칙 텐서를 분석하는 대표적인 기법으로는 PARAFAC2 가 있습니다. PARAFAC2 분해 기법은 주어진 불규칙 텐서를 저차원 요인 행렬들 (low-rank factor matrices) 로 분해하여 중요한 특징을 추출합니다. 멀티 도메인 불규칙 텐서 (multi-domain irregular tensor) 는 여러 도

Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range

본 문서에서는 CIKM 2018에서 발표된 " Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range Authors: Jun-Gi Jang, Dongjin Choi, Jinhong Jung, and U Kang Conference: 27th ACM International Conference on Information and Knowledge Management (CIKM 2018) Singular Value Decomposition 센서 데이터, 기상 데이터 등과 같이 여러 시계열 데이터 (multiple time series data)는 행이 시간 축, 열이 속성 (예를 들어, 센서 타입) 축인 행렬들로 표현 될 수 있습니다. Singular Value Decomposition (SVD)는 행렬로 표현된 실세계 데이터를 분석하는 가장 유명한 도구 중 하나입니다. SVD는 차원 축소, 클러스터링, 주성분 분석 등 데이터 마이닝 응용에서 많이 활용되고 있습니다. 아래 그림은 SVD 방식에 대한 예제를 나타냅니다. 그림 1. Singular Value Decomposition (SVD) - 출처[ link ] SVD는 주어진 행렬 A 를 세 개의 행렬들 U , 𝝨, V 로 분해합니다. 행렬 U 와 V 는 직교행렬이며, 𝝨는 대각행렬이고, 대각의 값은 내림차순으로 정렬되어 있습니다. 실세계 데이터는 중복이 많으며, 저차원 구조를 가지고 있으므로 작은 행렬들로 입력 데이터 행렬 A 를 표현할 수 있습니다. Problem Definition 해당 논문의 목표는 임의