【mahout笔记】初步理解KNN Linear interpolation item–based（基于物品的knn算法）在mahout的实现

参考大神的博客：https：//blog.csdn.net/wolvesqun/article/details/52757772

以下为大佬博客对KNN Linear interpolation的介绍：

这个算法在mahout-0.8版本中，已经被@Deprecated。

算法来自论文：
This algorithm is based in the paper of Robert M. Bell and Yehuda Koren in ICDM '07.

好吧，这个算法没有任何的例子，也没有任何关于算法的解读，我决定去其他的博客翻找一下KNN算法的资料。

就我浅薄的知识就只是知道这个算法的原名应该叫做k-th nearestneighbour，也就是k-近邻算法。

以下摘自大佬博客：https：//blog.csdn.net/qiang12qiang12/article/details/80281085

KNN思想

给定一个训练集T = {（X1，Y1），（X2，Y2），...，（XN，YN）} T = {（X1，Y1），（X2，Y2），...，（ XN，YN）}，对新输入的实例XX，在训练集中找到与实例XX最近的ķ个实例，根据ķ个实例中大多数类所属的类作为实例XX所属的类。

KNN算法

KNN模型3要素

ķ值得选择，距离度量方法选择，分类决策规则选择　

ķ值得选择

应用中，一般选择较小的ķ值，交叉验证可以选择最优的ķ值 
.K值减小，模型变复杂，容易过拟合（原因：选择较小ķ值时，近似误差减小，估计误差增大）。

近似误差：即对现有训练集的训练误差，更关注“训练”。 
估计误差：即对测试集的测试误差，更关注“测试”。

距离度量方法选择

氏欧距离 
曼哈顿距离 
切比雪夫距离  等等

分类决策规则选择

最常用的是，大多数原则：即由输入实例的ķ个近邻样本中大多数的类别确定输入实例的类。

KNN优缺点

优点

简单，精度高

缺点

计算时间，空间复杂度高

首先我们先把测试代码放上来：

 public static void main(String[] args) throws TasteException, IOException {
// 读取数据
String file = "/Users/zjgy/Documents/dataset/item.csv";
DataModel dataModel = new FileDataModel(new File(file));
System.out.println(dataModel.toString());
// 推荐算法
//itemCF(dataModel);
//userCF(dataModel);
//slopeOne(dataModel);
itemKNN(dataModel);
}
public static void itemKNN(DataModel dataModel) throws TasteException {
ItemSimilarity itemSimilarity = RecommendFactory.itemSimilarity(RecommendFactory.SIMILARITY.EUCLIDEAN, dataModel);
RecommenderBuilder recommenderBuilder = RecommendFactory.itemKNNRecommender(itemSimilarity, new NonNegativeQuadraticOptimizer(), 10);
RecommendFactory.evaluate(RecommendFactory.EVALUATOR.AVERAGE_ABSOLUTE_DIFFERENCE, recommenderBuilder, null, dataModel, 0.7);
RecommendFactory.statsEvaluator(recommenderBuilder, null, dataModel, 2);
LongPrimitiveIterator iter = dataModel.getUserIDs();
while (iter.hasNext()) {
long uid = iter.nextLong();
List list = recommenderBuilder.buildRecommender(dataModel).recommend(uid, RECOMMENDER_NUM);
RecommendFactory.showItems(uid, list, true);
}
}

因为我们是基于物品的KNN算法，也实际上我们可以说是基于物品相似度的KNN算法，所以我们需要先生成一个ItemSimilarity对象，根据我们之间的代码分析，构造这个对象实际上并不需要做任何的数据处理，就是简单的赋值。

1.评价

老规矩，我们先说KNN模型的评价过程，实际上，在之前的三篇博客中，我们都发现了：我们分析完了评价和求准确率和召回率的过程，基本上推荐算法里的东西就就说完了。对实际的推荐过程基本没有什么新的东西可讲了。

还有一个我们从之前的三篇博客里可以知道的经验就是，对于象夫来说，各个阶段都有很多共同的逻辑，比如我们来温习一下评价过程的通用逻辑是什么：

1.对所有的数据集进行划分，随机划分成训练集和测试集（根据trainPercentage，并尽量保证数据分布均匀，即尽量每个用户既有数据在训练集也有数据在测试集）。

2.并用训练集生成一个新的推荐器（此处为KnnItemBasedRecommender）

3.进行评价方法

