楼主: liyihongcug

gis与元胞机

[复制链接]
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-3-26 08:44 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-3-26 11:15 编辑

http://html5.9tech.cn/news/2013/0909/28626.html
http://leibris.blog.163.com/blog/static/45980610201211913135253/

GroundOverlay的好处,是根据所给定的LatLngBounds的大小自动调节图层图片的大小,为了保证匹配地图的需要,不得不定义ne的marker双击可以在不可拉动和可拉动之间切换,sw的在ne可拉动情况下可以移动整个overlay,在不可动的情况下可以调节该lay的bounds形状。

       var _b=new google.maps.LatLngBounds(BLH2LatLng("27:57:30","104:18:45"),

BLH2LatLng("28:0:0","104:22:30"));   
    var dLat=_b.getNorthEast().lat()-_b.getSouthWest().lat();
    var dLng=_b.getNorthEast().lng()-_b.getSouthWest().lng();
    var sw=new google.maps.Marker({position:BLH2LatLng("28:47:0","104:36:0"),map:map,draggable:true});
    var ne=new google.maps.Marker({position:new google.maps.LatLng(sw.getPosition().lat()+dLat,

sw.getPosition().lng()+dLng),map:map,draggable:true});
    _b=new google.maps.LatLngBounds(sw.getPosition(),ne.getPosition());
    var go=new google.maps.GroundOverlay("./1.jpg",_b,{map:map});
    google.maps.event.addListener(sw,'drag',function(evt){
            go.setMap(null);
            if(ne.getDraggable())
                ne.setPosition(new google.maps.LatLng(evt.latLng.lat()+dLat,evt.latLng.lng()+dLng));
            dLat=ne.getPosition().lat()-sw.getPosition().lat();
            dLng=ne.getPosition().lng()-sw.getPosition().lng();
            _b=new  google.maps.LatLngBounds(sw.getPosition(),ne.getPosition());
            go=new google.maps.GroundOverlay("./1.jpg"_b,{map:map});//要是GroundOverlay可以随时更新bounds多好?
        });
    map.setCenter(_b.getCenter());
    google.maps.event.addListener(ne,'dblclick',function(evt){
            if(this.getDraggable())
                this.setDraggable(false);
            else
                this.setDraggable(true);
        });


[backcolor=rgb(248, 248, 248) !important]

<title>Google Maps JavaScript API v3 Example: Ground Overlays</title>

07
<linkhref="http://code.google.com/apis/maps/documentation/javascript/examples/default.css"rel="stylesheet" type="text/css" />

[backcolor=rgb(248, 248, 248) !important]
08
<script type="text/javascript" src="http://maps.google.com/maps/api/js?sensor=false"></script>

09
<script type="text/javascript">

[backcolor=rgb(248, 248, 248) !important]
10
function initialize() {

11


[backcolor=rgb(248, 248, 248) !important]
12
  var newark = new google.maps.LatLng(40.740, -74.18);

13
  var imageBounds = new google.maps.LatLngBounds(

[backcolor=rgb(248, 248, 248) !important]
14
      new google.maps.LatLng(40.712216,-74.22655),

15
      new google.maps.LatLng(40.773941,-74.12544));

[backcolor=rgb(248, 248, 248) !important]
16


17
  var myOptions = {

[backcolor=rgb(248, 248, 248) !important]
18
    zoom: 13,

19
    center: newark,

[backcolor=rgb(248, 248, 248) !important]
20
    mapTypeId: google.maps.MapTypeId.ROADMAP

21
  }

[backcolor=rgb(248, 248, 248) !important]
22


23
  var map = new google.maps.Map(document.getElementById("map_canvas"), myOptions);

[backcolor=rgb(248, 248, 248) !important]
24


25
  var oldmap = new google.maps.GroundOverlay(

[backcolor=rgb(248, 248, 248) !important]
26
      "http://www.lib.utexas.edu/maps/historical/newark_nj_1922.jpg",

27
      imageBounds);

[backcolor=rgb(248, 248, 248) !important]
28
  oldmap.setMap(map);

29
}


http://www.167gps.com/gps_location.asp
http://blog.csdn.net/lijun_xiao2009/article/details/8110267
http://www.oschina.net/code/snippet_12_821

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-3-30 20:42 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-6 15:24 编辑

浅析地下管网虚拟现实系统的构建

为了实现对地下管线的数字化与可视化管理 ,结合虚拟现实技术对地下管网进行研究。系统根据分层概念和管网数据的特点 ,设计城市地下管网的概念模型,着重介绍栅格矢量一体化数据结构的形式,利用空间数据库将地下管网的相关信息存储在计算机上并做相应处理,最终运用 GIS和 LOD模型的建立实现管网系统的可视化和实时漫游 功能。

  城市地下各类管网是一个城市重要的基础设施,担负着信息传输、能源输送等工作,也是城市赖以生存和发展的物质基础。但由于多方面的原因,我国现有地下各类专业管网的资料残缺不全,且有关资料精度不高或与现状不符,在建设施工中时常发生挖断或挖坏地下管网,造成停气、停水、停暖、通信中断、污水 四溢等严重事故。另一方面,我国现有地下专业管网的资料都以图纸、图表等形式记录保存,采用人工方式管理,效率低下。为了解决这个问题 ,必须使用新的技术手段对地下管网进行管理。

  城市地下管网虚拟现实系统属于处理地下管网专题数据的一种信息系统,是以地下管网空间信息和属性信息为核心,利用计算机地理信息系统技术、计算机图形学技术、数据库管理技术和信息可视化技术对城市地下管网进行综合管理,为施工部门和管理部门提供地下管网准确的走向和埋深等有关信息,通过进行各种分析,为领导部门进行管网规划、管网改造等提供辅助决策功能。地下管线虚拟现实系统一是可以实现传统手工处理方式向现代化信息管理转型,以保证数据的实时更新、有效管理,避免重复收集数据信息;二是可为市政建设提供规划、设计、决策服务;三是可为应对突发事件提供支撑。

  1  管网数据模型与数据结构

  空间数据模型是关于现实世界中空间实体及其相互问联系的概念,它为描述空间数据的组织和设计空间数据库模式提供基本方法。管网空间数据模型是空间数据模型的一种,在管网数据的表达和管网空间分析等方面起着极其关键的作用。

  1.1 城市地下管网数据特点
