Mr.7

我将骄傲的活在这个大唐盛世

日志

关于我

Mr.7

“我来~我见~我征服!”

文章分类

如何找出一堆点中的异常点

2013-09-30 17:10:27| 分类：挨踢咋活 | 标签： |举报 |字号大中小订阅

下载LOFTER 我的照片书 |

1. 需求

场景其实可以更有意思，不过抽象成模型却是这样的：在一大堆点中，找出异常的点。对应的解决方案如何呢？

2. 模型

交给Excel来弄吧，可视化的模型如下：

散点图，可以看出分布情况，大致可以识别异常的数据：

气泡图，经过聚类，可以把孤独异常的数据挑出来：

其实线性拟合好像不管用；最管用的还是气泡图。但是如何挑出异常的呢？Excel应该可以深入分析，不过想想实现的原理，应该相对还比较简单。

3. 代码

圆状的气泡还是相对有点麻烦，简化为矩形吧。

这个算法对应的最原生算法，因为相比其它有名冠之的聚类算法，它暴力，不求速度，只求开发的简单。

算法原理：

1. 从原始数据中挑出一个未聚类的点，将该点聚类，直到原始数据中所有的点都聚完；
2. 聚每个点的时候，将相关点添加到该组列表上；直到该组的每个点都聚过

以下是代码：

function JL(data,dx,dy)
{
	this.dx_ = dx==undefined ? 2.2 : dx;
	this.dy_ = dy==undefined ? this.dx_ : dy;	
	this.data_src_ = data;
	
	this.data_ = [];
	var tmp;
	for(var i=0; i<data.length;i++)
	{
		tmp = new Array(4);
		tmp[0] = data[i][0];
		tmp[1] = data[i][1];
		if(data[i].length<3)
			tmp[2] = i;
		else
		{
			tmp[2] = data[i][2];
		}
		tmp[3] = 0;
		this.data_.push(tmp);
	}		
	
	//-结果: 聚类，this.rtn_jl_[i]为数组，对应原始数组id-
	this.rtn_jl_ = [];
	//-结果:飞点，-
	this.rtn_fly_ = [];
}

//-判断两个点是否接近-
JL.prototype.isNear = function(pt1,pt2)
{
	return ( Math.abs(pt1[0]-pt2[0])<this.dx_  &&  Math.abs(pt1[1]-pt2[1])<this.dy_ ) ? true : false;
}

//-深度遍历-
JL.prototype.depth = function(index)
{
	var rtn = [index];
	var i = 0,j,tmpdata,curdata;
	do
	{
		curdata = this.data_[rtn[i]];
		for(j=0; j<this.data_.length; j++)
		{
	             if(j==index)
				continue; 
                     tmpdata = this.data_[j];
			if(tmpdata[3]==0 && this.isNear(tmpdata,curdata) )
			{
				tmpdata[3] = 1;
				rtn.push(j)
			}				
		}
		i++;
		if(i>=rtn.length)
			break;
	}while(1);
			
	return rtn;
}

//-聚类分析-
JL.prototype.jl = function()
{		
	for(var i=0; i<this.data_.length; i++)
	{
		if(this.data_[i][3]==0)
		{			
			this.rtn_jl_.push(this.depth(i));
		}
	}
}

//-异常提取-
JL.prototype.pick = function()
{
	var i,j;
	for(i=0; i<this.rtn_jl_.length; i++)
	{
		//-转换成原始索引-
		for(j=0; j<this.rtn_jl_[i].length; j++)
		{
			this.rtn_jl_[i][j] = this.data_[this.rtn_jl_[i][j]][2];			
		}
		
		//-每类个数小于3当做错误，对应原始索引保存-
		if(this.rtn_jl_[i].length<3)
		{
			for(j=0; j<this.rtn_jl_[i].length; j++)				
			{				
				this.rtn_fly_.push(this.rtn_jl_[i][j]);			
			}
		}
	}		
}

JL.prototype.show = function()
{
	console.log("this.rtn_jl_.length = " + this.rtn_jl_.length);
	
	for(var i=0; i<this.rtn_jl_.length; i++)
	{
		console.log( i + " : " +this.rtn_jl_[i] );

		if(this.rtn_jl_[i].length<3)
		{
			for(var j=0; j<this.rtn_jl_[i].length; j++)
			{
				console.log("\r\t" + this.data_src_[this.rtn_jl_[i][j]]);
			}
		}
	}
}

//-统一:排序+聚类+异常提取-
JL.prototype.do = function()
{
	//this.data_.sort(); //--排序没什么用--
	this.jl();
	this.pick();
}