用多线程遍历每个用户的测试数据{

3.1单个用户的测试数据，用训练数据集训练后，进行估分

3.2用预测分数与实际分数对比，取出差值

}

3.3取出差值的均值作为分数返回

之前的几种算法的评价过程都可以归纳成以上的逻辑，只是不同的算法对单个数据进行估分的过程不相同。

以上过程如下图代码所示：

@Override
public double evaluate(RecommenderBuilder recommenderBuilder,
DataModelBuilder dataModelBuilder,
DataModel dataModel,
double trainingPercentage,
double evaluationPercentage) throws TasteException {
Preconditions.checkNotNull(recommenderBuilder);
Preconditions.checkNotNull(dataModel);
Preconditions.checkArgument(trainingPercentage >= 0.0 && trainingPercentage <= 1.0,
"Invalid trainingPercentage: " + trainingPercentage);
Preconditions.checkArgument(evaluationPercentage >= 0.0 && evaluationPercentage <= 1.0,
"Invalid evaluationPercentage: " + evaluationPercentage);
log.info("Beginning evaluation using {} of {}", trainingPercentage, dataModel);
// 划分训练集和测试集
int numUsers = dataModel.getNumUsers();
FastByIDMap<PreferenceArray> trainingPrefs = new FastByIDMap<PreferenceArray>(
1 + (int) (evaluationPercentage * numUsers));
FastByIDMap<PreferenceArray> testPrefs = new FastByIDMap<PreferenceArray>(
1 + (int) (evaluationPercentage * numUsers));
LongPrimitiveIterator it = dataModel.getUserIDs();
while (it.hasNext()) {
long userID = it.nextLong();
if (random.nextDouble() < evaluationPercentage) {
splitOneUsersPrefs(trainingPercentage, trainingPrefs, testPrefs, userID, dataModel);
}
}
DataModel trainingModel = dataModelBuilder == null ? new GenericDataModel(trainingPrefs)
: dataModelBuilder.buildDataModel(trainingPrefs);
// 生成不同的推荐器对象
Recommender recommender = recommenderBuilder.buildRecommender(trainingModel);
// 评价方法
double result = getEvaluation(testPrefs, recommender);
log.info("Evaluation result: {}", result);
return result;
}

第3步的详细代码如下：

private double getEvaluation(FastByIDMap<PreferenceArray> testPrefs, Recommender recommender)
throws TasteException {
reset();
Collection<Callable<Void>> estimateCallables = Lists.newArrayList();
AtomicInteger noEstimateCounter = new AtomicInteger();
// 每个用户的测试数据都作为一个多线程进行计算，预测分和实际分的差值
for (Map.Entry<Long,PreferenceArray> entry : testPrefs.entrySet()) {
estimateCallables.add(
new PreferenceEstimateCallable(recommender, entry.getKey(), entry.getValue(), noEstimateCounter));
}
log.info("Beginning evaluation of {} users", estimateCallables.size());
RunningAverageAndStdDev timing = new FullRunningAverageAndStdDev();
execute(estimateCallables, noEstimateCounter, timing);
// 获取差值平均值
return computeFinalEvaluation();
}

这些部分就不再多说了，直接进入KNN算法的详细估分过程：

