1/2, 10«‹12›»

阅读摘要：推荐算法介绍(隐性打分)

2010-3-1 19:40:59 开发者 抢沙发(0)

 来源:http://blog.csdn.net/liuzhenwen/archive/2009/04/22/4101003.aspx

推荐系统最早在亚马逊的网站上应用，根据以往用户的购买行为，推荐出购买某种产品同时可能购买的其他产品。

直接打分需要用户的参与程度比较高，很多网站都在内容页中留一个打分的按钮，从1～5选一 个，我可能喜欢这篇文章，可我哪里知道我喜欢的程度是几分啊，还要我去思考，而网站设计中一条很重要的原则是:Do not let me think!，于是我就胡打一个分数或者不打，而隐性的打分则不同，只有你喜欢的图书你才会购买，只有你喜欢的歌曲才会听多次。

最近邻搜索算法一般是皮尔森相关系数（Person Correlation Coefficient）、余弦相似性（Cosine-based Similarity）以及调整余弦相似性（Adjusted Cosine Similarity）。关于余弦定理在数据挖掘中的应用，google黑白报有过介绍，可以参考数学之美 系列 12 - 余弦定理和新闻的分类。

 

基本原理

用户          对事物A打分 对事物B打分
X 3 4
Y 2 4
Z 4 ?

用户Z对事物B的打分可能是多少呢？股票上有个说法是平均值可以掩盖一切异常波动，所以股票上的各个技术指标收拾不同时间段的平均值的曲线图或者柱 状图等。同样的，Slope one算法也认为：平均值也可以代替某两个未知个体之间的打分差异，事物A对事物B的平均很差是：((3 - 4) + (2 - 4)) / 2 = -1.5，也就是说人们对事物B的打分一般比事物A的打分要高1.5，于是Slope one算法就猜测Z对事物B的打分是4 + 1.5 = 5.5

 

 

加权算法

有n个人对事物A和事物B打分了，R(A->B)表示这n个人对A和对B打分的平均差（A-B）,有m个人对事物B和事物C打分 了，R（C->B）表示这m个人对C和对B打分的平均差（C-B），注意都是平均差而不是平方差，现在某个用户对A的打分是ra，对C的打分是 rc，那么A对B的打分可能是：

rb = (n * (ra - R(A->B)) + m * (rc - R(C->B)))/(m+n)

 

 

 

 

  1.  
  2. # This is the code in plain text out of the technical report. 
  3. # 
  4. # Daniel Lemire, Sean McGrath, Implementing a Rating-Based Item-to-Item 
  5. # Recommender System in PHP/SQL, Technical Report D-01, January 2005. 
  6. # 
  7. # http://www.ondelette.com/lemire/abstracts/TRD01.html 
  8. # 
  9. # This code is in the public domain, use at your own risks. 
  10. # It is assumed that you looked at the report and know some SQL and PHP. 
  11. # 
  12. # Daniel Lemire, February 3rd 2005 
  13. # 
  14. # First part is sample SQL code. 
  15. #########CUT HERE#################### 
  16.  
  17. CREATE TABLE rating ( 
  18.     userID INT PRIMARY KEY, 
  19.     itemID INT NOT NULL, 
  20.     ratingValue INT NOT NULL, 
  21.     datetimestamp TIMESTAMP NOT NULL 
  22. ); 
  23.  
  24.  
  25. CREATE TABLE dev ( 
  26.   itemID1 int(11) NOT NULL default '0', 
  27.   itemID2 int(11) NOT NULL default '0', 
  28.   count int(11) NOT NULL default '0', 
  29.   sum int(11) NOT NULL default '0', 
  30.   PRIMARY KEY  (itemID1,itemID2) 
  31. ); 
  32.  
  33.  
  34. # simple query to output 10 most liked items 
  35. # by people who rated item 1 
  36. SELECT itemID2, ( sum / count ) AS average 
  37. FROM dev 
  38. WHERE count > 2 AND itemID1 = 1 
  39. ORDER  BY ( sum / count ) DESC 
  40. LIMIT 10; 
  41.  
  42. # Next part is sample PHP code. 
  43. #########CUT HERE#################### 
  44.  
  45. // This code assumes $itemID is set to that of  
  46. // the item that was just rated.  
  47. // Get all of the user's rating pairs 
  48. $sql = "SELECT DISTINCT r.itemID, r2.ratingValue - r.ratingValue  
  49.             as rating_difference 
  50.             FROM rating r, rating r2 
  51.             WHERE r.userID=$userID AND  
  52.                     r2.itemID=$itemID AND  
  53.                     r2.userID=$userID;"; 
  54. $db_result = mysql_query($sql, $connection); 
  55. $num_rows = mysql_num_rows($db_result); 
  56. //For every one of the user's rating pairs,  
  57. //update the dev table 
  58. while ($row = mysql_fetch_assoc($db_result)) { 
  59.     $other_itemID = $row["itemID"]; 
  60.     $rating_difference = $row["rating_difference"]; 
  61.     //if the pair ($itemID, $other_itemID) is already in the dev table 
  62.     //then we want to update 2 rows. 
  63.     if (mysql_num_rows(mysql_query("SELECT itemID1  
  64.     FROM dev WHERE itemID1=$itemID AND itemID2=$other_itemID", 
  65.     $connection)) > 0)  { 
  66.         $sql = "UPDATE dev SET count=count+1,  
  67.     sum=sum+$rating_difference WHERE itemID1=$itemID  
  68.     AND itemID2=$other_itemID"; 
  69.         mysql_query($sql, $connection); 
  70.     //We only want to update if the items are different                 
  71.         if ($itemID != $other_itemID) { 
  72.             $sql = "UPDATE dev SET count=count+1,  
  73.         sum=sum-$rating_difference  
  74.         WHERE (itemID1=$other_itemID AND itemID2=$itemID)"; 
  75.             mysql_query($sql, $connection); 
  76.         } 
  77.     } 
  78.     else { //we want to insert 2 rows into the dev table 
  79.         $sql = "INSERT INTO dev VALUES ($itemID, $other_itemID, 
  80.         1, $rating_difference)"; 
  81.         mysql_query($sql, $connection);  
  82.     //We only want to insert if the items are different        
  83.         if ($itemID != $other_itemID) {          
  84.             $sql = "INSERT INTO dev VALUES ($other_itemID,  
  85.         $itemID, 1, -$rating_difference)"; 
  86.             mysql_query($sql, $connection); 
  87.         } 
  88.     }     
  89. } 
  90.  
  91.  
  92. function predict($userID, $itemID) { 
  93.     global $connection;     
  94.     $denom = 0.0; //denominator 
  95.     $numer = 0.0; //numerator     
  96.     $k = $itemID;     
  97.     $sql = "SELECT r.itemID, r.ratingValue  
  98.     FROM rating r WHERE r.userID=$userID AND r.itemID <> $itemID"; 
  99.     $db_result = mysql_query($sql, $connection);         
  100.     //for all items the user has rated 
  101.     while ($row = mysql_fetch_assoc($db_result))  { 
  102.         $j = $row["itemID"]; 
  103.         $ratingValue = $row["ratingValue"];         
  104.         //get the number of times k and j have both been rated by the same user 
  105.         $sql2 = "SELECT d.count, d.sum FROM dev d WHERE itemID1=$k AND itemID2=$j"; 
  106.         $count_result = mysql_query($sql2, $connection);         
  107.         //skip the calculation if it isn't found 
  108.         if(mysql_num_rows($count_result) > 0)  { 
  109.             $count = mysql_result($count_result, 0, "count"); 
  110.             $sum = mysql_result($count_result, 0, "sum");             
  111.             //calculate the average 
  112.             $average = $sum / $count;             
  113.             //increment denominator by count 
  114.             $denom += $count;             
  115.             //increment the numerator 
  116.             $numer += $count * ($average + $ratingValue); 
  117.         }         
  118.     }     
  119.     if ($denom == 0) 
  120.         return 0; 
  121.     else 
  122.         return ($numer / $denom); 
  123. } 
  124.  
  125.  
  126. function predict_all($userID ) { 
  127.     $sql2 = "SELECT d.itemID1 as 'item', sum(d.count) as 'denom',  
  128.     sum(d.sum + d.count*r.ratingValue) as 'numer' FROM item i, rating r, 
  129.     dev d WHERE r.userID=$userID  
  130.     AND d.itemID1<>r.itemID  
  131.     AND d.itemID2=r.itemID GROUP BY d.itemID1"; 
  132.     return mysql_query($sql2, $connection); 
  133. } 

 