exports.JL = JL;

以下是测试代码：

var JL = require('./julei.js');
var data = [
[417897.497135,143782.261573],
[417897.190857,143782.048861],
[417896.924219,143781.900988],
[417896.679199,143781.763937],
[417896.192915,143782.631089],
[417895.933481,143782.494021],
[417895.447032,143782.194715],
[417897.756803,143784.155517],
[417897.537008,143784.032893],
[417897.317213,143783.90667],
[417897.097417,143783.780446],
[417896.657823,143783.531596],
[417897.901004,143784.782087],
[417896.434421,143783.405367],
[417896.110127,143783.214232],
[417895.663317,143782.954569],
[417895.432705,143782.821129],
[417895.227317,143782.709315],
[417895.00391,143782.579483],
[417894.611145,143782.355871],
[417897.447001,143784.511627],
[417897.605544,143784.623389],
[417897.227205,143784.389003],
[417896.809233,143784.158177],
[417896.625467,143784.057189],
[417896.373241,143783.912928],
[417896.131821,143783.772279],
[417894.283457,143783.781198],
[417899.91476,143783.091968],
[417899.673353,143782.944129],
[417899.475183,143782.828733],
[417899.338656,143785.615128],
[417898.758239,143782.961243],
[417898.484401,143782.802569],
[417898.142101,143782.607825],
[417897.911499,143782.481593],
[417898.635971,143784.642401],
[417898.437801,143784.541403],
[417900.249551,143781.130199],
[417898.196389,143784.397161],
[417897.944166,143784.249305],
[417901.284153,143785.670988],
[417900.437589,143786.228211],
[417900.696865,143785.339217],
[417900.401417,143785.176929],
[417899.810518,143784.845149],
[417898.329631,143783.922069],
[417900.239421,143786.116417],
[417901.691188,143785.170948],
[417901.269638,143784.907741],
[417900.963383,143784.727443],
[417900.682349,143784.575969],
[417900.426533,143784.420919],
[417899.929313,143784.139629],
[417899.716733,143784.020621],
[417899.446503,143783.876353],
[417899.187081,143783.728495],
[417898.974499,143783.609483],
[417898.707867,143783.458017],
[417902.008177,143784.822029],
[417901.619055,143784.587655],
[417900.992137,143784.230647],
[417900.761545,143784.093623],
[417900.545363,143783.974611],
[417900.958005,143783.955627],
[417899.796246,143789.867581],
[417899.702247,143783.473381],
[417899.48246,143783.354364]
];
var obj = new JL.JL(data);
obj.do();
obj.show();

评论这张

转发至微博

阅读(667)| 评论(1)

历史上的今天

this.p={  m:2,
              b:2,
              loftPermalink:'',
              id:'fks_087064081086089064092081094070072082088066084084080074093',
              blogTitle:'如何找出一堆点中的异常点',
              blogAbstract:'<h2\>1. 需求</h2\>\n<p style=\"text-indent:2em;\"   \>场景其实可以更有意思，不过抽象成模型却是这样的：在一大堆点中，找出异常的点。对应的解决方案如何呢？</p\>\n<h2\>2. 模型</h2\>\n<p style=\"text-indent:2em;\"   \>交给Excel来弄吧，可视化的模型如下：</p\>\n<p style=\"text-indent:2em;\"   \><b\>散点图</b\>，可以看出分布情况，大致可以识别异常的数据：</p\>\n<div align=\"center\"   \> <img title=\"如何找出一堆点中的异常点 - Mr.7 - Mr.7\"   alt=\"如何找出一堆点中的异常点 - Mr.7 - Mr.7\"   style=\"margin:0 10px 0 0;\"   src=\"http://img2.ph.126.net/M2gSAkIsPZrE-zxlyiwKIA==/2285858285967274388.png\"   \></div\>\n<p style=\"text-indent:2em;\"   \><b\>气泡图</b\>，经过聚类，可以把孤独异常的数据挑出来：</p\><div\><div align=\"center\"   \></div\></div\>',
              blogTag:'',
              blogUrl:'blog/static/49102699201383043119176',
              isPublished:1,
              istop:false,
              type:0,
              modifyTime:1382086935832,
              publishTime:1380532227480,
              permalink:'blog/static/49102699201383043119176',
              commentCount:1,
              mainCommentCount:1,
              recommendCount:0,
              bsrk:-100,
              publisherId:0,
              recomBlogHome:false,
              currentRecomBlog:false,
              attachmentsFileIds:[],
              vote:{},
              groupInfo:{},
              friendstatus:'none',
              followstatus:'unFollow',
              pubSucc:'',
              visitorProvince:'',
              visitorCity:'',
              visitorNewUser:false,
              postAddInfo:{},
              mset:'000',
              mcon:'',
              srk:-100,
              remindgoodnightblog:false,
              isBlackVisitor:false,
              isShowYodaoAd:false,
              hostIntro:'    “我来~我见~我征服!” ',
              hmcon:'1',
              selfRecomBlogCount:'0',
              lofter_single:'<iframe width="140" height="560" style="overflow:hidden;" src="http://www.lofter.com/mailEntry.do?blogad=1&blog" frameBorder="0"></iframe>'
            }