http://resources.arcgis.com/en/home/
  城市地下管网是城市基础设施中的生命线,有地下神经之称,包括给水管网、燃气管网、供热管网、排水管网、电力管网、排污管网和电信管网等。每一类管网都由管线段和附属设施组成,呈树状、环状或辐射状,形成一个系统,系统的各组成元件相互影响,共同发挥作用 。

  首先,地下管 网数据是一种基本网络数据,满足网络的一般特性 ,其基本构成包括弧段和节点。节点包括管网点状实体和三类特征点,即管径变化点、埋深变化点和管网交点,弧段表示相邻节点问的管线段 。其次 ,地下管网数据有区别于一般网络数据的特殊性。地下管网数据包括两种基本类型:树状管网和环状管 网。树状管网大多是重力管网,其弧段都是单向弧段,方向取决于起始节点的高程值,如排水管网就属于这类管网。而燃气、给水等压力管线在设计时为了尽可能减少事故造成的影响,大多采用环状设计,同时大、中城市的燃气、给水等管网都采用多个源头,使得这些管线呈多源环状分布。

  1.2 系统概念模型设计

  概念模型反映了城市地下管网所包含的各部分数据之间的关系。根据分层概念和管网数据的特点,设计了城市地下管网的概念模型,如图1所示。

  

 在该模型中,首先将城市分成多个城区,每个城区的信息又分成基本框架信息和管网信息两部分。管网信息包含给水管网层、燃气管网层、供热管网层、排水管网层、电力管网层、排污管网层和电信管网层等 7个层。每层包含点状实体和特征点、线状实体两类数据。实体和特征点由节点和指明节点特征的标记组成,点由几何坐标定位;线状实体类由弧段和指明弧段特征的标记组成,弧段由一系列坐标点描述。基本框架信息反映了城市基本面貌,由点状、线状和面状三类实体组成。该模型中所有实体都有区别于其他实体的属性特征。

  1.3 地下管网数据存储结构

  在空间数据库中,空间数据的表达方法主要有栅格数据结构、矢量数据结构和栅格矢量一体化结构等。

  1.3.1 栅格数据结构

  栅格模型由规则的正方形或矩形栅格组成,每个栅格代表 1个像元。栅格数据结构实际上就是像元阵列,像元由行列号确定它的位置。点状实体在栅格数据结构中表示为 1个像元;线状实体则由在一定方向上连接成串的相邻像元集合;面状实体表示为聚合在一起的相邻像元集合。栅格数据有数据结构简单、空间数据的叠加和组合方便、各类空间分析易于进行以及模拟方便等优点,但同时存在着图形数据量大、数据精度低、地图输出不精美以及难以建立网络连接关系等缺点。

  1.3.2 矢量数据结构

  矢量数据结构用点串序列来表示空间实体的边界形状和分布。点状实体在矢量数据结构中表示为坐标;线状实体则由线上的一系列点的坐标表示;面状实体由面的边界弧段序列表示。矢量数据的优点是数据精度高、数据量小、完整的描述拓扑关系、图形美观以及图形数据的恢复、更新、综合容易实现等,但也有数据结构复杂、矢量多边形叠置算法和数学模拟困难的缺点。

  1.3.3 栅矢融合与地图配准

  作为管网系统的基础底图,考虑能充分利用矢量图画面精美、无级缩放的优势,同时利用栅格图更新速度快、能反映城市最新风貌的特点。解决方法是:将手头现有的矢量地图作为建立管网专题图层(矢量图)的基础,并设法将栅格图与矢量底图进行配准,从而有效结合两者的优点。

  管网系统的专题数据建立在矢量电子地图基础上,而矢量图的修改相当困难。当城市风貌发生变化时,为反映管网相对于新的参照物的位置,设想利用栅格图与当前管网进行比较;而比较的前提则是首先将栅格图与矢量图进行配准。

  栅格图配准时存在 3个问题:比例尺的配准、投影的配准、坐标的配准。考虑到本系统中匹配要求不太严格,经多次实验发现,如果选择的栅格图所包含的实际区域越小.那么矢量和栅格叠加的越精确。由此得到启发,是否可以将整个栅格图分成小块(不妨将分得的每 1块栅格图称为栅格图块)去配准,配准后将其作为 1个图层保存,当所有的栅格图块都配准后,在显示栅格图时,选择所有的栅格图块,那么就得到了一幅完整的、能够和矢量图准确匹配的栅格图。具体步骤如下:

  1)在制图软件 中将栅格图平均分割成 M 块(实际上 M 的大小代表 了配准的精度,M 越大,则精度越高),并分别保存 ;

  2)对每一栅格图块在 MapX环境中进行匹配控制点至少选择 2O个;

  3)在 MapX环境中显示所有的栅格图块,看整幅图与矢量图叠加的效果 。

  在分割的栅格 图全部显示时,两两相邻的栅格图块有可能会出现拼接不上的问题,比如 1条河流在拼接后不能衔接上、建筑物在拼接后出现错位现象、延续的道路有可能变为两条道路。可以采取以下两种方法解决栅格图块的拼接问题:

 1)增加栅格图块的个数。通过多次实践发现,如果栅格图分割的栅格图块越少,则上述问题会越严重,如果分割的栅格图块越多,拼接不上的程度会有所减少 ;如果对栅格的精度要求不太严格的话,可以忽略不计 。其次 ,如果道路或建筑物改变不多或知道其大体的区域,则可利用其它画图工具,直接分出包含这个 区域的最小的栅格图块,只要配准所有分割的栅格 图块即可。这时精度的问题已经转化为配准的问题 。

  2)选择特殊控制点。选择栅格图块的 4个顶点作为其 中一部分控制点及其图块中心的点,则两两相邻的栅格图块之间至少有 2个相同的控制点。在显示栅格 图块时,就会产生一幅完整的栅格图。本课题将 以上两种方法结合使用,以获得更好的效果。

  2 地下管网的可视化

  管网的可视化就是将存入计算机中的数据通过某种方式变成能看到的图片或者是界面。而空间数据坐标系定义 是可视化地理信息系统(GIS)的基础 ,正确定义 GIS系统的坐标系非常重要。

  2.1 地图坐标系及投影

  GIS中的坐标系定义 由基准面和地 图投影两组参数确定,而基准面的定义则由特定椭球体及其对应的转换参数确定,因此,欲正确定义 GIS系统坐标系,首先必须弄清地球椭球体(Ellipsoid)、大地基准面(Datum)及地 图投影(Projection)三者的基本概念及它们之间的关系。

  基准面是利用特定椭球体对特定地区地球表面的逼近,因此,每个国家或地区均有各自的基准面,通常称谓的北京 54坐标系、西安 80坐标系实际上指的是我国的两个大地基准面。WGS 1984基准面采用 WGS84椭球体,它是地心坐标系,即以地心作为椭球体中心,目前 GPS测量数据多以 WGS 1984基准。

  椭球体与基准面之间的关系是一对多的关系,也就是基准面是在椭球体基础上建立的,但椭球体不能代表基准面,但能定义不同的基准面。 地图投影是将地图从球面转换到平面的数学变换,例如某点北京 54坐标值为 x一4 231 898,y一21 655 933,实际上指的是北京 54基准面下的投影坐标,也就是北京 54基准面下的经纬度坐标在直角平面坐标上的投影结果。

  根据空间解析几何,参考坐标系点(x,y,z )向世界坐标系坐标(X,y,Z)的转换方程为

  

  式中:a、 、y为两坐标系相应坐标轴的夹角;(x。Y。z)为参考坐标系原点在世界坐标系中的坐标。

  2.2 三维数据的显示及 L0D模型

  三维显示通常采用截面图、等距平面、多层平面和立体块状图等多种表现形式,大多数三维显示技术局限于 CRT屏幕和绘图纸的二维表现形式,人们可以观察到地理现象的三维形状,但不能将它们作为离散的实体进行分析,如立体不能被测量、拉伸、改变形状或组合。为了提高场景的显示速度,实现实时交互,在实际的三维显示中常常采用降低场景复杂度的方法,从计算机硬件绘制的角度考虑,即减少每帧数中绘制的图元对象的数目。其中细节层次模型(L0D)的方法具有普遍性和高效性,在飞行模拟和地形仿真应用中得到了广泛的应用。所谓的L0D模型是指根据不同的显示对同一对象采用不同精度的几何描述,物体的细节程度越高,则数据量越大,描述越精细 ;细节程度越低 ,则数据量越小,描述越粗糙。因此,可以根据不同的显示需求,对需要绘制的对象采用不同的描述精度,从而大大地降低需要绘制的数据量,使实时三维显示成为可能。

  在场景的实时动态显示中,当视点距离某一物体很近时,它的图像将在屏幕上占据较多的像素,而当视点距离它很远时,图像只能在屏幕上占据很少的像素。在这种情况下,可以用多种不同的精度表示,并根据视点位置的变化或者物体图像在屏幕上所占据的像素数多少而选择不同精度的模型予以成像,这是非常有效的手段。这种方法通常称为层次细节 (1evel of details,LOD)显示和简化技术。

  LOD模型是对原始几何模型按照一定的算法进行简化后模型的一种总称。简化后的模型在几何数量上比原始的几何模型的数据量减少了很多,降低了对计算机软件和硬件设备的需求,从而提高了数据操纵 的速度,缩短了人机交互操作的时间,因此,在图像的渲染速度上会有很大的提高。LOD模型的种类在几何结构上大致分为以下 3种类型:不连续的 LOD模型;连续的 LOD模型;几何结构自身的 I OD模型,如图2所示。

  

 2.3 漫游过程中的实时处理

  在三维地下管网系统研究方面,使用地形 LOD模型和 R—Tree空间索引技术对大量的三维数据进行实时漫游研究,取得一定进展。但是在数据的状态交换、高速的内存交换机制、空问索引技术方面还有待进一步研究和提高。由于地下管网数据量比较大 ,很难实现实时漫游,因此,实时绘制出相应的结果成为一个主要瓶颈。针对地下管网地理信息系统在漫游过程中实现绘制的这一特殊性,实时加速方法主要通过使用改进的平行投影技术、空间跳跃重采样、相邻帧间的连贯性关系三种方法来实现。 通过一组平行投射线而得到的形体投影称平行投影 。平行投影又可根据投射线与投影面垂直与否分为平行正投影和平行斜投影。

  使用光线投射技术,在沿视点投射出的光线上进行重采样时,有许多空体素,使用改进的空问跳跃(Space--Leaping)技术可以跳过这些空体素,以加快绘制速度 。

  在漫游过程中,由于相邻的两个视点位置和视线方向变化较小,相邻帧的场景大部分是相同的,只有少部分不同,因此,可以利用相邻帧的这种连贯性关系实现实时处理。

  基于相邻帧的连贯性,提出了一种两步实时处理技术 ;将当前帧的处理分成两步:近景和远景的处理。近景的处理利用改进的两阶段光线投射技术,远景的处理利用改进的加速对象投影处理远视点区域,并考虑了相邻帧的连贯性,相邻帧场景变化在一定范围内近视点场景重新计算,其余部分利用上一帧的结果进行处理,然后再重新合成。

  使用 OpenGI 的双缓存技术可以实现部分漫游功能。该技术使用两个前后台和两个缓存绘制画面。在显示前台缓存内容中的一帧画面时,后台缓存正在绘制下一帧画面;当后台缓存绘制完毕,后台缓存内容便显示在屏幕上,而前台此时又在绘制下一帧画面内容,如此循环反复,屏幕上总是显示己经画好的图形,看起来所有的画面都是连续的。

  3  结束语

  三维可视化技术使传统二维的、静态的地图向三维的、动态的场景表示方向发展,在空间关系型数据库的支持下利用可虚拟现实技术不仅可以对空间对象进行全方位的交互,而且可以对其中的空间对象进行数据挖掘,探索其中隐含的逻辑规律,对未来状况进行预测,并制订出合理、可行的解决方案等。

  通过对地下管网一系列问题的研究,主要解决以下几个问题 :

  1)针对管线的布置特点和数据特点,设计合理的数据模型和数据结构,建立管线空间数据库,充分表现管线间的空间拓扑关系。

  2)在对管线数据进行入库后,对管线数据进行三维显示的可视化研究。

  3)使用 OpenGL的双缓存技术实现地下管线漫游查询功能。 http://www.elecfans.com/article/ ... 20100206163118.html https://developers.google.com/earth/forum/browser-pluginhttp://earth-api-samples.googlecode.com/svn/trunk/examples/http://www.hcharts.cn/demo/index.php?p=10&theme=grid
http://cache1.arcgisonline.cn/ArcGIS/rest/services/ChinaOnlineStreetCold/MapServer/0
http://my.oschina.net/chenhao901007/blog/212772

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-3 16:13 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-6 16:31 编辑

http://wenku.baidu.com/link?url= ... VReEm19LKfkoIw_MI77http://www.oschina.net/project/tag/401/Neural-Network
http://wenku.baidu.com/link?url=Yay39afs5IS53KtMfj1-TnIXWwYX7ZCnkeuUnr2wNiiJGLJ_6-3KNY2RlBiValjhAI4Sr79oU3V5sAsYxHxhEnc8hxDZoLhg1gJkZG5qmvK
http://wenku.baidu.com/view/7b55250979563c1ec5da71f7.html