Java：

  1. import java.util.*; 
  2. /** 
  3. * Daniel Lemire 
  4. * A simple implementation of the weighted slope one 
  5. * algorithm in Java for item-based collaborative  
  6. * filtering.  
  7. * Assumes Java 1.5. 
  8. * 
  9. * See main function for example. 
  10. * 
  11. * June 1st 2006. 
  12. * Revised by Marco Ponzi on March 29th 2007 
  13. */ 
  14.  
  15. public class SlopeOne { 
  16.    
  17.   public static void main(String args[]){ 
  18.     // this is my data base 
  19.     Map<UserId,Map<ItemId,Float>> data = new HashMap<UserId,Map<ItemId,Float>>(); 
  20.     // items 
  21.     ItemId item1 = new ItemId("       candy"); 
  22.     ItemId item2 = new ItemId("         dog"); 
  23.     ItemId item3 = new ItemId("         cat"); 
  24.     ItemId item4 = new ItemId("         war"); 
  25.     ItemId item5 = new ItemId("strange food"); 
  26.      
  27.     mAllItems = new ItemId[]{item1, item2, item3, item4, item5}; 
  28.      
  29.     //I'm going to fill it in 
  30.     HashMap<ItemId,Float> user1 = new HashMap<ItemId,Float>(); 
  31.     HashMap<ItemId,Float> user2 = new HashMap<ItemId,Float>(); 
  32.     HashMap<ItemId,Float> user3 = new HashMap<ItemId,Float>(); 
  33.     HashMap<ItemId,Float> user4 = new HashMap<ItemId,Float>(); 
  34.     user1.put(item1,1.0f); 
  35.     user1.put(item2,0.5f); 
  36.     user1.put(item4,0.1f); 
  37.     data.put(new UserId("Bob"),user1); 
  38.     user2.put(item1,1.0f); 
  39.     user2.put(item3,0.5f); 
  40.     user2.put(item4,0.2f); 
  41.     data.put(new UserId("Jane"),user2); 
  42.     user3.put(item1,0.9f); 
  43.     user3.put(item2,0.4f); 
  44.     user3.put(item3,0.5f); 
  45.     user3.put(item4,0.1f); 
  46.     data.put(new UserId("Jo"),user3);     
  47.     user4.put(item1,0.1f); 
  48.     //user4.put(item2,0.4f); 
  49.     //user4.put(item3,0.5f); 
  50.     user4.put(item4,1.0f); 
  51.     user4.put(item5,0.4f); 
  52.     data.put(new UserId("StrangeJo"),user4);     
  53.     // next, I create my predictor engine 
  54.     SlopeOne so = new SlopeOne(data); 
  55.     System.out.println("Here's the data I have accumulated..."); 
  56.     so.printData(); 
  57.     // then, I'm going to test it out... 
  58.     HashMap<ItemId,Float> user = new HashMap<ItemId,Float>(); 
  59.     System.out.println("Ok, now we predict..."); 
  60.     user.put(item5,0.4f); 
  61.     System.out.println("Inputting..."); 
  62.     SlopeOne.print(user); 
  63.     System.out.println("Getting..."); 
  64.     SlopeOne.print(so.predict(user)); 
  65.     // 
  66.     user.put(item4,0.2f); 
  67.     System.out.println("Inputting..."); 
  68.     SlopeOne.print(user); 
  69.     System.out.println("Getting..."); 
  70.     SlopeOne.print(so.predict(user)); 
  71.   } 
  72.    
  73.   Map<UserId,Map<ItemId,Float>> mData; 
  74.   Map<ItemId,Map<ItemId,Float>> mDiffMatrix; 
  75.   Map<ItemId,Map<ItemId,Integer>> mFreqMatrix; 
  76.    
  77.   static ItemId[] mAllItems; 
  78.    
  79.   public SlopeOne(Map<UserId,Map<ItemId,Float>> data) { 
  80.     mData = data; 
  81.     buildDiffMatrix();     
  82.   } 
  83.    
  84.   /** 
  85.   * Based on existing data, and using weights, 
  86.   * try to predict all missing ratings. 
  87.   * The trick to make this more scalable is to consider 
  88.   * only mDiffMatrix entries having a large  (>1) mFreqMatrix 
  89.   * entry. 
  90.   * 
  91.   * It will output the prediction 0 when no prediction is possible. 
  92.   */ 
  93.   public Map<ItemId,Float> predict(Map<ItemId,Float> user) { 
  94.     HashMap<ItemId,Float> predictions = new HashMap<ItemId,Float>(); 
  95.     HashMap<ItemId,Integer> frequencies = new HashMap<ItemId,Integer>(); 
  96.     for (ItemId j : mDiffMatrix.keySet()) { 
  97.       frequencies.put(j,0); 
  98.       predictions.put(j,0.0f); 
  99.     } 
  100.     for (ItemId j : user.keySet()) { 
  101.       for (ItemId k : mDiffMatrix.keySet()) { 
  102.         try { 
  103.         float newval = ( mDiffMatrix.get(k).get(j).floatValue() + user.get(j).floatValue() ) * mFreqMatrix.get(k).get(j).intValue(); 
  104.         predictions.put(k, predictions.get(k)+newval); 
  105.         frequencies.put(k, frequencies.get(k)+mFreqMatrix.get(k).get(j).intValue()); 
  106.         } catch(NullPointerException e) {} 
  107.       } 
  108.     } 
  109.     HashMap<ItemId,Float> cleanpredictions = new HashMap<ItemId,Float>(); 
  110.     for (ItemId j : predictions.keySet()) { 
  111.         if (frequencies.get(j)>0) { 
  112.           cleanpredictions.put(j, predictions.get(j).floatValue()/frequencies.get(j).intValue()); 
  113.         } 
  114.     } 
  115.     for (ItemId j : user.keySet()) { 
  116.          cleanpredictions.put(j,user.get(j)); 
  117.     } 
  118.     return cleanpredictions; 
  119.   } 
  120.    
  121.   /** 
  122.   * Based on existing data, and not using weights, 
  123.   * try to predict all missing ratings. 
  124.   * The trick to make this more scalable is to consider 
  125.   * only mDiffMatrix entries having a large  (>1) mFreqMatrix 
  126.   * entry. 
  127.   */ 
  128.   public Map<ItemId,Float> weightlesspredict(Map<ItemId,Float> user) { 
  129.     HashMap<ItemId,Float> predictions = new HashMap<ItemId,Float>(); 
  130.     HashMap<ItemId,Integer> frequencies = new HashMap<ItemId,Integer>(); 
  131.     for (ItemId j : mDiffMatrix.keySet()) { 
  132.       predictions.put(j,0.0f); 
  133.       frequencies.put(j,0); 
  134.     } 
  135.     for (ItemId j : user.keySet()) { 
  136.       for (ItemId k : mDiffMatrix.keySet()) { 
  137.         //System.out.println("Average diff between "+j+" and "+ k + " is "+mDiffMatrix.get(k).get(j).floatValue()+" with n = "+mFreqMatrix.get(k).get(j).floatValue()); 
  138.         float newval = ( mDiffMatrix.get(k).get(j).floatValue() + user.get(j).floatValue() ) ; 
  139.         predictions.put(k, predictions.get(k)+newval); 
  140.       } 
  141.     } 
  142.     for (ItemId j : predictions.keySet()) { 
  143.         predictions.put(j, predictions.get(j).floatValue()/user.size()); 
  144.     } 
  145.     for (ItemId j : user.keySet()) { 
  146.       predictions.put(j,user.get(j)); 
  147.     } 
  148.     return predictions; 
  149.   } 
  150.  
  151.  
  152.   public void printData() { 
  153.         for(UserId user : mData.keySet()) { 
  154.           System.out.println(user); 
  155.           print(mData.get(user)); 
  156.         } 
  157.         for (int i=0; i<mAllItems.length; i++) { 
  158.             System.out.print("\n" + mAllItems[i] + ":"); 
  159.             printMatrixes(mDiffMatrix.get(mAllItems[i]), mFreqMatrix.get(mAllItems[i])); 
  160.         } 
  161.       } 
  162.  
  163.     private void printMatrixes(Map<ItemId,Float> ratings, 
  164.                 Map<ItemId,Integer> frequencies) {   
  165.             for (int j=0; j<mAllItems.length; j++) { 
  166.                 System.out.format("%10.3f", ratings.get(mAllItems[j])); 
  167.                 System.out.print(" "); 
  168.                 System.out.format("%10d", frequencies.get(mAllItems[j])); 
  169.             } 
  170.         System.out.println(); 
  171.     } 
  172.    
  173.   public static void print(Map<ItemId,Float> user) { 
  174.     for (ItemId j : user.keySet()) { 
  175.       System.out.println(" "+ j+ " --> "+user.get(j).floatValue()); 
  176.     } 
  177.   } 
  178.    
  179.   public void buildDiffMatrix() { 
  180.     mDiffMatrix = new HashMap<ItemId,Map<ItemId,Float>>(); 
  181.     mFreqMatrix = new HashMap<ItemId,Map<ItemId,Integer>>(); 
  182.     // first iterate through users 
  183.     for(Map<ItemId,Float> user : mData.values()) { 
  184.       // then iterate through user data 
  185.       for(Map.Entry<ItemId,Float> entry: user.entrySet()) { 
  186.         if(!mDiffMatrix.containsKey(entry.getKey())) { 
  187.           mDiffMatrix.put(entry.getKey(), new HashMap<ItemId,Float>()); 
  188.           mFreqMatrix.put(entry.getKey(), new HashMap<ItemId,Integer>()); 
  189.         } 
  190.         for(Map.Entry<ItemId,Float> entry2: user.entrySet()) { 
  191.           int oldcount = 0; 
  192.           if(mFreqMatrix.get(entry.getKey()).containsKey(entry2.getKey())) 
  193.             oldcount = mFreqMatrix.get(entry.getKey()).get(entry2.getKey()).intValue(); 
  194.           float olddiff = 0.0f; 
  195.           if(mDiffMatrix.get(entry.getKey()).containsKey(entry2.getKey())) 
  196.             olddiff = mDiffMatrix.get(entry.getKey()).get(entry2.getKey()).floatValue(); 
  197.           float observeddiff = entry.getValue() - entry2.getValue(); 
  198.           mFreqMatrix.get(entry.getKey()).put(entry2.getKey(),oldcount + 1); 
  199.           mDiffMatrix.get(entry.getKey()).put(entry2.getKey(),olddiff+observeddiff);           
  200.         } 
  201.       } 
  202.     } 
  203.     for (ItemId j : mDiffMatrix.keySet()) { 
  204.       for (ItemId i : mDiffMatrix.get(j).keySet()) { 
  205.         float oldvalue = mDiffMatrix.get(j).get(i).floatValue(); 
  206.         int count = mFreqMatrix.get(j).get(i).intValue(); 
  207.         mDiffMatrix.get(j).put(i,oldvalue/count); 
  208.       } 
  209.     } 
  210.   } 
  211. } 
  212.  
  213. class UserId  { 
  214.   String content; 
  215.   public UserId(String s) { 
  216.     content = s; 
  217.   } 
  218.    
  219.   public int hashCode() { return content.hashCode();} 
  220.   public String toString() { return content; } 
  221. } 
  222. class ItemId  { 
  223.   String content; 
  224.   public ItemId(String s) { 
  225.     content = s; 
  226.   } 
  227.   public int hashCode() { return content.hashCode();} 
  228.   public String toString() { return content; } 
  229. } 

 

