arXiv:2408.16993

A Scalable k-Medoids Clustering via Whale Optimization Algorithm

Huang Chenan, Narumasa Tsutsumida

제출 2024-08-30

원문 초록

Unsupervised clustering has emerged as a critical tool for uncovering hidden patterns in vast, unlabeled datasets. However, traditional methods, such as Partitioning Around Medoids (PAM), struggle with scalability owing to their quadratic computational complexity. To address this limitation, we introduce WOA-kMedoids, a novel unsupervised clustering method that incorporates the Whale Optimization Algorithm (WOA), a nature-inspired metaheuristic inspired by the hunting strategies of humpback whales. By optimizing the centroid selection, WOA-kMedoids reduces the computational complexity from quadratic to near-linear with respect to the number of observations, enabling scalability to large datasets while maintaining high clustering accuracy. We evaluated WOA-kMedoids using 25 diverse time-series datasets from the UCR archive. Our empirical results show that WOA-kMedoids achieved a clustering performance comparable to PAM, with an average Rand Index (RI) of 0.731 compared to PAM's 0.739, outperforming PAM on 12 out of 25 datasets. While exhibiting a slightly higher runtime than PAM on small datasets (<300 observations), WOA-kMedoids outperformed PAM on larger datasets, with an average speedup of 1.7x and a maximum of 2.3x. The scalability of WOA-kMedoids, combined with its high accuracy, makes them a promising choice for unsupervised clustering in big data applications. This method has implications for efficient knowledge discovery in massive unlabeled datasets, particularly where traditional k-medoids methods are computationally infeasible, including IoT anomaly detection, biomedical signal analysis, and customer behavior clustering.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.02342v1cs.AI공통 태그 Anomaly Detection, Computational Efficiency

자연 가시성 그래프 기반 사이버 공격 탐지를 위한 위상 지표의 다중 방식 중요도 및 성능 효율성 분석

A Multi Method Importance and Performance Efficiency Analysis of Topological Metrics for Natural Visibility Graph Based Cyber Attack Detection

자연 가시성 그래프(Natural Visibility Graph, NVG) 기반 분석은 서로 다른 구조적 특성을 반영하는 위상 기술자(topological descriptor)를 통해 네트워크 트래픽을 특성화합니다. 그러나 모든 기술자가 사이버 공격 분류에 동일하게 기여하는 것은 아니며, 대규모 지표 집합을 추출하는 것은 계산 비용을 증가시킬 수 있습니다. 본 연구에서는 NVG에서 유도된 21개의 위상 지표를 평가하고, 축소된 하위 집합이 계산 효율성을 개선하면서도 분류 성능을 유지할 수 있는지 조사합니다. SHAP, 그룹화된 순열 중요도(Permutation Importance), Boruta, 재귀적 특징 제거(Recursive Feature Elimination, RFE)의 네 가지 중요도 분석 방법을 합의 순위(Consensus Ranking) 전략을 통해 통합합니다. 이 순위를 바탕으로 Full21, Top15, Top10, Top7, Top5, Top3 구성을 CICIDS2018 데이터셋, CNN 분류기, 계층화된 5겹 교차 검증을 사용하여 평가합니다. 가장 높은 순위를 기록한 세 가지 지표는 avg_clustering_coeff_median, avg_clustering_coeff_std, avg_clustering_coeff_mean입니다. Top3는 97.148%의 정확도, 97.055%의 가중 F1 점수, 0.9675의 MCC를 기록하여 Full21의 95.999%, 95.521%, 0.9549와 비교해 관측된 최고 평균 성능을 달성했습니다. 또한 전체 실행 시간을 14,961.39초에서 589.22초로 96.06% 단축했습니다. 이러한 결과는 중요도 기반의 지표 축소가 평가된 환경에서 더 높은 관측 평균 예측 성능과 실질적으로 훨씬 낮은 계산 비용을 갖춘 간결한 NVG 표현을 제공할 수 있음을 보여줍니다.

arXiv:2610.03649v1cs.CV공통 태그 Anomaly Detection, Computational Efficiency

효율적인 해양 환경 모니터링을 위한 위성 탑재 이상 탐지

On-Board Anomaly Detection for Efficient Marine Environmental Monitoring