墨卡托投影(Mercator)将地球投影到一个圆柱上,地球切着圆柱的切线圆就是赤道线。这种投影的结果就是越接近赤道的地方,变形就越小,离赤道越远,变形就越大。这个投影有很大局限性,因为大部分的人口和地区都不是分布在赤道周围,而是南北向的分布,如南美洲和北美洲。

UTM(Universal Transverse Mercator)投影,又叫横轴墨卡托投影,就是把墨卡托投影的那个圆柱作个旋转,使圆柱切着地球的子午线(经度线)。结果还是接近那个切线圆的地方才会相对的没有变形。解决这个问题,可以轻轻转动这个圆柱,使它切着不同的子午线,这样每隔6度转一次,就产生了60个不同的带(UTM zone)。由于每个度用不同的子午线来投影,所以参数完全不一样,因此不能将属于不同带的影像拼接起来。但是如果你把处于不同带的地区用一个投影带的参数进行投影的话,不属于这个投影带的地区就会有变形。

地图投影按变形性质分为三类:等角投影(角度变形为零),等积投影(面积变形为零)和任意投影。一般等角就不等积,等积就不是等角,任意投影既不等角也不等积。墨卡托投影属于等角投影,比较适用于航海图,洋流图和风向图。UTM投影只用于比较小的地区,方向无变形,面积变形也比较小,可以忽略不计。

大概就是这些了,还是把原文链接进来,里面的内容更充实些。

UTM投影将全球划分为60个投影带,每6度为一个带。经度自180°W为起始带连续向东,计算按照上述方法,东经118.243°属于第几带   (180+118.2)/6,求出结果后采用进一法即只要有余数则数量加一,可得结果50

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-11 18:14 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-15 15:46 编辑

递归与回溯
[算法分析]
    为了描述问题的某一状态,必须用到它的上一状态,而描述上一状态,又必须用到它的上一状态……这
种用自已来定义自己的方法,称为递归定义。例如:定义函数f(n)为:
        /n*f(n-1) (n>0)
f(n)= |
        \ 1(n=0)
    则当0时,须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时,f(n)=1。
    由上例我们可看出,递归定义有两个要素:
    (1)递归边界条件。也就是所描述问题的最简单情况,它本身不再使用递归的定义。
         如上例,当n=0时,f(n)=1,不使用f(n-1)来定义。
    (2)递归定义:使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。
         如上例:f(n)由f(n-1)定义,越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。

    递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构
复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步
没其结果仍维持原问题的关系, 则采用递归算法编程比较合适.

    递归按其调用方式分为: 1. 直接递归, 递归过程p直接自己调用自己; 2. 间接递归, 即p包含另一过程
d, 而d又调用p.

    递归算法适用的一般场合为:
    1. 数据的定义形式按递归定义.
       如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
       对应的递归程序为:
         function fib(n : integer) : integer;
         begin
            if n = 0 then fib := 1     { 递归边界 }
                     else if n = 1 then fib := 2
                                   else fib := fib(n-2) + fib(n-1)   { 递归 }
         end;
       这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.
    2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.
    3. 问题解法按递归算法实现. 例如回溯法等.

    从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "
的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作
" 回溯法 ".归算法

程序调用自身的编程技巧称为递归(recursion)。
回溯算法的一些知识   

1.  回溯算法的主要特征是什么?

答:把回溯算法看成一个不断地进行各种尝试直至问题解决的过程,这个过程似乎具有迭代性。

2.  用自己的语言来描述,如何用右手规则穿越迷宫。用左手法则是否也能达到同样的效果?

答:可以。

3.  用递归回溯法则解决迷宫问题的核心是什么?

答:出口就在其中的一条线上。如果选对了方向,那么将向解决方案更靠近一步。因此,沿着那条路走,问题就变得简单起来,这就是递归式解法的关键。

4.  在SolveMaze的递归实现中,有哪些简单情景?

答:这个参数是起始位置,它返回一些指示值,说明是否成功。到找到返回TURE,否则返回FALSE。

5.  为什么说穿越迷宫时做标记是重要的?如果未作标记,那么SolveMaze函数将会发生什么情况?

答:因为做标记是递归实现的核心,如果没有标记,那么它只能在一个地方向四周判断,然后不会进入下一步。

6.  在SolveMaze的实现中,为什么要在for循环后调用UnmarkSquare函数?这对于该算法是否必要?

答:必须有的。它让递归进入下一步。

7.  SolveMaze函数所返回的布尔结果有何作用?

答:找到返回TURE,否则返回FALSE。这样就判断出循环跳出的条件。

8.  用自己的语言,解释回溯过程在SolveMaze的递归实现中是如何发挥作用的。

答:它可以在错误的时候返回到没有错误的地方,这样一步一步的简化了问题,直至走出迷宫。

9.  在简单的拿子游戏中,开始时的硬币是13个,人类玩家先走第一步,有利还是不利?为什么?

答:有利,因为这样就可以对这个条件判断。然后找到最佳方法。先找到最佳方法,对以后的步骤更有利。

10.              编写一个简单的C语言程序,局势对当前玩家有利时nCoins的值shi TURE,反之为FALSE(提示:使用%运算符)。

11.              什么是最大最小算法?它的名字有什么意义?

答:在任何局势下,最佳走法,简单说,就是让你的对手处在最坏的局势中,最坏的局势就是使得对手只能走出最弱的好棋。这种思想——寻找使对手只能走出最差的局势——被称为“最小最大策略”。他的目标就是将对手的最大机会最小化。

12.              分析一个游戏时,ply这个词是什么意思?

答:单个游戏者的单步动作。

13.              假设您处在下图所示的局势中,分析下两步棋以显示出从您的角度的平分结果:

答:第3种+4+3-2+5的得分是10。

14.              为什么最小最大算法的抽象开发是很有意义的?

答:最小最大算法是一个非常通用的法则,它可以用在各种游戏中而不一览于游戏的形式。

15.              使用哪两种数据结构使得最小最大算法的实现独立于某一特殊游戏的特性?

答:它要有2个互相递归的函数,所以要求:1必须可以限制递归搜索的深度。2。必须可以为为每步棋和每个局势评定一个分数。

16.              FindBestMove函数中有3个参数,每个参数的作用是什么?



答:stateT state, int depth, int *pRating.

17.              解释EvaluateStaticPosition函数在最小最大算法的实现过程中的作用。

答:这个函数在游戏结束或已经达到最大递归深度时,简单情景就会出现,这些简单情景允许递归终止。这个函数就是用来执行评估的。









回溯算法  

对于给定的问题,如果有简明的数学模型揭示问题的本质,我们尽量用解析法求解;如果无法建立数学模型,或者即使有一定的数学模型,但采用数学方法解决有一定的困难,我们只好用模拟或搜索来求解.搜索的本质是枚举,回溯是最常用的搜索方法之一,它采用深度优先的策略来枚举所有可能的解,结合题设条件的限定,从而得到问题的解.其递归形式的框架如分析:

该题无法建立合适的数学模型,简单的贪心法很容易找出反例;该题目不同于相邻堆的石子进行合并的石子归并问题,石子的合并顺序对于最终结果没有影响,无法归纳相邻阶段之间的转化关系,动态规划方法也难以解决,故考虑采用回溯法求解,确定一堆石子的归属为一个阶段,全部石子的归属确定后即可获得一个两堆质量之差的绝对值,搜索全部可能的归属可能并比较记录最小的绝对值,即是问题的解。

剪枝:

如前所述,回溯的本质是枚举,就该题目而言,理论上所有可能的分组方法是2N种(即每堆石子都有在第一堆或第二堆两种可能)。对于N最大可取到20来说,2N个方案组合的判定时间复杂度难以接受。考虑到分成两个堆,知道一个堆中的石子构成即可推算出另一个堆中的石子构成情况,也就是说在 2N 种方案组合中每种方案都有与之等价的方案。因此,可以假定给定的某堆石子(考虑编程实现方便,一般选择第一堆)分在第一堆,由此可将原来的2N种方案组合减少为  2N-1  种;如果第一堆中石子质量之和已超过总质量的一半,继续向该堆中加入石子,两堆质量差的绝对值必然增大,没有继续搜索的必要,因此剪枝。http://www.cnblogs.com/hahawgp/archive/2013/02/19/2917723.html
递归--recurse
回溯 ---backtrack  到处翻译错误

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历。

前序遍历:根节点->左子树->右子树

中序遍历:左子树->根节点->右子树

后序遍历:左子树->右子树->根节点

http://blog.csdn.net/fansongy/article/details/6798278
http://google-maps-utility-library-v3.googlecode.com/svn/trunk/markerclusterer/examples/speed_test.js   聚类分析
lass MarkerClusterer
This class extends google.maps.OverlayView.
Constructor
ConstructorDescription
MarkerClusterer(map:google.maps.Map, opt_markers:Array.<google.maps.Marker>, opt_options:Object)A Marker Clusterer that clusters markers.
Methods
MethodsReturn ValueDescription
addMarker(marker:google.maps.Marker, opt_nodraw:boolean)NoneAdds a marker to the clusterer and redraws if needed.
addMarkers(markers:Array.<google.maps.Marker>, opt_nodraw:boolean)NoneAdd an array of markers to the clusterer.
clearMarkers()NoneClears all clusters and markers from the clusterer.
getCalculator()function(Array|number)Get the calculator function.
getExtendedBounds(bounds:google.maps.LatLngBounds)google.maps.LatLngBoundsExtends a bounds object by the grid size.
getGridSize()numberReturns the size of the grid.
getMap()google.maps.MapReturns the google map that the clusterer is associated with.
getMarkers()Array.Returns the array of markers in the clusterer.
getMaxZoom()numberGets the max zoom for the clusterer.
getStyles()ObjectGets the styles.
getTotalClusters()numberReturns the number of clusters in the clusterer.
getTotalMarkers()Array.Returns the array of markers in the clusterer.
isZoomOnClick()booleanWhether zoom on click is set.
redraw()NoneRedraws the clusters.
removeMarker(marker:google.maps.Marker)booleanRemove a marker from the cluster.
resetViewport()NoneClears all existing clusters and recreates them.
setCalculator(calculator:function(Array|number))NoneSet the calculator function.
setGridSize(size:number)NoneReturns the size of the grid.
setMap(map:google.maps.Map)NoneSets the google map that the clusterer is associated with.
setMaxZoom(maxZoom:number)NoneSets the max zoom for the clusterer.
setStyles(styles:Object)NoneSets the styles.

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-15 17:28 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-21 20:37 编辑