Python：

  1. # Copyright 2006 Bryan O'Sullivan <bos@serpentine.com>. 
  2. # 
  3. # This software may be used and distributed according to the terms 
  4. # of the GNU General Public License, version 2 or later, which is 
  5. # incorporated herein by reference. 
  6.  
  7. class SlopeOne(object): 
  8.     def __init__(self): 
  9.         self.diffs = {} 
  10.         self.freqs = {} 
  11.  
  12.     def predict(self, userprefs): 
  13.         preds, freqs = {}, {} 
  14.         for item, rating in userprefs.iteritems(): 
  15.             for diffitem, diffratings in self.diffs.iteritems(): 
  16.                 try: 
  17.                     freq = self.freqs[diffitem][item] 
  18.                 except KeyError: 
  19.                     continue 
  20.                 preds.setdefault(diffitem, 0.0) 
  21.                 freqs.setdefault(diffitem, 0) 
  22.                 preds[diffitem] += freq * (diffratings[item] + rating) 
  23.                 freqs[diffitem] += freq 
  24.         return dict([(item, value / freqs[item]) 
  25.                      for item, value in preds.iteritems() 
  26.                      if item not in userprefs and freqs[item] > 0]) 
  27.  
  28.     def update(self, userdata): 
  29.         for ratings in userdata.itervalues(): 
  30.             for item1, rating1 in ratings.iteritems(): 
  31.                 self.freqs.setdefault(item1, {}) 
  32.                 self.diffs.setdefault(item1, {}) 
  33.                 for item2, rating2 in ratings.iteritems(): 
  34.                     self.freqs[item1].setdefault(item2, 0) 
  35.                     self.diffs[item1].setdefault(item2, 0.0) 
  36.                     self.freqs[item1][item2] += 1 
  37.                     self.diffs[item1][item2] += rating1 - rating2 
  38.         for item1, ratings in self.diffs.iteritems(): 
  39.             for item2 in ratings: 
  40.                 ratings[item2] /= self.freqs[item1][item2] 
  41.  
  42. if __name__ == '__main__': 
  43.     userdata = dict( 
  44.         alice=dict(squid=1.0, 
  45.                    cuttlefish=0.5, 
  46.                    octopus=0.2), 
  47.         bob=dict(squid=1.0, 
  48.                  octopus=0.5, 
  49.                  nautilus=0.2), 
  50.         carole=dict(squid=0.2, 
  51.                     octopus=1.0, 
  52.                     cuttlefish=0.4, 
  53.                     nautilus=0.4), 
  54.         dave=dict(cuttlefish=0.9, 
  55.                   octopus=0.4, 
  56.                   nautilus=0.5), 
  57.         ) 
  58.     s = SlopeOne() 
  59.     s.update(userdata) 
  60.     print s.predict(dict(squid=0.4)) 

 

 =-========================== 延伸文章===========================

来源 ： http://my.donews.com/clickstone/2006/10/16/fktEQWUckzvGDyfjugcqcJjkaDpdjemooGTf/

 

