DataMining タグのついた記事一覧 - 京の路

データマイニング技術をスパムブログ検出に用いる事例が増えているのでしょうか？

今週は２度もそういったビジネスの話を聞く機会がありました。僕も大学院でデータマイニングの研究をかじったので、ちょっと親近感が沸きました。

僕がやってたのは単純な数値データのクラスタリングなので、テキストタイプのデータマイニングはあまりよく知りませんが、話を聞いた感じだと

1. 大量のテキストデータから似ている部分を探し出し
2. それらに類似度を付けた上でグルーピング化し
3. 一定の閾値を超えたものをスパムとする

という感じなのかな？

Read more Comments Retweet

多目的最適化は無視。
多目的遺伝的アルゴリズムも無視。
がしかし、スライドは35枚。
今はかったら20分かかってたので、まずはこれを15分にしなければ。

でも、今の内容じゃ伝わんないだろうなぁ〜。。
月曜日pinkさんにいじめてもらおう。

Comments Retweet

ひとまず完成。MOCKのアルゴリズム自体は変えず、所持するデータと初期化時の最小全域木生成アルゴリズムを変更しました。ただし実行時間とデータ量を両方ともに減らすため、最小全域木の代わりに「準最小全域木」的なものを作り、さらにデータによっては最小全域木を作成できずにエラーになるという仕様なのですが。

メモリ使用量の面では、13,000データで100MB、26,000データで200MBというメモリ使用量になっており、データ数Nに対してO(N)にすることができました。

実行時間の面では、初期化には（おそらく必須の）O(N^2)の処理が含まれているのですが、いままでよりはかなり高速になりました。いままで自身に近いものから順に自身以外のデータのIDをならべた配列をすべてのデータについて作っており、そこでO(N^2*logN)のコストがかかっていたのですが、これをTop M個（Mはパラメータ）だけしか計測しないようにしてO(N*logN)にしたので。13,000個のデータで45分くらいかかってたのが、これが数分で終わるようになりました。ただし距離情報はいっさい持たないことにしたので、GAの評価部分は処理が数倍おそくなりました。まぁでもオーダーはO(N)でかわらないので大丈夫でしょう。

Read more Comments Retweet

現在のプログラムだと、8,000件の2次元データを処理するために、初期化で30分以上かかる。
そして初期化が終わると5分くらい。
データの書き出しにまた5分くらい。

10,000件だと1時間経っても初期化が終わらない。

原因ははっきりしていて、MST生成時にO(N^2)のコストをかけているから。
Primのアルゴリズムを使うとO(NlogN)までコストが下がるらしいので、勉強してみるか。。。

あと10,000件で1.5GBメモリを食うので、そしてメモリはN^2に比例するので、100,000件のデータを処理する為には150GBのメモリが必要。
DBに退避させる（クラスタにDBが必要）か、距離は適宜計算する（「現在の計算コスト*世代数*個体数」分の計算コストがかかる。今1時間かかってるとしたら、ざっと計算して1[hours]*200[generations]*50[solutions]=10,000[hours]かかる。10,000[hours]⇒1年以上）か。。。

まぁ確実に前者な訳だけど、だとすると500,000件のデータを扱うためにはDB用にHDDが3.75TB必要。

マジ？
Googleさんって1億以上のサイトをどうやって処理してるの？？
1億って10,000の10,000倍...2次元の実数値データでも...150PB！？
GridとかHPCとかの次元でなんとかなるもんなの？？？

Read more Comments Retweet

【文献調査】Improvements to the scalability of multiobjective clustering

Abstract

本報告ではImprovements to the scalability of multiobjective clustering[1]の調査結果を述べた。調査文献でHandlらはMOCKのデータサイズやデータの次元数に対するスケーラビリティを向上させるために、新たな初期化と突然変異、最良解を唯一に決定するために用いるランダムデータの生成法を提案している。またデータサイズ、データの次元共に大きなテスト問題を用意するため、テストデータ生成方法についても述べ、それらのテストデータを用いた実験を通して従来の単目的クラスタリング手法との性能比較を行っている。本報告では新たに提案されたオペレータとテストデータ生成方法についてまとめた。

細かいとこも読んだよ。読んだけどさ...

Read more Comments Retweet

Mining the Web: Discovering Knowledge from Hypertext Data (The Morgan Kaufmann Series in Data Management Systems)

Soumen Chakrabarti

Morgan Kaufmann Pub 2002-08-15

売り上げランキング : 52677

by G-Tools , 2008/09/12

洋書だけど、翻訳版があったら読んでみたい。

Comments Retweet

Edge-Sets: An Effective Evolutionary Coding of Spanning Trees

