カーネル・トリックについて昨日書いた 簡単にまとめると、動かす前の測度から簡単に計算できるような測度を動かした後の測度として定義すると線形サポートベクターマシンに持ち込める、ということだった Rのe1071パッケージのsvm()関数では、動かす前の座標…

鎖状のグラフとは、枝分かれのない木グラフのこと ノードは１次元座標で表すこともできて、隣接するノードの位置座標の差をノード間距離と言う このようなノード数Nのグラフがあったとき、それぞれのノードの値を表す長さNのベクトルVを考える Vの値がノード…

木のグラフがある ノードに値が与えられている 木の上で、この値が順序よく並んでいるのかを評価したい そのために、次のようにする ノードの並びのうち、値が昇順(降順でもよい)になっている鎖状のセグメントに分割する そのセグメントを１つのノードとみた…

木はグラフ 全域木は、すべてのノードが連結な木グラフ ノード数Nに対してエッジ数はN-1 すべてのノードは少なくても１個の隣接ノードを持つ 辺の取り方を考える 木グラフをだんだんに大きくしていく 初めはノードなし ノード数１個の木グラフを作る N個のノ…

木を作ってから距離行列を作る すべての辺の長さを１で考えれば、ペアの距離のうち、木の辺の数のペアの距離が１ 残りののペアの長さを2,3,...で分配するわけだが、その分配の仕方は、木の構造(枝分かれの様子)と関係する情報になる ペア間距離はigraphパッ…

最小全域木を考えている ある空間に均等に散らばることができる点の集合があるときに、その点の集合の存在具合の方よりを表す一つの方法が最小全域木 空間(必ずしも連続でなくてもよい(はず))に広がる「不均一分布」を点集合がサンプルとして代表している そ…

今、M次元格子上にN個の点を取る M次元格子は(0,1,2)としてみる これらの点はその遠近関係(以下のソースではマンハッタン距離にしてある)により、最小全域木を取ることができる 今、このN個の点にある値を付与しよう この値は相対的なものであるとすると、定…

トーラスの一部(少し曲がった円筒)の３次最小全域木を作ってみた 処理はすごく重い：重くて使えない 多様体推定がどんな具合なのかはだいたいわかったので、いい方法がないか、探してみることにする たとえばこちら Isomapとは→こちら RでIsomap→veganパッケ…

空間に多様体がある 多様体をあっちこっち観察すると、多様体の存在する点が観測される その複数の点の位置データから、多様体が空間上で何次元なのかを知るにはどうしたらよいのだろう？ 「多次元最小全域木」を作ってやると、多様体の次元までは、「多次元…

とはいえ、一応、メモ １次元最小全域木では、頂点数に対して、辺の数は(木だから) これは、このように考える 点があって、辺がない状態から、辺を１つ増やすと、点が２つ結ばれる それに連結するように辺を１つ増やすと、連結な点の数が１つ増える したがっ…

最小全域木の多次元化についてこちらにメモした 多次元化する別の方法について考えてみる 最小全域木をもう一度見直す 最小全域木作成のアルゴリズムを確認する すべての点が「辺」でつながるように持っていく 「辺」は１次元的なもの (作りうる)すべての「…

最小全域木 N個のノードがある すべてのノードが連結であるようなグラフのうち、エッジの数が最少なとき、その数はN-1 ここで、エッジの重さ(長さ)の和が最小であるようなエッジの取り方があり、そのようなエッジのセットでノードを連結したとき、それを最小…

参考こちら ２つの主なテーマ ユークリッド空間上のランダムな点(の完全グラフ)におけるユークリッド最小全域木の重みの分布 点を固定(グラフも固定、完全グラフとは限らない(多分))して(エッジの重みをランダムに振った上での最小全域木の重みの分布

最小全域木もいろいろある(距離の定め方によって) 特にユークリッド距離での最小全域木の場合には、選択される辺に幾何学的な制約をして候補を減らせるので、通常の解探索より速くできる(Euclidean menimum spanning treeのWiki記事) 完全グラフから最小全域…