ちょっと勉強のためにクラスター分析をjavascriptで書いてみました。
いろいろと調査していると、距離の演算にはウォード法がいいんじゃないかというポストがたくさんあったのでウォード法を使っています。今回はクラスター分析結果で何かをしたいわけじゃないのでこれでいいとします。
で、使ってみるとデータの数×変数の数を抑えてあげないとブラウザが固まります(ノ∀`)ﾀﾞﾊｰ。実装の仕方が悪いというのもありますが、サーバサイドでやったほうがいい処理なのかもしれません。実際、そんなにデータ量が多くてもピンとこないと思いますので初期値を勝手に設定してあります。
・データの数を２０～３０個くらいで
・変数１にして
・グループ数を１０くらいから１に向かってぐりぐり変えてあげると、
なんとなく上手くグルーピングされていってるんじゃねーか？ってのがわかります。本当はクリック位置とかを分析して視覚的に見せようかと思ったのですが途中で投げてしまいました。
いろいろと調査していると、距離の演算にはウォード法がいいんじゃないかというポストがたくさんあったのでウォード法を使っています。今回はクラスター分析結果で何かをしたいわけじゃないのでこれでいいとします。
で、使ってみるとデータの数×変数の数を抑えてあげないとブラウザが固まります(ノ∀`)ﾀﾞﾊｰ。実装の仕方が悪いというのもありますが、サーバサイドでやったほうがいい処理なのかもしれません。実際、そんなにデータ量が多くてもピンとこないと思いますので初期値を勝手に設定してあります。
・データの数を２０～３０個くらいで
・変数１にして
・グループ数を１０くらいから１に向かってぐりぐり変えてあげると、
なんとなく上手くグルーピングされていってるんじゃねーか？ってのがわかります。本当はクリック位置とかを分析して視覚的に見せようかと思ったのですが途中で投げてしまいました。
| input | output | ||||||||||
| |||||||||||
サンプルソース
function ClusterAnalysis(){
this.init.apply( this, arguments );
}
ClusterAnalysis.prototype = {
dataStore : {
grpCnt : 0,
dataCnt : 0,
rngCnt : 0,
grpRng : null,
data : null
},
init : function(){
var store = this.dataStore;
store.grpCnt = parseInt( $( "grpcnt" ).value );
store.dataCnt = parseInt( $( "datacnt" ).value );
store.rngCnt = parseInt( $( "rngcnt" ).value );
if( $( "retain" ).checked ){
store.grpRng = new Array( store.dataCnt );
store.data = new Array( store.dataCnt );
for( var idx = 0; idx < store.dataCnt; idx++ ){
store.data[ idx ] = new Array( store.rngCnt );
}
for( var idx = 0; idx < store.dataCnt; idx++ ){
for( var ndx = 0; ndx < store.rngCnt; ndx++ )
store.data[ idx ][ ndx ] = Math.round( Math.random() * 100 );
}
}
$( "retain" ).checked = false;
},
analysis : function(){
var store = this.dataStore;
var dataCntBuf = new Array( store.dataCnt );
var rangeBuf = new Array( store.dataCnt )
for( var idx = 0; idx < store.dataCnt; idx++ ){
rangeBuf[ idx ] = new Array( store.dataCnt );
}
for( var idx = 0; idx < store.dataCnt; idx++ ){
store.grpRng[ idx ] = idx;
dataCntBuf[ idx ] = 1;
for( var ndx = idx + 1; ndx < store.dataCnt; ndx++ )
rangeBuf[ idx ][ ndx ] = this.getRange( idx, ndx );
}
for( var idx = 0; idx < store.dataCnt; idx++ ) {
for ( var ndx = idx + 1; ndx < store.dataCnt; ndx++ )
rangeBuf[ ndx ][ idx ] = rangeBuf[ idx ][ ndx ];
}
var loopCnt = store.dataCnt;
while ( loopCnt > store.grpCnt ) {
var range = this.getMinimumRange( rangeBuf );
for( var idx = 0; idx < store.dataCnt; idx++ ){
if( store.grpRng[ idx ] == idx ) {
for ( var ndx = idx + 1; ndx < store.dataCnt; ndx++ ) {
if( store.grpRng[ ndx ] == ndx ) {
if( idx != range.to && ndx != range.to ) {
if ( idx == range.from ) {
rangeBuf[ idx ][ ndx ] = this.analyticRange({
dest1 : rangeBuf[ range.from ][ ndx ],
dest2 : rangeBuf[ range.to ][ ndx ],
dest3 : rangeBuf[ range.from ][ range.to ],
size1 : dataCntBuf[ range.from ],
size2 : dataCntBuf[ range.to ],
size3 : dataCntBuf[ ndx ]
});
rangeBuf[ ndx ][ idx ] = rangeBuf[ idx ][ ndx ];
}
else if ( ndx == range.to ) {
rangeBuf[ idx ][ ndx ] = this.analyticRange({
dest1 : rangeBuf[ idx ][ range.from ],
dest2 : rangeBuf[ idx ][ range.to ],
dest3 : rangeBuf[range.from][ range.to ],
size1 : dataCntBuf[ range.from ],
size2 : dataCntBuf[ range.to ],
size3 : dataCntBuf[ ndx ]
});
rangeBuf[ ndx ][ idx ] = rangeBuf[ idx ][ ndx ];
}
}
}
}
}
}
dataCntBuf[ range.from ] += dataCntBuf[ range.to ];
for( var idx = 0; idx < store.dataCnt; idx++ ) {
if( store.grpRng[ idx ] == range.to )
store.grpRng[ idx ] = range.from;
}
loopCnt--;
}
},
getRange: function( from, to ){
var store = this.dataStore;
var buf = 0 ;
var range = 0;
for( var idx = 0; idx < store.rngCnt; idx++ ){
buf = store.data[ from ][ idx ] - store.data[ to ][ idx ];
range = range + ( buf * buf );
}
return range;
},
getMinimumRange : function( rangeBuf ){
var store = this.dataStore;
var range = { from:0, to:0 };
var min = -1.0;
for ( var idx = 0; idx < store.dataCnt; idx++ ) {
if ( store.grpRng[ idx ] == idx ) {
for ( var ndx = idx + 1; ndx < store.dataCnt; ndx++ ) {
if ( store.grpRng[ ndx ] == ndx ) {
if( min < 0.0 || rangeBuf[ idx ][ ndx ] < min ) {
min = rangeBuf[ idx ][ ndx ];
range.from = idx;
range.to = ndx;
}
}
}
}
}
return range;
},
analyticRange : function( relation )
{
var range = (
( relation.size1 + relation.size3 ) * relation.dest1 +
( relation.size2 + relation.size3 ) * relation.dest2 -
relation.size3 * relation.dest3
) / ( relation.size1 + relation.size2 + relation.size3 );
return range;
},
dataStore : {
grpCnt : 0,
dataCnt : 0,
rngCnt : 0,
grpRng : null,
data : null
},
renderOutput : function(){
var store = this.dataStore;
var grpidx = 1;
var grpndx;
var renderText = '';
while( grpidx <= store.grpCnt ) {
grpndx = -1;
renderText += '\nグループ ' + grpidx + "\n";
for ( var idx = 0; idx < store.dataCnt && grpndx < 0; idx++ ) {
if( store.grpRng[ idx ] >= 0 )
grpndx = store.grpRng[ idx ];
}
for ( var idx = 0; idx < store.dataCnt; idx++ ) {
if( store.grpRng[ idx ] == grpndx ) {
var head = 'データ No.' + idx + '\t[ ';
for ( var ndx = 0; ndx < store.rngCnt; ndx++ ){
renderText += head + store.data[ idx ][ ndx ] +
( ( ndx == store.rngCnt -1 ) ? "" : ", ");
head = '';
}
renderText += ' ]\n';
store.grpRng[ idx ] = -1;
}
}
grpidx++;
}
$( 'outarea' ).value = renderText;
},
renderInput : function(){
var store = this.dataStore;
var renderText = '';
for ( var idx = 0; idx < store.dataCnt; idx++ ) {
var head = 'データ No.' + idx + '\t[ ';
for ( var ndx = 0; ndx < store.rngCnt; ndx++ ){
renderText += head + store.data[ idx ][ ndx ] +
( ( ndx == store.rngCnt -1 ) ? "" : ", ");
head = '';
}
renderText += ' ]\n';
}
$( 'inarea').value = renderText;
}
}
function exec(){
$( "inarea" ).value = '';
$( "outarea" ).value = '';
try {
execInst = new ClusterAnalysis();
execInst.renderInput();
execInst.analysis();
execInst.renderOutput();
}
catch( e ){ alert( e.description )}
}
function $( id ){
return document.getElementById( id );
}
[ 最近のエントリーとその関連エントリー ]
[ スポンサードリンク ]
| パーマリンク