タイトルは面白そうなんだけど、４０ページもあるのであまり読む気になれない。でも著者のRaidlさんはこの業界で有名な人のようなのでそのうち読むかも。

これで５つ全部のアブストを読み終えた。
どれを読むかはまた今度考えることにして、MOCKの論文を１本読んでしまうことにする。

Read more Comments Retweet

A Comparison of Encodings and Algorithms for Multiobjective Minimum Spanning Tree Problems

MOCKの提案者による論文。97年なので、MOCKはこの研究成果の影響をうけている可能性が高い。

Read more Comments Retweet

研究ミーティングにて自分の研究について発表した。で、そこでいろいろ議論してて、大切な論文を忘れてたことに気づく。

そうそう、これザーッとしか読んで無かったんだ。こいつをきちんと深くまで読まないと、進む先が決められないじゃないか！！

Improvements to the scalability of multiobjective clustering

Read more Comments Retweet

An Efficient Evolutionary Algorithm for the Degree-Constrained Minimum Spanning Tree Prolem

Degree-Constrainedな最小全域木問題って何？効果的な個体表現というのは面白そうなところ。アブスト訳を以下に。

Read more Comments Retweet

Expected Runtimes of a Simple Evolutionary Algorithm for the Multi-objective Minimum Spanning Tree problem

多目的最小全域木問題というのが何かは良く分からないけど、MOCKで扱うMSTは単一目的な気がする。多目的だと数理的に解くのが難しくなるのだろうか？ちなみに単一目的のMST生成はO(N*logN)。ま、とりあえずアブストだけ。

Read more Comments Retweet

Computing a Diameter-Constrained Minimum Spanning Tree in Parallel

『直径制約あり最小全域木の並列計算』とでも訳せばいいのか？
Diameter-Constrainedは「k個以上のエッジを持つパスが存在してはいけない」という制約を意味するのだと思うのだが...よく分からん。とりあえずアブストだけ訳してみた。

Read more Comments Retweet

Webコミ班では今年初の勉強会。
日時は今週水曜日の全ゼミ後。

資料は久々にKeynoteで作ってみた。
スライド116枚を10分くらい。
途中問題を解いてもらうので、トータルでは20〜25分くらいになるだろうか。
参加する人は電卓と紙とペンを持って来てもらえれば嬉しいです。

クラスタリングとかSOMとかは今回の勉強会ではあまり触れないつもり。
むしろ統計学をなんとなくイメージできるよってくらいの人向けに、同じようにデータマイニングのイメージを掴んでもらうような内容。

こういうスピード感のある発表は学会や月例発表会では絶対受け入れられないのだろうけど、データマイニングのイメージを掴んでもらうにはこっちのほうが良いだろうと思う。

さて、この試みはうまくいくでしょうか？

Comments Retweet

とりあえず面白そうなのを３つリストアップ。

Learning a Model of a Web User's Interests

Abstract. There are many recommender systems that are designed to help users find relevant information on the web. To produce recommendations that are rel- evant to an individual user, many of these systems first attempt to learn a model of the user's browsing behavior. This paper presents a novel method for learning such a model from a set of annotated web logs -- i.e., web logs that are aug- mented with the user's assessment of whether each webpage is an information content (IC) page (i.e., contains the information required to complete her task). Our systems use this to learn what properties of a webpage, within a sequence, identify such IC-pages, and similarly what "browsing properties" characterize the words on such pages ("IC-words"). As these methods deal with properties of webpages (or of words), rather than specific URLs (words), they can be used anywhere throughout the web; i.e., they are not specific to a particular website, or a particular task. This paper also describes the enhanced browser, A I E, that we designed and implemented for collecting these annotated web logs, and an em- pirical study we conducted to investigate the effectiveness of our approach. This empirical evidence shows that our approach, and our algorithms, work effectively.

Measuring and Understanding User Comfort With Resource Borrowing

Abstract. Resource borrowing is a common underlying approach in grid computing and thin-client computing. In both cases, external processes borrow resources that would otherwise be delivered to the interactive processes of end-users, creating contention that slows these processes and decreases the comfort of the end-users. How resource borrowing and user comfort are related is not well understood and thus resource borrowing tends to be extremely conservative. To address this lack of understanding, we have developed a sophisticated distributed application for directly measuring user comfort with the borrowing of CPU time, memory space, and disk bandwidth. Using this tool, we have conducted a controlled user study with qualitative and quantitative results that are of direct interest to the designers of grid and thin-client systems. We have found that resource borrowing can be quite aggressive without creating user discomfort, particularly in the case of memory and disk. We also describe an on-going Internet-wide study using our tool.

Learning Web Request Patterns