本文是关于推荐系统的系列研究文章之一，其他内容将陆续发布。这些内容，大多数来自我在2004年底完成的一篇项目方案建议书。放在这里，抛砖引玉，供大家讨论之用。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

在推荐系统简介中，我们给出了推荐系统的一般框架。很明显，推荐方法是整个推荐系统中最核心、最关键的部分，很大程度上决定了推荐系统性能的优劣。目前，主要的推荐方法包括：基于内容推荐、协同过滤推荐、基于关联规则推荐、基于效用推荐、基于知识推荐和组合推荐。

一、基于内容推荐

基于内容的推荐（Content-based Recommendation）是信息过滤技术的延续与发展，它是建立在项目的内容信息上作出推荐的，而不需要依据用户对项目的评价意见，更多地需要用机 器学习的方法从关于内容的特征描述的事例中得到用户的兴趣资料。在基于内容的推荐系统中，项目或对象是通过相关的特征的属性来定义，系统基于用户评价对象 的特征，学习用户的兴趣，考察用户资料与待预测项目的相匹配程度。用户的资料模型取决于所用学习方法，常用的有决策树、神经网络和基于向量的表示方法等。 基于内容的用户资料是需要有用户的历史数据，用户资料模型可能随着用户的偏好改变而发生变化。

基于内容推荐方法的优点是：
 1）不需要其它用户的数据，没有冷开始问题和稀疏问题。
 2）能为具有特殊兴趣爱好的用户进行推荐。
 3）能推荐新的或不是很流行的项目，没有新项目问题。
 4）通过列出推荐项目的内容特征，可以解释为什么推荐那些项目。
 5）已有比较好的技术，如关于分类学习方面的技术已相当成熟。

缺点是要求内容能容易抽取成有意义的特征，要求特征内容有良好的结构性，并且用户的口味必须能够用内容特征形式来表达，不能显式地得到其它用户的判断情况。

二、协同过滤推荐

协同过滤推荐（Collaborative Filtering Recommendation）技术是推荐系统中应用最早和最为成功的技术之一。它一般采用最近邻技术，利用用户的历史喜好信息计算用户之间的距离，然后 利用目标用户的最近邻居用户对商品评价的加权评价值来预测目标用户对特定商品的喜好程度，系统从而根据这一喜好程度来对目标用户进行推荐。协同过滤最大优 点是对推荐对象没有特殊的要求，能处理非结构化的复杂对象，如音乐、电影。

协同过滤是基于这样的假设：为一用户找到他真正感兴趣的内容的好方法是首先找到与此用户有相似兴趣的其他用户，然后将他们感兴趣的内容推荐给此用 户。其基本思想非常易于理解，在日常生活中，我们往往会利用好朋友的推荐来进行一些选择。协同过滤正是把这一思想运用到电子商务推荐系统中来，基于其他用 户对某一内容的评价来向目标用户进行推荐。

基于协同过滤的推荐系统可以说是从用户的角度来进行相应推荐的，而且是自动的，即用户获得的推荐是系统从购买模式或浏览行为等隐式获得的，不需要用户努力地找到适合自己兴趣的推荐信息，如填写一些调查表格等。

和基于内容的过滤方法相比，协同过滤具有如下的优点：
1） 能够过滤难以进行机器自动内容分析的信息，如艺术品，音乐等。
2） 共享其他人的经验，避免了内容分析的不完全和不精确，并且能够基于一些复杂的，难以表述的概念（如信息质量、个人品味）进行过滤。
3） 有推荐新信息的能力。可以发现内容上完全不相似的信息，用户对推荐信息的内容事先是预料不到的。这也是协同过滤和基于内容的过滤一个较大的差别，基于内容的过滤推荐很多都是用户本来就熟悉的内容，而协同过滤可以发现用户潜在的但自己尚未发现的兴趣偏好。
4） 能够有效的使用其他相似用户的反馈信息，较少用户的反馈量，加快个性化学习的速度。

虽然协同过滤作为一种典型的推荐技术有其相当的应用，但协同过滤仍有许多的问题需要解决。最典型的问题有稀疏问题（Sparsity）和可扩展问题（Scalability）。

三、基于关联规则推荐

基于关联规则的推荐（Association Rule-based Recommendation）是以关联规则为基础，把已购商品作为规则头，规则体为推荐对象。关联规则挖掘可以发现不同商品在销售过程中的相关性，在零 售业中已经得到了成功的应用。管理规则就是在一个交易数据库中统计购买了商品集X的交易中有多大比例的交易同时购买了商品集Y，其直观的意义就是用户在购 买某些商品的时候有多大倾向去购买另外一些商品。比如购买牛奶的同时很多人会同时购买面包。

算法的第一步关联规则的发现最为关键且最耗时，是算法的瓶颈，但可以离线进行。其次，商品名称的同义性问题也是关联规则的一个难点。

四、基于效用推荐

基于效用的推荐（Utility-based Recommendation）是建立在对用户使用项目的效用情况上计算的，其核心问题是怎么样为每一个用户去创建一个效用函数，因此，用户资料模型很大 程度上是由系统所采用的效用函数决定的。基于效用推荐的好处是它能把非产品的属性，如提供商的可靠性（Vendor Reliability）和产品的可得性（Product Availability）等考虑到效用计算中。

五、基于知识推荐

基于知识的推荐（Knowledge-based Recommendation）在某种程度是可以看成是一种推理（Inference）技术，它不是建立在用户需要和偏好基础上推荐的。基于知识的方法因 它们所用的功能知识不同而有明显区别。效用知识（Functional Knowledge）是一种关于一个项目如何满足某一特定用户的知识，因此能解释需要和推荐的关系，所以用户资料可以是任何能支持推理的知识结构，它可以 是用户已经规范化的查询，也可以是一个更详细的用户需要的表示。

六、组合推荐

由于各种推荐方法都有优缺点，所以在实际中，组合推荐（Hybrid Recommendation）经常被采用。研究和应用最多的是内容推荐和协同过滤推荐的组合。最简单的做法就是分别用基于内容的方法和协同过滤推荐方法 去产生一个推荐预测结果，然后用某方法组合其结果。尽管从理论上有很多种推荐组合方法，但在某一具体问题中并不见得都有效，组合推荐一个最重要原则就是通 过组合后要能避免或弥补各自推荐技术的弱点。

在组合方式上，有研究人员提出了七种组合思路：
1）加权（Weight）：加权多种推荐技术结果。
2）变换（Switch）：根据问题背景和实际情况或要求决定变换采用不同的推荐技术。
3）混合（Mixed）：同时采用多种推荐技术给出多种推荐结果为用户提供参考。
4）特征组合（Feature combination）：组合来自不同推荐数据源的特征被另一种推荐算法所采用。
5）层叠（Cascade）：先用一种推荐技术产生一种粗糙的推荐结果，第二种推荐技术在此推荐结果的基础上进一步作出更精确的推荐。
6）特征扩充（Feature augmentation）：一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中。
7）元级别（Meta-level）：用一种推荐方法产生的模型作为另一种推荐方法的输入。
七、主要推荐方法的对比

各种推荐方法都有其各自的优点和缺点，见表1。

表1 主要推荐方法对比
推荐方法 优点 缺点
基于内容推荐 推荐结果直观，容易解释；

 

不需要领域知识

 新用户问题；

 

复杂属性不好处理；

要有足够数据构造分类器
协同过滤推荐 新异兴趣发现、不需要领域知识；

 

随着时间推移性能提高；

推荐个性化、自动化程度高；

能处理复杂的非结构化对象

 稀疏问题；

 

可扩展性问题；

新用户问题；

质量取决于历史数据集；

系统开始时推荐质量差；
基于规则推荐 能发现新兴趣点；

 

不要领域知识

 规则抽取难、耗时；

 

产品名同义性问题；

