〇、序文
立异关于学术研讨或工业运用都具有显而易见的重要作用，现在国家也提出了要树立立异型国家的发展战略。假如回到咱们所评论的图画处理或数据发掘研讨，细细品读其间的某些点滴，你是否能窥探出少许启迪?首要，立异能够分红两种，一种是原始立异，别的一种便是所谓的二次立异。假如一个东西曩昔彻底不存在，你鬼使神差的就想出来，那便是原始立异。比方图灵开端惊天动地地构想出图灵机模型便是原始立异。到现在也没有任何迹象标明，他遭到了什么事或什么人的启示。事实上，现在人们(包含我学习图灵机的时分)也十分惊奇，图灵是怎么提出这种前无古人的奇思妙想的!
二次立异也有许多种办法。比方逆向立异。听说人们在创造吸尘器之前最早创造的是吹尘器。一吸一吹，看似简略的一个倒置，作用却如此奇特。现在同学们学习形式匹配算法时，必定是言必称KMP算法。确实，就原有的思路来说，KMP算法现已是做到极致了。但假如你还想有所打破呢?那就得首要打破旧有的条条框框。所以Boyer和Moore逆其道而行之，便提出了BM算法。KMP是早年向后做比较，而BM则是从后向前做比较。BM算法不只供给了功率，更重要的是，由他们所提出的新思路为发端，后续产生了一个巨大的算法族。像BMH，BMHS等等又接二连三。现在实践中依据BM算法的改善算法(比较于KMP)运用得其实更为广泛!
可是今日要谈的还不是逆序立异的论题。咱们要谈的是二次立异中别的一种办法，暂时称之为“推衍立异”。这个思路在现代核算机科学中可谓随处可见，假如你还没有捉住他的名门，那么阐明就研讨工作来说，你还没入门。举一个简略的比方作为序文的完毕。开端，“伟哥”是作为医治心绞痛的药物而研制的。可是，后来在临床试验中发现对医治男性勃起功能障碍愈加有用。所以现在它主要被运用于这方面的疾病。所以咱们所说的推衍的大约意思便是，把一个范畴的作用平行地转移到别的一个范畴，说不定就能发挥起效!希望本文在这方面能够给咱们一些启示。
一、均匀值与中位数：一对死缠烂打的概念
均匀数是计算学中用来衡量全体水平的一个计算量。可是，显着它并不“完美”。举个比方，现在房间里有6个人，他们的财富不尽相同，但又相差无几，这时咱们能够说他们的均匀身价是100万元。这个均匀数根本上是有含义的，因为在假定前提下，咱们知道他们6个人的财富或多或少都在100万元上下。现在马云忽然来了，然后房间里变成7个人了。相同的问题，房间里一切的人均匀身价或许现已打破100亿，可是这个均匀数就没有什么含义了。现在房间里没有谁的身价在100亿上下。这时就引出了中位数的概念!把一组数从小到大摆放，取中心方位的那个数来作为衡量该组全体水平的一个计算量。假如取包含马云在内的7个人之财富的中位数，咱们知道应该仍是100万左右，那么它显着是有含义的，它至少代表了这个全体中绝大多少人的状况。
你看出中位数的含义和作用了吗?现在当数据点散布比较均匀的时分，均匀值是有含义的。可是一旦数据中存在异常值时，均匀数就有或许失灵，这时就要用中位数来排除去异常值的影响。可是均匀数依然有存在的价值，(仅仅某些时分咱们要对其进行批改)。例如体育比赛时的打分机制，一般是“去掉一个最高分，去掉一个最低分，然后去均匀值”。显着在体育比赛打分中，用中位数就不适宜。所以咱们说均匀数和中位数便是一对死缠烂打的狐朋狗友!后边的内容会评论这对概念在图画处理和数据发掘中的重要运用。这涉及到简略滑润、中值滤波、K-means算法、k-Median算法等。你应该留意领会前面谈到的推衍立异思维。这能很好地协助你触类旁通。
二、简略滑润与中值滤波：一起联系到LeetCode上一道Hard等级的标题
实践中图画因为遭到环境的影响，很简略被噪声所污染。如下图中的左上所示，这是一幅被椒盐噪声污染的图画。噪声体现为原本过渡滑润的(天然图画)区域中一个突兀的像素值。处理它最简略的战略是用一个低通滤波器对信号进行过滤。比方能够选用简略滑润算法。说白了，便是针对某个像素点，在其范畴的一个小窗口内(例如3×3)，对一切像素值取均匀，然后用这个均匀值来代替窗口中心方位的像素值。这样就能缩小噪声和非噪声像素之间的间隔。也便是让原本高的值变低一点，而让原本低的值变高一点。作用如左下图所示。易见，简略滑润有必定作用，可是并不“完美”。举个比方，现在有一杯碱性溶液(PH>7)，咱们不断向其间参加纯水来稀释，作用PH值会越来越小。可是不管咱们放多少水，这个值也不或许小于7。就算竭尽全世界的水，它的全体依然呈现碱性!
有没有更好的办法?假如你还没有想到用中位数来代替均值，那么我觉得你的脑筋应该不必再继续读下去了!已然(椒盐)噪声是一个异常值，那么显着用中位数的办法来将其排掉是最好的挑选了，这便是所谓的“中值”滤波的根本思维。上图右下便是选用中值滤波算法处理的图画，显着比简略滑润作用好。
可是，问题还没完!你有没有想过中值滤波相关于简略滑润的一个缺乏或许下风?是的，中值滤波的复杂度太高，核算起来那是适当的耗时。为什么我会想到这个论题。因为最近我在更新我的MagicHouse(一款小型的图画处理软件http://blog.csdn.NET/baimafujinji/article/details/50500757)。原本中值滤波算法是由我的刘师弟完结的。他曾经是腾讯电脑管家研制的开端中心成员，现在现已自主创业变成刘总了~我也趁便遥祝他宏图大展：)。刘同学写的中值滤波没有选用进行任何优化办法(当然这也是为了算法演示之用，假如优化了他人比较难掌握原始算法的中心思维)，每次履行起来都跟感觉死机了相同。所以最近我决议重写这个算法。
有爱好的读者无妨搜一下关于中值滤波的加快算法，结论是这方面的paper许多，但我不得不告知你大部分其实没啥立异。许多都是在串行转并行上下功夫，我真不以为这有啥含义。因为它们的根底依然是下面我要谈的两个算法。
首要来看Leetcode上一道评级为Hard等级的标题，如下。两个有序数组，求它们兼并后的中位数。这当然没啥难的，你或许会想到兼并后用一个quicksort()，然后取中心方位。作用上当然能够得到正确答案。可是必定要留意：标题要求算法时刻复杂度是O(log(t))，t是兼并后数组的长度。可是，quicksort()的复杂度应该是O(t·log(t))。显着这样做行不通。满意时刻复杂度要求才是本题的难点!
有没有什么好办法?标题给出的提示是要用“分治法”战略。并且你应该能想到是，咱们要取中位数的两个子数组原本便是有序的，这个条件有必要要好好运用。所以，本题的战略应该是：
该办法的中心是将原问题转变成一个寻觅第k小数的问题(假定两个原序列升序摆放)，这样中位数实践上是第(m+n)/2小的数。所以只需处理了第k小数的问题，原问题也得以处理。
首要假定数组A和B的元素个数都大于k/2，咱们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素别离表明A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种状况：>、<和=。假如A[k/2-1]
当A[k/2-1]=B[k/2-1]时，则现已找到了第k小的数，也即这个持平的元素，将其记为m。因为在A和B中别离有k/2-1个元素小于m，所以m便是第k小的数。(这儿或许有人会有疑问，假如k为奇数，则m不是中位数。当然这种状况咱们后边给出的代码里已有做特别考虑，但整个算法的大体思路并无不同)
经过上面的剖析，咱们即能够选用递归的办法完成寻觅第k小的数。此外还需要考虑几个边界条件：
假如A或许B为空，则直接回来B[k-1]或许A[k-1];
假如k为1，咱们只需要回来A[0]和B[0]中的较小值;
假如A[k/2-1]=B[k/2-1]，回来其间一个;
终究完成的代码为：
[cpp] view plain copy
vector
{
//Always assume that size1 is equal or smaller than size2
if (size1 > size2)
return findKth(nums2, size2, it2, nums1, size1, it1, k);
if (size1 == 0) return *(it2+k-1);
if (k == 1) return min(*it1, *it2);
//Divide k into two parts
int offset1 = min(k / 2, size1);
int offset2 = k – offset1;
if (*(it1+offset1-1) <= *(it2+offset2-1))
{
return findKth(nums1, size1 – offset1 , it1+offset1, nums2, offset2, it2, k – offset1);
}
else
{
return findKth(nums1, offset1, it1, nums2, size2 – offset2, it2+offset2, k – offset2);
}
}
double findMedianSortedArrays(vector
int m = nums1.size();
int n = nums2.size();
int total = m + n;
double result = findKth(nums1, m, nums1.begin(), nums2, n, nums2.begin(), (total + 1) / 2);
if ((total & 1) == 0) //Odd
{
result = (result + findKth( nums1, m, nums1.begin(), nums2, n, nums2.begin(), total / 2 + 1)) / 2;
}
return result;
}
经过对上述LeetCode标题的评论，其完成已能够给出咱们一些优化的主意了。来看下面这个图，当咱们开端核算赤色像素的邻域中值时，其完成已得到了红框中像素值的一个有序摆放。然后在核算绿色像素的邻域中值时，咱们把滑块向后移动。这时为了防止重复核算，必定要充分运用之前的有序作用。除掉最左边三个像素后的红框中的6个像素依然有序，这时只需把新参加的绿框中的三个元素也做排序，然后得到两个有序的序列，是不是就变成了上咱们评论的问题了?并且，这个算法面临更大的滑动窗口时，优势会更为显着。
可是，假如咱们只想核算3×3邻域内的中值，其实还有别的一个挑选。例如下面的邻域
0 1 2
3 4 5
6 7 8
首要对窗口内的每一列别离核算最大值，中值和最小值，这样就得到了3组数据
最大值组：Max0 = max[P0，P3，P6]，Max1 = max[P1，P4，P7]，Max2 = max[P2，P5，P8]
中值组： Med0 = med[P0，P3，P6]，Med1 = med[P1，P4，P7]， Med2 = med[P2，P5，P8]
最小值组：Min0 = Min[P0，P3，P6]，Min1 = Min[P1，P4，P7]，Min2 = max[P2，P5，P8]
由此能够看到，最大值组中的最大值与最小值组中的最小值必定是9个元素中的最大值和最小值，不或许为中值，剩余7个;中值组中的最大值至少大于5个像素，中值组中的最小值至少小于5个像素，不或许为中值，剩余5个;最大值组中的中值至少大于5个元素，最小值组中的中值至少小于5个元素，不或许为中值，终究剩余3个要比较的元素，即
最大值组中的最小值Maxmin，中值组中的中值Medmed，最小值组中的最大值MinMax;找出这三个值中的中值为9个元素的中值。
选用上述办法，也会大大下降核算量。可见规划一个好算法永远是那么的重要!
三、数据发掘中的K-means和K-median
聚类是将相似目标归到同一个簇中的办法，这有点像全自动分类。簇内的目标越相似，聚类的作用越好。支撑向量机、神经网络所评论的分类问题都是有监督的学习办法，现在咱们所介绍的聚类则是无监督的。其间，K均值(K-means)是最根本、最简略的聚类算法。
在K均值算法中，质心是界说聚类原型(也便是机器学习取得的作用)的中心。在介绍算法施行的具体过程中，咱们将演示质心的核算办法。并且你将看到除了榜首次的质心是被指定的以外，尔后的质心都是经由核算均值而取得的。
首要，挑选K个初始质心(这K个质心并不要求来自于样本数据集)，其间K是用户指定的参数，也便是所希望的簇的个数。每个数据点都被收归到距其最近之质心的分类中，而同一个质心所收归的点集为一个簇。然后，依据本次分类的作用，更新每个簇的质心。重复上述数据点分类与质心改动过程，直到簇内数据点不再改动，或许等价地说，直到质心不再改动。
根本的K均值算法描绘如下：
依据数据点到新质心的间隔，再次对数据会集的数据进行分类，如图13-2(c)所示。然后，算法依据新的分类来核算新的质心，并再次依据数据点到新质心的间隔，对数据会集的数据进行分类。作用发现簇内数据点不再改动，所以算法履行完毕，终究的聚类作用如图13-2(d)所示。
关于间隔函数和质心类型的某些组合，算法总是收敛到一个解，即K均值抵达一种状况，聚类作用和质心都不再改动。但为了防止过度迭代所导致的时刻耗费，实践中，也常用一个较弱的条件替换掉“质心不再发生变化”这个条件。例如，运用“直到仅有1%的点改动簇”。
虽然K均值聚类比较简略，但它也确实适当有用。它的某些变种乃至更有用， 并且不太受初始化问题的影响。但K均值并不合适一切的数据类型。它不能处理非球形簇、不同尺度和不同密度的簇，虽然指定足够大的簇个数时它一般能够发现纯子簇。对包含离群点的数据进行聚类时，K均值也有问题。在这种状况下，离群点检测和删去大有协助。K均值的另一个问题是，它对初值的挑选是灵敏的，这阐明不同初值的挑选所导致的迭代次数或许相差很大。此外，K值的挑选也是一个问题。显着，算法自身并不能自适应地断定数据集应该被划分红几个簇。终究，K均值仅限于具有质心(均值)概念的数据。一种相关的K中心点聚类技能没有这种约束。在K中心点聚类中，咱们每次挑选的不再是均值，而是中位数。这种算法完成的其他细节与K均值相差不大，咱们不再赘述。
终究咱们给出一个实践运用的比方。(代码选用我最喜欢用做数据发掘的R言语来完成)
一组来自世界银行的数据计算了30个国家的两项目标，咱们用如下代码读入文件并显现其间最开端的几行数据。可见，数据共涣散列，其间榜首列是国家的姓名，该项与后边的聚类剖析无关，咱们更关怀后边两列信息。第二列给出的该国第三工业增加值占GDP的比重，终究一列给出的是人口结构中年纪大于等于65岁的人口(也便是老龄人口)占总人口的比重。
为了便利后续处理，下面临读入的数据库进行一些必要的预处理，主要是调整列标签，以及用国名替换掉行标签(一起删去包含国名的列)。
假如你制作这些数据的散点图，不难发现这些数据大致能够分为两组。事实上，数据中有一半的国家是OECD成员国，而别的一半则归于发展中国家(包含一些东盟国家、南亚国家和拉美国家)。所以咱们能够选用下面的代码来进行K均值聚类剖析。
关于聚类作用，限于篇幅咱们依然只列出了最开端的几条。可是假如用图形来显现的话，或许更易于承受。下面是示例代码。
上述代码的履行作用如图13-3所示。
现在假如我问能不能提出别的一种与k-means相似的算法，你会想到什么?假如你能从k-均值算法想到提出k-中值算法，那么你算是没白读这篇文章!触类旁通，触类旁通这招你算真学会了。(我想我现已无需再具体介绍k-中值算法的细节了，根本上和k-means相同，仅仅把一切均值呈现的当地换成中值罢了)这个思维看起如同很不起眼，可是你还甭说，k-median算法还真的存在，并且是k-means算法的一个重要弥补和改善。你或许会说提出k-median算法的人肯定是捡了一个大便宜，这么轻轻松松地就提出了一个足以留名的算法。但其实我想说，真实想到这一点的人，功力也肯定不行小觑。冰冻三尺、非一日之寒。唯有根底厚实，内力深沉的咱们才干具有这般敏锐的立异嗅觉。