http://www.cnblogs.com/step1/archive/2005/11/24/433119.html大地坐标系是一种固定在地球上,随地球一起转动的非惯性坐标系。大地坐标系根据其原点的位置不同,分为地心坐标系和参心坐标系。地心坐标系的原点与地球质 心重合,参心坐标系的原点与某一地区或国家所采用的参考椭球中心重合,通常与地球质心不重合。我国先后建立的1954年北京坐标系、1980西安坐标系和 新1954年北京坐标系,都是参心坐标系。这些坐标系为我国经济社会发展和国防建设作出了重要贡献。但是,随着现代科技的发展,特别是全球卫星定位技术的 发展和应用,世界上许多发达国家和中等发达国家都已在多年前就开始使用地心坐标系。545路、10路、518路、24路、703路公交http://max.book118.com/html/2014/0316/6646665.shtm
http://bbs.chinacloud.cn/showforum.aspx?forumid=27
http://www.docin.com/p-473038039.html
http://www.doc88.com/p-066195922908.html

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-22 15:11 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-22 16:23 编辑

 空间数据挖掘技术理论及方法 空间数据挖掘技术理论及方法葛继科
  (西南农业大学信息学院400716)
  摘要 本文简要论述了空间数据库技术及空间数据挖掘技术的理论及特点,分析了空间数据挖掘技术的层次、方法,并重点介绍了当前常用的分类、聚类、关联规则等空间数据挖掘方法,指出了当前空间数据挖掘技术中尚需解决的问题、发展趋势及方向。
  关键词空间数据挖掘分类聚类关联规则
  0 引言
  地理信息系统(Geographic Information System,简称GIS)是计算机科学、地理学、测量学、地图学等多门学科综合的技术[1]。GIS的基本技术是空间数据库、地图可视化及空间分析,而空间数据库是GIS的关键。空间数据挖掘技术作为当前数据库技术最活跃的分支与知识获取手段,在GIS中的应用推动着GIS朝智能化和集成化的方向发展。
  1 空间数据库与空间数据挖掘技术的特点
  随着数据库技术的不断发展和数据库管理系统的广泛应用,数据库中存储的数据量也在急剧增大,在这些海量数据的背后隐藏了很多具有决策意义的信息。但是,现今数据库的大多数应用仍然停留在查询、检索阶段,数据库中隐藏的丰富的知识远远没有得到充分的发掘和利用,数据库中数据的急剧增长和人们对数据库处理和理解的困难形成了强烈的反差,导致“人们被数据淹没,但却饥饿于知识”的现象。
  空间数据库(数据仓库)中的空间数据除了其显式信息外,还具有丰富的隐含信息,如数字高程模型〔DEM或TIN〕,除了载荷高程信息外,还隐含了地质岩性与构造方面的信息;植物的种类是显式信息,但其中还隐含了气候的水平地带性和垂直地带性的信息,等等。这些隐含的信息只有通过数据挖掘才能显示出来。空间数据挖掘(Spatial Data Mining,简称SDM),或者称为从空间数据库中发现知识,是为了解决空间数据海量特性而扩展的一个新的数据挖掘的研究分支,是指从空间数据库中提取隐含的、用户感兴趣的空间或非空间的模式和普遍特征的过程[2]。由于SDM的对象主要是空间数据库,而空间数据库中不仅存储了空间事物或对象的几何数据、属性数据,而且存储了空间事物或对象之间的图形空间关系,因此其处理方法有别于一般的数据挖掘方法。SDM与传统的地学数据分析方法的本质区别在于SDM是在没有明确假设的前提下去挖掘信息、发现知识,挖掘出的知识应具有事先未知、有效和可实用3个特征。
  空间数据挖掘技术需要综合数据挖掘技术与空间数据库技术,它可用于对空间数据的理解,对空间关系和空间与非空间关系的发现、空间知识库的构造以及空间数据库的重组和查询的优化等。
  2 空间数据挖掘技术的主要方法及特点
  常用的空间数据挖掘技术包括:序列分析、分类分析、预测、聚类分析、关联规则分析、时间序列分析、粗集方法及云理论等。本文从挖掘任务和挖掘方法的角度,着重介绍了分类分析、聚类分析和关联规则分析三种常用的重要的方法。
  2.1、分类分析
  分类在数据挖掘中是一项非常重要的任务,目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个。分类和我们熟知的回归方法都可用于预测,两者的目的都是从历史数据纪录中自动推导出对给定数据的推广描述,从而能对未来数据进行预测。和回归方法不同的是,分类的输出是离散的类别值,而回归的输出则是连续的数值。二者常表现为一棵决策树,根据数据值从树根开始搜索,沿着数据满足的分支往上走,走到树叶就能确定类别。空间分类的规则实质是对给定数据对象集的抽象和概括,可用宏元组表示。
  要构造分类器,需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成,每个元组是一个由特征(又称属性)值组成的特征向量,此外,训练样本还有一个类别标记。一个具体样本的形式可为 v1, v2, ..., vn; c );其中vi表示字段值,c表示类别。
  分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方法包括贝叶斯法和非参数法(近邻学习或基于事例的学习),对应的知识表示是判别函数和原型事例。机器学习方法包括决策树法和规则归纳法,前者对应的表示为决策树或判别树,后者则一般为产生式规则。神经网络方法主要是反向传播(Back-Propagation,简称BP)算法,它的模型表示是前向反馈神经网络模型(由代表神经元的节点和代表联接权值的边组成的一种体系结构),BP算法本质上是一种非线性判别函数[3]。另外,最近又兴起了一种新的方法:粗糙集(rough set),其知识表示是产生式规则。
  不同的分类器有不同的特点。有三种分类器评价或比较尺度:1) 预测准确度;2) 计算复杂度;3) 模型描述的简洁度。预测准确度是用得最多的一种比较尺度,特别是对于预测型分类任务,目前公认的方法是10番分层交叉验证法。计算复杂度依赖于具体的实现细节和硬件环境,在数据挖掘中,由于操作对象是海量的数据库,因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述型的分类任务,模型描述越简洁越受欢迎。例如,采用规则归纳法表示的分类器构造法就很有用,而神经网络方法产生的结果就难以理解。
  另外要注意的是,分类的效果一般和数据的特点有关。有的数据噪声大,有的有缺值, 有的分布稀疏,有的字段或属性间相关性强,有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。
  分类技术在实际应用非常重要,比如:可以根据房屋的地理位置决定房屋的档次等。
  2. 2 聚类分析
  聚类是指根据“物以类聚”的原理,将本身没有类别的样本聚集成不同的组,并且对每一个这样的组进行描述的过程。它的目的是使得属于同一个组的样本之间应该彼此相似,而不同组的样本应足够不相似。与分类分析不同,进行聚类前并不知道将要划分成几个组和什么样的组,也不知道根据哪些空间区分规则来定义组。其目的旨在发现空间实体的属性间的函数关系,挖掘的知识用以属性名为变量的数学方程来表示。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。基于聚类分析方法的空间数据挖掘算法包括均值近似算法[4]、CLARANS、BIRCH、DBSCAN等算法。目前,对空间数据聚类分析方法的研究是一个热点。
  对于空间数据,利用聚类分析方法,可以根据地理位置以及障碍物的存在情况自动地进行区域划分。例如,根据分布在不同地理位置的ATM机的情况将居民进行区域划分,根据这一信息,可以有效地进行ATM机的设置规划,避免浪费,同时也避免失掉每一个商机。
  2.3 关联规则分析
  关联规则分析主要用于发现不同事件之间的关联性,即一事物发生时,另一事物也经常发生。关联分析的重点在于快速发现那些有实用价值的关联发生的事件。其主要依据是:事件发生的概率和条件概率应该符合一定的统计意义。空间关联规则的形式是X->Y[S%,C%],其中X、Y是空间或非空间谓词的集合,S%表示规则的支持度,C%表示规则的置信度。空间谓词的形式有3种:表示拓扑结构的谓词、表示空间方向的谓词和表示距离的谓词[5]。各种各样的空间谓词可以构成空间关联规则。如,距离信息(如Close_to(临近)、Far_away(远离))、拓扑关系(Intersect(交)、Overlap(重叠)、Disjoin(分离))和空间方位(如Right_of(右边)、West_of(西边))。实际上大多数算法都是利用空间数据的关联特性改进其分类算法,使得它适合于挖掘空间数据中的相关性,从而可以根据一个空间实体而确定另一个空间实体的地理位置,有利于进行空间位置查询和重建空间实体等。大致算法可描述如下:(1)根据查询要求查找相关的空间数据;(2)利用临近等原则描述空间属性和特定属性;(3)根据最小支持度原则过滤不重要的数据;(4)运用其它手段对数据进一步提纯(如OVERLAY);(5)生成关联规则。
  关联规则通常可分为两种:布尔型的关联规则和多值关联规则。多值关联规则比较复杂,一种自然的想法是将它转换为布尔型关联规则,由于空间关联规则的挖掘需要在大量的空间对象中计算多种空间关系,因此其代价是很高的。—种逐步求精的挖掘优化方法可用于空间关联的分析,该方法首先用一种快速的算法粗略地对一个较大的数据集进行一次挖掘,然后在裁减过的数据集上用代价较高的算法进一步改进挖掘的质量。因为其代价非常高,所以空间的关联方法需要进一步的优化。
  对于空间数据,利用关联规则分析,可以发现地理位置的关联性。例如,85%的靠近高速公路的大城镇与水相邻,或者发现通常与高尔夫球场相邻的对象是停车场等。
  3 空间数据挖掘技术的研究方向
  3.1 处理不同类型的数据
  绝大多数数据库是关系型的,因此在关系数据库上有效地执行数据挖掘是至关重要的。但是在不同应用领域中存在各种数据和数据库,而且经常包含复杂的数据类型,例如结构数据、复杂对象、事务数据、历史数据等。由于数据类型的多样性和不同的数据挖掘目标,一个数据挖掘系统不可能处理各种数据。因此针对特定的数据类型,需要建立特定的数据挖掘系统。
  3.2 数据挖掘算法的有效性和可测性
  海量数据库通常有上百个属性和表及数百万个元组。GB数量级数据库已不鲜见,TB数量级数据库已经出现,高维大型数据库不仅增大了搜索空间,也增加了发现错误模式的可能性。因此必须利用领域知识降低维数,除去无关数据,从而提高算法效率。从一个大型空间数据库中抽取知识的算法必须高效、可测量,即数据挖掘算法的运行时间必须可预测,且可接受,指数和多项式复杂性的算法不具有实用价值。但当算法用有限数据为特定模型寻找适当参数时,有时也会导致物超所值,降低效率。
  3.3 交互性用户界面
  数据挖掘的结果应准确地描述数据挖掘的要求,并易于表达。从不同的角度考察发现的知识,并以不同形式表示,用高层次语言和图形界面表示数据挖掘要求和结果。目前许多知识发现系统和工具缺乏与用户的交互,难以有效利用领域知识。对此可以利用贝叶斯方法和演译数据库本身的演译能力发现知识。
  3.4 在多抽象层上交互式挖掘知识
  很难预测从数据库中会挖掘出什么样的知识,因此一个高层次的数据挖掘查询应作为进一步探询的线索。交互式挖掘使用户能交互地定义一个数据挖掘要求,深化数据挖掘过程,从不同角度灵活看待多抽象层上的数据挖掘结果。
  3.5 从不同数据源挖掘信息
  局域网、广域网以及Internet网将多个数据源联成一个大型分布、异构的数据库,从包含不同语义的格式化和非格式化数据中挖掘知识是对数据挖掘的一个挑战。数据挖掘可揭示大型异构数据库中存在的普通查询不能发现的知识。数据库的巨大规模、广泛分布及数据挖掘方法的计算复杂性,要求建立并行分布的数据挖掘。
  3.6 私有性和安全性
  数据挖掘能从不同角度、不同抽象层上看待数据,这将影响到数据挖掘的私有性和安全性。通过研究数据挖掘导致的数据非法侵入,可改进数据库安全方法,以避免信息泄漏。
  3.7 和其它系统的集成
  方法、功能单一的发现系统的适用范围必然受到一定的限制。要想在更广泛的领域发现知识,空间数据挖掘系统就应该是数据库、知识库、专家系统、决策支持系统、可视化工具、网络等技术的集成。
  4 有待研究的问题
  我们虽然在空间数据挖掘技术的研究和应用中取得了很大的成绩,但在一些理论及应用方面仍存在急需解决的问题。
  4.1 数据访问的效率和可伸缩性
  空间数据的复杂性和数据的大量性,TB数量级的数据库的出现,必然增大发现算法的搜索空间,增加了搜索的盲目性。如何有效的去除与任务无关的数据,降低问题的维数,设计出更加高效的挖掘算法对空间数据挖掘提出了巨大的挑战。
  4.2 对当前一些GIS软件缺乏时间属性和静态存储的改进
  由于数据挖掘的应用在很大的程度上涉及到时序关系,因此静态的数据存储严重妨碍了数据挖掘的应用。基于图层的计算模式、不同尺度空间数据之间的完全割裂也对空间数据挖掘设置了重重障碍。空间实体与属性数据之间的联系仅仅依赖于标识码,这种一维的连接方式无疑将丢失大量的连接信息,不能有效的表示多维和隐含的内在连接关系,这些都增加了数据挖掘计算的复杂度,极大地增加了数据准备阶段的工作量和人工干预的程度。
  4.3 发现模式的精炼
  当发现空间很大时会获得大量的结果,尽管有些是无关或没有意义的模式,这时可利用领域的知识进一步精炼发现的模式,从而得到有意义的知识。
  在空间数据挖掘技术方面,重要的研究和应用的方向还包括:网络环境上的数据挖掘、栅格矢量一体化的挖掘、不确定性情况下的数据挖掘、分布式环境下的数据挖掘、数据挖掘查询语言和新的高效的挖掘算法等。
  5 小结
  随着GIS与数据挖掘及相关领域科学研究的不断发展,空间数据挖掘技术在广度和深度上的不断深入,在不久的将来,一个集成了挖掘技术的GIS、GPS、RS集成系统必将朝着智能化、网络化、全球化与大众化的方向发展。
  参考文献:
  [1] 邬伦等地理信息系统――原理、方法和应用 .科学出版社.2001.
  [2] 邸凯昌.空间数据挖掘和知识发现的理论与方法[D].武汉:武汉测绘科技大学,1999.
  [3] 蔡自兴,徐光祐. 人工智能及其应用. 清华大学出版社. 1999. 206~216.
  [4] Sheikholeslami G, Chatterjee S, Zhang A. Wave-Cluster: A multi-resolution clustering approach for very large spatiall databases. In:Proceedings of the 24th International Conference on Very Large Databases. New York, 1998. 428~439.
  [5] 朱建秋,张晓辉,菇伟杰,朱杨勇.数据挖掘语言浅析[Z].
  http://www.sqlmine.com/warehouse/htm/40.htm.
  The Technology and Methods of Spatial Data Mining
  Ge Ji-Ke
  (Information College South West Agricultural University Chongqing 400716)
  Abstract: This paper introduces the theory and characteristic ofspatial database and spatial data mining, analyses the hierarchy method and knowledge’s classification of spatial data mining, introduces spatial classification rules , spatial clustering rules and spatial association rules, points out unsolved question, trend and direction.
  Key words: spatial data mining, classification, clustering, association rules(王朝网络 wangchao.net.cn)http://wenku.baidu.com/link?url=y42gcV6015S07PAopNVTUViXO9tSfBc_Xaa6XAyNSUwL9IH7ywn6Bg6Ocz_h6DZN6Wc4MxQCG_KEte8dympPkleihHu9vSUVslWagKXzSra ----idd3算法

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-22 16:24 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-24 09:33 编辑

