論文の概要: Biclustering and Boolean Matrix Factorization in Data Streams
- arxiv url: http://arxiv.org/abs/2012.03138v1
- Date: Sat, 5 Dec 2020 23:02:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-22 12:10:59.127677
- Title: Biclustering and Boolean Matrix Factorization in Data Streams
- Title（参考訳）: データストリームにおけるビクラスタリングとブール行列分解
- Authors: Stefan Neumann, Pauli Miettinen
- Abstract要約: データストリームにおける二部グラフのクラスタリングとブール行列の分解について検討する。
ストリームを渡った後、サブ線形空間を用いてグラフの右側のクラスタの集合を復元するアルゴリズムを提案する。
合成データと実世界のデータに対するアルゴリズムの実装を評価する。
- 参考スコア（独自算出の注目度）: 12.005731086591139
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the clustering of bipartite graphs and Boolean matrix factorization
in data streams. We consider a streaming setting in which the vertices from the
left side of the graph arrive one by one together with all of their incident
edges. We provide an algorithm that, after one pass over the stream, recovers
the set of clusters on the right side of the graph using sublinear space; to
the best of our knowledge, this is the first algorithm with this property. We
also show that after a second pass over the stream, the left clusters of the
bipartite graph can be recovered and we show how to extend our algorithm to
solve the Boolean matrix factorization problem (by exploiting the
correspondence of Boolean matrices and bipartite graphs). We evaluate an
implementation of the algorithm on synthetic data and on real-world data. On
real-world datasets the algorithm is orders of magnitudes faster than a static
baseline algorithm while providing quality results within a factor 2 of the
baseline algorithm. Our algorithm scales linearly in the number of edges in the
graph. Finally, we analyze the algorithm theoretically and provide sufficient
conditions under which the algorithm recovers a set of planted clusters under a
standard random graph model.
- Abstract（参考訳）: データストリームにおける二部グラフのクラスタリングとブール行列分解について検討する。
グラフの左側から頂点が1つずつ入ってくるようなストリーミング設定を,すべての入射エッジと共に考慮する。
ストリームを渡った後、サブ線形空間を用いてグラフの右側のクラスタの集合を復元するアルゴリズムを提供する。
また,ストリームを2度通過すると,二部グラフの左クラスタを復元し,ブール行列因数分解問題(ブール行列と二部グラフの対応を利用して)を解く方法を示す。
本研究では,合成データおよび実世界データに対するアルゴリズムの実装を評価する。
実世界のデータセットでは、アルゴリズムは静的ベースラインアルゴリズムよりも桁違いに高速であり、ベースラインアルゴリズムの係数2内で品質結果を提供する。
我々のアルゴリズムはグラフの辺の数を線形にスケールする。
最後に,このアルゴリズムを理論的に解析し,標準ランダムグラフモデルの下で植込みクラスタ群を復元するのに十分な条件を提供する。
関連論文リスト
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Fast and Simple Spectral Clustering in Theory and Practice [7.070726553564701]
スペクトルクラスタリング(Spectral clustering)は、グラフの$G$で$k$のクラスタを見つけるために設計された、人気があり効果的なアルゴリズムである。
電力法により計算された$O(log(k))$の頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。
合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
論文 参考訳（メタデータ） (2023-10-17T02:31:57Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。
従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。
提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
論文 参考訳（メタデータ） (2022-03-17T19:26:00Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
階層クラスタリングのための2時間近似アルゴリズムを提案する。
本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
論文 参考訳（メタデータ） (2021-12-16T17:52:04Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。
行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-15T13:40:07Z) - MC2G: An Efficient Algorithm for Matrix Completion with Social and Item
Similarity Graphs [85.89744949820376]
MC2Gは、ソーシャルグラフとアイテム類似性グラフの存在下で行列補完を行うアルゴリズムである。
スペクトルクラスタリングと局所的な精細化のステップに基づいている。
我々は、MC2Gが他の最先端行列補完アルゴリズムより優れている合成データセットと実データセットの両方に関する広範な実験を通して示す。
論文 参考訳（メタデータ） (2020-06-08T06:11:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。