apriori算法c
㈠ 设c是apriori算法产生的ck中的一个候选项集.在剪枝步，需要检查多少个长度为
2 FAA算法思想
2.1 链表数组定义及生成算法。链表数组定义：数组为n个指针的一维数组P[n]，对应数据库中的频繁项I1，I2，…，In，对应数组长度n为数据库中频繁项的数量。结点为事务结点，分为事务域、计数域和指针域。事务域是以频繁项为后缀的事务编码。计数域是该事务编码的数量，指针域是指向下一结点的指针。
编码方法：设数据库中有n个频繁项I1，I2，…，In。事务t的编码就是长度为n的0、1位串。在t中出现的项，其相应位置用1表示，否则填0。例如，有四个频繁项a，b，c，d。那么，一个包含a和c的事务就被映射为1010。
链表数组的构造过程如下：（1）扫描事务数据库，产生所有频繁1-项集及支持度计数，依据支持度计数降序排列，生成FI-List。（2）再次扫描数据库，将每条记录中不满足最小支持度计数的项删除，并将剩余项按照FI-List重新排序。设形成的新序列为{m1，m2，…，mn}，依次取出序列中的前k（1≤k≤n）项组成子序列{m1，m2，…，mk}，对每个子序列进行编码并建立一个与之对应的事务结点，并按照子序列中最后一项追加到P[n]中相应链上。
㈡ 怎么用java实现apriori算法
作者：何史提
链接：https://www.hu.com/question/22590018/answer/26646688
来源：知乎
着作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Apriori算法的理念其实很简单，可是实现起上来却复杂无比，因为当中无可避免用Set和Hash Table等高阶的数据结构，而且有很多loop用以读取数据。
我不建议用Java，应改用Python或Scala一类的语言。如果用Python，代码大概50行左右，但可以想象用Java便看起来复杂得多。看如下：
from operator import and_
from itertools import combinations
class AprioriAssociationRule:
def __init__(self, inputfile):
self.transactions = []
self.itemSet = set([])
inf = open(inputfile, 'rb')
for line in inf.readlines():
elements = set(filter(lambda entry: len(entry)>0, line.strip().split(',')))
if len(elements)>0:
self.transactions.append(elements)
for element in elements:
self.itemSet.add(element)
inf.close()
self.toRetItems = {}
self.associationRules = []
def getSupport(self, itemcomb):
if type(itemcomb) != frozenset:
itemcomb = frozenset([itemcomb])
within_transaction = lambda transaction: rece(and_, [(item in transaction) for item in itemcomb])
count = len(filter(within_transaction, self.transactions))
return float(count)/float(len(self.transactions))
def runApriori(self, minSupport=0.15, minConfidence=0.6):
itemCombSupports = filter(lambda freqpair: freqpair[1]>=minSupport,
map(lambda item: (frozenset([item]), self.getSupport(item)), self.itemSet))
currentLset = set(map(lambda freqpair: freqpair[0], itemCombSupports))
k = 2
while len(currentLset)>0:
currentCset = set([i.union(j) for i in currentLset for j in currentLset if len(i.union(j))==k])
currentItemCombSupports = filter(lambda freqpair: freqpair[1]>=minSupport,
map(lambda item: (item, self.getSupport(item)), currentCset))
currentLset = set(map(lambda freqpair: freqpair[0], currentItemCombSupports))
itemCombSupports.extend(currentItemCombSupports)
k += 1
for key, supportVal in itemCombSupports:
self.toRetItems[key] = supportVal
self.calculateAssociationRules(minConfidence=minConfidence)
def calculateAssociationRules(self, minConfidence=0.6):
for key in self.toRetItems:
subsets = [frozenset(item) for k in range(1, len(key)) for item in combinations(key, k)]
for subset in subsets:
confidence = self.toRetItems[key] / self.toRetItems[subset]
if confidence > minConfidence:
self.associationRules.append([subset, key-subset, confidence])
㈢ 计算机大神请进啊！这个Apriori算法这个题，由L2到底怎么产生候选C3的怎么连接啊，完
自连接不是与自身连接
你说的只有频繁2项集{A,B}{C,D}，那{A,C}，{A,D}呢？找到前几项相同的，最后一项不同的连接，那么必然产生K+1项集
㈣ 急需C++实现的Apriori算法代码
用C++ 实现的 可以 到http://download.csdn.net/down/188143/chanjuanzz下载 不过要注册扣积分的
算法实现
（一）核心类
Apriori算法的核心实现类为AprioriAlgorithm，实现的Java代码如下所示：
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
/**
* <B>关联规则挖掘：Apriori算法</B>
*
* <P>该算法基本上按照Apriori算法的基本思想来实现的。
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class AprioriAlgorithm {
private Map<Integer, Set<String>> txDatabase; // 事务数据库
private Float minSup; // 最小支持度
private Float minConf; // 最小置信度
private Integer txDatabaseCount; // 事务数据库中的事务数
private Map<Integer, Set<Set<String>>> freqItemSet; // 频繁项集集合
private Map<Set<String>, Set<Set<String>>> assiciationRules; // 频繁关联规则集合
public AprioriAlgorithm(
Map<Integer, Set<String>> txDatabase,
Float minSup,
Float minConf) {
this.txDatabase = txDatabase;
this.minSup = minSup;
this.minConf = minConf;
this.txDatabaseCount = this.txDatabase.size();
freqItemSet = new TreeMap<Integer, Set<Set<String>>>();
assiciationRules = new HashMap<Set<String>, Set<Set<String>>>();
}
/**
* 扫描事务数据库，计算频繁1-项集
* @return
*/
public Map<Set<String>, Float> getFreq1ItemSet() {
Map<Set<String>, Float> freq1ItemSetMap = new HashMap<Set<String>, Float>();
Map<Set<String>, Integer> candFreq1ItemSet = this.getCandFreq1ItemSet();
Iterator<Map.Entry<Set<String>, Integer>> it = candFreq1ItemSet.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Set<String>, Integer> entry = it.next();
// 计算支持度
Float supported = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
if(supported>=minSup) {
freq1ItemSetMap.put(entry.getKey(), supported);
}
}
return freq1ItemSetMap;
}
/**
* 计算候选频繁1-项集
* @return
*/
public Map<Set<String>, Integer> getCandFreq1ItemSet() {
Map<Set<String>, Integer> candFreq1ItemSetMap = new HashMap<Set<String>, Integer>();
Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
// 统计支持数，生成候选频繁1-项集
while(it.hasNext()) {
Map.Entry<Integer, Set<String>> entry = it.next();
Set<String> itemSet = entry.getValue();
for(String item : itemSet) {
Set<String> key = new HashSet<String>();
key.add(item.trim());
if(!candFreq1ItemSetMap.containsKey(key)) {
Integer value = 1;
candFreq1ItemSetMap.put(key, value);
}
else {
Integer value = 1+candFreq1ItemSetMap.get(key);
candFreq1ItemSetMap.put(key, value);
}
}
}
return candFreq1ItemSetMap;
}
/**
* 根据频繁(k-1)-项集计算候选频繁k-项集
*
* @param m 其中m=k-1
* @param freqMItemSet 频繁(k-1)-项集
* @return
*/
public Set<Set<String>> aprioriGen(int m, Set<Set<String>> freqMItemSet) {
Set<Set<String>> candFreqKItemSet = new HashSet<Set<String>>();
Iterator<Set<String>> it = freqMItemSet.iterator();
Set<String> originalItemSet = null;
while(it.hasNext()) {
originalItemSet = it.next();
Iterator<Set<String>> itr = this.getIterator(originalItemSet, freqMItemSet);
while(itr.hasNext()) {
Set<String> identicalSet = new HashSet<String>(); // 两个项集相同元素的集合(集合的交运算)
identicalSet.addAll(originalItemSet);
Set<String> set = itr.next();
identicalSet.retainAll(set); // identicalSet中剩下的元素是identicalSet与set集合中公有的元素
if(identicalSet.size() == m-1) { // (k-1)-项集中k-2个相同
Set<String> differentSet = new HashSet<String>(); // 两个项集不同元素的集合(集合的差运算)
differentSet.addAll(originalItemSet);
differentSet.removeAll(set); // 因为有k-2个相同，则differentSet中一定剩下一个元素，即differentSet大小为1
differentSet.addAll(set); // 构造候选k-项集的一个元素(set大小为k-1,differentSet大小为k)
candFreqKItemSet.add(differentSet); // 加入候选k-项集集合
}
}
}
return candFreqKItemSet;
}
/**
* 根据一个频繁k-项集的元素(集合)，获取到频繁k-项集的从该元素开始的迭代器实例
* @param itemSet
* @param freqKItemSet 频繁k-项集
* @return
*/
private Iterator<Set<String>> getIterator(Set<String> itemSet, Set<Set<String>> freqKItemSet) {
Iterator<Set<String>> it = freqKItemSet.iterator();
while(it.hasNext()) {
if(itemSet.equals(it.next())) {
break;
}
}
return it;
}
/**
* 根据频繁(k-1)-项集，调用aprioriGen方法，计算频繁k-项集
*
* @param k
* @param freqMItemSet 频繁(k-1)-项集
* @return
*/
public Map<Set<String>, Float> getFreqKItemSet(int k, Set<Set<String>> freqMItemSet) {
Map<Set<String>, Integer> candFreqKItemSetMap = new HashMap<Set<String>, Integer>();
// 调用aprioriGen方法，得到候选频繁k-项集
Set<Set<String>> candFreqKItemSet = this.aprioriGen(k-1, freqMItemSet);
// 扫描事务数据库
Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
// 统计支持数
while(it.hasNext()) {
Map.Entry<Integer, Set<String>> entry = it.next();
Iterator<Set<String>> kit = candFreqKItemSet.iterator();
while(kit.hasNext()) {
Set<String> kSet = kit.next();
Set<String> set = new HashSet<String>();
set.addAll(kSet);
set.removeAll(entry.getValue()); // 候选频繁k-项集与事务数据库中元素做差元算
if(set.isEmpty()) { // 如果拷贝set为空，支持数加1
if(candFreqKItemSetMap.get(kSet) == null) {
Integer value = 1;
candFreqKItemSetMap.put(kSet, value);
}
else {
Integer value = 1+candFreqKItemSetMap.get(kSet);
candFreqKItemSetMap.put(kSet, value);
}
}
}
}
// 计算支持度，生成频繁k-项集，并返回
return support(candFreqKItemSetMap);
}
/**
* 根据候选频繁k-项集，得到频繁k-项集
*
* @param candFreqKItemSetMap 候选k项集(包含支持计数)
*/
public Map<Set<String>, Float> support(Map<Set<String>, Integer> candFreqKItemSetMap) {
Map<Set<String>, Float> freqKItemSetMap = new HashMap<Set<String>, Float>();
Iterator<Map.Entry<Set<String>, Integer>> it = candFreqKItemSetMap.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Set<String>, Integer> entry = it.next();
// 计算支持度
Float supportRate = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
if(supportRate<minSup) { // 如果不满足最小支持度，删除
it.remove();
}
else {
freqKItemSetMap.put(entry.getKey(), supportRate);
}
}
return freqKItemSetMap;
}
/**
* 挖掘全部频繁项集
*/
public void mineFreqItemSet() {
// 计算频繁1-项集
Set<Set<String>> freqKItemSet = this.getFreq1ItemSet().keySet();
freqItemSet.put(1, freqKItemSet);
// 计算频繁k-项集(k>1)
int k = 2;
while(true) {
Map<Set<String>, Float> freqKItemSetMap = this.getFreqKItemSet(k, freqKItemSet);
if(!freqKItemSetMap.isEmpty()) {
this.freqItemSet.put(k, freqKItemSetMap.keySet());
freqKItemSet = freqKItemSetMap.keySet();
}
else {
break;
}
k++;
}
}
/**
* <P>挖掘频繁关联规则
* <P>首先挖掘出全部的频繁项集，在此基础上挖掘频繁关联规则
*/
public void mineAssociationRules() {
freqItemSet.remove(1); // 删除频繁1-项集
Iterator<Map.Entry<Integer, Set<Set<String>>>> it = freqItemSet.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Integer, Set<Set<String>>> entry = it.next();
for(Set<String> itemSet : entry.getValue()) {
// 对每个频繁项集进行关联规则的挖掘
mine(itemSet);
}
}
}
/**
* 对从频繁项集集合freqItemSet中每迭代出一个频繁项集元素，执行一次关联规则的挖掘
* @param itemSet 频繁项集集合freqItemSet中的一个频繁项集元素
*/
public void mine(Set<String> itemSet) {
int n = itemSet.size()/2; // 根据集合的对称性，只需要得到一半的真子集
for(int i=1; i<=n; i++) {
// 得到频繁项集元素itemSet的作为条件的真子集集合
Set<Set<String>> properSubset = ProperSubsetCombination.getProperSubset(i, itemSet);
// 对条件的真子集集合中的每个条件项集，获取到对应的结论项集，从而进一步挖掘频繁关联规则
for(Set<String> conditionSet : properSubset) {
Set<String> conclusionSet = new HashSet<String>();
conclusionSet.addAll(itemSet);
conclusionSet.removeAll(conditionSet); // 删除条件中存在的频繁项
confide(conditionSet, conclusionSet); // 调用计算置信度的方法，并且挖掘出频繁关联规则
}
}
}
/**
* 对得到的一个条件项集和对应的结论项集，计算该关联规则的支持计数，从而根据置信度判断是否是频繁关联规则
* @param conditionSet 条件频繁项集
* @param conclusionSet 结论频繁项集
*/
public void confide(Set<String> conditionSet, Set<String> conclusionSet) {
// 扫描事务数据库
Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
// 统计关联规则支持计数
int conditionToConclusionCnt = 0; // 关联规则(条件项集推出结论项集)计数
int conclusionToConditionCnt = 0; // 关联规则(结论项集推出条件项集)计数
int supCnt = 0; // 关联规则支持计数
while(it.hasNext()) {
Map.Entry<Integer, Set<String>> entry = it.next();
Set<String> txSet = entry.getValue();
Set<String> set1 = new HashSet<String>();
Set<String> set2 = new HashSet<String>();
set1.addAll(conditionSet);
set1.removeAll(txSet); // 集合差运算：set-txSet
if(set1.isEmpty()) { // 如果set为空，说明事务数据库中包含条件频繁项conditionSet
// 计数
conditionToConclusionCnt++;
}
set2.addAll(conclusionSet);
set2.removeAll(txSet); // 集合差运算：set-txSet
if(set2.isEmpty()) { // 如果set为空，说明事务数据库中包含结论频繁项conclusionSet
// 计数
conclusionToConditionCnt++;
}
if(set1.isEmpty() && set2.isEmpty()) {
supCnt++;
}
}
// 计算置信度
Float conditionToConclusionConf = new Float(supCnt)/new Float(conditionToConclusionCnt);
if(conditionToConclusionConf>=minConf) {
if(assiciationRules.get(conditionSet) == null) { // 如果不存在以该条件频繁项集为条件的关联规则
Set<Set<String>> conclusionSetSet = new HashSet<Set<String>>();
conclusionSetSet.add(conclusionSet);
assiciationRules.put(conditionSet, conclusionSetSet);
}
else {
assiciationRules.get(conditionSet).add(conclusionSet);
}
}
Float conclusionToConditionConf = new Float(supCnt)/new Float(conclusionToConditionCnt);
if(conclusionToConditionConf>=minConf) {
if(assiciationRules.get(conclusionSet) == null) { // 如果不存在以该结论频繁项集为条件的关联规则
Set<Set<String>> conclusionSetSet = new HashSet<Set<String>>();
conclusionSetSet.add(conditionSet);
assiciationRules.put(conclusionSet, conclusionSetSet);
}
else {
assiciationRules.get(conclusionSet).add(conditionSet);
}
}
}
/**
* 经过挖掘得到的频繁项集Map
*
* @return 挖掘得到的频繁项集集合
*/
public Map<Integer, Set<Set<String>>> getFreqItemSet() {
return freqItemSet;
}
/**
* 获取挖掘到的全部的频繁关联规则的集合
* @return 频繁关联规则集合
*/
public Map<Set<String>, Set<Set<String>>> getAssiciationRules() {
return assiciationRules;
}
}
（二）辅助类
ProperSubsetCombination类是一个辅助类，在挖掘频繁关联规则的过程中，用于生成一个频繁项集元素的非空真子集，实现代码如下：
package org.shirdrn.datamining.association;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;
/**
* <B>求频繁项集元素(集合)的非空真子集集合</B>
* <P>从一个集合（大小为n）中取出m(m属于2~n/2的闭区间)个元素的组合实现类，获取非空真子集的集合
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class ProperSubsetCombination {
private static String[] array;
private static BitSet startBitSet; // 比特集合起始状态
private static BitSet endBitSet; // 比特集合终止状态，用来控制循环
private static Set<Set<String>> properSubset; // 真子集集合
/**
* 计算得到一个集合的非空真子集集合
*
* @param n 真子集的大小
* @param itemSet 一个频繁项集元素
* @return 非空真子集集合
*/
public static Set<Set<String>> getProperSubset(int n, Set<String> itemSet) {
String[] array = new String[itemSet.size()];
ProperSubsetCombination.array = itemSet.toArray(array);
properSubset = new HashSet<Set<String>>();
startBitSet = new BitSet();
endBitSet = new BitSet();
// 初始化startBitSet，左侧占满1
for (int i=0; i<n; i++) {
startBitSet.set(i, true);
}
// 初始化endBit，右侧占满1
for (int i=array.length-1; i>=array.length-n; i--) {
endBitSet.set(i, true);
}
// 根据起始startBitSet，将一个组合加入到真子集集合中
get(startBitSet);
while(!startBitSet.equals(endBitSet)) {
int zeroCount = 0; // 统计遇到10后，左边0的个数
int oneCount = 0; // 统计遇到10后，左边1的个数
int pos = 0; // 记录当前遇到10的索引位置
// 遍历startBitSet来确定10出现的位置
for (int i=0; i<array.length; i++) {
if (!startBitSet.get(i)) {
zeroCount++;
}
if (startBitSet.get(i) && !startBitSet.get(i+1)) {
pos = i;
oneCount = i - zeroCount;
// 将10变为01
startBitSet.set(i, false);
startBitSet.set(i+1, true);
break;
}
}
// 将遇到10后，左侧的1全部移动到最左侧
int counter = Math.min(zeroCount, oneCount);
int startIndex = 0;
int endIndex = 0;
if(pos>1 && counter>0) {
pos--;
endIndex = pos;
for (int i=0; i<counter; i++) {
startBitSet.set(startIndex, true);
startBitSet.set(endIndex, false);
startIndex = i+1;
pos--;
if(pos>0) {
endIndex = pos;
}
}
}
get(startBitSet);
}
return properSubset;
}
/**
* 根据一次移位操作得到的startBitSet，得到一个真子集
* @param bitSet
*/
private static void get(BitSet bitSet) {
Set<String> set = new HashSet<String>();
for(int i=0; i<array.length; i++) {
if(bitSet.get(i)) {
set.add(array[i]);
}
}
properSubset.add(set);
}
}
测试用例
对上述Apriori算法的实现进行了简单的测试，测试用例如下所示：
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import org.shirdrn.datamining.association.AprioriAlgorithm;
import junit.framework.TestCase;
/**
* <B>Apriori算法测试类</B>
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class TestAprioriAlgorithm extends TestCase {
private AprioriAlgorithm apriori;
private Map<Integer, Set<String>> txDatabase;
private Float minSup = new Float("0.50");
private Float minConf = new Float("0.70");
@Override
protected void setUp() throws Exception {
create(); // 构造事务数据库
apriori = new AprioriAlgorithm(txDatabase, minSup, minConf);
}
/**
* 构造模拟事务数据库txDatabase
*/
public void create() {
txDatabase = new HashMap<Integer, Set<String>>();
Set<String> set1 = new TreeSet<String>();
set1.add("A");
set1.add("B");
set1.add("C");
set1.add("E");
txDatabase.put(1, set1);
Set<String> set2 = new TreeSet<String>();
set2.add("A");
set2.add("B");
set2.add("C");
txDatabase.put(2, set2);
Set<String> set3 = new TreeSet<String>();
set3.add("C");
set3.add("D");
txDatabase.put(3, set3);
Set<String> set4 = new TreeSet<String>();
set4.add("A");
set4.add("B");
set4.add("E");
txDatabase.put(4, set4);
}
/**
* 测试挖掘频繁1-项集
*/
public void testFreq1ItemSet() {
System.out.println("挖掘频繁1-项集 : " + apriori.getFreq1ItemSet());
}
/**
* 测试aprioriGen方法，生成候选频繁项集
*/
public void testAprioriGen() {
System.out.println(
"候选频繁2-项集 ： " +
this.apriori.aprioriGen(1, this.apriori.getFreq1ItemSet().keySet())
);
}
/**
* 测试挖掘频繁2-项集
*/
public void testGetFreq2ItemSet() {
System.out.println(
"挖掘频繁2-项集 ：" +
this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet())
);
}
/**
* 测试挖掘频繁3-项集
*/
public void testGetFreq3ItemSet() {
System.out.println(
"挖掘频繁3-项集 ：" +
this.apriori.getFreqKItemSet(
3,
this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet()).keySet()
)
);
}
/**
* 测试挖掘全部频繁项集
*/
public void testGetFreqItemSet() {
this.apriori.mineFreqItemSet(); // 挖掘频繁项集
System.out.println("挖掘频繁项集 ：" + this.apriori.getFreqItemSet());
}
/**
* 测试挖掘全部频繁关联规则
*/
public void testMineAssociationRules() {
this.apriori.mineFreqItemSet(); // 挖掘频繁项集
this.apriori.mineAssociationRules();
System.out.println("挖掘频繁关联规则 ：" + this.apriori.getAssiciationRules());
}
}
测试结果：
挖掘频繁1-项集 : {[E]=0.5, [A]=0.75, [B]=0.75, [C]=0.75}
候选频繁2-项集 ： [[E, C], [A, B], [B, C], [A, C], [E, B], [E, A]]
挖掘频繁2-项集 ：{[A, B]=0.75, [B, C]=0.5, [A, C]=0.5, [E, B]=0.5, [E, A]=0.5}
挖掘频繁3-项集 ：{[E, A, B]=0.5, [A, B, C]=0.5}
挖掘频繁项集 ：{1=[[E], [A], [B], [C]], 2=[[A, B], [B, C], [A, C], [E, B], [E, A]], 3=[[E, A, B], [A, B, C]]}
挖掘频繁关联规则 ：{[E]=[[A], [B], [A, B]], [A]=[[B]], [B]=[[A]], [B, C]=[[A]], [A, C]=[[B]], [E, B]=[[A]], [E, A]=[[B]]}
从测试结果看到，使用Apriori算法挖掘得到的全部频繁项集为：
{1=[[E], [A], [B], [C]], 2=[[A, B], [B, C], [A, C], [E, B], [E, A]], 3=[[E, A, B], [A, B, C]]}
使用Apriori算法挖掘得到的全部频繁关联规则为：
{E}→{A}、{E}→{B}、{E}→{A,B}、{A}→{B}、{B}→{A}、{B,C}→{A}、{A,C}→{B}、{B,E}→{A}、{A,E}→{B}。
㈤ 解释一段Apriori算法的意思，越详细越好偶电脑白痴
这段是经典Ariori算法产生频繁项集的伪代码
㈥ 急求用C实现的Apriori算法的 代码
http://www.csc.liv.ac.uk/~frans/Notes/KDD/AssocRuleMine/apriori.html
.h
====================================
/*----------------------------------------------------------------------
File : apriori.h
Contents: apriori algorithm for finding frequent item sets
(specialized version for FIMI 2003 workshop)
Author : Christian Borgelt
History : 15.08.2003 file created from normal apriori.c
16.08.2003 parameter for transaction filtering added
18.08.2003 dynamic filtering decision based on times added
21.08.2003 transaction sort changed to heapsort
20.09.2003 output file made optional
----------------------------------------------------------------------*/
/*
Modified by : Frédéric Flouvat
Modifications : store the positive and negative border into an
an input trie for ABS
process stastical informations on dataset to stop
the apriori classical iterations
Author : Frédéric Flouvat
----------------------------------------------------------------------*/
#ifndef APRIRORI_H
#define APRIRORI_H
#include <iostream>
using namespace std;
#define MAXIMAL
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include "tract.h"
#include "istree.h"
#include "Application.h"
/*----------------------------------------------------------------------
Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME "fim/apriori"
#define DESCRIPTION "frequent item sets miner for FIMI 2003"
#define VERSION "version 1.7 (2003.12.02) " \
"(c) 2003 Christian Borgelt"
/* --- error codes --- */
#define E_OPTION (-5) /* unknown option */
#define E_OPTARG (-6) /* missing option argument */
#define E_ARGCNT (-7) /* too few/many arguments */
#define E_SUPP (-8) /* invalid minimum support */
#define E_NOTAS (-9) /* no items or transactions */
#define E_UNKNOWN (-18) /* unknown error */
#ifndef QUIET /* if not quiet version */
#define MSG(x) x /* print messages */
#else /* if quiet version */
#define MSG(x) /* suppress messages */
#endif
#define SEC_SINCE(t) ((clock()-(t)) /(double)CLOCKS_PER_SEC)
#define RECCNT(s) (tfs_reccnt(is_tfscan(s)) \
+ ((tfs_delim(is_tfscan(s)) == TFS_REC) ? 0 : 1))
#define BUFFER(s) tfs_buf(is_tfscan(s))
/*----------------------------------------------------------------------
Constants
----------------------------------------------------------------------*/
#ifndef QUIET /* if not quiet version */
/* --- error messages --- */
static const char *errmsgs[] = {
/* E_NONE 0 */ "no error\n",
/* E_NOMEM -1 */ "not enough memory\n",
/* E_FOPEN -2 */ "cannot open file %s\n",
/* E_FREAD -3 */ "read error on file %s\n",
/* E_FWRITE -4 */ "write error on file %s\n",
/* E_OPTION -5 */ "unknown option -%c\n",
/* E_OPTARG -6 */ "missing option argument\n",
/* E_ARGCNT -7 */ "wrong number of arguments\n",
/* E_SUPP -8 */ "invalid minimal support %d\n",
/* E_NOTAS -9 */ "no items or transactions to work on\n",
/* -10 to -15 */ NULL, NULL, NULL, NULL, NULL, NULL,
/* E_ITEMEXP -16 */ "file %s, record %d: item expected\n",
/* E_DUPITEM -17 */ "file %s, record %d: plicate item %s\n",
/* E_UNKNOWN -18 */ "unknown error\n"
};
#endif
/*----------------------------------------------------------------------
Global Variables
----------------------------------------------------------------------*/
#ifndef QUIET
static char *prgname; /* program name for error messages */
#endif
static ITEMSET *itemset = NULL; /* item set */
static TASET *taset = NULL; /* transaction set */
static TATREE *tatree = NULL; /* transaction tree */
static ISTREE *istree = NULL; /* item set tree */
static FILE *in = NULL; /* input file */
static FILE *out = NULL; /* output file */
extern "C" TATREE * apriori( char*fn_in, char*fn_out, int supp, int & level,
Trie * bdPapriori, Trie * bdn, set<Element> * relist, double ratioNfC, double & eps, int ismax,
vector< unsigned int > * stat, int & maxBdP, bool & generatedFk, bool verbose ) ;
#endif
.c
============================================
/*----------------------------------------------------------------------
File : apriori.c
Contents: apriori algorithm for finding frequent item sets
(specialized version for FIMI 2003 workshop)
Author : Christian Borgelt
History : 15.08.2003 file created from normal apriori.c
16.08.2003 parameter for transaction filtering added
18.08.2003 dynamic filtering decision based on times added
21.08.2003 transaction sort changed to heapsort
20.09.2003 output file made optional
----------------------------------------------------------------------*/
/*
Modified by : Frédéric Flouvat
Modifications : store the positive and negative border into an
an input trie for ABS
process stastical informations on dataset to stop
the apriori classical iterations
Author : Frédéric Flouvat
----------------------------------------------------------------------*/
#include "apriori.h"
/*----------------------------------------------------------------------
Main Functions
----------------------------------------------------------------------*/
static void error (int code, ...)
{ /* --- print an error message */
#ifndef QUIET /* if not quiet version */
va_list args; /* list of variable arguments */
const char *msg; /* error message */
assert(prgname); /* check the program name */
if (code < E_UNKNOWN) code = E_UNKNOWN;
if (code < 0) { /* if to report an error, */
msg = errmsgs[-code]; /* get the error message */
if (!msg) msg = errmsgs[-E_UNKNOWN];
fprintf(stderr, "\n%s: ", prgname);
va_start(args, code); /* get variable arguments */
vfprintf(stderr, msg, args);/* print error message */
va_end(args); /* end argument evaluation */
}
#endif
#ifndef NDEBUG /* if debug version */
if (istree) ist_delete(istree);
if (tatree) tat_delete(tatree);
if (taset) tas_delete(taset, 0);
if (itemset) is_delete(itemset);
if (in) fclose(in); /* clean up memory */
if (out) fclose(out); /* and close files */
#endif
exit(code); /* abort the program */
} /* error() */
/*--------------------------------------------------------------------*/
TATREE * apriori( char*fn_in, char*fn_out, int supp, int & level, Trie * bdPapriori,
Trie * bdn , set<Element> * relist , double ratioNfC, double & eps,int ismax,
vector< unsigned int > * stat, int & maxBdP, bool & generatedFk, bool verbose )
{
int i, k, n; /* loop variables, counters */
int tacnt = 0; /* number of transactions */
int max = 0; /* maximum transaction size */
int empty = 1; /* number of empty item sets */
int *map, *set; /* identifier map, item set */
char *usage; /* flag vector for item usage */
clock_t t, tt, tc, x; /* timer for measurements */
double actNfC = 1 ;
double avgNfC = 0 ;
int nbgen = 0 ;
int nbfreq = 0 ;
level = 1 ;
bool endApriori = false ; // boolean to stop the initial classial apriori approach
int bdnsize = 0 ; // number of itemsets found infrequent
/* --- create item set and transaction set --- */
itemset = is_create(); /* create an item set and */
if (!itemset) error(E_NOMEM); /* set the special characters */
taset = tas_create(itemset); /* create a transaction set */
if (!taset) error(E_NOMEM); /* to store the transactions */
if( verbose ) MSG(fprintf(stderr, "\n")); /* terminate the startup message */
/* --- read transactions --- */
if( verbose )MSG(fprintf(stderr, "reading %s ... ", fn_in));
t = clock(); /* start the timer and */
in = fopen(fn_in, "r"); /* open the input file */
if (!in) error(E_FOPEN, fn_in);
for (tacnt = 0; 1; tacnt++) { /* transaction read loop */
k = is_read(itemset, in); /* read the next transaction */
if (k < 0) error(k, fn_in, RECCNT(itemset), BUFFER(itemset));
if (k > 0) break; /* check for error and end of file */
k = is_tsize(itemset); /* update the maximal */
if (k > max) max = k; /* transaction size */
if (taset && (tas_add(taset, NULL, 0) != 0))
error(E_NOMEM); /* add the loaded transaction */
} /* to the transaction set */
fclose(in); in = NULL; /* close the input file */
n = is_cnt(itemset); /* get the number of items */
if( verbose ) MSG(fprintf(stderr, "[%d item(s),", n));
if( verbose ) MSG(fprintf(stderr, " %d transaction(s)] done ", tacnt));
if( verbose ) MSG(fprintf(stderr, "[%.2fs].\n", SEC_SINCE(t)));
/* --- sort and recode items --- */
if( verbose ) MSG(fprintf(stderr, "sorting and recoding items ... "));
t = clock(); /* start the timer */
map = (int*)malloc(is_cnt(itemset) *sizeof(int));
if (!map) error(E_NOMEM); /* create an item identifier map */
n = is_recode(itemset, supp, 2, map); /* 2: sorting mode */
tas_recode(taset, map, n); /* recode the loaded transactions */
max = tas_max(taset); /* get the new maximal t.a. size */
// use in the other part of the implementation to have the corresponding
// identifiant to an internal id
stat->reserve( n+2 ) ;
stat->push_back( 0 ) ;
for(int j= 0; j< n ; j++ )
{
stat->push_back( 0 ) ;
relist->insert( Element( atoi( is_name( itemset, j ) ) ,j) );
}
if( verbose ) MSG(fprintf(stderr, "[%d item(s)] ", n));
if( verbose ) MSG(fprintf(stderr, "done [%.2fs].\n", SEC_SINCE(t)));
/* --- create a transaction tree --- */
if( verbose ) MSG(fprintf(stderr, "creating transaction tree ... "));
t = clock(); /* start the timer */
tatree = tat_create(taset,1); /* create a transaction tree */
if (!tatree) error(E_NOMEM); /* (compactify transactions) */
tt = clock() -t; /* note the construction time */
if( verbose ) MSG(fprintf(stderr, "done [%.2fs].\n", SEC_SINCE(t)));
/* --- create an item set tree --- */
if( verbose ) MSG(fprintf(stderr, "checking subsets of size 1"));
t = clock(); tc = 0; /* start the timer and */
istree = ist_create(n, supp); /* create an item set tree */
if (!istree) error(E_NOMEM);
for (k = n; --k >= 0; ) /* set single item frequencies */
ist_setcnt(istree, k, is_getfrq(itemset, k));
ist_settac(istree, tacnt); /* set the number of transactions */
usage = (char*)malloc(n *sizeof(char));
if (!usage) error(E_NOMEM); /* create a item usage vector */
/* --- check item subsets --- */
while (ist_height(istree) < max && ( ( ismax == -1 && endApriori == false )
|| ist_height(istree) < ismax )
)
{
nbgen = 0 ;
nbfreq = 0 ;
level ++ ;
i = ist_check(istree,usage);/* check current item usage */
if (i < max) max = i; /* update the maximum set size */
if (ist_height(istree) >= i) break;
k = ist_addlvl(istree, nbgen); /* while max. height is not reached, */
if (k < 0) error(E_NOMEM); /* add a level to the item set tree */
if (k != 0) break; /* if no level was added, abort */
if( verbose ) MSG(fprintf(stderr, " %d", ist_height(istree)));
if ((i < n) /* check item usage on current level */
&& (i *(double)tt < 0.1 *n *tc)) {
n = i; x = clock(); /* if items were removed and */
tas_filter(taset, usage); /* the counting time is long enough, */
tat_delete(tatree); /* remove unnecessary items */
tatree = tat_create(taset, 1);
if (!tatree) error(E_NOMEM);
tt = clock() -x; /* rebuild the transaction tree and */
} /* note the new construction time */
x = clock(); /* start the timer */
ist_countx(istree, tatree, nbfreq, istree->supp ); /* count the transaction tree */
tc = clock() -x; /* in the item set tree */
actNfC = 1-double(nbfreq)/double(nbgen) ;
avgNfC = avgNfC + actNfC ;
if( verbose )
{
cout<<" \t Fk : "<<nbfreq<<" Ck : "<<nbgen<<" NFk/Ck "<<actNfC<<" avg NFk/Ck "<<avgNfC/(level-1)<<endl;
}
bdnsize += nbgen - nbfreq ;
if( level >=4 && ( bdnsize / nbgen < 1.5 ) && ( bdnsize > 100 ) )
{
if( actNfC < ratioNfC )
{
eps = 0 ;
endApriori = true ;
}
else if( actNfC > 0.25 )
endApriori = true ;
}
} /* and note the new counting time */
if( verbose ) MSG(fprintf(stderr, " done [%.2fs].\n", SEC_SINCE(t)));
/* --- filter item sets --- */
t = clock(); /* start the timer */
#ifdef MAXIMAL /* filter maximal item sets */
if( verbose ) MSG(fprintf(stderr, "filtering maximal item sets ... "));
if( ratioNfC == 0 || nbgen < k+1 || ist_height(istree)>= max )
ist_filter2(istree, IST_MAXFRQ, 0);
else
ist_filter2(istree, IST_MAXFRQ, bdn);
if( verbose ) MSG(fprintf(stderr, " done [%.2fs].\n", SEC_SINCE(t)));
empty = (n <= 0) ? 1 : 0; /* check whether the empty item set */
#endif /* is maximal */
#ifdef CLOSED /* filter closed item sets */
if( verbose ) MSG(fprintf(stderr, "filtering closed item sets ... "));
ist_filter(istree, IST_CLOSED);
if( verbose ) MSG(fprintf(stderr, " done [%.2fs].\n", SEC_SINCE(t)));
for (k = n; --k >= 0; ) /* check for an item in all t.a. */
if (is_getfrq(itemset, k) == tacnt) break;
empty = (k <= 0) ? 1 : 0; /* check whether the empty item set */
#endif /* is closed */
/* --- print item sets --- */
for (i = ist_height(istree); --i >= 0; )
map[i] = 0; /* clear the item set counters */
if( verbose ) MSG(fprintf(stderr, "writing %s ... ", (fn_out) ? fn_out : "<none>"));
t = clock(); /* start the timer and */
if (fn_out) { /* if an output file is given, */
out = fopen(fn_out, "w"); /* open the output file */
if (!out) error(E_FOPEN, fn_out);
if (empty) fprintf(out, " (%d)\n", tacnt);
} /* report empty item set */
ist_init(istree); /* init. the item set extraction */
set = is_tract(itemset); /* get the transaction buffer */
for (n = empty; 1; n++) { /* extract item sets from the tree */
k = ist_set(istree, set, &supp);
if (k <= 0) break; /* get the next frequent item set */
map[k-1]++; /* count the item set */
if (fn_out) { /* if an output file is given */
for (i = 0; i < k; i++) { /* traverse the items */
fputs(is_name(itemset, set[i]), out);
fputc(' ', out); /* print the name of the next item */
} /* followed by a separator */
fprintf(out, "(%d)\n", supp);
} /* print the item set's support */
else
{
short unsigned * is = new short unsigned[k] ;
for (i = 0; i < k; i++) /* traverse the items */
{
is[i] = set[i] ;
}
if( k < level || nbgen < k+1 || ist_height(istree)>= max )
{
bdPapriori->insert(is, k ,supp ) ;
(*stat)[ 0 ] ++;
(*stat)[ k+1 ]++;
if( maxBdP < k )
maxBdP = k ;
}
else
{
generatedFk = true ;
}
delete[] is;
}
}
if (fn_out) { /* if an output file is given */
if (fflush(out) != 0) error(E_FWRITE, fn_out);
if (out != stdout) fclose(out);
out = NULL; /* close the output file */
}
if( verbose ) MSG(fprintf(stderr, "[%d set(s)] done ", n));
if( verbose ) MSG(fprintf(stderr, "[%.2fs].\n", SEC_SINCE(t)));
/* --- print item set statistics --- */
k = ist_height(istree); /* find last nonzero counter */
if ((k > 0) && (map[k-1] <= 0)) k--;
if( verbose ){
printf("%d\n", empty); /* print the numbers of item sets */
for (i = 0; i < k; i++) printf("%d\n", map[i]);
}
/* --- clean up --- */
#ifndef NDEBUG /* if this is a debug version */
free(usage); /* delete the item usage vector */
free(map); /* and the identifier map */
ist_delete(istree); /* delete the item set tree, */
if (taset) tas_delete(taset, 0); /* the transaction set, */
is_delete(itemset); /* and the item set */
#endif
return tatree ;
}
㈦ 数据挖掘中的apriori算法的具体步骤是什么
算法：Apriori
输入：D - 事务数据库；min_sup - 最小支持度计数阈值
输出：L - D中的频繁项集
方法：
L1=find_frequent_1-itemsets(D); // 找出所有频繁1项集
For(k=2;Lk-1!=null;k++){
Ck=apriori_gen(Lk-1); // 产生候选，并剪枝
For each 事务t in D{ // 扫描D进行候选计数
Ct =subset(Ck,t); // 得到t的子集
For each 候选c 属于 Ct
c.count++;
}
Lk={c属于Ck | c.count>=min_sup}
}
Return L=所有的频繁集；
Procere apriori_gen(Lk-1:frequent(k-1)-itemsets)
For each项集l1属于Lk-1
For each项集 l2属于Lk-1
If((l1[1]=l2[1])&&( l1[2]=l2[2])&&……..
&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])) then{
c=l1连接l2 //连接步：产生候选
if has_infrequent_subset(c,Lk-1) then
delete c; //剪枝步：删除非频繁候选
else add c to Ck;
}
Return Ck;
Procere has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets)
For each(k-1)-subset s of c
If s不属于Lk-1 then
Return true;
Return false;
㈧ apriori算法 怎么处理连续值
Apriori算法流程
1. 扫描数据库，生成候选1项集和频繁1项集。
2. 从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。
2.1 频繁k-1项集生成2项子集，这里的2项指的生成的子集中有两个k-1项集。使如有3个2项频繁集｛a, b｝｛b, c｝｛c, f｝，则它所有的2项子集为｛｛a, b｝｛b, c｝｝｛｛a, b｝｛e, f｝｝｛｛b, c｝｛c, f｝｝
2.2 对由2.1生成的2项子集中的两个项集根据上面所述的定理 i 进行连接，生成k项集。
2.3 对k项集中的每个项集根据如上所述的定理 ii 进行计算，舍弃掉子集不是频繁项集即不在频繁k-1项集中的项集。
2.4 扫描数据库，计算2.3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。
3. 当当前生成的频繁k项集中只有一个项集时循环结束。
㈨ 用Matlab实现apriori算法关联规则的挖掘程序，完整有详细注解
下面这段是apriori算法中由2频繁项集找k频繁项集的程序，程序中有两个问题：
1、似乎while循环的K永远都是固定的，也就是都是频繁2项集的个数。得到频繁3项集后K的个数不是要变吗？如何体现呢？
2、程序中有两个for的大循环，但是发现结果是只要找到一个频繁3项集第二个for循环就会结束，但是其实还应该有其它的频繁3项集。for循环不是应该无条件执行到参数k结束吗？当时k值是15，可是程序结束的时候i=2，j=3,然后j就不执行4以及一直到k的部分了。是什么原因呢？麻烦高手指点一下。急啊……
while( k>0)
le=length(candidate{1});
num=2;
nl=0;
for i=1:k-1
for j=i+1:k
x1=candidate{i}; %candidate初始值为频繁2项集，这个表示频繁项集的第i项
x2=candidate{j};
c = intersect(x1, x2);
M=0;
r=1;
nn=0;
l1=0;
if (length(c)==le-1) & (sum(c==x1(1:le-1))==le-1)
houxuan=union(x1(1:le),x2(le));
%树剪枝,若一个候选项的某个K-1项子集为非频繁，则剪枝掉
sub_set=subset(houxuan);
%生成该候选项的所有K-1项子集
NN=length(sub_set);
%判断这些K-1项自己是否都为频繁的
while(r & M<NN)
M=M+1;
r=in(sub_set{M},candidate);
end
if M==NN
nl=nl+1;
%候选k项集
cand{nl}=houxuan;
%记录每个候选k项集出现的次数
le=length(cand{1});
for i=1:m
s=cand{nl};
x=X(i,:);
if sum(x(s))==le
nn=nn+1;
end
end
end
end
%从候选集中找频繁项集
if nn>=th
ll=ll+1;
candmid{nl}=cand{nl};
pfxj(nl).element=cand{nl};
pfxj(nl).time=nn;
disp('得到的频繁项集为:')
result=(candmid{nl});
disp(result);
end
end
end
end
㈩ 数据挖掘十大算法-
整理里一晚上的数据挖掘算法，其中主要引自wiki和一些论坛。发布到上作为知识共享，但是发现Latex的公式转码到网页的时候出现了丢失，暂时没找到解决方法，有空再回来填坑了。
——编者按
一、 C4.5
C4.5算法是由Ross Quinlan开发的用于产生决策树的算法[1]，该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法主要应用于统计分类中，主要是通过分析数据的信息熵建立和修剪决策树。
1.1 决策树的建立规则
在树的每个节点处，C4.5选择最有效地方式对样本集进行分裂，分裂规则是分析所有属性的归一化的信息增益率，选择其中增益率最高的属性作为分裂依据，然后在各个分裂出的子集上进行递归操作。
依据属性A对数据集D进行分类的信息熵可以定义如下：
划分前后的信息增益可以表示为：
那么，归一化的信息增益率可以表示为：
1.2 决策树的修剪方法
C4.5采用的剪枝方法是悲观剪枝法(Pessimistic Error Pruning，PEP)，根据样本集计算子树与叶子的经验错误率，在满足替换标准时，使用叶子节点替换子树。
不妨用K表示训练数据集D中分类到某一个叶子节点的样本数，其中其中错误分类的个数为J，由于用估计该节点的样本错误率存在一定的样本误差，因此用表示修正后的样本错误率。那么，对于决策树的一个子树S而言，设其叶子数目为L(S)，则子树S的错误分类数为：
设数据集的样本总数为Num，则标准错误可以表示为：
那么，用表示新叶子的错误分类数，则选择使用新叶子节点替换子树S的判据可以表示为：
二、KNN
最近邻域算法(k-nearest neighbor classification, KNN)[2]是一种用于分类和回归的非参数统计方法。KNN算法采用向量空间模型来分类，主要思路是相同类别的案例彼此之间的相似度高，从而可以借由计算未知样本与已知类别案例之间的相似度，来实现分类目标。KNN是一种基于局部近似和的实例的学习方法，是目前最简单的机器学习算法之一。
在分类问题中，KNN的输出是一个分类族群，它的对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。在回归问题中，KNN的输出是其周围k个邻居的平均值。无论是分类还是回归，衡量邻居的权重都非常重要，目标是要使较近邻居的权重比较远邻居的权重大，例如，一种常见的加权方案是给每个邻居权重赋值为1/d，其中d是到邻居的距离。这也就自然地导致了KNN算法对于数据的局部结构过于敏感。
三、Naive Bayes
在机器学习的众多分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive Bayesian Model，NBC)[3]。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。
在假设各个属性相互独立的条件下，NBC模型的分类公式可以简单地表示为：
但是实际上问题模型的属性之间往往是非独立的，这给NBC模型的分类准确度带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型；而在属性相关性较小时，NBC模型的性能最为良好。
四、CART
CART算法(Classification And Regression Tree)[4]是一种二分递归的决策树，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤：将样本递归划分进行建树过程；用验证数据进行剪枝。
五、K-means
k-平均算法(k-means clustering)[5]是源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-means的聚类目标是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类。
5.1 k-means的初始化方法
通常使用的初始化方法有Forgy和随机划分(Random Partition)方法。Forgy方法随机地从数据集中选择k个观测作为初始的均值点；而随机划分方法则随机地为每一观测指定聚类，然后执行“更新”步骤,即计算随机分配的各聚类的图心，作为初始的均值点。Forgy方法易于使得初始均值点散开，随机划分方法则把均值点都放到靠近数据集中心的地方；随机划分方法一般更适用于k-调和均值和模糊k-均值算法。对于期望-最大化(EM)算法和标准k-means算法，Forgy方法作为初始化方法的表现会更好一些。
5.2 k-means的标准算法
k-means的标准算法主要包括分配(Assignment)和更新(Update)，在初始化得出k个均值点后，算法将会在这两个步骤中交替执行。
分配(Assignment)：将每个观测分配到聚类中，使得组内平方和达到最小。
更新(Update)：对于上一步得到的每一个聚类，以聚类中观测值的图心，作为新的均值点。
六、Apriori
Apriori算法[6]是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。Apriori采用自底向上的处理方法，每次只扩展一个对象加入候选集，并且使用数据集对候选集进行检验，当不再产生匹配条件的扩展对象时，算法终止。
Apriori的缺点在于生成候选集的过程中，算法总是尝试扫描整个数据集并尽可能多地添加扩展对象，导致计算效率较低；其本质上采用的是宽度优先的遍历方式，理论上需要遍历次才可以确定任意的最大子集S。
七、SVM
支持向量机(Support Vector Machine, SVM)[7]是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。
除了进行线性分类之外，SVM还可以使用所谓的核技巧有效地进行非线性分类，将其输入隐式映射到高维特征空间中，即支持向量机在高维或无限维空间中构造超平面或超平面集合，用于分类、回归或其他任务。直观来说，分类边界距离最近的训练数据点越远越好，因为这样可以缩小分类器的泛化误差。
八、EM
最大期望算法(Expectation–Maximization Algorithm, EM)[7]是从概率模型中寻找参数最大似然估计的一种算法。其中概率模型依赖于无法观测的隐性变量。最大期望算法经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望(E)，利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化(M)，最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。
九、PageRank
PageRank算法设计初衷是根据网站的外部链接和内部链接的数量和质量对网站的价值进行衡量。PageRank将每个到网页的链接作为对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。
算法假设上网者将会不断点网页上的链接，当遇到了一个没有任何链接出页面的网页，这时候上网者会随机转到另外的网页开始浏览。设置在任意时刻，用户到达某页面后并继续向后浏览的概率，该数值是根据上网者使用浏览器书签的平均频率估算而得。PageRank值可以表示为：
其中，是被研究的页面集合，N表示页面总数，是链接入页面的集合，是从页面链接处的集合。
PageRank算法的主要缺点是的主要缺点是旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多外链，除非它是某个站点的子站点。
十、AdaBoost
AdaBoost方法[10]是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器Ck[，并且如此迭代地进行下去。
AdaBoost方法的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，AdaBoost方法相对于大多数其它学习算法而言，不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。
引用
[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
[2] Altman, N. S. An introction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879
[3] Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6
[4] decisiontrees.net Interactive Tutorial
[5] Hamerly, G. and Elkan, C. Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 2002
[6] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.
[7] Cortes, C.; Vapnik, V. Support-vector networks. Machine Learning. 1995, 20 (3): 273–297. doi:10.1007/BF00994018
[8] Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39 (1):1–38, 1977
[9] Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]
[10] Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855