Beyond Search

最好走的路越走越难，最难走的路越走越容易！

推荐系统：关联规则(2)

Apriori Algorithm 是关联规则领域里最具影响力的基础算法。它是由 Rakesh Agrawal 在 1994 年提出的，详细的介绍在这里《Fast Algorithms for Mining Association Rules》。十几年过去了，不少学者围绕着 Apriori 进行了诸多改良。但与 1994 年相比，目前基于互联网的应用，数据量大了几十倍甚至是几百倍，因此，基于 Apriori 的算法逐渐暴露出其运算成本过高的问题。但不管怎样，对于大师及其做出的贡献，我们也只有高山仰止的份儿。

Apriori 是一种广度优先算法，通过多次扫描数据库来获取支持度大于最小支持度的频繁项集。它的理论基础是频繁项集的两个单调性原则：频繁项集的任一子集一定是频繁 的；非频繁项集的任一超集一定是非频繁的。晦涩的理论我这里就不多写了，有兴趣的可以去看论文。我把里面的例子给翻译一下，图文并茂，简明易懂。
某数据库 DB 里有 4 条事务记录，取最小支持度（min support）为 0.5，则计算频繁项集的过程如下：

TID Items
100 A, C, D
200 B, C, E
300 A, B, C, E
400 B, E
扫描DB
Itemset Support
{A} 2 (0.5)
{B} 3 (0.75)
{C} 3 (0.75)
{D} 1 (0.25)
{E} 3 (0.75)
取满足
最小支持度
项集
Itemset Support
{A} 2
{B} 3
{C} 3
{E} 3
Itemset
{A, B}
{A, C}
{A, E}
{B, C}
{B, E}
{C, E}
扫描DB
Itemset Support
{A, B} 1 (0.25)
{A, C} 2 (0.5)
{A, E} 1 (0.25)
{B, C} 2 (0.5)
{B, E} 3 (0.75)
{C, E} 2 (0.5)
取满足
最小支持度
项集
Itemset Support
{A, C} 2
{B, C} 2
{B, E} 3
{C, E} 2
Itemset
{A, B, C}
{A, B, E}
{A, C, E}
{B, C, E}
扫描DB
Itemset Support
{A, B, C} 1 (0.25)
{A, B, E} 1 (0.25)
{A, C, E} 1 (0.35)
{B, C, E} 2 (0.5)
取满足
最小支持度
项集
Itemset Support
{B, C, E} 2 (0.5)

如上可以看出，在海量数据的情况下，Apriori 算法的运算过程有 2 个问题：

  1. 需要多次扫描数据库，时间成本很高；
  2. 运算过程中需要产生大量的候选集，空间成本也非常高。

针对 Apriori 算法所做的改进也基本上是围绕着解决这两个问题进行的，如在扫描DB前首先进行以便事务合并和压缩，数据分区或抽样等。

Weka 里有 Apriori 算法的 Java 实现，非常值得一看。

貌似 wikipedia 已经解封了，呵呵！

预报：关联规则(3)，关于 FP-Growth 算法。

七月 11th, 2007 Posted by clickstone at 10:50pm | 推荐系统 | 156 comments

« Previous Post | Next Post »

