文献

J-GLOBAL ID：201802234274556292   整理番号：18A0864591

高速k-最近傍に基づく最小スパニング木異常値検出手法【JST・京大機械翻訳】

A Fast kNN-Based MST Outlier Detection Method

著者 (4件)： Zhu Li (西安交通大学軟件学院 西安 710049) ,  Qiu Yuanyuan (西安交通大学軟件学院 西安 710049) ,  Yu Shuai (西安交通大学軟件学院 西安 710049) ,  Yuan Sheng (西安交通大学軟件学院 西安 710049)
資料名： Jisuanji Xuebao  (Jisuanji Xuebao)
巻： 40  号： 12  ページ： 2856-2870  発行年： 2017年 
JST資料番号： C2531A  ISSN： 0254-4164  CODEN： JIXUDT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： 異常値検出も異常点検出と呼ばれ、データマイニング領域の意義のあるホットポイント問題の1つであり、多くの方面で広く応用され、例えば侵入行為、詐欺行為、医学上疾病前期の兆候など。k-最近傍に基づくアルゴリズムは,大きなデータセットにうまく適用できるので,距離と密度に基づく異常値検出技術において広く応用される。しかし,k-最近傍アルゴリズムの時間複雑性はO(N2)であり,データセットのサイズの増加とともに,時間オーバヘッドは大いに増加する。最小スパニングツリーに基づくクラスタリングアルゴリズムは,PrimまたはKruskalアルゴリズムを使用して,最小スパニングツリーを構築するときの空間複雑性と時間複雑性は,O(N2)であり,クラスタ化結果は,ユーザパラメータの選択に依存し,そして,高密度クラスタの局所的異常値を,容易に検出することができた。以上の問題に対して、密度とクラスタリング方法に基づく優位性を融合し、新たな異常値検出方法を提案した。この方法は以下の長所を持つ:(1)k-最近傍の時間複雑度がO(kN)(女「N)」と計算され、最小スパニングツリーを構築する時間複雑度がO(NlogN)(3)、適応識別クラスタリング数であり、(4)複数のタイプの異常値データを検出することができる。最後に,KDNSアルゴリズム,FkNNアルゴリズム,およびADCアルゴリズムの効率を,多くの実験を通して検証した。実験結果は,既存のアルゴリズムと比較して,提案したアルゴリズムは時間複雑性を大幅に低減でき,異常値検出率を大幅に改善できることを示した。Data from Wanfang. Translated by JST【JST・京大機械翻訳】

シソーラス用語： 特異点 ,  *スパンニング木 ,  アルゴリズム ,  クラスタ化 ,  *異常値 ,  *高速度 ,  クラスタ ,  データマイニング
準シソーラス用語： 複雑度 ,  高密度 ,  クラスタリングアルゴリズム ,  オーバヘッド ,  複雑性 ,  詐欺 ,  *異常値検出 , 【Automatic Indexing@JST】

著者キーワード (6件)： well separated pair ,  MST ,  kNN ,  auto clustering ,  outlier detection ,  data mining

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (3件)： スパニング木 ,  異常値検出 ,  手法