个性化程度低；
基于效用推荐 无冷开始和稀疏问题；

 

对用户偏好变化敏感；

能考虑非产品特性

 用户必须输入效用函数；

 

推荐是静态的，灵活性差；

属性重叠问题；
基于知识推荐 能把用户需求映射到产品上；

 

能考虑非产品属性

 知识难获得；

 

推荐是静态的

 

 

阅读更多...
Sql, Algorithms

Lita - SQLite Administration Tool (For AIR)

2008-11-11 9:31:52 开发者 抢沙发(0)

Dowload Here

 

Main Features

  • An administration tool for your AIR SQLite Database
  • Open, create, compact databases
  • Create, rename, delete, and empty tables
  • Create, rename and delete columns
  • Create, modify and delete records
  • Easily run your custom SQL statements
  • Create and delete indices
  •  

阅读更多...
My-X-Intend, Sql, Adobe-Front-End-Technology

SQL 中文三种排序方式

2008-9-12 9:52:55 开发者 抢沙发(1)
中文共有三种排序方式:
1.根据拼音排序
2.根据笔画排序
3.根据偏旁排序

系统的默认排序方式为拼音排序,可以通过修改nls_sort参数修改
alter session set nls_sort = SCHINESE_STROKE_M;


基础数据,以及数据表的结构
SQL> select * from test;
NAME
--------------------------------------------------------------------------------
忠
周
作
就
一
不
众
仁
已选择8行。

 

使用拼音排序
SQL> select * from test order by nlssort(name,'NLS_SORT=SCHINESE_PINYIN_M');
NAME
--------------------------------------------------------------------------------
不
就
仁
一
忠
众
周
作
已选择8行。


使用笔画排序
SQL> select * from test order by nlssort(name,'NLS_SORT=SCHINESE_STROKE_M');
NAME
--------------------------------------------------------------------------------
一
不
仁
众
作
周
忠
就
已选择8行。
 

使用偏旁部首排序
SQL> select * from test order by nlssort(name,'NLS_SORT=SCHINESE_RADICAL_M');
NAME
--------------------------------------------------------------------------------
一
不
仁
众
作
周
就
忠
已选择8行。

系统的默认排序方式
19:04:04 SQL> select * from test order by test;
SQL> select * from test order by name;
NAME
--------------------------------------------------------------------------------
不
就
仁
一
忠
众
周
作
已选择8行。
阅读更多...
Sql, My-X-Intend

MySQL-Python

2008-8-15 0:21:32 开发者 抢沙发(0)

http://mysql-python.sourceforge.net/

 记录下

http://mysql-python.sourceforge.net/

 记录下

 

  1. #!/usr/bin/env python  
  2. # -*-coding:UTF-8-*-#这一句告诉python用UTF-8编码  
  3. #=========================================================================  
  4. #  
  5. # NAME: Python MySQL test  
  6. #  
  7. # AUTHOR: benyur  
  8. # DATE  : 2004-12-28  
  9. #  
  10. # COMMENT: 这是一个python连接mysql的例子  
  11. #  
  12. #=========================================================================   
  13. """  
  14.  ***** This is a MySQL test *****  
  15.    
  16.  select:  
  17.   conn=Connection()  
  18.   conn.select_db('test')  
  19.   cur=conn.cursor()  
  20.   cur.execute('select * from user')  
  21.   cur.scroll(0)  
  22.   row1=cur.fetchone()  
  23.   row1[0]  
  24.   row1[1]  
  25.   row1[2]  
  26.     
  27.  insert:  
  28.   cur.execute('insert into user (name,passwd) values('benyur','12345')')  
  29.   cur.insert_id()  
  30.     
  31.  update:  
  32.   cur.execute('update user set passwd='123456' where name='benyur'')  
  33.     
  34.  delete:  
  35.   cur.execute('delete from user where id=2')  
  36.    
  37.  **********************************  
  38. """ 
  39.  
  40. from MySQLdb import *  
  41.  
  42. def conn():  
  43.  conn=Connection()  
  44.  conn.select_db('test')  
  45.  cur=conn.cursor()  
  46.  cur.execute('select * from user')  
  47.  cur.scroll(0)  
  48.  row1=cur.fetchone()  
  49.  row1[0]  
  50.  row1[1]  
  51.  row1[2]  
  52.  
  53. def usage():  
  54.  print __doc__  
  55.  
  56. if __name__=='__main__':  
  57.  usage()  
阅读更多...
My-X-Intend, OpenSource, Sql

.Net连接同服务器下多个Mysql问题终于解决

2008-8-5 23:52:10 开发者 抢沙发(0)

哎，我太逊了，以致以为是IPAdd:Port形式的............糗字怎一个字了得！！！

PS:我的MyDotnet连接库是5.2的........

 

以下为[转]，标记以记录。。。。  红色的为本次解决方式...............
 

[数据库连接字符串] MySQL 连接字符串
MyODBC
 
MyODBC 2.50 本地数据库
Driver={mySQL};Server=localhost;Option=16834;Database=myDataBase;
 
   
MyODBC 2.50 远程数据库 
Driver={mySQL};Server=myServerAddress;Port=3306;Option=131072;Stmt=; Database=myDataBase;Uid=myUsername;Pwd=myPassword;
 
   
MyODBC 3.51 本地数据库
Driver={MySQL ODBC 3.51 Driver};Server=localhost;Database=myDataBase; User=myUsername;Password=myPassword;Option=3;
 
   
MyODBC 3.51 远程数据库
Driver={MySQL ODBC 3.51 Driver};Server=data.domain.com;Port=3306;Database=myDataBase;User=myUsername; Password=myPassword;Option=3;
 
   
OLE DB, OleDbConnection (.NET)
 
标准
Provider=MySQLProv;Data Source=mydb;User Id=myUsername;Password=myPassword;
 
   
Connector/Net 1.0 (.NET)
 
标准
Server=myServerAddress;Database=myDataBase;Uid=myUsername;Pwd=myPassword;
 
默认端口号是3306.  
  
指定端口号
Server=myServerAddress;Port=1234;Database=myDataBase;Uid=myUsername;Pwd=myPassword; 
 
   
命名管道
Server=myServerAddress;Port=-1;Database=myDataBase;Uid=myUsername;Pwd=myPassword;
 
如果端口是-1，意思是告诉驱动程序使用命名管道网络协议来连接数据库。
  
MySqlConnection (.NET)
 
eInfoDesigns.dbProvider
Data Source=myServerAddress;Database=myDataBase;User ID=myUsername;Password=myPassword;Command Logging=false;
 
   
SevenObjects MySqlClient (.NET)
 
标准
Host=myServerAddress;UserName=myUsername;Password=myPassword;Database=myDataBase;
 
   
Core Labs MySQLDirect (.NET)
 
标准
User ID=root;Password=myPassword;Host=localhost;Port=3306;Database=myDataBase; Direct=true;Protocol=TCP;Comdivss=false;Pooling=true;Min Pool Size=0;Max Pool Size=100;Connection Lifetime=0;
 
   
MySQLDriverCS (.NET)
 