1.1
    id3是一种基于决策树的分类算法,由J.Ross Quinlan
在1986年开发。id3根据信息增益,运用自顶向下的贪心策略
建立决策树。信息增益用于度量某个属性对样本集合分类的好坏程度。
由于采用了信息增益,id3算法建立的决策树规模比较小,
查询速度快。id3算法的改进是C4.5算法,C4.5算法可以
处理连续数据,采用信息增益率,而不是信息增益。
理解信息增益,需要先看一下信息熵。

1.2 信息熵
    信息熵是随机变量的期望。度量信息的不确定程度。
信息的熵越大,信息就越不容易搞清楚。处理信息就是
为了把信息搞清楚,就是熵减少的过程。
    Entropy(X) = -Sum(p(xi) * log(p(xi))) {i: 0 <= i <= n}
    p(x)是概率密度函数;对数是以2为底;

1.3 信息增益
    用于度量属性A降低样本集合X熵的贡献大小。信息增益
越大,越适于对X分类。
    Gain(A, X) = Entropy(X) - Sum(|Xv| / |X| * Entropy(Xv))  {v: A的所有可能值}
    Xv表示A中所有为v的值;|Xv|表示A中所有为v的值的数量;

2 id3算法流程
    输入:样本集合S,属性集合A
    输出:id3决策树。
    1) 若所有种类的属性都处理完毕,返回;否则执行2)
    2)计算出信息增益最大属性a,把该属性作为一个节点。
        如果仅凭属性a就可以对样本分类,则返回;否则执行3)
    3)对属性a的每个可能的取值v,执行一下操作:
        i.  将所有属性a的值是v的样本作为S的一个子集Sv;
        ii. 生成属性集合AT=A-{a};
        iii.以样本集合Sv和属性集合AT为输入,递归执行id3算法;

3 一个的例子
    3.1
    这个例子来源于Quinlan的论文。
    假设,有种户外活动。该活动能否正常进行与各种天气因素有关。
    不同的天气因素组合会产生两种后果,也就是分成2类:能进行活动或不能。
    我们用P表示该活动可以进行,N表示该活动无法进行。
    下表描述样本集合是不同天气因素对该活动的影响。

                     Attribute                       class
    outlook    temperature    humidity    windy
    ---------------------------------------------------------
    sunny       hot             high           false       N
    sunny       hot             high           true         N
    overcast   hot             high           false       P
    rain           mild           high           false       P
    rain           cool           normal      false       P
    rain           cool           normal      true         N
    overcast   cool           normal      true         P
    sunn y      mild           high           false       N
    sunny       cool           normal      false       P
    rain           mild           normal      false       P
    sunny       mild           normal      true         P
    overcast   mild           high           true         P
    overcast   hot             normal      false       P
    rain           mild           high           true        N

    3.2
    该活动无法进行的概率是:5/14
    该活动可以进行的概率是:9/14
    因此样本集合的信息熵是:-5/14log(5/14) - 9/14log(9/14) = 0.940

    3.3
    接下来我们再看属性outlook信息熵的计算:
    outlook为sunny时,
    该活动无法进行的概率是:3/5
    该活动可以进行的概率是:2/5
    因此sunny的信息熵是:-3/5log(3/5) - 2/5log(2/5) = 0.971

    同理可以计算outlook属性取其他值时候的信息熵:
    outlook为overcast时的信息熵:0
    outlook为rain时的信息熵:0.971

    属性outlook的信息增益:gain(outlook) = 0.940 - (5/14*0.971 + 4/14*0 + 5/14*0.971) = 0.246

    相似的方法可以计算其他属性的信息增益:
    gain(temperature) = 0.029
    gain(humidity) = 0.151
    gain(windy) = 0.048

    信息增益最大的属性是outlook。

    3.4
    根据outlook把样本分成3个子集,然后把这3个子集和余下的属性
    作为输入递归执行算法。