@Override
protected float doEstimatePreference(long theUserID, PreferenceArray preferencesFromUser, long itemID)
throws TasteException {
DataModel dataModel = getDataModel();
int size = preferencesFromUser.length();
FastIDSet possibleItemIDs = new FastIDSet(size);
for (int i = 0; i < size; i++) {
// 遍历训练数据集，将该用户在训练集中有评价的物品的id都加到possibleItemIDs
possibleItemIDs.add(preferencesFromUser.getItemID(i));
}
// 我们需要进行估分的物品id绝对不能在其中，将我们要估分的物品移除
possibleItemIDs.remove(itemID);
// 获取前neighborhoodSize个最接近的物品的list
List<RecommendedItem> mostSimilar = mostSimilarItems(itemID, possibleItemIDs.iterator(),
neighborhoodSize, null);
long[] theNeighborhood = new long[mostSimilar.size() + 1];
theNeighborhood[0] = -1;
List<Long> usersRatedNeighborhood = new ArrayList<Long>();
int nOffset = 0;
for (RecommendedItem rec : mostSimilar) {
// 将最接近物品list中的物品id依次放到theNeighborhood这个数组中来。
theNeighborhood[nOffset++] = rec.getItemID();
}
// 假如最近物品list不为空
if (!mostSimilar.isEmpty()) {
// 将我们要计算的物品id放在theNeighborhood的最末尾
theNeighborhood[mostSimilar.size()] = itemID;
// 遍历theNeighborhood中的物品id，取得所有
for (int i = 0; i < theNeighborhood.length; i++) {
// 获取此次轮到的物品A在训练集中的用户评价列表
PreferenceArray usersNeighborhood = dataModel.getPreferencesForItem(theNeighborhood[i]);
// size1为在训练集中评价了a的用户的数量
int size1 = usersRatedNeighborhood.isEmpty() ? usersNeighborhood.length() : usersRatedNeighborhood.size();
// 遍历usersNeighborhood，并且将用户id放入usersRatedNeighborhood数组
// 加入usersRatedNeighborhood列表的必须是对所有近邻数组中的物品都进行过评价的用户，如果用户制评价了物品A和B没有评价C，这这个用户不能加入
for (int j = 0; j < size1; j++) {
if (i == 0) {
// 首个物品循环的时候直接把userID加到数组里就好了
usersRatedNeighborhood.add(usersNeighborhood.getUserID(j));
} else {
// 非首次循环则进入这块代码块，
// 如果单物品评价的循环次数已经超过了userRatedNeighborhood列表的容量，那么就说明这个对象不可能在列表里，直接跳出该物品循环进入下个物品
if (j >= usersRatedNeighborhood.size()) {
break;
}
long index = usersRatedNeighborhood.get(j);
// 如果这个用户在这次的物品的评价列表里没有出现，或者这个用户就是我们要给推荐的用户，这把usersRatedNeighborhood列表中的这个id拿掉， 同时j --（因为移除了本元素所以需要--）
if (!usersNeighborhood.hasPrefWithUserID(index) || index == theUserID) {
usersRatedNeighborhood.remove(index);
j--;
}
}
}
}
}
double[] weights = null;
if (!mostSimilar.isEmpty()) {
weights = getInterpolations(itemID, theNeighborhood, usersRatedNeighborhood);
}
int i = 0;
double preference = 0.0;
double totalSimilarity = 0.0;
for (long jitem : theNeighborhood) {
Float pref = dataModel.getPreferenceValue(theUserID, jitem);
if (pref != null) {
double weight = weights[i];
preference += pref * weight;
totalSimilarity += weight;
}
i++;
}
return totalSimilarity == 0.0 ? Float.NaN : (float) (preference / totalSimilarity);
}

我们先详细分析一下mostSimilarItems（）这个方法，顾名思义，这个方法的主要作用是获取和该物品最接近的物品列表：

private List<RecommendedItem> mostSimilarItems(long itemID,
LongPrimitiveIterator possibleItemIDs,
int howMany,
Rescorer<LongPair> rescorer) throws TasteException {
// 生成一个新预测器（MostSimilarEstimator对象)
TopItems.Estimator<Long> estimator = new MostSimilarEstimator(itemID, getSimilarity(), rescorer);
// 从可能物品列表中，获取相似度最高的前howMany个物品
return TopItems.getTopItems(howMany, possibleItemIDs, null, estimator);
}

从代码中可以看出比较重要的是getTopItems（）方法，接下来我们再更深入的看一下这个方法：