Summary. Most requests on the Web are made on behalf of human users, and like other human-computer interactions, the actions of the user can be characterized by identifiable regularities. Much of these patterns of activity, both within a user, and between users, can be identified and exploited by intelligent mechanisms for learn- ing Web request patterns. Our focus is on Markov-based probabilistic techniques, both for their predictive power and their popularity in Web modeling and other domains. Although history-based mechanisms can provide strong performance in predicting future requests, performance can be improved by including predictions from additional sources. In this chapter we review the common approaches to learning and predicting Web request patterns. We provide a consistent description of various algorithms (often independently proposed), and compare performance of those techniques on the same data sets. We also discuss concerns for accurate and realistic evaluation of these techniques.

今日中にアブストを訳したエントリーを書いてここからリンクする。と書いてみるテスト。

注）このエントリーで紹介された論文は後にMatake's ISDL Reports : 2006にて詳細に紹介する予定です。

Read more Comments Retweet

データをSOMにかけて２次元にマッピングしたあとでMOCKでクラスタリングをしようとしたけれど、SOMのマッピングは空間にほぼ均等にデータをばらまいてしまうようです。これじゃMOCKにはかけられない。

というか、そもそもSOMってよほど頑張らないと順序尺度しか扱えないんじゃないかな。２次元にマッピングできるというところが面白いところなだけで、今回狙っていたような動作はしないっぽいね。そしてMOCKはデータアイテム間の距離さえ分かればクラスタリングできるし。

Read more Comments Retweet

いままでは3列目にクラスタIDを出力していたので、おバカなエクセルではクラスタリング結果のグラフを描くのが超めんどくさかったのだが、今日すばらしい方法を発見♪

一番上の行は一番左のセルを空白にして、その次からクラスタID（ex. Cluster 1, Cluster 2, ...）を書いておく。
2行目からはデータの値を出力するわけだが、ここでX軸のデータを一番左に、Y軸のデータはその次の列からクラスタ事に列を変えて出力する。

プログラムの出力形式をこういう形にしておけば、エクセルを開いて全選択=>散布図作成とするだけでクラスタリング結果が出力される。

実際のエクセルファイル

俺天才♪

Comments Retweet

いままでは3列目にクラスタIDを出力していたので、おバカなエクセルではクラスタリング結果のグラフを描くのが超めんどくさかったのだが、今日すばらしい方法を発見♪

一番上の行は一番左のセルを空白にして、その次からクラスタID（ex. Cluster 1, Cluster 2, ...）を書いておく。
2行目からはデータの値を出力するわけだが、ここでX軸のデータを一番左に、Y軸のデータはその次の列からクラスタ事に列を変えて出力する。

プログラムの出力形式をこういう形にしておけば、エクセルを開いて全選択=>散布図作成とするだけでクラスタリング結果が出力される。

実際のエクセルファイル

俺天才♪

Comments Retweet

日本IBM、自社サイト利用者の属性に応じて最適なコンテンツを表示するサービス - CNET Japan

日本IBMは6月2日、自社ウェブサイト上で、ユーザーの属性にあわせて最適なコンテンツを自動表示するサービスを始めると発表した。ユーザーのドメイン情報から所属企業と業種を判別し、適当な製品やサービスの情報を追加表示するという。

ビジネスユーザに特化したコンテンツマッチング（だと思われる）。これが適用できるサイトは極限られているかもしれないが、Cookieを使ったユーザ単位のマッチングではなく、ドメイン単位なところが面白い。まぁ「登録した属性がパソコンに依存するといった問題も解決した」ってのはちょっと的外れな気もするが。

Comments Retweet

日本IBM、自社サイト利用者の属性に応じて最適なコンテンツを表示するサービス - CNET Japan

日本IBMは6月2日、自社ウェブサイト上で、ユーザーの属性にあわせて最適なコンテンツを自動表示するサービスを始めると発表した。ユーザーのドメイン情報から所属企業と業種を判別し、適当な製品やサービスの情報を追加表示するという。

ビジネスユーザに特化したコンテンツマッチング（だと思われる）。これが適用できるサイトは極限られているかもしれないが、Cookieを使ったユーザ単位のマッチングではなく、ドメイン単位なところが面白い。まぁ「登録した属性がパソコンに依存するといった問題も解決した」ってのはちょっと的外れな気もするが。

Comments Retweet

テスト問題はおおよそ解けているっぽい。あとは「クラスタサイズ>2」の制約を与えればOKかな？

今日まではSquare1というテスト問題を解けるように開発していたのだけれど、他のテスト問題もデータ構造がほぼ同じで簡単に組み込めたよ。

SPEA2+いい感じ。

Comments Retweet