4 代码演示
    4.1
    代码说明:
    代码只是演示上一节的例子,写的比较仓促,没有经过仔细的设计和编码,
    只是在fedora 16上做了初步的测试,所以有一些错误和不适当的地方。
    4.2
    编译:
        g++ -g -W -Wall -Wextra -o mytest main.cpp id3.cpp
    4.3
    执行:
        ./mytest
    4.4


id3.h:
================================================
// 2012年 07月 12日 星期四 15:07:10 CST
// author: 李小丹(Li Shao Dan) 字 殊恒(shuheng)
// K.I.S.S
// S.P.O.T


#ifndef ID3_H
#define ID3_H


#include <list>
#include <map>
#include <utility>


// value and index: >= 0, and index 0 is classification
// value and index: not decision is -1
class id3_classify {
public:
    id3_classify(int);
    ~id3_classify();

public:
    int push_sample(const int *, int);
    int classify();
    int match(const int *);
    void print_tree();

private:
    typedef std::list<std::list<std:air<int, int> > > sample_space_t;

    struct tree_node {
        int index;
        int classification;
        std::map<int, struct tree_node *> next;
        sample_space_t unclassified;
    };

private:

    void clear(struct tree_node *);
    int recur_classify(struct tree_node *, int);
    int recur_match(const int *, struct tree_node *);
    int max_gain(struct tree_node *);
    double cal_entropy(const std::map<int, int> &, double);
    int cal_max_gain(const sample_space_t &;
    int cal_split(struct tree_node *, int);
    void att_statistics(const sample_space_t &,
            std::map<int, std::map<int, int> > &,
            std::map<int, std::map<int, std::map<int, int> > > &,
            std::map<int, int> &;
    double cal_gain(std::map<int, int> &,
            std::map<int, std::map<int, int> > &,
            double, double);

    int is_classfied(const sample_space_t &;
    void dump_tree(struct tree_node *);

private:
    sample_space_t unclassfied;
    struct tree_node *root;
    std::map<int, int> *attribute_values;
    int dimension;
};


#endif
===================================================

id3.cpp:
==================================================
// 2012年 07月 16日 星期一 10:07:43 CST
// author: 李小丹(Li Shao Dan) 字 殊恒(shuheng)
// K.I.S.S
// S.P.O.T


#include <iostream>

#include <cmath>
#include <cassert>

#include "id3.h"


using namespace std;


id3_classify::id3_classify(int d)
:root(new struct tree_node), dimension(d)
{
    root->index = -1;
    root->classification = -1;
}

id3_classify::~id3_classify()
{
    clear(root);
}

int id3_classify:ush_sample(const int *vec, int c)
{
    list<pair<int, int> > v;

    for(int i = 0; i < dimension; ++i)
        v.push_back(make_pair(i + 1, vec));
    v.push_front(make_pair(0, c));

    root->unclassified.push_back(v);

    return 0;
}

int id3_classify::classify()
{
    return recur_classify(root, dimension);
}

int id3_classify::match(const int *v)
{
    return recur_match(v, root);
}

void id3_classify::clear(struct tree_node *node)
{
    unclassfied.clear();

    std::map<int, struct tree_node *> &next = node->next;
    for(std::map<int, struct tree_node *>::iterator pos
            = next.begin(); pos != next.end(); ++pos)
        clear(pos->second);

    next.clear();
    delete node;
}

int id3_classify::recur_classify(struct tree_node *node, int dim)
{
    sample_space_t &unclassified = node->unclassified;
    int cls;
    if((cls = is_classfied(unclassified)) >= 0) {
        node->index = -1;
        node->classification = cls;
        return 0;
    }
    int ret = max_gain(node);
    unclassified.clear();
    if(ret < 0) return 0;

    map<int, struct tree_node *> &next = node->next;
    for(map<int, struct tree_node *>::iterator pos
            = next.begin(); pos != next.end(); ++pos)
        recur_classify(pos->second, dim - 1);

    return 0;
}

int id3_classify::is_classfied(const sample_space_t &ss)
{
    const list<pair<int, int> > &f = ss.front();
    if(f.size() == 1)
        return f.front().second;

    int cls;
    for(list<pair<int, int> >::const_iterator p
            = f.begin(); p != f.end(); ++p) {
            if(!p->first) {
                cls = p->second;
                break;
            }
    }
    for(sample_space_t::const_iterator s
            = ss.begin(); s != ss.end(); ++s) {
        const list<pair<int, int> > &v = *s;
        for(list<pair<int, int> >::const_iterator vp
                = v.begin(); vp != v.end(); ++vp) {
            if(!vp->first) {
                if(cls != vp->second)
                    return -1;
                else
                    break;
            }
        }
    }
    return cls;
}

int id3_classify::max_gain(struct tree_node *node)
{
    // index of max attribute gain
    int mai = cal_max_gain(node->unclassified);
    assert(mai >= 0);
    node->index = mai;
    cal_split(node, mai);
    return 0;
}

int id3_classify::cal_max_gain(const sample_space_t &ss)
{
    map<int, map<int, int> >att_val;
    map<int, map<int, map<int, int> > >val_cls;
    map<int, int> cls;

    att_statistics(ss, att_val, val_cls, cls);

    double s = (double)ss.size();
    double entropy = cal_entropy(cls, s);

    double mag = -1;        // max information gain
    int mai = -1;  // index of max information gain

    for(map<int, map<int, int> >::iterator p
            = att_val.begin(); p != att_val.end(); ++p) {
        double g;
        if((g = cal_gain(p->second, val_cls[p->first],
                        s, entropy)) > mag) {
            mag = g;
            mai = p->first;
        }
    }
    if(!att_val.size() && !val_cls.size() && cls.size())
        return 0;
    return mai;
}

void id3_classify::att_statistics(const sample_space_t &ss,
        map<int, map<int, int> > &att_val,
        map<int, map<int, map<int, int> > > &val_cls,
        map<int, int> &cls)
{
    for(sample_space_t::const_iterator spl = ss.begin();
            spl != ss.end(); ++spl) {
        const list<pair<int, int> > &v = *spl;
        int c;
        for(list<pair<int, int> >::const_iterator vp
                = v.begin(); vp != v.end(); ++vp) {
            if(!vp->first) {
                c = vp->second;
                break;
            }
        }
        ++cls[c];
        for(list<pair<int, int> >::const_iterator vp
                = v.begin(); vp != v.end(); ++vp) {
            if(vp->first) {
                ++att_val[vp->first][vp->second];
                ++val_cls[vp->first][vp->second][c];
            }
        }
    }
}

double id3_classify::cal_entropy(const map<int, int> &att, double s)
{
    double entropy = 0;
    for(map<int, int>::const_iterator pos = att.begin();
            pos != att.end(); ++pos) {
        double tmp = pos->second / s;
        entropy += tmp * log2(tmp);
    }
    return -entropy;
}

double id3_classify::cal_gain(map<int, int> &att_val,
        map<int, map<int, int> > &val_cls,
        double s, double entropy)
{
    double gain = entropy;
    for(map<int, int>::const_iterator att = att_val.begin();
            att != att_val.end(); ++att) {
        double r = att->second / s;
        double e = cal_entropy(val_cls[att->first], att->second);
        gain -= r * e;
    }
    return gain;
}

int id3_classify::cal_split(struct tree_node *node, int idx)
{
    map<int, struct tree_node *> &next = node->next;
    sample_space_t &unclassified = node->unclassified;

    for(sample_space_t::iterator sp = unclassified.begin();
            sp != unclassified.end(); ++sp) {
        list<pair<int, int> > &v = *sp;
        for(list<pair<int, int> >::iterator vp = v.begin();
                vp != v.end(); ++vp) {
            if(vp->first == idx) {
                struct tree_node *tmp;
                if(!(tmp = next[vp->second])) {
                    tmp = new struct tree_node;
                    tmp->index = -1;
                    tmp->classification = -1;
                    next[vp->second] = tmp;
                }
                v.erase(vp);
                tmp->unclassified.push_back(v);
                break;
            }
        }
    }
    return 0;
}

int id3_classify::recur_match(const int *v, struct tree_node *node)
{
    if(node->index < 0)
        return node->classification;

    map<int, struct tree_node *>::iterator p;
    map<int, struct tree_node *> &next = node->next;

    if((p = next.find(v[node->index-1])) == next.end())
        return -1;

    return recur_match(v, p->second);
}

void id3_classify:rint_tree()
{
    return dump_tree(root);
}

void id3_classify::dump_tree(struct tree_node *node)
{
    cout << "I: " << node->index << endl;
    cout << "C: " << node->classification << endl;
    cout << "N: " << node->next.size() << endl;
    cout << "+++++++++++++++++++++++\n";

    map<int, struct tree_node *> &next = node->next;
    for(map<int, struct tree_node *>::iterator p
            = next.begin(); p != next.end(); ++p) {
        dump_tree(p->second);
    }
}
====================================================

main.cpp:
===================================================
// 2012年 07月 18日 星期三 13:59:10 CST
// author: 李小丹(Li Shao Dan) 字 殊恒(shuheng)
// K.I.S.S
// S.P.O.T


#include <iostream>

#include "id3.h"

using namespace std;


int main()
{
    enum outlook {SUNNY, OVERCAST, RAIN};
    enum temp {HOT, MILD, COOL};
    enum hum {HIGH, NORMAL};
    enum windy {WEAK, STRONG};

    int samples[14][4] = {
        {SUNNY   ,       HOT ,      HIGH  ,       WEAK  },
        {SUNNY   ,       HOT ,      HIGH  ,       STRONG},
        {OVERCAST,       HOT ,      HIGH  ,       WEAK  },
        {RAIN    ,       MILD,      HIGH  ,       WEAK  },
        {RAIN    ,       COOL,      NORMAL,       WEAK  },
        {RAIN    ,       COOL,      NORMAL,       STRONG},
        {OVERCAST,       COOL,      NORMAL,       STRONG},
        {SUNNY   ,       MILD,      HIGH  ,       WEAK  },
        {SUNNY   ,       COOL,      NORMAL,       WEAK  },
        {RAIN    ,       MILD,      NORMAL,       WEAK  },
        {SUNNY   ,       MILD,      NORMAL,       STRONG},
        {OVERCAST,       MILD,      HIGH  ,       STRONG},
        {OVERCAST,       HOT ,      NORMAL,       WEAK  },
        {RAIN    ,       MILD,      HIGH  ,       STRONG}};

    id3_classify cls(4);
    cls.push_sample((int *)&samples[0], 0);
    cls.push_sample((int *)&samples[1], 0);
    cls.push_sample((int *)&samples[2], 1);
    cls.push_sample((int *)&samples[3], 1);
    cls.push_sample((int *)&samples[4], 1);
    cls.push_sample((int *)&samples[5], 0);
    cls.push_sample((int *)&samples[6], 1);
    cls.push_sample((int *)&samples[7], 0);
    cls.push_sample((int *)&samples[8], 1);
    cls.push_sample((int *)&samples[9], 1);
    cls.push_sample((int *)&samples[10], 1);
    cls.push_sample((int *)&samples[11], 1);
    cls.push_sample((int *)&samples[12], 1);
    cls.push_sample((int *)&samples[13], 0);

    cls.classify();
    cls.print_tree();
    cout << "===============================\n";
    for(int i = 0; i < 14; ++i)
        cout << cls.match((int *)&samples) << endl;
    return 0;
}
================================================
http://blog.csdn.net/leeshuheng/article/details/7777722
要计算log 2  8 【前面底数】
按键下:
8, log, ÷2log

8ln÷2ln

原因对数有特性
即 log a  b= (log c  b)÷(log c  a)

个“纯”数据集(所谓“纯”,指的就是所覆盖的数据集都属于同一个类),那么其熵增益显然就是最大的,那么Day就默认得作为第一个属性。之所以出现这样的情况,是因为增益这个指标天然得偏向于选择那些分支比较多的属性,也就是那些具有的值比较多的那些属性。这种偏向性使我们希望克服的,我们希望公正地评价所有的属性。因此又一个指标被提出来了Gain Ratio-增益比。某一属性A的增益比计算公式如下:

Gain(A)就是前面计算的增益,而SplitInfo(A)计算如下:

公式2

与公式1进行比较,你会发现,SplitInfo(A)实际上就是属性A的熵,只不过这个熵有所不同,他不是样本最终分类{PlayGolf?}的熵,而是对应属性分组{A?}的熵,它反映的是属性A本身的信息量。通过计算我们很容易得到GainRatio(Outlook)=0.246/1.577=0.156。增益比实际上就是对增益进行了归一化,这样就避免了指标偏向分支多的属性的倾向。

通过上述方法得到了决策树,这一切看起来都很完美,但是这还不够。决策树能够帮助我们对新出现的样本进行分类,但还有一些问题它不能很好得解决。比如我们想知道对于最终的分类,哪个属性的贡献更大?能否用一种比较简洁的规则来区分样本属于哪个类?等等。为了解决这些问题,基于产生的决策树,各位大牛们又提出了一些新的方法。

3. C4.5的功能

3.1 决策树的剪枝

决策树为什么要剪枝?原因就是避免决策树“过拟合”样本。前面

http://fangdonghao1029.blog.163.com/blog/static/34364307201281352032174/
http://wenku.baidu.com/link?url=yZRVDaKIdQ6oeMhDqp24xprZMCNaoBa0FajZpzBdBlqYTQGGPscgrKZdIwpLkU8GzhEyNqVO4T5oAcEWPSxEnVPSXiqHbQRU0rpM32KbL1S

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-22 16:27 | 显示全部楼层
初探数据挖掘中的十大经典算法  

2011-03-28 14:55:12|  分类: 数据挖掘 |  标签:数据挖掘   |举报|字号 订阅
以下就是从参加评选的18种候选算法中,最终决选出来的十大经典算法:

一、C4.5

C4.5,是机器学习算法中的一个分类决策树算法,它是决策树(决策树也就是做决策的节点间的组织方式像一棵树,其实是一个倒树)核心算法ID3的改进算法,所以基本上了解了一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。

C4.5相比于ID3改进的地方有:

1、用信息增益率来选择属性。

ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy,熵是一种不纯度度量准则),也就是熵的变化值。而C4.5用的是信息增益率。对,区别就在于一个是信息增益,一个是信息增益率。一般来说率就是用来取平衡用的,就像方差起的作用差不多,比如有两个跑步的人,一个起点是10m/s的人、其10s后为20m/s;另一个人起速是1m/s、其1s后为2m/s。

如果紧紧算差值那么两个差距就很大了,如果使用速度增加率(加速度,即都是为1m/s^2)来衡量,2个人就是一样的加速度。因此,C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。

2、在树构造过程中进行剪枝,在构造决策树的时候,那些挂着几个元素的节点,不考虑最好,不然容易导致overfitting。

3、对非离散数据也能处理。

4、能够对不完整数据进行处理。

二、The k-means algorithm 即K-Means算法

k-means algorithm算法是一个聚类算法,把n的对象根据他们的属性分为k个分割(k < n)。它与处理混合正态分布的最大期望算法(本十大算法第五条)很相似,因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量,并且目标是使各个群组内部的均方误差总和最小。

三、 Support vector machines

支持向量机,英文为Support Vector Machine,简称SV机(论文中一般简称SVM)。它是一种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面,分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大,分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。

四、The Apriori algorithm

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集。

五、最大期望(EM)算法

在统计计算中,最大期望 (EM,Expectation–Maximization)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variabl)。最大期望经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域。

六、PageRank

PageRank是Google算法的重要内容。2001年9月被授予美国专利,专利人是Google创始人之一拉里?佩奇(Larry Page)。因此,PageRank里的page不是指网页,而是指佩奇,即这个等级方法是以佩奇来命名的。PageRank根据网站的外部链接和内部链接的数量和质量,衡量网站的价值。PageRank背后的概念是,每个到页面的链接都是对该页面的一次投票, 被链接的越多,就意味着被其他网站投票越多。

这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多,一般判断这篇论文的权威性就越高。

七、AdaBoost

Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。

将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器融合起来,作为最后的决策分类器。

八、kNN: k-nearest neighbor classification

K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。

九、Naive Bayes

在众多的分类模型中,应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive Bayesian Model,NBC)。朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。同时,NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。理论上,NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时,NBC模型的分类效率比不上决策树模型。而在属性相关性较小时,NBC模型的性能最为良好。