public static List<RecommendedItem> getTopItems(int howMany,
LongPrimitiveIterator possibleItemIDs,
IDRescorer rescorer,
Estimator<Long> estimator) throws TasteException {
Preconditions.checkArgument(possibleItemIDs != null, "argument is null");
Preconditions.checkArgument(estimator != null, "argument is null");
// 创建一个空的优先级队列，大小为howMany+1
Queue<RecommendedItem> topItems = new PriorityQueue<RecommendedItem>(howMany + 1,
Collections.reverseOrder(ByValueRecommendedItemComparator.getInstance()));
// 先把队列是否满了初始化为没有
boolean full = false;
double lowestTopValue = Double.NEGATIVE_INFINITY;
// 遍历所有可能的物品
while (possibleItemIDs.hasNext()) {
long itemID = possibleItemIDs.next();
// 当rescorer还未空的时候
if (rescorer == null || !rescorer.isFiltered(itemID)) {
double preference;
try {
preference = estimator.estimate(itemID);
} catch (NoSuchItemException nsie) {
continue;
}
// 如果有指定的分数从新计算器对象，则对相似度重新处理，否则就直接用原始相似度
double rescoredPref = rescorer == null ? preference : rescorer.rescore(itemID, preference);
// 相似度不为空，且队列未满或者目前的相似度大于最低相似度。
if (!Double.isNaN(rescoredPref) && (!full || rescoredPref > lowestTopValue)) {
// 如果计算出的相似度，不为空，就生成一个GenericRecommendedItem对象，放入topItems
队列。topItems队列因为自己是一个优先级队列，所以，是会根据传入的优先级（也就是相似度）从大到小进行排序
topItems.add(new GenericRecommendedItem(itemID, (float) rescoredPref));
if (full) {
// 如果队列满了，调用Poll方法
topItems.poll();
} else if (topItems.size() > howMany) {
// 如果队列满了，且遍历完成，则置为已满，并调用poll方法
full = true;
topItems.poll();
}
// 重新定义最低分
lowestTopValue = topItems.peek().getValue();
}
}
}
// 看看有多少物品被加入相似物品队列
int size = topItems.size();
if (size == 0) {
return Collections.emptyList();
}
// 将队列中的RecommenderItem对象，添加到list中，并且进行排序，最后将List返回
List<RecommendedItem> result = Lists.newArrayListWithCapacity(size);
result.addAll(topItems);
Collections.sort(result, ByValueRecommendedItemComparator.getInstance());
return result;
}

从代码中可以看出，实际上这个求最相近物品的计算过程里使用到了估分，下面我来具体看一看这个分和之前的估分有什么区别（如果毫无区别，那不是一个itemCF的翻版吗？）

从代码preference = estimator.estimate(itemID)进去后，的代码如下：

public double estimate(Long itemID) throws TasteException {
// 根据estimate预测器自己已经初始话好的属性toItemID，和本次传入的itemID,生成一个LongPair对象，至于这个对象到底是什么结构完全能从名字中看出。
LongPair pair = new LongPair(toItemID, itemID);
if (rescorer != null && rescorer.isFiltered(pair)) {
return Double.NaN;
}
// 获取两物品之间的相似度（下一张图详细分析这一句）
double originalEstimate = similarity.itemSimilarity(toItemID, itemID);
// 如果没有特别指定分值指定计算器，则直接返回原始的相似度，
// 否则用计算器计算了再返回，我们的代码里是直接放回原始数据
return rescorer == null ? originalEstimate : rescorer.rescore(pair, originalEstimate);
}

我们详细分析获取两个物品之间相似度的过程：

 public final double itemSimilarity(long itemID1, long itemID2) throws TasteException {
DataModel dataModel = getDataModel();
PreferenceArray xPrefs = dataModel.getPreferencesForItem(itemID1);
PreferenceArray yPrefs = dataModel.getPreferencesForItem(itemID2);
int xLength = xPrefs.length();
int yLength = yPrefs.length();
if (xLength == 0 || yLength == 0) {
return Double.NaN;
}
long xIndex = xPrefs.getUserID(0);
long yIndex = yPrefs.getUserID(0);
int xPrefIndex = 0;
int yPrefIndex = 0;
double sumX = 0.0;
double sumX2 = 0.0;
double sumY = 0.0;
double sumY2 = 0.0;
double sumXY = 0.0;
double sumXYdiff2 = 0.0;
int count = 0;
// No, pref inferrers and transforms don't appy here. I think.
while (true) {
int compare = xIndex < yIndex ? -1 : xIndex > yIndex ? 1 : 0;
if (compare == 0) {
// Both users expressed a preference for the item
double x = xPrefs.getValue(xPrefIndex);
double y = yPrefs.getValue(yPrefIndex);
sumXY += x * y;
sumX += x;
sumX2 += x * x;
sumY += y;
sumY2 += y * y;
double diff = x - y;
sumXYdiff2 += diff * diff;
count++;
}
if (compare <= 0) {
if (++xPrefIndex == xLength) {
break;
}
xIndex = xPrefs.getUserID(xPrefIndex);
}
if (compare >= 0) {
if (++yPrefIndex == yLength) {
break;
}
yIndex = yPrefs.getUserID(yPrefIndex);
}
}
double result;
if (centerData) {
// 如果有centerData为true则用这种方法进行计算
// See comments above on these computations
double n = (double) count;
double meanX = sumX / n;
double meanY = sumY / n;
// double centeredSumXY = sumXY - meanY * sumX - meanX * sumY + n * meanX * meanY;
double centeredSumXY = sumXY - meanY * sumX;
// double centeredSumX2 = sumX2 - 2.0 * meanX * sumX + n * meanX * meanX;
double centeredSumX2 = sumX2 - meanX * sumX;
// double centeredSumY2 = sumY2 - 2.0 * meanY * sumY + n * meanY * meanY;
double centeredSumY2 = sumY2 - meanY * sumY;
result = computeResult(count, centeredSumXY, centeredSumX2, centeredSumY2, sumXYdiff2);
} else {
// 我们是用这个方法进行计算的
// 相似度的计算公式为1/(1+sqrt((x1-y1)^2+(x2-y2)^2+...+(xn-yn)^2))/sqrt(n)。
// x y分别是不同用户的分值。其实sqrt(n)更像一个正则量，我在上一篇也说过
result = computeResult(count, sumXY, sumX2, sumY2, sumXYdiff2);
}
if (similarityTransform != null) {
result = similarityTransform.transformSimilarity(itemID1, itemID2, result);
}
if (!Double.isNaN(result)) {
result = normalizeWeightResult(result, count, cachedNumUsers);
}
return result;
}