해양 생태계는 기름 유출, 유해 조류 번식, 퇴적물 범람 등 서식지와 야생동물, 인간 활동을 방해하는 다양한 위협의 영향을 받습니다. 위성 영상과 인공지능(AI)의 발전은 이러한 위험 요소를 조기에 탐지하고 완화할 수 있는 역량을 향상시켰습니다. 본 논문에서는 다중분광 또는 초분광 센서를 탑재한 지구 관측 위성을 위한 해양 이벤트 탐지 파이프라인을 제안합니다. 제안하는 접근법은 위성 영상을 축소된 잠재 공간(latent space)으로 압축하여 효율적인 위성 탑재(onboard) 처리를 가능하게 하는 자기지도 학습(self-supervised) 신경망(neural network) 인코더를 포함합니다. 머신러닝 이상 탐지 모델(model)은 정상적인 해양 패턴으로부터의 편차를 식별하여 환경적 이상 현상을 감지합니다. 이 성능을 Isolation Forest, One-Class Support Vector Machine, Local Outlier Factor와 같은 전통적인 알고리즘과 비교합니다. 리소스 효율적인 경량 파이프라인은 임베디드 CPU부터 AI 하드웨어 가속기에 이르기까지 계산 자원이 제한된 위성에 배포할 수 있도록 최적화되었습니다. 중요한 정보의 전송을 우선시함으로써, 본 솔루션은 시스템 응답성을 높이고 위성 통신 대역폭을 최적화합니다. 유럽우주국(ESA)의 Phisat-2 미션 및 Microsoft/Thales Alenia Space의 IMAGIN-e 미션을 포함한 여러 실제 미션에 적용되어 입증된 이 파이프라인은 적시 경보와 효율적인 데이터 감축을 제공하여 해양 환경 모니터링을 개선하는 것을 목표로 합니다.

arXiv:2609.27865v1cs.LG공통 태그 Clustering, Anomaly Detection

무엇이 바뀌었는가? 실제·가상·비교 불가 진단을 통한 드리프트 탐지

What Changed? Drift Detection with Real, Virtual, and Incomparable Diagnosis

깊은 인코더를 공유한다고 해서 그 자체만으로 과제 비교 점수의 핵심 교란(confound)을 해소하지는 못한다. 우리는 고정된 공유 표현 위에서 교차 평가된 head가 얕은 exchange 점수의 외삽(extrapolation) 교란을 그대로 물려받음을 보인다. 레이블은 고정한 채 순수 입력 회전만 적용하면 깊은 exchange 점수가 약 0에서 0.80까지 부풀어 오르는 반면, 표현-신규성(novelty) 점수는 상보적인 방향에서는 맹점이 있다(과제를 완전히 바꾸는 레이블 순열 아래에서는 평평하게 유지된다). 조건부 이중 판별자(two-discriminator) discrepancy를 임베딩 공간으로 이식하면 두 맹점을 모두 해소한다. 기능(functional) 축은 회전 아래에서 ±0.001 이내로 유지되고, 레이블 순열 드리프트 질량(drift mass)을 단조적으로 추적한다. mixture-of-heads 수명주기에 통합하면 두 축 게이트(two-axis gate)는 동일 학습 예산에서 exchange 또는 novelty 트리거보다 더 적은 head로 더 나은 의사결정 품질을 달성한다. 일반화된 범주 발견(generalized category discovery)에서는 동일한 청크 수준(chunk-level) 기능 축이 AUROC 0.98–0.99로 의미적 신규성(semantic novelty)과 photometric shift를 분리하는데, 입력별 OOD 점수(MSP, Energy, Mahalanobis, KNN)는 그 구분에 대해 거의 우연(chance) 수준에 머문다. 모든 결과는 CIFAR-100에서 frozen ImageNet-21k ViT-B/16과 자기지도(self-supervised) DINOv2 백본에서 재현되며, recurrence를 갖는 residual adapter pool로도 확장된다. null 보정 novelty 트리거는 메커니즘 변화에서 한 번도 발화하지 않는 반면, 두 축 게이트는 recurrence를 전부 재사용하여 이를 처리한다. 임베딩 공간에서의 결론이 원래 메커니즘으로 전이되기 위한 공통 요인화(common-factoring) 조건을 명시적으로 기술한다.

arXiv:2609.27936v1cs.LG공통 태그 Clustering, Anomaly Detection

