设为首页收藏本站
开启辅助访问
切换到窄版

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 2067|回复: 0

libsvm源码分析

[复制链接]
发表于 2011-10-6 11:28:03 | 显示全部楼层 |阅读模式
SVM(Support Vector Machine)是一个统计学概念,它的作用是通过已分类的样本点进行训练,找出类别分界面。之后可以将任意未知样本分类。这也就是个学习和识别的过程。而libsvm就是这样一个用C++编写而成的库。在识别系统:例如手写识别、语音识别都是很重要的东西。网上相关的分析资料不多,源代码的注释也很少。另上海交大模式识别人工智能实验室发表的《libsvm 2.6 代码注释》中有些疏漏,故我对其进行了再次的注释。不过这篇文档也给了我不少启发。(拜伦的技术空间)



  1. OPen_SVM: http://sourceforge.net/projects/opensvm
  2. 分析模块:cache类
  3. 分析者:Byron
  4. E-Mail: byronm@sina.com
  5. 分析日期:2007年8月2日
  6. ==============================================*/
  7. //
  8. // Kernel Cache
  9. //
  10. // l is the number of total data items
  11. // size is the cache size limit in bytes
  12. //
  13. class Cache
  14. {
  15. public:
  16. Cache(int l,long int size); //构建Cache的参数,包含l(数据个数)和size(空间大小)
  17.   // l is the number of total data items
  18.   // size is the cache size limit in bytes
  19. ~Cache();//析构函数
  20. // request data [0,len)
  21. // return some position p where [p,len) need to be filled
  22. // (p >= len if nothing needs to be filled)
  23. int get_data(const int index, Qfloat **data, int len);//读取数据
  24. void swap_index(int i, int j); // future_option
  25. private:
  26. int l;
  27. long int size;
  28. struct head_t
  29. {
  30. head_t *prev, *next; // a cicular list 双向链表
  31. Qfloat *data;
  32. int len; // data[0,len) is cached in this entry
  33. };
  34. head_t *head;   
  35. head_t lru_head;
  36. void lru_delete(head_t *h);
  37. void lru_insert(head_t *h);
  38. };

  39. //cache保证索引结构的大小,余下的大小用来存放数据
  40. //size最后被修改为可以存放Qfloat类型数据的大小
  41. Cache::Cache(int l_,long int size_):l(l_),size(size_)
  42. {
  43. head = (head_t *)calloc(l,sizeof(head_t)); //initialized to 0,分配所有数据结构所需内存(地址连续)
  44. size /= sizeof(Qfloat);   //Qfloat 类型的个数,(size 的 意义已经由数据空间大小变为数据个数)
  45. size -= l * sizeof(head_t) / sizeof(Qfloat); //除结构体所占用的空间外,剩下用于存放数据的个数
  46. size = max(size, (long int) 2*l); //cache must be large enough for two columns
  47. lru_head.next = lru_head.prev = lru_head;
  48. }
  49. Cache::~Cache()//释放内存数据区,然后释放结构
  50. {
  51. for(head_t *h = lru_head.next; h != lru_head; h=h->next)
  52. free(h->data);
  53. free(head);
  54. }
  55. void Cache::lru_delete(head_t *h)
  56. {
  57. // delete from current location
  58. h->prev->next = h->next;
  59. h->next->prev = h->prev;
  60. }
  61. //循环链表插入
  62. void Cache::lru_insert(head_t *h)
  63. {
  64. // insert to last position
  65. h->next = lru_head;
  66. h->prev = lru_head.prev;
  67. h->prev->next = h;
  68. h->next->prev = h;
  69. }

  70. // request data [0,len)
  71. // return some position p where [p,len) need to be filled
  72. // (p >= len if nothing needs to be filled) //返回cache的空白数据区的第一个位置
  73. // [p,len) is empty
  74. //
  75. /*插入代码(svm.cpp(1389~1408))
  76. ------------------------------------
  77. Qfloat *get_Q(int i, int len) const
  78. {
  79. Qfloat *data; //数据存放地址
  80. int start;
  81. //返回缓冲分配的地址,若不存在所要数据,返回缓冲区的空闲地址
  82. if((start = cache->get_data(i,data,len)) < len)
  83. {
  84. for(int j=start;j<len;j++)
  85.   data[j] = (Qfloat)(y*y[j]*(this->*kernel_function)(i,j));//将计算结果写入缓冲区
  86. }
  87. return data; //返回缓冲区的地址
  88. }
  89. ------------------------------------
  90. */
  91. //如果所要数据项存在,就取出,如果所要数据不够,就由补充空间,维持cache的大小,返回cache空闲区的大小
  92. int Cache::get_data(const int index, Qfloat **data, int len)//len 是 data 的长度,同时也返回空白数据区的首地址
  93. {
  94. head_t *h = head[index];//定位链表中的记录,物理访问,因head是连续分配的
  95. if(h->len) lru_delete(h);//如果有数据,先删除逻辑结构
  96. int more = len - h->len;//如果需要取得的数据和原有数据不匹配,需要多取的数据
  97.   //如果more == len,即h->len == 0,表示该结点没有存放数据,要将该结点插入cache链表
  98.   //如果more < 0 表示空间内有数据,
  99. if(more > 0)   //如果more > 0 表示有的计算数据不在缓冲区内,返回空白空间的位置
  100. {
  101. // free old space
  102. while(size < more)//如果数据项大于cache的大小,为了维持cache的大小,删除使用过的数据结点
  103. {
  104.   head_t *old = lru_head.next;   //定位最早被使用的结点
  105.   lru_delete(old); //删除此结点
  106.   free(old->data); //释放数据项,腾出空间
  107.   size += old->len; //size被修正,从逻辑上看是增加了大小
  108.   old->data = 0;   //对数据项进行清零
  109.   old->len = 0;   //
  110. }
  111. // allocate new space
  112. // (size > more)重新分配内存以满足data大小
  113. // (size < more)在空闲内存中分配内存以满足data大小
  114. h->data = (Qfloat *)realloc(h->data,sizeof(Qfloat)*len);
  115. size -= more; //修正size的值,变成原来的大小,cache的物理大小和逻辑大小精确匹配
  116. swap(h->len,len); //h->len 的大小被改为len,即所存放数据的大小
  117.   //len 被改为h->len,即新分配的空闲cache空间的地址
  118. }
  119. lru_insert(h); //插入结点,此结点中存有数据区的地址信息
  120.   //如果重新分配内存而插入,维持cache的逻辑结构
  121.   //如果没有重新分配内存,将结点放回
  122. *data = h->data; //将cache的空间的地址传出
  123.   //more >= len 时,传出空闲空间的地址
  124.   //more < 0   时,传出数据区的地址
  125. return len; //返回更新后的len值,即空闲的cache空间的地址
  126. }
  127. libsvm-2.84 源代码分析(一)——cache类
  128. //交换cache中的两个数据
  129. void Cache::swap_index(int i, int j)
  130. {
  131. if(i==j) return;
  132. //如果有数据,就先断开逻辑结构
  133. if(head.len) lru_delete(head);
  134. if(head[j].len) lru_delete(head[j]);
  135. //交换数据区地址和len大小
  136. swap(head.data,head[j].data);
  137. swap(head.len,head[j].len);
  138. //重新插入链表
  139. if(head.len) lru_insert(head);
  140. if(head[j].len) lru_insert(head[j]);
  141. if(i>j) swap(i,j); //保证地址由低至高,i为低地址,j为高地址

  142. //h points to a column. The implementation roughly handles three situations:
  143. //(0) h includes neither i nor j: do nothing.
  144. //(1) h includes both i and j: the corresponding data would be swapped.
  145. //(2) h contains i but not j (recall that i < j): the column would be thrown away.
  146. //保持矩阵交换后的数据对应继续有效
  147. for(head_t *h = lru_head.next; h!=lru_head; h=h->next)
  148. {
  149. if(h->len > i)
  150. {
  151.   if(h->len > j)
  152.   swap(h->data,h->data[j]);//交换数据区内容
  153.   else
  154.   {
  155.   // give up
  156.   lru_delete(h);
  157.   free(h->data);
  158.   size += h->len;
  159.   h->data = 0;
  160.   h->len = 0;
  161.   }
  162. }
  163. }
  164. }
复制代码







来源:http://www.5iai.com/bbs/read.php ... ;toread=page=1
您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|申请友链|小黑屋|手机版|Archiver|生物信息学论坛 ( 蜀ICP备09031721号  

GMT+8, 2017-2-20 19:00 , Processed in 0.097891 second(s), 19 queries .

Powered by Discuz! X3

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表