十、CART: 分类与回归树

CART, Classification and Regression Trees。 在分类树下面有两个关键的思想:第一个是关于递归地划分自变量空间的想法;第二个想法是用验证数据进行剪枝。ok,日后择其一二详细研究、阐述,完。

至于18种候选算法,可参考这里:http://www.cs.uvm.edu/~icdm/algorithms/CandidateList.shtml
http://youdianluan.blog.163.com/ ... 096201122825512783/

使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-22 19:18 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-22 20:00 编辑

http://blog.sina.com.cn/s/blog_6002b97001014nho.html  c4.5

C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.  C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:

    1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
    2) 在树构造过程中进行剪枝;
    3) 能够完成对连续属性的离散化处理;
    4) 能够对不完整数据进行处理。

    C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。


分类算法的目的是根据其他参数的取值预测类别参数的取值,希望这种预测尽可能准确。分类算法的总体框架可以分为两步:第一步是基于训练集构建分类模型,第二步是用测试集检测分类模型的准确度,若可接受,即可用于预测新数据的类别。决策树分类
    本文介绍决策树分类算法。决策树分类算法的一般流程如下:一开始,所有的实例均位于根节点,所有参数的取值均离散化;根据启发规则选择一个参数,根据参数取值的不同对实例集进行分割;对分割后得到的节点进行同样的启发式参数选择分割过程,如此往复,直到(a)分割得到的实例集合属于同一类;(b)参数用完,以子集中绝大多数的实例类别作为该叶节点的类别。