标准
Location=myServerAddress;Data Source=myDataBase;UserID=myUsername;Password=myPassword;Port=3306;Extended Properties=""""; 
 
 

阅读更多...
My-X-Intend, Sql

[转]数据库表地址数据（中国地区）

2008-5-30 21:32:03 软件 抢沙发(0)
阅读更多...
Sql, code

SQLite B+树实现代码

2008-5-13 2:10:49 开发者 抢沙发(0)

 from: http://www.sqlite.com.cn/MySqlite/6/373.Html

C++代码
  1. /* btrees.h */    
  2. /*   
  3. * 平衡多路树的一种重要方案。   
  4. * 在 1970 年由 R. Bayer 和 E. McCreight 发明。   
  5. */    
  6. #define M 1    
  7. /* B 树的阶，即非根节点中键的最小数目。   
  8. * 有些人把阶定义为非根节点中子树的最大数目。   
  9. */    
  10. typedef int typekey;    
  11. typedef struct btnode { /* B-Tree 节点 */    
  12. int d; /* 节点中键的数目 */    
  13. typekey k[2*M]; /* 键 */    
  14. char *v[2*M]; /* 值 */    
  15. struct btnode *p[2*M+1]; /* 指向子树的指针 */    
  16. } node, *btree;    
  17. /*   
  18. * 每个键的左子树中的所有的键都小于这个键，   
  19. * 每个键的右子树中的所有的键都大于等于这个键。   
  20. * 叶子节点中的每个键都没有子树。   
  21. */    
  22.   
  23. /* 当 M 等于 1 时也称为 2-3 树   
  24. * +----+----+   
  25. * | k0 | k1 |   
  26. * +-+----+----+---   
  27. * | p0 | p1 | p2 |   
  28. * +----+----+----+   
  29. */    
  30. extern int btree_disp; /* 查找时找到的键在节点中的位置 */    
  31. extern char * InsValue; /* 与要插的键相对应的值 */    
  32.   
  33. extern btree search(typekey, btree);    
  34. extern btree insert(typekey,btree);    
  35. extern btree delete(typekey,btree);    
  36. extern int height(btree);    
  37. extern int count(btree);    
  38. extern double payload(btree);    
  39. extern btree deltree(btree);    
  40. /* end of btrees.h */    
  41.   
  42. /*******************************************************/  
C++代码
  1. /*******************************************************/    
  2.   
  3. /* btrees.c */    
  4. #include    
  5. #include    
  6. #include "btrees.h"    
  7.   
  8. btree search(typekey, btree);    
  9. btree insert(typekey,btree);    
  10. btree delete(typekey,btree);    
  11. int height(btree);    
  12. int count(btree);    
  13. double payload(btree);    
  14. btree deltree(btree);    
  15.   
  16. static void InternalInsert(typekey, btree);    
  17. static void InsInNode(btree, int);    
  18. static void SplitNode(btree, int);    
  19. static btree NewRoot(btree);    
  20.   
  21. static void InternalDelete(typekey, btree);    
  22. static void JoinNode(btree, int);    
  23. static void MoveLeftNode(btree t, int);    
  24. static void MoveRightNode(btree t, int);    
  25. static void DelFromNode(btree t, int);    
  26. static btree FreeRoot(btree);    
  27.   
  28. static btree delall(btree);    
  29. static void Error(int,typekey);    
  30.   
  31. int btree_disp; /* 查找时找到的键在节点中的位置 */    
  32. char * InsValue = NULL; /* 与要插的键相对应的值 */    
  33. static int flag; /* 节点增减标志 */    
  34. static int btree_level = 0; /* 多路树的高度 */    
  35. static int btree_count = 0; /* 多路树的键总数 */    
  36. static int node_sum = 0; /* 多路树的节点总数 */    
  37. static int level; /* 当前访问的节点所处的高度 */    
  38. static btree NewTree; /* 在节点分割的时候指向新建的节点 */    
  39. static typekey InsKey; /* 要插入的键 */    
  40.   
  41. btree search(typekey key, btree t)    
  42. {    
  43. int i,j,m;    
  44. level=btree_level-1;    
  45. while (level >= 0){    
  46. for(i=0, j=t->d-1; i t->k[m])?(i=m+1):(j=m));    
  47. if (key == t->k){    
  48. btree_disp = i;    
  49. return t;    
  50. }    
  51. if (key > t->k) /* i == t->d-1 时有可能出现 */    
  52. i++;    
  53. t = t->p;    
  54. level--;    
  55. }    
  56. return NULL;    
  57. }    
  58.   
  59. btree insert(typekey key, btree t)    
  60. {    
  61. level=btree_level;    
  62. InternalInsert(key, t);    
  63. if (flag == 1) /* 根节点满之后，它被分割成两个半满节点 */    
  64. t=NewRoot(t); /* 树的高度增加 */    
  65. return t;    
  66. }    
  67.   
  68. void InternalInsert(typekey key, btree t)    
  69. {    
  70. int i,j,m;    
  71.   
  72. level--;    
  73. if (level < 0){ /* 到达了树的底部: 指出要做的插入 */    
  74. NewTree = NULL; /* 这个键没有对应的子树 */    
  75. InsKey = key; /* 导致底层的叶子节点增加键值+空子树对 */    
  76. btree_count++;    
  77. flag = 1; /* 指示上层节点把返回的键插入其中 */    
  78. return;    
  79. }    
  80. for(i=0, j=t->d-1; i t->k[m])?(i=m+1):(j=m));    
  81. if (key == t->k) {    
  82. Error(1,key); /* 键已经在树中 */    
  83. flag = 0;    
  84. return;    
  85. }    
  86. if (key > t->k) /* i == t->d-1 时有可能出现 */    
  87. i++;    
  88. InternalInsert(key, t->p);    
  89.   
  90. if (flag == 0)    
  91. return;    
  92. /* 有新键要插入到当前节点中 */    
  93. if (t->d < 2*M) {/* 当前节点未满 */    
  94. InsInNode(t, i); /* 把键值+子树对插入当前节点中 */    
  95. flag = 0; /* 指示上层节点没有需要插入的键值+子树，插入过程结束 */    
  96. }    
  97. else /* 当前节点已满，则分割这个页面并把键值+子树对插入当前节点中 */    
  98. SplitNode(t, i); /* 继续指示上层节点把返回的键值+子树插入其中 */    
  99. }    
  100.   
  101. /*   
  102. * 把一个键和对应的右子树插入一个节点中   
  103. */    
  104. void InsInNode(btree t, int d)    
  105. {    
  106. int i;    
  107. /* 把所有大于要插入的键值的键和对应的右子树右移 */    
  108. for(i = t->d; i > d; i--){    
  109. t->k = t->k[i-1];    
  110. t->v = t->v[i-1];    
  111. t->p[i+1] = t->p;    
  112. }    
  113. /* 插入键和右子树 */    
  114. t->k = InsKey;    
  115. t->p[i+1] = NewTree;    
  116. t->v = InsValue;    
  117. t->d++;    
  118. }    
  119. /*   
  120. * 前件是要插入一个键和对应的右子树，并且本节点已经满   
  121. * 导致分割这个节点，插入键和对应的右子树，   
  122. * 并向上层返回一个要插入键和对应的右子树   
  123. */    
  124. void SplitNode(btree t, int d)    
  125. {    
  126. int i,j;    
  127. btree temp;    
  128. typekey temp_k;    
  129. char *temp_v;    
  130. /* 建立新节点 */    
  131. temp = (btree)malloc(sizeof(node));    
  132. /*   
  133. * +---+--------+-----+-----+--------+-----+   
  134. * | 0 | ...... | M | M+1 | ...... |2*M-1|   
  135. * +---+--------+-----+-----+--------+-----+   
  136. * |<- M+1 ->|<- M-1 ->|   
  137. */    
  138. if (d > M) { /* 要插入当前节点的右半部分 */    
  139. /* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中,   
  140. * 并且为要插入的键值+子树空出位置 */    
  141. for(i=2*M-1,j=M-1; i>=d; i--,j--) {    
  142. temp->k[j] = t->k;    
  143. temp->v[j] = t->v;    
  144. temp->p[j+1] = t->p[i+1];    
  145. }    
  146. for(i=d-1,j=d-M-2; j>=0; i--,j--) {    
  147. temp->k[j] = t->k;    
  148. temp->v[j] = t->v;    
  149. temp->p[j+1] = t->p[i+1];    
  150. }    
  151. /* 把节点的最右子树转移成新节点的最左子树 */    
  152. temp->p[0] = t->p[M+1];    
  153. /* 在新节点中插入键和右子树 */    
  154. temp->k[d-M-1] = InsKey;    
  155. temp->p[d-M] = NewTree;    
  156. temp->v[d-M-1] = InsValue;    
  157. /* 设置要插入上层节点的键和值 */    
  158. InsKey = t->k[M];    
  159. InsValue = t->v[M];    
  160.   
  161. }    
  162. else { /* d <= M */    
  163. /* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */    
  164. for(i=2*M-1,j=M-1; j>=0; i--,j--) {    
  165. temp->k[j] = t->k;    
  166. temp->v[j] = t->v;    
  167. temp->p[j+1] = t->p[i+1];    
  168. }    
  169. if (d == M) /* 要插入当前节点的正中间 */    
  170. /* 把要插入的子树作为新节点的最左子树 */    
  171. temp->p[0] = NewTree;    
  172. /* 直接把要插入的键和值返回给上层节点 */    
  173. else { /* (d /* 把节点当前的最右子树转移成新节点的最左子树 */    
  174. temp->p[0] = t->p[M];    
  175. /* 保存要插入上层节点的键和值 */    
  176. temp_k = t->k[M-1];    
  177. temp_v = t->v[M-1];    
  178. /* 把所有大于要插入的键值的键和对应的右子树右移 */    
  179. for(i=M-1; i>d; i--) {    
  180. t->k = t->k[i-1];    
  181. t->v = t->v[i-1];    
  182. t->p[i+1] = t->p;    
  183. }    
  184. /* 在节点中插入键和右子树 */    
  185. t->k[d] = InsKey;    
  186. t->p[d+1] = NewTree;    
  187. t->v[d] = InsValue;    
  188. /* 设置要插入上层节点的键和值 */    
  189. InsKey = temp_k;    
  190. InsValue = temp_v;    
  191. }    
  192. }    
  193. t->d =M;    
  194. temp->d = M;    
  195. NewTree = temp;    
  196. node_sum++;    
  197. }    
  198.   
  199. btree delete(typekey key, btree t)    
  200. {    
  201. level=btree_level;    
  202. InternalDelete(key, t);    
  203. if (t->d == 0)    
  204. /* 根节点的子节点合并导致根节点键的数目随之减少，   
  205. * 当根节点中没有键的时候，只有它的最左子树可能非空 */    
  206. t=FreeRoot(t);    
  207. return t;    
  208. }    
  209.   
  210. void InternalDelete(typekey key, btree t)    
  211. {    
  212. int i,j,m;    
  213. btree l,r;    
  214. int lvl;    
  215.   
  216. level--;    
  217. if (level < 0) {    
  218. Error(0,key); /* 在整个树中未找到要删除的键 */    
  219. flag = 0;    
  220. return;    
  221. }    
  222. for(i=0, j=t->d-1; i t->k[m])?(i=m+1):(j=m));    
  223. if (key == t->k) { /* 找到要删除的键 */    
  224. if (t->v != NULL)    
  225. free(t->v); /* 释放这个节点包含的值 */    
  226. if (level == 0) { /* 有子树为空则这个键位于叶子节点 */    
  227. DelFromNode(t,i);    
  228. btree_count--;    
  229. flag = 1;    
  230. /* 指示上层节点本子树的键数量减少 */    
  231. return;    
  232. } else { /* 这个键位于非叶节点 */    
  233. lvl = level-1;    
  234. /* 找到前驱节点 */    
  235. r = t->p;    
  236. while (lvl > 0) {    
  237. r = r->p[r->d];    
  238. lvl--;    
  239. }    
  240. t->k=r->k[r->d-1];    
  241. t->v=r->v[r->d-1];    
  242. r->v[r->d-1]=NULL;    
  243. key = r->k[r->d-1];    
  244. }    
  245. }    
  246. else if (key > t->k) /* i == t->d-1 时有可能出现 */    
  247. i++;    
  248. InternalDelete(key,t->p);    
  249. /* 调整平衡 */    
  250. if (flag == 0)    
  251. return;    
  252. if (t->p->d < M) {    
  253. if (i == t->d) /* 在最右子树中发生了删除 */    
  254. i--; /* 调整最右键的左右子树平衡 */    
  255. l = t->p;    
  256. r = t->p[i+1];    
  257. if (r->d > M)    
  258. MoveLeftNode(t,i);    
  259. else if(l->d > M)    
  260. MoveRightNode(t,i);    
  261. else {    
  262. JoinNode(t,i);    
  263. /* 继续指示上层节点本子树的键数量减少 */    
  264. return;    
  265. }    
  266. flag = 0;    
  267. /* 指示上层节点本子树的键数量没有减少，删除过程结束 */    
  268. }    
  269. }    
  270.   
  271. /*   
  272. * 合并一个节点的某个键对应的两个子树   
  273. */    
  274. void JoinNode(btree t, int d)    
  275. {    
  276. btree l,r;    
  277. int i,j;    
  278. l = t->p[d];    
  279. r = t->p[d+1];    
  280.   
  281. /* 把这个键下移到它的左子树 */    
  282. l->k[l->d] = t->k[d];    
  283. l->v[l->d] = t->v[d];    
  284. /* 把右子树中的所有键值和子树转移到左子树 */    
  285. for (j=r->d-1,i=l->d+r->d; j >= 0 ; j--,i--) {    
  286. l->k = r->k[j];    
  287. l->v = r->v[j];    
  288. l->p = r->p[j];    
  289. }    
  290. l->p[l->d+r->d+1] = r->p[r->d];    
  291. l->d += r->d+1;    
  292. /* 释放右子树的节点 */    
  293. free(r);    
  294. /* 把这个键右边的键和对应的右子树左移 */    
  295. for (i=d; i < t->d-1; i++) {    
  296. t->k = t->k[i+1];    
  297. t->v = t->v[i+1];    
  298. t->p[i+1] = t->p[i+2];    
  299. }    
  300. t->d--;    
  301. node_sum--;    
  302. }    
  303. /*   
  304. * 从一个键的右子树向左子树转移一些键，使两个子树平衡   
  305. */    
  306. void MoveLeftNode(btree t, int d)    
  307. {    
  308. btree l,r;    
  309. int m; /* 应转移的键的数目 */    
  310. int i,j;    
  311. l = t->p[d];    
  312. r = t->p[d+1];    
  313. m = (r->d - l->d)/2;    
  314.   
  315. /* 把这个键下移到它的左子树 */    
  316. l->k[l->d] = t->k[d];    
  317. l->v[l->d] = t->v[d];    
  318. /* 把右子树的最左子树转移成左子树的最右子树   
  319. * 从右子树向左子树移动 m-1 个键+子树对 */    
  320. for (j=m-2,i=l->d+m-1; j >= 0; j--,i--) {    
  321. l->k = r->k[j];    
  322. l->v = r->v[j];    
  323. l->p = r->p[j];    
  324. }    
  325. l->p[l->d+m] = r->p[m-1];    
  326. /* 把右子树的最左键提升到这个键的位置上 */    
  327. t->k[d] = r->k[m-1];    
  328. t->v[d] = r->v[m-1];    
  329. /* 把右子树中的所有键值和子树左移 m 个位置 */    
  330. r->p[0] = r->p[m];    
  331. for (i=0; id-m; i++) {    
  332. r->k = r->k[i+m];    
  333. r->v = r->v[i+m];    
  334. r->p = r->p[i+m];    
  335. }    
  336. r->p[r->d-m] = r->p[r->d];    
  337. l->d+=m;    
  338. r->d-=m;    
  339. }    
  340. /*   
  341. * 从一个键的左子树向右子树转移一些键，使两个子树平衡   
  342. */    
  343. void MoveRightNode(btree t, int d)    
  344. {    
  345. btree l,r;    
  346. int m; /* 应转移的键的数目 */    
  347. int i,j;    
  348. l = t->p[d];    
  349. r = t->p[d+1];    
  350.   
  351. m = (l->d - r->d)/2;    
  352. /* 把右子树中的所有键值和子树右移 m 个位置 */    
  353. r->p[r->d+m]=r->p[r->d];    
  354. for (i=r->d-1; i>=0; i--) {    
  355. r->k[i+m] = r->k;    
  356. r->v[i+m] = r->v;    
  357. r->p[i+m] = r->p;    
  358. }    
  359. /* 把这个键下移到它的右子树 */    
  360. r->k[m-1] = t->k[d];    
  361. r->v[m-1] = t->v[d];    
  362. /* 把左子树的最右子树转移成右子树的最左子树 */    
  363. r->p[m-1] = l->p[l->d];    
  364. /* 从左子树向右子树移动 m-1 个键+子树对 */    
  365. for (i=l->d-1,j=m-2; j>=0; j--,i--) {    
  366. r->k[j] = l->k;    
  367. r->v[j] = l->v;    
  368. r->p[j] = l->p;    
  369. }    
  370. /* 把左子树的最右键提升到这个键的位置上 */    
  371. t->k[d] = l->k;    
  372. t->v[d] = l->v;    
  373. l->d-=m;    
  374. r->d+=m;    
  375. }    
  376. /*   
  377. * 把一个键和对应的右子树从一个节点中删除   
  378. */    
  379. void DelFromNode(btree t, int d)    
  380. {    
  381. int i;    
  382. /* 把所有大于要删除的键值的键左移 */    
  383. for(i=d; i < t->d-1; i++) {    
  384. t->k = t->k[i+1];    
  385. t->v = t->v[i+1];    
  386. }    
  387. t->d--;    
  388. }    
  389. /*   
  390. * 建立有两个子树和一个键的根节点   
  391. */    
  392. btree NewRoot(btree t)    
  393. {    
  394. btree temp;    
  395. temp = (btree)malloc(sizeof(node));    
  396. temp->d = 1;    
  397. temp->p[0] = t;    
  398. temp->p[1] = NewTree;    
  399. temp->k[0] = InsKey;    
  400. temp->v[0] = InsValue;    
  401. btree_level++;    
  402. node_sum++;    
  403. return(temp);    
  404. }    
  405. /*   
  406. * 释放根节点，并返回它的最左子树   
  407. */    
  408. btree FreeRoot(btree t)    
  409. {    
  410. btree temp;    
  411. temp = t->p[0];    
  412. free(t);    
  413. btree_level--;    
  414. node_sum--;    
  415. return temp;    
  416. }    
  417.   
  418. void Error(int f,typekey key)    
  419. {    
  420. if (f)    
  421. printf("Btrees error: Insert %d! ",key);    
  422. else    
  423. printf("Btrees error: delete %d! ",key);    
  424. }    
  425.   
  426. int height(btree t)    
  427. {    
  428. return btree_level;    
  429. }    
  430.   
  431. int count(btree t)    
  432. {    
  433. return btree_count;    
  434. }    
  435. double payload(btree t)    
  436. {    
  437. if (node_sum==0)    
  438. return 1;    
  439. return (double)btree_count/(node_sum*(2*M));    
  440. }    
  441. btree deltree (btree t)    
  442. {    
  443. level=btree_level;    
  444. btree_level = 0;    
  445. return delall(t);    
  446.   
  447. }    
  448. btree delall(btree t)    
  449. {    
  450. int i;    
  451. level--;    
  452. if (level >= 0) {    
  453. for (i=0; i < t->d; i++)    
  454. if (t->v != NULL)    
  455. free(t->v);    
  456. if (level > 0)    
  457. for (i=0; i<= t->d ; i++)    
  458. t->p=delall(t->p);    
  459. free(t);    
  460. }    
  461. return NULL;    
  462. }    
  463.   
  464. /* end of btrees.c */   
阅读更多...
Sql, code

B+ 树的组织结构

2008-5-13 1:59:22 软件 抢沙发(0)

  

、B+树索引的总体结构
①B+树索引是一个多级索引，但是其结构不同于多级顺序索引；
②B+树索引采用平衡树结构，即每个叶结点到根的路径长度都相同；
③每个非叶结点有到n个子女，n对特定的树是固定的；
④B+树的所有结点结构都相同，它最多包含n-1个搜索码值K1、K2、…、Kn-1，以及n个指针P1、P2、…、Pn，每个结点中的搜索码值按次序存放，即如果i<j，那么Ki<Kj，如图8-3-1所示。
图8-3-1：B+树的结点结构 
2、B+树索引的叶结点
①指针Pi(i=1,2,…,n-1)指向具有搜索码值Ki的一个文件记录或一个指针（存储）桶，桶中的每个指针指向具有搜索码值Ki的一个文件记录。指针桶只在文件不按搜索码顺序物理存储时才使用。指针Pn具有特殊的作用；
②每个叶结点最多可有n-1个搜索码值，最少也要有个搜索码值。各个叶结点中搜索码值的范围互不相交。要使B+树索引成为稠密索引，数据文件中的各搜索码值都必须出现在某个叶结点中且只能出现一次；
③由于各叶结点按照所含的搜索码值有一个线性顺序，所以就可以利用各个叶结点的指针Pn将叶结点按搜索码顺序链接在一起。这种排序能够高效地对文件进行顺序处理，而B+树索引的其他结构能够高效地对文件进行随机处理，如图8-3-2所示。
图8-3-2：B+树索引的叶结点结构示例 
3、B+树索引的非叶结点
①B+树索引的非叶结点形成叶结点上的一个多级（稀疏）索引；
②非叶结点的结构和叶结点的结构相同，即含有能够存储n-1个搜索码值和n个指针的存储单元的数据结构。只不过非叶结点中的所有指针都指向树中的结点；
③如果一个非叶结点有m个指针，则≤m≤n。若m<n，则非叶结点中指针Pm之后的所有空闲空间作为预留空间，与叶结点的区别在于结点的最后一个指针Pm和Pn的位置与指向不同，如图8-3-3所示；
图8-3-3：B+树索引的非叶结点结构 
④在一个含有m个指针的非叶结点中，指针Pi(i=2,…,m-1)指向一棵子树，该子树的所有结点的搜索码值大于等于Ki-1而小于Ki。指针Pm指向子树中所含搜索码值大于等于Km-1的那一部分，而指针P1指向子树中所含搜索码值小于K1的那一部分，如图8-3-4所示。
图8-3-4：B+树索引的非叶结点中指针Pi的指向
4、B+树索引的根结点
①根结点的结构也与叶结点相同；
②根结点包含的指针数可以小于。但是，除非整棵树只有一个结点，否则根结点必须至少包含两个指针。图8-3-5给出一个B+树结构的示意图。
图8-3-5：account关系的B+树索引结构 

 

来源：http://www.sqlite.com.cn/MySqlite/6/373.Html 

阅读更多...
Sql
1/2, 10«‹12›»
系统公告
2010-07-23 升级至Roclog 5.0.2
文章分类
搜索
随机文章
最新评论
标签云集
My-X-Intend Experience Front-End-Technology Adobe-Front-End-Technology code Sql Rules Algorithms Settings Web-Technology
站点数据
文章数量: 220 篇
评论数量: 29 条
标签数量: 19 个
引用通告: 1 条
总访问数: 6873 次
友情链接

Powered by Roclog v5.0.2

Copyright © 2009-2010 X-Intend. All rights reserved.

浙ICP备09082105号