计算物品相似度的方式和itemCF一样一样？取出两个物品的评分矩阵，如果训练集中两个矩阵有一个为空矩阵，则直接返回Double.NaN。如果两个矩阵都不为空，则分别取出第一个user的id，如果id相同，则分别取出各自的评分算出各种值和差值，如果各自矩阵的userId没有取完，则分别取下一个；如果id不同，则保留较大的那个，较小的跳过取下一个userId，直到其中一个矩阵的userId被取空。相似度的计算公式为1/(1+sqrt((x1-y1)^2+(x2-y2)^2+...+(xn-yn)^2))/sqrt(n)。x y分别是不同用户的分值。其实sqrt(n)更像一个正则量，这段话就是从itemCF里拷贝出来的，算给自己省点力。

根据上面的几份代码可以看出，我们计算了目标物品和其他可能物品的相似度（有可能计算不出来），取出前neighborhoodSize个（neighborhoodSize为参数传入，代码中是所有的可能物品有都返回，但是一般不能全部返回）。然后根据该物品的近邻物品和本物品，依次从取出对这些物品评过分的用户，将对所有近邻物品（包括本物品）都评价过的用户单独整理出来，根据这些人对近邻物品的评价，计算权重：

weights = getInterpolations(itemID, theNeighborhood, usersRatedNeighborhood);