{list a as x}
    {if !!x}
    <div class="iblock nbw-fce nbw-f40">
      <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.visitorName}/">
      {if x.visitorName==visitor.userName}
      <img alt="${x.visitorNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.visitorName)}&r=${visitor.imageUpdateTime}"/>
      {else}
      <img alt="${x.visitorNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.visitorName)}"/>
      {/if}
      </a>
      <div class="cwd vname thide">
        {if x.moveFrom=='wap'}
          <a class="noul pnt" target="_blank" href="http://blog.163.com/services/wapblog.html?frompersonalbloghome"><span title="来自网易手机博客" class="iblock wapIcon"> </span></a>
        {elseif x.moveFrom=='iphone'}
          <a class="noul pnt" target="_blank"><span title="来自iPhone客户端" class="iblock iphoneIcon"> </span></a>
        {elseif x.moveFrom=='android'}
          <a class="noul pnt" target="_blank"><span title="来自Android客户端" class="iblock androidIcon"> </span></a>
        {elseif x.moveFrom=='mobile'}
          <a class="noul pnt" target="_blank" href="http://blog.163.com/services/emsblog.html?frompersonalbloghome"><span title="来自网易短信写博" class="iblock wapIcon"> </span></a>
        {/if}
        <a class="fc03 m2a"  target="_blank" hidefocus="true" href="http://blog.163.com/${x.visitorName}/">
          ${fn(x.visitorNickname,8)|escape}
        </a>
      </div>
    </div>
    {/if}
    {/list}

<#--最新日志，群博日志--> <#--推荐日志-->

<p class="fc06">推荐过这篇日志的人：</p>
    <div>
      {list a as x}
      {if !!x}
      <div class="iblock nbw-fce nbw-f40">
        <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.recommenderName}/">
        <img alt="${x.recommenderNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.recommenderName)}"/>
        </a>
        <div class="cwd thide">
          <a class="fc03 m2a" target="_blank" hidefocus="true" href="http://blog.163.com/${x.recommenderName}/">
            ${fn(x.recommenderNickname,6)|escape}
          </a>
        </div>
      </div>
      {/if}
      {/list}
    </div>
    {if !!b&&b.length>0}
    <p  class="fc06">他们还推荐了：</p>
    <ul>
    {list b as y}
      {if !!y}
        <li class="rrb"><span class="iblock">·</span><a class="fc03 m2a" target="_blank" href="http://blog.163.com/${y.recommendBlogPermalink}/?from=blog/static/49102699201383043119176">${y.recommendBlogTitle|escape}</a></li>
      {/if}
    {/list}
    </ul>
    {/if}

<#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇，下一篇--> <#-- 热度 -->

{list a as x}
    {if !!x}
    <div class="hotItem iblock nbw-fce nbw-f40">
      <a class="fc03 noul" target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/">
      {if x.publisherUsername==visitor.userName}
      <img alt="${x.publisherNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.publisherUsername)}&r=${visitor.imageUpdateTime}"/>
      {else}
      <img alt="${x.publisherNickname|escape}" onerror="this.src=location.f40" class="cwd bdwa bdc0" src="${fn1(x.publisherUsername)}"/>
      {/if}
      </a>
      <div class="cwd vname thide">
        <a class="fc03 m2a"  target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/">
          ${fn(x.publisherNickname,8)|escape}
        </a>
      </div>
      <a class="f-myLikeIcons hottype {if x.type==1} js-liketype{elseif x.type==2} js-reblogtype{elseif x.type==3} js-sharetype{else}{/if}" target="_blank" hidefocus="true" href="http://blog.163.com/${x.publisherUsername}/"> </a>
    </div>
    {/if}
    {/list}

<#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->

页脚

我的照片书 - 手机博客 - 下载LOFTER APP - 订阅此博客

Mr.7

导航

日志

如何找出一堆点中的异常点

1. 需求

2. 模型

3. 代码

历史上的今天

最近读者

热度

评论

页脚