156条评论 »

  1. http://www.arosson.net

    评论 由 ˿ | 2008-10-21

  2. http://www.nanpuhospital.com.cn/fuke/view.asp?newsid=968&classid=4

    评论 由 ǻˮ | 2008-10-23

  3. http://www.wjgb120.cn/news/gqw/088191621F7JKBC6HJ60B5K3E7ADC.html

    评论 由 Ҹε֢״ | 2008-10-25

  4. http://www.xiandaishi.com.cn/101.htm

    评论 由 ˿͡ | 2008-10-30

  5. http://www.wholesale-from-china.com/index.php

    评论 由 Ugg boots | 2008-11-04

  6. http://www.chuxin.cn

    评论 由 豸 | 2008-11-06

  7. http://www.rxwzzj.com/english/product.asp

    评论 由 cross cutting machine | 2008-11-13

  8. http://www.bjrdxb.com/

    评论 由 Բ | 2008-11-15

  9. http://www.top-account.com/

    评论 由 account for sale | 2008-11-17

  10. http://www.kang51.cn/html/864/200706/20070624287589.htm

    评论 由 | 2008-11-19

  11. http://www.ineedairjordan.com

    评论 由 Cheap Jordans | 2008-11-24

  12. http://www.eastern8.com/OnlineTravel/

    评论 由 holiday travel | 2008-11-28

  13. martha steward com
    microsoft com isapi redir dll prd ie
    jason maraz

    评论 由 Hero | 2008-11-29

  14. a

    评论 由 Arnie | 2008-12-02

  15. http://www.aimaled.com

    评论 由 LED | 2008-12-02

  16. http://www.wjgb120.cn/news/gz/08731112157K30FK24J16DG78IJE9HC.html

    评论 由 ҸС | 2008-12-07

  17. http://www.wjgb120.cn/news/gyh/2007/1022/07102222654FHAHCFID0A5G4AJIBHJ4.html

    评论 由 ҸôȾ | 2008-12-09

  18. http://www.totradeunion.com

    评论 由 jordan retro | 2008-12-11

  19. lisa raye daughter kai
    www fuse pants com
    www pokemon crater log in com
    capcon vs snk mugen screenpa

    评论 由 Neo | 2008-12-11

  20. http://www.4cdk.com

    评论 由 WOW CD Key | 2008-12-13

  21. wentworth miller girlfriend
    1970 marshall crash pictures
    karrine steffans vs mr marcus
    niurka marcos calendario 2007

    评论 由 Neo | 2008-12-14

  22. http://www.96096055.com

    评论 由 | 2008-12-15

  23. http://champrinting.com/aboutus.asp

    评论 由 paper products | 2008-12-16

  24. http://www.travel-sichuan.com/sichuan/jiuzhaigou/

    评论 由 կ | 2008-12-18

  25. http://www.topsoftwareol.com/products/ipod_ripper.html

    评论 由 ipod ripper | 2008-12-21

  26. http://www.play4uber.com/

    评论 由 wow account | 2008-12-24

  27. http://www.wjgb120.cn/news/gz/08731112157K30FK24J16DG78IJE9HC.html

    评论 由 Сʲô֢״ | 2008-12-25

  28. http://www.hzqs.com.cn/www/41/2008/3200.html

    评论 由 ״ | 2008-12-28

  29. [url=http://zxc123st2.yourfreehosting.net/aboriginal-cultureinitiation-ceremonies.html]aboriginal cultureinitiation ceremonies[/url]
    [url=http://zxc123st2.yourfreehosting.net/do-yo-chains-hang-low.html]do yo chains hang low[/url]
    young gay chub gets fucked
    animated hands clapping

    评论 由 collbrvs | 2008-12-30

  30. http://www.eastern8.com/travel/Shanghai/

    评论 由 Shanghai Traveling | 2008-12-30

  31. http://www.1000woman.cn/zxxm/rfsx/c01.htm

    评论 由 | 2008-12-30

  32. http://www.man51.com/news.asp?classid=1036

    评论 由 Ƥ | 2009-01-04

  33. http://www.nbwks.com/index.asp

    评论 由 Һѹ | 2009-01-06

  34. http://www.hzqs.com.cn

    评论 由 ҽԺ | 2009-01-10

  35. http://www.aotair.com/product.asp?pro_type=13

    评论 由 12Cr1MoVGϽ | 2009-01-15

  36. http://www.guttu.cn

    评论 由 ȡů | 2009-01-19

  37. how to overclock a cpu
    embroidered personalised gifts
    [url=http://po6el5.yourfreehosting.net/how-to-overclock-a-cpu.html]how to overclock a cpu[/url]
    [url=http://po6el5.yourfreehosting.net/embroidered-personalised-gifts.html]embroidered personalised gifts[/url]

    评论 由 kirkoloh | 2009-01-20

  38. Hi! Ebanij vrot! 4kt6to5bc1 ntxdhaglka! http://www.zimbio.com/Personal+Finance/articles/10328/By+Loan+Movable+Payday+Powered+Type ; No Fax Payday Loan Manifest Louisiana ; [url=http://www.zimbio.com/Personal+Finance/articles/10322/Need+Payday+Loan+No+Teletrac+Emergency]Instant Online Payday Loan Arkinda Arkansas[/url] ; Bye! =)

    评论 由 zovrx8aygc | 2009-01-22

  39. dungeon seige 2 help
    mini crawlers
    [url=http://ski7rt.yourfreehosting.net/dungeon-seige-2-help.html]dungeon seige 2 help[/url]
    [url=http://ski7rt.yourfreehosting.net/mini-crawlers.html]mini crawlers[/url]

    评论 由 narkopedik | 2009-01-23

  40. imagen del esqueleto humano
    smothering insecure behavior in men
    [url=http://qaz321r.yourfreehosting.net/berry-gordy-jr-recent-photo.html]berry gordy jr recent photo[/url]
    [url=http://qaz321r.yourfreehosting.net/gackt-lyrics-love-letter.html]gackt lyrics love letter[/url]

    评论 由 burjachihasam | 2009-01-24

  41. http://www.electrical-tape.cn/en/gsjj.asp

    评论 由 electrical tape | 2009-01-24

  42. Hello my dear friend! I’m a pure student…

    评论 由 Statute Of Limitations Debt Coll | 2009-01-28

  43. cialis
    http://technorati.com/posts/tag/Buy+Cialis+Online.+FDA+Approved+Quality+Pills.+cialisxl
    [url=http://technorati.com/posts/tag/Buy+Cialis+Online.+FDA+Approved+Quality+Pills.+cialisxl]cialis[/url]

    评论 由 cialis | 2009-01-28

  44. [URL=http://cheap-adobe.com/info-Symantec_ACT_2005_7.0.html]downloadable Symantec ACT 2005 7.0[/URL]

    评论 由 ARossi | 2009-02-03

  45. [URL=http://software-oem.net/info-QuarkXPress_6.5.html]full oem QuarkXPress 6.5[/URL]

    评论 由 KukkoDrukko | 2009-02-03

  46. buying retail MS SQL Server 2005 - Full software

    评论 由 ElizeSommer | 2009-02-06

  47. download Corel Painter IX MAC software

    评论 由 ElizeSommer | 2009-02-06

  48. ogg vorbis downloads
    football programmes uk
    [url=http://ajk79.yourfreehosting.net/ogg-vorbis-downloads.html]ogg vorbis downloads[/url]
    [url=http://ajk79.yourfreehosting.net/football-programmes-uk.html]football programmes uk[/url]

    评论 由 pesdolosohatij2 | 2009-02-06

  49. create bootable xp cd
    proteus vulgaris gram stain
    [url=http://gf7ghu.yourfreehosting.net/create-bootable-xp-cd.html]create bootable xp cd[/url]
    [url=http://gf7ghu.yourfreehosting.net/proteus-vulgaris-gram-stain.html]proteus vulgaris gram stain[/url]

    评论 由 treslo2huipesdovij | 2009-02-06

  50. pa sphynx cat breeders
    high tensile fence brace
    [url=http://l4kmn.yourfreehosting.net/pa-sphynx-cat-breeders.html]pa sphynx cat breeders[/url]
    [url=http://l4kmn.yourfreehosting.net/high-tensile-fence-brace.html]high tensile fence brace[/url]

    评论 由 njinikolaevskij79 | 2009-02-07

  51. purchase retail Adobe Premiere PRO 2.0 software

    评论 由 ElizeSommer | 2009-02-07

  52. girls lockerrooms
    homing pigeonscobourg ontario
    [url=http://mks76.yourfreehosting.net/girls-lockerrooms.html]girls lockerrooms[/url]
    [url=http://mks76.yourfreehosting.net/homing-pigeonscobourg-ontario.html]homing pigeonscobourg ontario[/url]

    评论 由 huiiyaichishki | 2009-02-07

  53. http://www.mygamesale.de/wowkonto.jsp

    评论 由 wow account kaufen | 2009-02-07

  54. computer aided design definition
    brandy and mr. whiskers hentai
    [url=http://yui081.yourfreehosting.net/computer-aided-design-definition.html]computer aided design definition[/url]
    [url=http://yui081.yourfreehosting.net/brandy-and-mr-whiskers-hentai.html]brandy and mr. whiskers hentai[/url]

    评论 由 cheburilo2309 | 2009-02-07

  55. jeet kune do videos
    handi rifles
    [url=http://www.dfg45.happyhost.org/jeet-kune-do-videos.html]jeet kune do videos[/url]
    [url=http://www.dfg45.happyhost.org/handi-rifles.html]handi rifles[/url]

    评论 由 slishbiknebikuj | 2009-02-07

  56. [link http://www.sle999.com/zhuanti/jzxjnkjzl/]甲状腺机能亢进治疗[/link]
    [link http://www.sle999.com/zhuanti/jzxkjz/]甲状腺亢进症[/link]
    [link http://www.sle999.com/zhuanti/jkzl/]甲亢治疗[/link]

    评论 由 fds | 2009-02-09

  57. downloadable McAfee Alert Manager v4.7.1 software

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  58. Adobe Drea
    mweaver CS3 software

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  59. AutoCAD 2005

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  60. downloadable full version Adobe Acrobat Distiller 6

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  61. where to buy Adobe Creative Suite 3 Design Premium

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  62. download online Macromedia FlashPaper 2 software

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  63. download computer Microsoft Windows 2000 Professional w
    ith SP4 software

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  64. where to buy Adobe Creative Suite 3 Design Premium

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  65. buying retail MS SQL Server 2005 - Full software

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  66. purchase retail Adobe Premiere PRO 2.0 software

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  67. Adobe Illustrator CS2 MAC

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  68. downloadable McAfee Alert Manager v4.7.1 software

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  69. download Corel Painter IX MAC software

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  70. Macromedia Flash Communication Server MX software

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  71. Corel Designer Technical Suite 12.0

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  72. Microsoft Works 7

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  73. Adobe Dreamweaver CS3

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  74. downloadable full oem Adobe InDesign CS2 software

    oem software

    评论 由 KukkoDrukko | 2009-02-09

  75. Macromedia Fireworks 8

    cheap software

    评论 由 KukkoDrukko | 2009-02-09

  76. http://www.yilimy.com/tzm.html

    评论 由 ľ | 2009-02-12

  77. http://www.bjdfssjxw.cn

    评论 由 ʱмУ | 2009-02-12

  78. http://www.bote-office.com

    评论 由 칫Ҿ | 2009-02-18

  79. http://www.nanpuhospital.com.cn/nvxin/view.asp?newsid=460&classid=3

    评论 由 ׳ʲôҩ | 2009-02-20

  80. us currency convert
    final fantsy 7-cloud strife
    wet teen coochie
    bpm studio 4 8 full

    评论 由 prostokolhoznic | 2009-02-25

  81. http://www.homeloanwt.net

    评论 由 סլ` | 2009-02-26

  82. http://www.bwgolf88.com

    评论 由 golf equipment | 2009-03-02

  83. http://www.rank10google.com

    评论 由 google | 2009-03-04

  84. http://www.yasuda-seiki.cn/use/pull.html

    评论 由 ѹ | 2009-03-05

  85. bobby lashley bodybuilder pics
    1/2 npt adapter
    in memoriam patch
    we love katamari walkthrough

    评论 由 buksdf13u29 | 2009-03-06

  86. buy wow gold,cheap wow gold,world of warcrft gold.

    评论 由 wowgold | 2009-03-07

  87. http://www.sjlogo.com

    评论 由 ƹ˾ | 2009-03-08

  88. building stair banister
    awakendisturbed
    [url=http://pes13da0.freewaywebhost.com/building-stair-banister.html]building stair banister[/url]
    [url=http://pes13da0.freewaywebhost.com/awakendisturbed.html]awakendisturbed[/url]

    评论 由 samagoncheg | 2009-03-13

  89. http://www.haagendazs.sh.cn

    评论 由 Ϻ±Ź | 2009-03-14

  90. http://deaicatch.com/category/service-muryou.html

    评论 由 oϡᤤ | 2009-03-16

  91. http://www.zdgree.com.cn

    评论 由 յ | 2009-03-19

  92. http://www.yxjlaw.com

    评论 由 ʦ | 2009-03-23

  93. http://www.88858060.com

    评论 由 ι˾ | 2009-03-24

  94. http://www.jxsprings.com/

    评论 由 Һѹ | 2009-03-29

  95. http://www.haagendazs.sh.cn

    评论 由 ± | 2009-03-30

  96. Goldsoon has rich experience in VCT (Virtual Currency Trading wow gold) industry. By August.10, 2008, We have 328, 252 precious members, 1,852,235,400 WoW Gold and other game gold has been delivered successfully.
    We also set up worldwide branch offices in Europe, USA, China and Hong Kong. Our Support team of 400 members provide 7/24 Customer Service. If you have any questions about buying wow gold, you can contact our Live Support for assistance.
    To Make sure our customers can get wow gold Faster, Cheaper and more safe, we have established the long-term cooperation with 18,266 wow gold farming studios in China. All we were doing was improving our customers’gaming experience.

    评论 由 wowgold | 2009-03-31

  97. propecia
    http://www.propeciainfo.com/
    [url=http://www.propeciainfo.com/]propecia[/url]

    评论 由 propecia | 2009-04-02

  98. http://www.buyonetrading.com

    评论 由 Hot water bottle | 2009-04-08

  99. http://www.haagendazs.org.cn

    评论 由 ˹ٷվ | 2009-04-10

  100. http://www.taisyokujp.com

    评论 由 š | 2009-04-19

  101. http://www.shenbing.org/shenbingzhishi/niaoduzheng.asp

    评论 由 ֢ | 2009-04-23

  102. buy propecia
    http://www.propeciainfo.com/
    [url=http://www.propeciainfo.com/]buy propecia[/url]

    评论 由 buy propecia | 2009-04-23

  103. http://www.welding2008.cn/wed/productShow.asp?id=51

    评论 由 纸 | 2009-04-25

  104. http://www.ga-sale.com/lotro-account/

    评论 由 lotro account | 2009-04-29

  105. http://www.translationchina.com/l_japanese.htm

    评论 由 ﷭ | 2009-04-30

  106. http://www.96096055.com/html/393/200701/20070119172807.htm

    评论 由 ѹ˫Ƥ | 2009-05-01

  107. http://www.wjgb120.cn/news/gqw/088593036E128BF6DD9C9A534BDF9.html

    评论 由 ҸβȾ; | 2009-05-03

  108. http://www.meidepump.com/about.asp

    评论 由 DZ۱ | 2009-05-06

  109. http://www.jcmech.com

    评论 由 ĥ | 2009-05-07

  110. http://www.since-china.com/2.asp

    评论 由 豸 | 2009-05-08

  111. http://www.qhxxkj.cn

    评论 由 ϺŽ | 2009-05-10

  112. http://www.da-ben.com.cn/

    评论 由 ƺ | 2009-05-11

  113. generic propecia
    http://www.propeciainfo.com/
    [url=http://www.propeciainfo.com/]generic propecia[/url]

    评论 由 generic propecia | 2009-05-11

  114. http://www.chinashade.com

    评论 由 Shade cloth | 2009-05-14

  115. http://www.hzzxyy.com/news_zx.asp?classid=14&ICI_ID=1902

    评论 由 | 2009-05-17

  116. http://www.nikeshoesunion.com

    评论 由 cheap jordans | 2009-05-19

  117. http://www.sd1718.com/yiqi/1-7.html

    评论 由 Ӽ | 2009-05-21

  118. http://www.linesun.com

    评论 由 | 2009-05-22

  119. http://www.jncncrouter.cn/english.html

    评论 由 cnc router | 2009-05-23

  120. http://www.cn-tiane.com/pro.asp

    评论 由 swimming pool heat pump | 2009-05-26

  121. http://www.usajumpman.com/

    评论 由 cheap shoes | 2009-05-26

  122. http://www.topsofts.com/internet/73.html

    评论 由 internet software | 2009-05-28

  123. http://www.uggforever.com/

    评论 由 boots shoes | 2009-05-29

  124. 很好，很强大。。。呵呵

    评论 由 双色球 | 2009-05-31

  125. http://www.eastern8.com/china_guides/smart_tools/china_weather.jsp

    评论 由 China Weather | 2009-06-03

  126. http://www.airflow-plus.com

    评论 由 air diffuser | 2009-06-04

  127. Buy viagra
    http://www.viagra2000.com/
    [url=http://www.viagra2000.com/]Buy Viagra[/url]

    评论 由 Buy Viagra | 2009-06-06

  128. http://www.proswell.com.cn/service_1_6.htm

    评论 由 ҩз | 2009-06-07

  129. http://www.yudan.com.cn/tuiguang/xinzangbing.asp

    评论 由 ಡ | 2009-06-08

  130. http://www.sh.xcmc.com.cn/shenghao/

    评论 由 ɺУ | 2009-06-09

  131. http://www.aimaled.com

    评论 由 Ϸʷ | 2009-06-11

  132. http://www.mygamesale.com/lotro/

    评论 由 lotro gold | 2009-06-12

  133. http://www.dl32.com/product/iPhone/TOP_WMV_to_iPhone_Converter.html

    评论 由 WMV iPhone Mac | 2009-06-14

  134. http://www.xnchem.com/a-5.asp

    评论 由 | 2009-06-15

  135. http://www.hmbusiness.com/html/blister_packing.html

    评论 由 blister packing | 2009-06-16

  136. http://www.eastlawyer.cn/

    评论 由 Ϻʦ | 2009-06-17

  137. http://www.bestbuynike.com/products/Max-95-n62_p1.html

    评论 由 air max 95 | 2009-06-17

  138. http://www.liangyipump.com/fy.htm

    评论 由 Һ± | 2009-06-19

  139. http://www.powerlevelings.com

    评论 由 power leveling | 2009-06-20

  140. http://www.mygamesale.com/wowgold/

    评论 由 easy world of warcraft gold | 2009-06-22

  141. http://www.earth-soft.com/prodcuts.html

    评论 由 Blu Ray Copy | 2009-06-23

  142. http://www.111zhongliu.com/Html/20080401/7034418.html

    评论 由 ֱ | 2009-06-23

  143. http://www.77745.com/wowus/index.jsp

    评论 由 powerleveling | 2009-06-23

  144. http://www.hzjlzt.cn

    评论 由 ̿ | 2009-06-24

  145. http://www.shbinglong.cn/

    评论 由 綯 | 2009-06-25

  146. http://www.hzqs.com.cn/www/91/2008/3334.html

    评论 由 Сʹ | 2009-06-25

  147. http://www.fengyuanqimo.com/cn/index.asp

    评论 由 ģ | 2009-06-27

  148. http://www.96096055.com/mr/tuomao/200904/6389.html

    评论 由 ë | 2009-06-30

  149. http://www.delicare4u.com/products.asp?me_id=36

    评论 由 automatic flushers | 2009-07-01

  150. http://www.welding2008.cn/wed/product.asp?productsort=365&xsp=product

    评论 由 㺸 | 2009-07-03

  151. http://www.youlo.com.cn/c16.html

    评论 由 | 2009-07-03

  152. http://www.fybest.cn

    评论 由 Ϻ빫˾ | 2009-07-04

  153. http://www.buybestjordan.com/shoe/?Nike-Dunk-13-c-1.html

    评论 由 NIKE DUNKs | 2009-07-05

  154. http://www.treasurecn.com/

    评论 由 Կ׿ | 2009-07-07

  155. http://www.yzspd.com/user_brand.asp

    评论 由 Դ | 2009-07-07

  156. http://www.kicksforever.com/

    评论 由 wholesale shoes | 2009-07-09

发表评论

提示：如果你刚刚提交过评论，但是还没有被显示出来，请点击这里刷新一下： 刷新评论 。