即上面这条代码，深入看是如下代码：

 private double[] getInterpolations(long itemID,
long[] itemNeighborhood,
Collection<Long> usersRatedNeighborhood) throws TasteException {
// 取出非本物品的其他物品个数，为length，将本物品的那一项id置为-1，并跳出循环
int length = 0;
for (int i = 0; i < itemNeighborhood.length; i++) {
if (itemNeighborhood[i] == itemID) {
itemNeighborhood[i] = -1;
length = itemNeighborhood.length - 1;
break;
}
}
int k = length;
double[][] aMatrix = new double[k][k];
double[] b = new double[k];
int i = 0;
// 获取训练集数据
DataModel dataModel = getDataModel();
// 获取对所有近邻物品都评分过的用户的数量
int numUsers = usersRatedNeighborhood.size();
// 遍历近邻物品列表
for (long iitem : itemNeighborhood) {
// 如果物品是id为-1的物品则直接跳出,否则继续操作
if (iitem == -1) {
break;
}
// 初始化
int j = 0;
double value = 0.0;
// 再一次遍历近邻物品列表（两次遍历应该是为了形成矩阵，毕竟x[a,b]和x[b,a]在关系数据上相等，但是在意义上不同），计算一个矩阵数据
for (long jitem : itemNeighborhood) {
// 如果遍历到id为-1的物品则跳出循环，否则继续操作
if (jitem == -1) {
continue;
}
// 遍历共同用户表，取出iitem和jitem 共同用户的评分，计算乘积（如果俩物品id相同也一样计算）
// value = iprev1*jprev1+...+iprevn*jprevn
for (long user : usersRatedNeighborhood) {
float prefVJ = dataModel.getPreferenceValue(user, iitem);
float prefVK = dataModel.getPreferenceValue(user, jitem);
value += prefVJ * prefVK;
}
// aMatrix[i][j] = (iprev1*jprev1+...+iprevn*jprevn)/n 等于是求均值
aMatrix[i][j] = value/numUsers;
j++;
}
i++;
}
// 再一次遍历近邻物品，算出所有近邻物品与带预测物品的value均值，计算方法同上
i = 0;
for (long jitem : itemNeighborhood) {
// 当物品id为-1的时候跳出，否则继续下面的代码
if (jitem == -1) {
break;
}
// 遍历所有共同用户，并计算此次循环取出的物品和带预测物品的之间的value已经均值
double value = 0.0;
for (long user : usersRatedNeighborhood) {
float prefVJ = dataModel.getPreferenceValue(user, jitem);
float prefVI = dataModel.getPreferenceValue(user, itemID);
value += prefVJ * prefVI;
}
b[i] = value / numUsers;
i++;
}
// Find the larger diagonal and calculate the average
double avgDiagonal = 0.0;
if (k > 1) {
double diagonalA = 0.0;
// 取出矩阵中所有自己和自己的数据
for (i = 0; i < k; i++) {
diagonalA += aMatrix[i][i];
}
// 取出矩阵中itemid不同的数据
double diagonalB = 0.0;
for (i = k - 1; i >= 0; i--) {
for (int j = 0; j < k; j++) {
diagonalB += aMatrix[i--][j];
}
}
// 取出diagonalA和diagonalB中较大的那个除以近邻物品数算平均值
avgDiagonal = Math.max(diagonalA, diagonalA) / k;
}
// Calculate the average of non-diagonal values
double avgMatrixA = 0.0;
double avgVectorB = 0.0;
for (i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (i != j || k <= 1) {
avgMatrixA += aMatrix[i][j];
}
}
avgVectorB += b[i];
}
// avgMatrixA为不相同物品矩阵数据的总和除以k(k-1)
// avgVectorB为近邻物品与预测物品对应向量的数据的总和除以k
if (k > 1) {
avgMatrixA /= k * k - k;
}
avgVectorB /= k;
double numUsersPlusBeta = numUsers + BETA; // BETA默认为500
// 计算一个均值average，如果是i=j则用avgDiagonal, 如果i!=j则用avgMatrixA
// 依次重置aMatrix[i][j]的数据，aMatrix[i][j] = (numUsers * aMatrix[i][j] + 500 * average) / （500+numUsers）
// 并且对每个近邻物品重置向量b, b[i] = (numUsers*b[i] + 500*avgVectorB)/(numUser+500)
for (i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
double average;
if (i == j && k > 1) {
average = avgDiagonal;
} else {
average = avgMatrixA;
}
aMatrix[i][j] = (numUsers * aMatrix[i][j] + BETA * average) / numUsersPlusBeta;
}
b[i] = (numUsers * b[i] + BETA * avgVectorB) / numUsersPlusBeta;
}
return optimizer.optimize(aMatrix, b);
}