양보다 질: 특징 엔지니어링을 통한 불법 비트코인 흐름의 반지도 학습 탐지

Quality over Quantity: Semi-Supervised Detection of Illicit Bitcoin Flows via Feature Engineering

불법 암호화폐 거래 탐지는 극심한 클래스 불균형, 적대적 난독화, 신뢰할 수 있는 라벨의 부족으로 어렵다. 반지도 학습(SSL)은 비라벨 데이터를 활용해 유망한 해결책을 제공하지만, 우리는 그 성공이 데이터 양만으로 보장되지 않으며 데이터 품질에 달려 있음을 보인다. 우리는 Shared Send Mixers(SSM) 거래에서 불법 비트코인 흐름을 탐지하기 위한 SSL 프레임워크를 제안하며, 이는 1억 6,300만 건의 거래로 구성된 포괄적 역사적 데이터셋 위에 구축되었다. 핵심 결론은 SSL의 성공이 데이터 양이 아니라 품질에 달려 있다는 것이다: KeyLinker 주소 클러스터링 및 Shared Send Untangling(SSU) 복잡도 지표와 같은 고충실도 특징은 비라벨 데이터에서 F1 점수 0.84를 달성한다. 마지막으로, One-Time Change(OTC)와 같은 흔한 휴리스틱은 풍부하지만 노이즈를 유입시키는 반면, KeyLinker와 같은 고충실도 특징에 대한 전략적 의존이 필수적임을 실증적으로 보인다. 본 연구는 블록체인 포렌식에서 더 나은 성능으로 가는 길이 더 큰 데이터셋만이 아니라, 데이터 품질을 위한 더 스마트한 특징 엔지니어링에 있음을 확립한다.

arXiv:2609.28262v1cs.CV공통 태그 Clustering, Computational Efficiency

RAMP: 엣지 CPU 비전 모델을 위한 강건한 적응형 혼합 정밀도 양자화

RAMP: Robust Adaptive Mixed-Precision Quantization for Edge CPU Vision Models

엣지 CPU에 심층 학습 모델을 배포할 때는 계산 및 메모리 제약이 병목이 된다. 혼합 정밀도 양자화는 정확도를 유지하면서 추론 지연을 줄일 수 있다고 기대된다. 그러나 양자화는 층 유형마다 서로 다르게 영향을 미치므로, 정확도 손실이 최소화되고 지연 감소가 최대화되는 위치를 찾는 것이 중요하며, 그 효과는 전체 배포에 걸쳐 누적되어 상당한 이득 또는 허용 불가능한 과제 성능 저하로 이어진다. 이러한 식별은 민감도 지표, 즉 모든 후보 정책의 과제 정확도를 평가하지 않고 층별 열화를 추정하는 대리 지표에 의존한다. 그럼에도 널리 쓰이는 지표는 최신 아키텍처에서 체계적으로 실패한다. 우리는 서로 뚜렷이 다른 네 개의 신경망에 걸친 층별 INT8 양자화에 대한 13개 민감도 지표의 체계적 실증 연구를 제시하고, 그로부터 얻은 정책을 두 ARM64 플랫폼에서 검증한다. 그래디언트 기반 민감도 방법은 8개 모델-하드웨어 구성 중 4개에서 실패하고, 가중치 기반 통계는 2개에서 실패한다. 반면 Jensen-Shannon Divergence는 치명적 실패가 전혀 없으며, 안전하게 양자화할 수 없는 층을 안정적으로 분리한다. 민감도 지표만으로는 정책이 정의되지 않으며, 그 단계에 흔히 쓰이는 고정 임계값은 최신 아키텍처의 고도로 치우친 분포에서 취약하다. 우리는 K-Means 클러스터링으로 이를 해결하여 거의 무손실 정확도와 전체 정밀도 모델 대비 평균 $1.81\times$ 속도 향상을 달성한다. 마지막으로, 민감도와 관계없이 속도 향상이 미미한 층을 양자화에서 제외하는 것이 역효과를 낼 수 있음을 밝힌다. 이는 계산 그래프 단편화를 유발하고 연산자 융합(operator fusion)을 비활성화하기 때문이다. 우리 결과는 GPU 접근이나 그래디언트 계산 없이 이질적 엣지 CPU에 양자화된 비전 모델을 배포하는 실무자와 연구자에게 구체적인 할당 정책을 제공한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.