核心问题:参数选择规则
    在每一个节点进行参数选择时,由于有众多的选项,需要一个选择规则。基本的原则是使最后构造出的决策树规模最小。基于这个基本原则,我们启发式地定义规则为使分割后得到的子节点纯度最大。于是参数选择规则问题就转化为了纯度定义的问题。
    我们利用熵(Entropy)的概念去描述“不纯度”,熵值越大,说明这个节点的纯度越低:当节点的类别均匀分布时,熵值为1;当只包含一类时,熵值为0.熵的计算公式如下图,以2为底的概率对数与概率乘积之和的相反数。
    基于熵的概念,我们可以得到参数选择的第一个规则:信息增益(Info Gain).信息增益的定义是分裂前的节点熵减去分裂后子节点熵的加权和,即不纯度的减少量,也就是纯度的增加量。参数选择的规则是:选择使信息增益最大的参数分割该节点。信息增益计算的算例如下图。
    信息增益存在的问题时:总是倾向于选择包含多取值的参数,因为参数的取值越多,其分割后的子节点纯度可能越高。为了避免这个问题,我们引入了增益比例(Gain Ratio)的选择指标,其定义如下图所示。
    增益比例存在的问题是:倾向于选择分割不均匀的分裂方法,举例而言,即一个拆分若分为两个节点,一个节点特别多的实例,一个节点特别少的实例,那么这种拆分有利于被选择。
    为了克服信息增益和增益比例各自的问题,标准的解决方案如下:首先利用信息增益概念,计算每一个参数分割的信息增益,获得平均信息增益;选出信息增益大于平均值的所有参数集合,对该集合计算增益比例,选择其中增益比例最大的参数进行决策树分裂。
    上面介绍的是基于熵概念的参数选择规则,另一种流行的规则称为基尼指数(Gini Index),其定义如下图。基尼系数在节点类别分布均匀时取最大值1-1/n,在只包含一个类别时取最小值0. 所以与熵类似,也是一个描述不纯度的指标。
    基于基尼系数的规则是:选择不纯度减少量(Reduction in impurity)最大的参数。不纯度减少量是分割前的Gini index减去分割后的Gini index。基尼系数的特点与信息增益的特点类似。
过度拟合问题(Overfitting)
过度拟合问题是对训练数据完全拟合的决策树对新数据的预测能力较低。为了解决这个问题,有两种解决方法。第一种方法是前剪枝(prepruning),即事先设定一个分裂阈值,若分裂得到的信息增益不大于这个阈值,则停止分裂。第二种方法是后剪枝(postpruning),首先生成与训练集完全拟合的决策树,然后自下而上地逐层剪枝,如果一个节点的子节点被删除后,决策树的准确度没有降低,那么就将该节点设置为叶节点(基于的原则是Occam剪刀:具有相似效果的两个模型选择较简单的那个)。
代表算法
    这里介绍两个算法,一个是RainForest,其主要的贡献是引入了一个称为AVC的数据结构,其示意图如下。主要的作用是加速参数选择过程的计算。
    另一个算法称为BOAT,其采用了称为bootstrap的统计技术对数据集进行分割,在分割的子数据集上分别构造决策树,再基于这些决策树构造一个新的决策树,文章证明这棵新树与基于全局数据集构造的决策树非常相近。这种方法的主要优势在于支持增量更新。
本文所采用图片均来自清华大学计算机系王建勇老师的课程《数据挖掘:原理与算法》
http://dbgroup.cs.tsinghua.edu.cn/wangjy/DM/DataMining.html
http://wenku.baidu.com/view/e0074cd2195f312b3169a525.html



使用道具 举报

回复
论坛徽章:
18
授权会员
日期:2005-10-30 17:05:33美羊羊
日期:2015-03-04 14:48:58马上有车
日期:2014-02-18 16:41:112014年新春福章
日期:2014-02-18 16:41:11紫蜘蛛
日期:2012-02-21 15:06:16嫦娥
日期:2012-02-21 15:05:212012新春纪念徽章
日期:2012-01-04 11:49:54ITPUB十周年纪念徽章
日期:2011-11-01 16:20:282009日食纪念
日期:2009-07-22 09:30:00数据库板块每日发贴之星
日期:2009-02-26 01:01:03
 楼主| 发表于 2014-4-22 21:31 | 显示全部楼层
本帖最后由 liyihongcug 于 2014-4-23 10:12 编辑

本周首先对C4.5的算法步骤进行了梳理:
  Step1.对数据源进行数据预处理,将连续型的属性变量进行离散化处理形成决策树的训练集(如果没有连续取
值的属性则忽略);
  (1)根据原始数据,找到该连续型属性的最小取值a0。、最大取值a(n+1) ;
  (2)在区间[a,b]内插入n个数值等分为n+1个小区间;
  (3)分别以ai,i=l,2,… ,n为分段点,将区间【a0, a(n+1) 】划分为两个子区间:
  Step2.计算每个属性的信息增益和信息增益率;
  (1)计算属性A的信息增益Gain(A)
信息增益Gain(A)的计算和ID3算法中的完全一致;
  (2)计算属性A的信息增益率Gain—Ratio(A)
Gain—Ratio(A)= Gain(A)/I(A)
  对于取值连续的属性而言,分别计算以ai (i=l,2,…,n)为分割点,对应分类的信息增益率,选择最大信息
增益率对应的n ,作为该属性分类的分割点。
  选择信息增益率最大的属性,作为当前的属性节点,得到决策树的根节点。
  Step3.根节点属性每一个可能的取值对应一个子集,对样本子集递归地执行以上Step2过程,直到划分的每个
子集中的观测数据在分类属性上取值都相同,生成决策树。
  Step4.根据构造的决策树提取分类规则,对新的数据集进行分类。

    随后对数据挖掘十大算法之一的另一个进行了研究——CART算法。
  CART算法是决策树算法中的一种,基本理论与C4.5算法类似,也是一种比较经典的决策树算法。
1.背景:
  分类与回归树(CART——Classification And Regression Tree) ) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。该方法是四位美国统计学家耗时十多年辛勤劳动的成果。在他们所著的“Classification And Regression Tree(1 9 8 4) ”一书中有该方法的详细说明。
  分类与回归树CART 模型最早由Breiman 等人提出,已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则,它是以二叉树的形式给出,易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确,且数据越复杂、变量越多,算法的优越性就越显著。模型的关键是预测准则的构建,准确的。
  2.定义:
  分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。

P.S.下两周主要对C4.5算法进行应用,阅读《基于C4.5决策树的流量分类方法》和《基于C4.5算法的数据挖掘应用研究》进行理论实践,并尝试用软件运行;同时了解CART的预测准则和应用范围。
http://blog.sina.com.cn/s/blog_7399ad1f01014oic.htmlhttp://wenku.baidu.com/link?url=G7HkU5oqn01amLK7MWGKI-6bWag4T_s7FRZk-Pb6vw03h6E4iG3-Dcq77PBm8IFxVDAct6Hncd5V9SqObFjgH-A0d4PUEn9Z9jg0WgzlJvq
http://doc.mbalib.com/view/c9bb3918c6684e2ad916096613fd74ee.html
http://www.docin.com/p-473038039.html

计算方法编辑若x1,x2,x3......xn的平均数为m

方差公式


则方差


2
方差的概念与计算公式编辑
例1 两人的5次测验成绩如下:
X: 50,100,100,60,50 E(X )=72;
Y: 73, 70, 75,72,70 E(Y )=72。
平均成绩相同,但X 不稳定,对平均值的偏离大。方差描述随机变量对于数学期望的偏离程度。
单个偏离是消除符号影响方差即偏离平方的均值,记为D(X ):
直接计算公式分离散型和连续型,具体为:这里 是一个数。推导另一种计算公式
得到:“方差等于平方的均值减去均值的平方”。
其中,分别为离散型和连续型计算公式。 称为标准差或均方差,方差描述波动
方差的性质1.设C为常数,则D(C) = 0(常数无波动);
2. D(CX )=C2 D(X ) (常数平方提取);
证:特别地 D(-X ) = D(X ), D(-2X ) = 4D(X )(方差无负值)
3.若X 、Y 相互独立,则,证:记
前面两项恰为 D(X )和D(Y ),第三项展开后为
当X、Y 相互独立时,故第三项为零。特别地独立前提的逐项求和,可推广到有限项。
方差公式:
平均数
(n表示这组数据个数,x1、x2、x3……xn表示这组数据具体数值)

方差公式:

常用分布的方差1.两点分布
2.二项分布
X ~ B ( n, p )
引入随机变量 Xi (第i次试验中A 出现的次数,服从两点分布)
3.泊松分布(推导略)
4.均匀分布
另一计算过程为
5.指数分布(推导略)
6.正态分布(推导略)
7.t分布 :其中X~T(n),E(X)=0;

8.F分布:其中X~F(m,n),
;

正态分布的后一参数反映它与均值 的偏离程度,即波动程度(随机波动),这与图形的特征是相符的。
例2 求上节例2的方差。
解 根据上节例2给出的分布律,计算得到
工人乙废品数少,波动也小,稳定性好。

3
方差的定义:编辑
设一组数据x1,x2,x3……xn中,各组数据与它们的平均数x(拔)的差的平方分别是(x1-x拔)2,(x2-x拔)2……(xn-x拔)2,那么我们用他们的平均数来衡量这组数据的波动大小,并把它叫做这组数据
的方差。



Kmeans算法
编辑
k-means 算法接受参数 k ;然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。
K-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果。
假设要把样本集分为c个类别,算法描述如下:
(1)适当选择c个类的初始中心;
(2)在第k次迭代中,对任意一个样本,求其到c各中心的距离,将该样本归到距离最短的中心所在的类;
(3)利用均值等方法更新该类的中心值;
(4)对于所有的c个聚类中心,如果利用(2)(3)的迭代法更新后,值保持不变,则迭代结束,否则继续迭代。
算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

2
算法流程编辑
首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

3
具体流程编辑
输入:k, data[n];
(1) 选择k个初始中心点,例如c[0]=data[0],…c[k-1]=data[k-1];
(2) 对于data[0]….data[n], 分别与c[0]…c[k-1]比较,假定与c差值最少,就标记为i;
(3) 对于所有标记为i点,重新计算c={ 所有标记为i的data[j]之和}/标记为i的个数;
(4) 重复(2)(3),直到所有c值的变化小于给定阈值。 http://blog.csdn.net/aladdina/article/details/4141127
http://www.cs.uvm.edu/~icdm/algorithms/CandidateList.shtml

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时9.5折

【架构革新 高效可控】2020年8月17日~19日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
TOP技术积分榜 社区积分榜 徽章 团队 统计 知识索引树 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 
京ICP备09055130号-4  北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表