上图的代码主要是共同用户评分算出了一个近邻物品之间相互对应的矩阵，一个近邻物品对我们要计算的物品的对应向量。我们继续用这个矩阵和向量做计算，optinizer.optimize()方法的代码如下：

 /**
* Non-negative Quadratic Optimization.
*
* @param matrix
*
matrix nxn positions
* @param b
*
vector b, n positions
* @return vector of n weights
*/
@Override
public double[] optimize(double[][] matrix, double[] b) {
// k为向量b的长度，也就是近邻物品的个数
int k = b.length;
// 初始化两个空数组，大小为近邻物品的个数
double[] r = new double[k];
double[] x = new double[k];
// 用3.0/k来填充x数组（也可以叫向量吧，其实）
Arrays.fill(x, 3.0 / k);
// 遍历，MAX_ITERATIONS为1000，所以我猜测最多可以一次处理1000个物品
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
double rdot = 0.0;
// 遍历matrix的每一行
// sumAw为单行中的每一个数值*x向量中对应的值的总和
// rn为b中的单个数据-sumAw
// 根据matrix和b的定义，我们知道，sumAw为近邻列表中单个物品与其他物品关系数据*(3.0/k)的值的总和，而rn为（单个物品与预测物品的关系数据-该单个物品与其他物品关系数据*(3.0/k)）
// 然后根据rn 计算rdot.rdot为rn的平方和
// 用rn给数组r[n]赋值
for (int n = 0; n < k; n++) {
double sumAw = 0.0;
double[] rowAn = matrix[n];
for (int i = 0; i < k; i++) {
sumAw += rowAn[i] * x[i];
}
// r = b - Ax; // the residual, or 'steepest gradient'
double rn = b[n] - sumAw;
// find active variables - those that are pinned due to
// nonnegativity constraints; set respective ri's to zero
// 如果rn为负，且x[n]的值小于10^(-10)（x[n]太小）的rn直接置为0.0，并不计入rdot的计算
if (x[n] < EPSILON && rn < 0.0) {
rn = 0.0;
} else {
// max step size numerator
// rn>=0且x[n]不会太小则，加入rdot的计算
rdot += rn * rn;
}
r[n] = rn;
}
// 如果rdot <= 0.1，则认为rdot太小，不再计入下面的计算
if (rdot <= CONVERGENCE_LIMIT) {
break;
}
// 取出Matrix的单行与向量r（上面计算得到）进行点乘得到sumAr
// 再用sumAr乘以r向量的每一个值，算出这些结果之和rArdotSum
// max step size denominator
double rArdotSum = 0.0;
for (int n = 0; n < k; n++) {
double sumAr = 0.0;
double[] rowAn = matrix[n];
for (int i = 0; i < k; i++) {
sumAr += rowAn[i] * r[i];
}
rArdotSum += r[n] * sumAr;
}
// max step size
// 用之前算出的rdot/rArdotSum得到stepSize
double stepSize = rdot / rArdotSum;
// 如果stepSize无意义则用默认值给他赋值
if (Double.isNaN(stepSize)) {
stepSize = DEFAULT_STEP;
}
// adjust step size to prevent negative values
for (int n = 0; n < k; n++) {
if (r[n] < 0.0) {
double absStepSize = stepSize < 0.0 ? -stepSize : stepSize;
stepSize = Math.min(absStepSize, Math.abs(x[n] / r[n])) * stepSize / absStepSize;
}
}
// update x values
for (int n = 0; n < k; n++) {
x[n] += stepSize * r[n];
if (x[n] < EPSILON) {
x[n] = 0.0;
}
}
// TODO: do something in case of divergence
}
return x;
}

这块代码是在太难懂了。。。总之就是不断的计算计算，我还是没有理解这块计算到底是用什么公式来进行计算的，总而言之，我们会根据举证和向量，算出各个物品相对于预测物品的权值x。因为在训练集里，我们针对的这个用户对近邻物品肯定都是有评分的，就算出用户对近邻物品的评分*权重的总和全重总和，然后用preference/totalSimilarity来算预测分。

因为在测试集里的用户对对应物品都有实际评分，所以根据实际评分和预测分之间的计算差值的绝对值的平均值作为评分返回。

2. 准确率和召回率

一知半解的路过的评价过程，我们来看一看如何计算准确率和召回率的，实际上，根据前几个算法的分析，这部分代码将会包含整个推荐过程。

划分训练集和测试集的过程，毋庸赘言，和之前用的是同一套逻辑，我们先来复习一下：

每个用户依次循环 {

1. 根据均值+标准差算出阈值

2. 取出实际评分中的正相关记录。

3. 划分训练集（实际上每个用户的训练集就是除了他的正相关记录以外的他的评分和其他人的所有记录）

4. 按照训练集对训练集对该用户没有评分过的物品进行估分，并进行推荐（取评分最高N个）

5. 假设推荐数据即是预测正相关，用计算公式计算单个用户的准确率和召回率

}

6. 计算总体的准确率和召回率

本来觉得应该有什么可以一说的东西，发现推荐的算法和上面的很大相同，就是先根据训练集算各种矩阵向量，然后算出近邻物品和相似权值进行股份，取前n个，作为正相关物品返回。略过。

3. 实际推荐

和算准确率和召回率的中的推荐过程基本相同，即是把所有数据当做训练集，然后算各种矩阵向量，然后算出近邻物品和相似权值进行股份，取前n个，作为推荐物品返回。_(:з」∠)_

最后

以上就是文艺猫咪为你收集整理的【mahout笔记】初步理解KNN Linear interpolation item–based（基于物品的knn算法）在mahout的实现的全部内容，希望文章能够帮你解决【mahout笔记】初步理解KNN Linear interpolation item–based（基于物品的knn算法）在mahout的实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。