在分佈式系統中，負載均衡是必不可少的一個模塊，dubbo 中提供了五種負載均衡的實現，在閱讀這塊源碼之前，建議先學習負載均衡的基礎知識。把看源碼當做一個印證自己心中所想的過程，這樣會得到事半功倍的效果

以下源碼分析基於 dubbo 2.77 版本

類結構

先來看一下這一塊的類結構圖

大部分算法都是在權重比的基礎上進行負載均衡，RandomLoadBalance 是默認的算法

AbstractLoadBalance

AbstractLoadBalance 對一些通用的操作做了處理，是一個典型的模板方法模式的實現

select 方法只做一些簡單的範圍校驗，具體的實現有子類通過 doSelect 方法去實現

    @Override
    public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        if (CollectionUtils.isEmpty(invokers)) {
            return null;
        }
        if (invokers.size() == 1) {
            return invokers.get(0);
        }
        return doSelect(invokers, url, invocation);
    }

getWeight方法封裝了獲取一個調用者的權重值的方法，並加入了預熱處理

    int getWeight(Invoker<?> invoker, Invocation invocation) {
        int weight;
        URL url = invoker.getUrl();
        // Multiple registry scenario, load balance among multiple registries.
        // 註冊中心不需要預熱
        if (REGISTRY_SERVICE_REFERENCE_PATH.equals(url.getServiceInterface())) {
            weight = url.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY, DEFAULT_WEIGHT);
        } else {
            // 獲取配置的權重值
            weight = url.getMethodParameter(invocation.getMethodName(), WEIGHT_KEY, DEFAULT_WEIGHT);
            if (weight > 0) {
                // 獲取服務提供者啟動時的時間戳
                long timestamp = invoker.getUrl().getParameter(TIMESTAMP_KEY, 0L);
                if (timestamp > 0L) {
                    //  獲取啟動時長
                    long uptime = System.currentTimeMillis() - timestamp;
                    // 當前時間小於服務提供者啟動時間，直接給一個最小權重1
                    if (uptime < 0) {
                        return 1;
                    }
                    // 獲取預熱時間
                    int warmup = invoker.getUrl().getParameter(WARMUP_KEY, DEFAULT_WARMUP);
                    // 如果小於預熱時間，計算權重
                    if (uptime > 0 && uptime < warmup) {
                        weight = calculateWarmupWeight((int)uptime, warmup, weight);
                    }
                }
            }
        }
        // 取與零比較的最大值，保證不會出現負值權重
        return Math.max(weight, 0);
    }

calculateWarmupWeight 方法用來計算權重，保證隨着預熱時間的增加，權重逐漸達到設置的權重

    static int calculateWarmupWeight(int uptime, int warmup, int weight) {
        // 運行時間/(預熱時間/權重)
        int ww = (int) ( uptime / ((float) warmup / weight));
        // 保證計算的權重最小值是1，並且不能超過設置的權重
        return ww < 1 ? 1 : (Math.min(ww, weight));
    }

RandomLoadBalance

隨機調用是負載均衡算法中最常用的算法之一，也是 dubbo 的默認負載均衡算法，實現起來也較為簡單
隨機調用的缺點是在調用量比較少的情況下，有可能出現不均勻的情況

	@Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // Number of invokers
        int length = invokers.size();
        // Every invoker has the same weight?
        boolean sameWeight = true;
        // the weight of every invokers
        int[] weights = new int[length];
        // the first invoker's weight
        int firstWeight = getWeight(invokers.get(0), invocation);
        weights[0] = firstWeight;
        // The sum of weights
        int totalWeight = firstWeight;
        for (int i = 1; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            // save for later use
            // 依次把權重放到數組對應的位置
            weights[i] = weight;
            // Sum
            // 累加權重
            totalWeight += weight;
            // 如果出現權重不一樣的，sameWeight 設為false
            if (sameWeight && weight != firstWeight) {
                sameWeight = false;
            }
        }
        if (totalWeight > 0 && !sameWeight) {
            // If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on totalWeight.
            // 在總權重裏面隨機選擇一個偏移量
            int offset = ThreadLocalRandom.current().nextInt(totalWeight);
            // Return a invoker based on the random value.
            for (int i = 0; i < length; i++) {
                offset -= weights[i];
                // 依次用偏移量減去當前權重，小於0說明選中
                if (offset < 0) {
                    return invokers.get(i);
                }
            }
        }
        // If all invokers have the same weight value or totalWeight=0, return evenly.
        // 如果所有的調用者有同樣的權重或者總權重為0，則隨機選擇一個
        return invokers.get(ThreadLocalRandom.current().nextInt(length));
    }

RoundRobinLoadBalance

輪訓算法避免了隨機算法在小數據量產生的不均勻問題，我個人認為，輪訓算法可以理解為隨機算法的一種特例，在大量請求的情況下，從調用次數看，和隨機並無區別，主要區別在於短時間內的調用分配上

加權輪訓算法給人的直觀感受，實現起來並不複雜，算出一權重總量，依次調用即可
例如A，B，C 三個節點的權重比依次 1，200，1000，如果依次輪訓調用，就會出現先調用A 10 次，再調用B 200次，最後調用 C 1000次，不斷重複前面的過程
但這樣有一個問題，我們可以發現C 被練習調用1000次，會對C瞬間造成很大的壓力

dubbo的新版本採用的是平滑加權輪詢算法，輪訓的過程中節點之間穿插調用，可以避免了上面說的問題，因此這塊源碼看起來會稍有難度

輪訓算法 在dubbo 在升級的過程中，做過多次優化，有興趣的可以去了解下該算法的優化過程，也是件很有意思的事情

public class RoundRobinLoadBalance extends AbstractLoadBalance {
    public static final String NAME = "roundrobin";

    private static final int RECYCLE_PERIOD = 60000;

    protected static class WeightedRoundRobin {
        // 權重值
        private int weight;
        // 當前權重值
        private AtomicLong current = new AtomicLong(0);
        // 最後一次使用該對象時間
        private long lastUpdate;

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
            current.set(0);
        }

        // 獲取自增權重基數的當前權重值
        public long increaseCurrent() {
            return current.addAndGet(weight);
        }

        public void sel(int total) {
            current.addAndGet(-1 * total);
        }

        public long getLastUpdate() {
            return lastUpdate;
        }

        // 設置最後一次更新時間戳
        public void setLastUpdate(long lastUpdate) {
            this.lastUpdate = lastUpdate;
        }
    }

    private ConcurrentMap<String, ConcurrentMap<String, WeightedRoundRobin>> methodWeightMap = new ConcurrentHashMap<String, ConcurrentMap<String, WeightedRoundRobin>>();

    /**
     * get invoker addr list cached for specified invocation
     * <p>
     * <b>for unit test only</b>
     *
     * @param invokers
     * @param invocation
     * @return
     */
    protected <T> Collection<String> getInvokerAddrList(List<Invoker<T>> invokers, Invocation invocation) {
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
        Map<String, WeightedRoundRobin> map = methodWeightMap.get(key);
        if (map != null) {
            return map.keySet();
        }
        return null;
    }

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // {group}/{interfaceName}:{version} + methoName 獲取當前消費者的唯一標示
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
        // 獲取對應的 WeightedRoundRobin map,如果不存在，new 一個map放進去
        ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.computeIfAbsent(key, k -> new ConcurrentHashMap<>());
        int totalWeight = 0;
        long maxCurrent = Long.MIN_VALUE;
        long now = System.currentTimeMillis();
        Invoker<T> selectedInvoker = null;
        WeightedRoundRobin selectedWRR = null;
        for (Invoker<T> invoker : invokers) {
            // 服務提供者在的唯一標識
            String identifyString = invoker.getUrl().toIdentityString();
            int weight = getWeight(invoker, invocation);
            WeightedRoundRobin weightedRoundRobin = map.computeIfAbsent(identifyString, k -> {
                WeightedRoundRobin wrr = new WeightedRoundRobin();
                wrr.setWeight(weight);
                return wrr;
            });
            // 如果權重改變了，更新 weightedRoundRobin 裏面權重的值
            if (weight != weightedRoundRobin.getWeight()) {
                //weight changed
                weightedRoundRobin.setWeight(weight);
            }
            // 當前權重自增自身權重
            long cur = weightedRoundRobin.increaseCurrent();
            // 設置最後一次更新時間戳
            weightedRoundRobin.setLastUpdate(now);
            // 如果當前權重大於最大當前權重
            if (cur > maxCurrent) {
                // 重置最大當前權重的值
                maxCurrent = cur;
                // 把當前提供者設為選中的提供者
                selectedInvoker = invoker;
                // 把當前輪訓權重實例設為選中
                selectedWRR = weightedRoundRobin;
            }
            // 累計總權重
            totalWeight += weight;
        }
        // 提供者有變化
        if (invokers.size() != map.size()) {
            // 超過60s沒有使用，刪除掉
            map.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
        }
        if (selectedInvoker != null) {
            // 減去總權重
            // 關於這個地方為什麼要減去總權重，是一個很容易造成迷惑的地方
            // 我的理解：每一次調用循環 每個提供者的 當前權重 都會自增自己的權重
            // 因此在選中后（只有一個被選中），再減去總權重，正好保證了所有 WeightedRoundRobin 中當前權重之和永遠等於0
            selectedWRR.sel(totalWeight);
            return selectedInvoker;
        }
        // 理論上不會走到這個地方
        // should not happen here
        return invokers.get(0);
    }

}

LeastActiveLoadBalance

最少活躍數調用算法是指在調用時判斷此時每個服務提供者此時正在處理的請求個數，選取最小的調用

dubbo 在實現該算法時的具體邏輯如下

1. 選取所有活躍數最少的提供者
2. 如果只有一個，直接返回
3. 如果權重不同，加權隨機選擇一個
4. 如果權重相同，隨機選擇一個

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // Number of invokers
        int length = invokers.size();
        // The least active value of all invokers
        // 最少活躍數量
        int leastActive = -1;
        // The number of invokers having the same least active value (leastActive)
        // 有同樣活躍值的提供者數量
        int leastCount = 0;
        // The index of invokers having the same least active value (leastActive)
        int[] leastIndexes = new int[length];
        // the weight of every invokers
        // 每一個提供者的權重
        int[] weights = new int[length];
        // The sum of the warmup weights of all the least active invokers
        // 最少活躍提供者的總權重
        int totalWeight = 0;
        // The weight of the first least active invoker
        int firstWeight = 0;
        // Every least active invoker has the same weight value?
        // 所有的最少活躍提供者是否擁有同樣的權重值
        boolean sameWeight = true;


        // Filter out all the least active invokers
        for (int i = 0; i < length; i++) {
            Invoker<T> invoker = invokers.get(i);
            // Get the active number of the invoker
            // 活躍數量
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
            // Get the weight of the invoker's configuration. The default value is 100.
            // 獲取權重值
            int afterWarmup = getWeight(invoker, invocation);
            // save for later use
            // 保存權重留着後面用
            weights[i] = afterWarmup;
            // If it is the first invoker or the active number of the invoker is less than the current least active number
            // 如果是第一個提供者，或者當前活躍數量比最少的少
            if (leastActive == -1 || active < leastActive) {
                // Reset the active number of the current invoker to the least active number
                // 重置最少活躍數量
                leastActive = active;
                // Reset the number of least active invokers
                // 重置最少活躍提供者的數量
                leastCount = 1;
                // Put the first least active invoker first in leastIndexes
                // 把最少活躍提供者的索引保存起來
                leastIndexes[0] = i;
                // Reset totalWeight
                // 重置總權重
                totalWeight = afterWarmup;
                // Record the weight the first least active invoker
                // 記錄第一個最少活躍提供者的權重
                firstWeight = afterWarmup;
                // Each invoke has the same weight (only one invoker here)
                // 每個最少活躍提供者是否有同樣的權重？？？
                sameWeight = true;
                // If current invoker's active value equals with leaseActive, then accumulating.
                // 如果當前活躍數量等於最少活躍數量
            } else if (active == leastActive) {
                // Record the index of the least active invoker in leastIndexes order
                // 最少活躍提供者的索引依次放入 leastIndexes
                leastIndexes[leastCount++] = i;
                // Accumulate the total weight of the least active invoker
                // 累計最少活躍提供者的總權重
                totalWeight += afterWarmup;
                // If every invoker has the same weight?
                // 如果當前權重和第一個最少活躍的權重不同，sameWeight 設為false
                if (sameWeight && afterWarmup != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        // Choose an invoker from all the least active invokers
        // 最少活躍提供者只有一個，直接返回
        if (leastCount == 1) {
            // If we got exactly one invoker having the least active value, return this invoker directly.
            return invokers.get(leastIndexes[0]);
        }
        // 如擁有不同的權重，在權重的基礎上隨機選取一個，可以參考 RandomLoadBalance，有同樣的寫法
        if (!sameWeight && totalWeight > 0) {
            // If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on 
            // totalWeight.
            int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
            // Return a invoker based on the random value.
            for (int i = 0; i < leastCount; i++) {
                int leastIndex = leastIndexes[i];
                offsetWeight -= weights[leastIndex];
                if (offsetWeight < 0) {
                    return invokers.get(leastIndex);
                }
            }
        }
        // 權重相同，隨機選取一個
        // If all invokers have the same weight value or totalWeight=0, return evenly.
        return invokers.get(leastIndexes[ThreadLocalRandom.current().nextInt(leastCount)]);
    }

ShortestResponseLoadBalance

最短時間調用調用算法是指預估出來每個處理完請求的提供者所需時間，然後又選擇最少最短時間的提供者進行調用，整體處理邏輯和最少活躍數算法基本相似

dubbo 在實現該算法時的具體邏輯如下

1. 選取所有預估處理時間最短的提供者
2. 如果只有一個，直接返回
3. 如果權重不同，加權隨機選擇一個
4. 如果權重相同，隨機選擇一個

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // Number of invokers
        int length = invokers.size();
        // Estimated shortest response time of all invokers
        // 最少響應時間
        long shortestResponse = Long.MAX_VALUE;
        // The number of invokers having the same estimated shortest response time
        // 最少響應時間的提供者數量
        int shortestCount = 0;
        // The index of invokers having the same estimated shortest response time
        int[] shortestIndexes = new int[length];
        // the weight of every invokers
        int[] weights = new int[length];
        // The sum of the warmup weights of all the shortest response  invokers
        // 最少響應時間的提供者的總權重
        int totalWeight = 0;
        // The weight of the first shortest response invokers
        // 第一個最少響應時間的權重
        int firstWeight = 0;
        // Every shortest response invoker has the same weight value?
        // 所有的最少響應時間提供者是否擁有同樣的權重值
        boolean sameWeight = true;

        // Filter out all the shortest response invokers
        for (int i = 0; i < length; i++) {
            Invoker<T> invoker = invokers.get(i);
            RpcStatus rpcStatus = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName());
            // Calculate the estimated response time from the product of active connections and succeeded average elapsed time.
            //  平均響應成功時間
            long succeededAverageElapsed = rpcStatus.getSucceededAverageElapsed();
            // 活躍的連接連接數量
            int active = rpcStatus.getActive();
            // 預估響應時間
            long estimateResponse = succeededAverageElapsed * active;
            // 獲取權重值
            int afterWarmup = getWeight(invoker, invocation);
            // 保存權重留着後面用
            weights[i] = afterWarmup;
            // Same as LeastActiveLoadBalance
            // 如果預估時間小於最少的響應時間
            if (estimateResponse < shortestResponse) {
                // 重置最少響應時間
                shortestResponse = estimateResponse;
                // 最少響應時間的提供者數量設為1
                shortestCount = 1;
                // 保存提供者下標
                shortestIndexes[0] = i;
                // 重置最少響應時間的提供者的總權重
                totalWeight = afterWarmup;
                // 重置第一個最少響應時間的權重
                firstWeight = afterWarmup;
                sameWeight = true;
                // 如果當前最少響應時間等於最少響應時間
            } else if (estimateResponse == shortestResponse) {
                // 最少最少響應時間的下標依次放入 shortestIndexes
                shortestIndexes[shortestCount++] = i;
                // 累計最少響應時間的總權重
                totalWeight += afterWarmup;
                // 如果當前權重和第一個最少響應時間的權重不同，sameWeight 設為false
                if (sameWeight && i > 0
                        && afterWarmup != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        // 最少最少響應時間只有一個，直接返回
        if (shortestCount == 1) {
            return invokers.get(shortestIndexes[0]);
        }
        // 如擁有不同的權重，在權重的基礎上隨機選取一個，可以參考 RandomLoadBalance，有同樣的寫法
        if (!sameWeight && totalWeight > 0) {
            int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
            for (int i = 0; i < shortestCount; i++) {
                int shortestIndex = shortestIndexes[i];
                offsetWeight -= weights[shortestIndex];
                if (offsetWeight < 0) {
                    return invokers.get(shortestIndex);
                }
            }
        }
        // 權重相同，隨機選取一個
        return invokers.get(shortestIndexes[ThreadLocalRandom.current().nextInt(shortestCount)]);
    }

ConsistentHashLoadBalance

一致性hash算法是一種廣泛應用與分佈式緩存中的算法，該算法的優勢在於新增和刪除節點后，只有少量請求發生變動，大部分請求仍舊映射到原來的節點
為了防止節點過少，造成節點分佈不均勻，一般採用虛擬節點的方式，dubbo默認的是160個虛擬節點

網上關於一致性hash算法的文章有很多，這裏就不再多贅述，以下是dubbo中的實現，需要說明的是， 一致性hash算法中權重配置不起作用

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String methodName = RpcUtils.getMethodName(invocation);
        // {group}/{interfaceName}:{version} + methoName 獲取當前消費者的唯一標示
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
        // using the hashcode of list to compute the hash only pay attention to the elements in the list
        int invokersHashCode = invokers.hashCode();
        // 獲取當前消費者的一致性hash選擇器
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        // 如果 selector 還沒初始化，或者 invokers 已經變化，重新初始化 selector
        if (selector == null || selector.identityHashCode != invokersHashCode) {
            selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, invokersHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }
        return selector.select(invocation);
    }
    // 一致性hash選擇器
    private static final class ConsistentHashSelector<T> {

        // 存儲hash環的數據結構 節點 -> 提供者
        private final TreeMap<Long, Invoker<T>> virtualInvokers;

        // 虛擬節點數量
        private final int replicaNumber;

        // 用來標示所有提供者是唯一標示
        private final int identityHashCode;
        // 用來存儲計算hash值參數下標的數組，例如計算第一個和第三個參數 該數組為[0,2]
        private final int[] argumentIndex;

        ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
            this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
            this.identityHashCode = identityHashCode;
            URL url = invokers.get(0).getUrl();
            // 虛擬節點數量，默認 160
            this.replicaNumber = url.getMethodParameter(methodName, HASH_NODES, 160);
            // 默認只對第一個參數進行hash
            String[] index = COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, HASH_ARGUMENTS, "0"));
            argumentIndex = new int[index.length];
            for (int i = 0; i < index.length; i++) {
                argumentIndex[i] = Integer.parseInt(index[i]);
            }
            for (Invoker<T> invoker : invokers) {
                String address = invoker.getUrl().getAddress();
                // 關於這個地方為什麼要除以4，我理解的是md5後為16字節的數組，計算hash值只需要用到四個字節，所以可以用四次
                // 因此除以4，算是一個性能優化點
                for (int i = 0; i < replicaNumber / 4; i++) {
                    // md5, 獲得一個長度為16的字節數組
                    byte[] digest = md5(address + i);
                    for (int h = 0; h < 4; h++) {
                        // 如果h=0，則用第0,1,2,3四個字節進行位運算，得出一個0-2^32-1的值
                        // 如果h=1，則用第4,5,6,7四個字節進行位運算，得出一個0-2^32-1的值
                        // 如果h=2，則用第8,9,10,11四個字節進行位運算，得出一個0-2^32-1的值
                        // 如果h=3，則用第12,13,14,15四個字節進行位運算，得出一個0-2^32-1的值
                        long m = hash(digest, h);
                        virtualInvokers.put(m, invoker);
                    }
                }
            }
        }

        public Invoker<T> select(Invocation invocation) {
            String key = toKey(invocation.getArguments());
            byte[] digest = md5(key);
            return selectForKey(hash(digest, 0));
        }
        // 根據配置生成計算hash值的key
        private String toKey(Object[] args) {
            StringBuilder buf = new StringBuilder();
            for (int i : argumentIndex) {
                if (i >= 0 && i < args.length) {
                    buf.append(args[i]);
                }
            }
            return buf.toString();
        }

        private Invoker<T> selectForKey(long hash) {
            // 找到hash值在hash環上的位置
            // ceilingEntry 方法返回大於或者等於當前key的鍵值對
            Map.Entry<Long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash);
            // 如果返回為空，說明落在了hash環中2的32次方-1的最後，直接返回第一個
            if (entry == null) {
                entry = virtualInvokers.firstEntry();
            }
            return entry.getValue();
        }
        // 得出一個0-2^32-1的值， 四個字節組成一個長度為32位的二進制数字並轉化為long值
        private long hash(byte[] digest, int number) {
            return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                    | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                    | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                    | (digest[number * 4] & 0xFF))
                    & 0xFFFFFFFFL;
        }

        private byte[] md5(String value) {
            MessageDigest md5;
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                throw new IllegalStateException(e.getMessage(), e);
            }
            md5.reset();
            byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
            md5.update(bytes);
            return md5.digest();
        }

    }

總結

以上就是dubbo負載均衡源碼的全部解析，如果還是不明白，可以看下官方文檔的解析  
http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html

dubbo的負載均衡算法總體來說並不複雜，代碼寫的也很優雅，簡潔，看起來很舒服，而且有很多細節的處理值得稱讚，例如預熱處理，輪訓算法的平滑處理等。

我們平時使用時，可以根據自己的業務場景，選擇適合自己的算法，當然，一般情況下，默認的的隨機算法就能滿足我們的日常需求，而且隨機算法的性能足夠好。

如果覺得dubbo提供的五種算法都不能滿足自己的需求，還可以通過dubbo的SPI機制很方便的擴展自己的負載均衡算法。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

參考：菜菜的sklearn教學之降維算法.pdf!!

PCA(主成分分析法)

1. PCA(最大化方差定義或者最小化投影誤差定義)是一種無監督算法，也就是我們不需要標籤也能對數據做降維，這就使得其應用範圍更加廣泛了。那麼PCA的核心思想是什麼呢？

• 例如D維變量構成的數據集，PCA的目標是將數據投影到維度為K的子空間中，要求K<D且最大化投影數據的方差。這裏的K值既可以指定，也可以利用主成分的信息來確定。
• PCA其實就是方差與協方差的運用。
• 降維的優化目標：將一組 N 維向量降為 K 維，其目標是選擇 K 個單位正交基，使得原始數據變換到這組基上后，各變量兩兩間協方差為 0，而變量方差則盡可能大（在正交的約束下，取最大的 K 個方差）。

2. PCA存在的問題：

• 原來的數據中比如包括了年齡，性別，身高等指標降維后的數據既然維度變小了，那麼每一維都是什麼含義呢？這個就很難解釋了，所以PCA本質來說是無法解釋降維后的數據的物理含義，換句話說就是降維完啦計算機能更好的認識這些數據，但是咱們就很難理解了。
• PCA對數據有兩個假設：數據必須是連續數值型；數據中沒有缺失值。
• 過擬合：PCA 保留了主要信息，但這個主要信息只是針對訓練集的，而且這個主要信息未必是重要信息。有可能捨棄了一些看似無用的信息，但是這些看似無用的信息恰好是重要信息，只是在訓練集上沒有很大的表現，所以 PCA 也可能加劇了過擬合；

3. PCA的作用：

• 緩解維度災難：PCA 算法通過捨去一部分信息之後能使得樣本的採樣密度增大（因為維數降低了），這是緩解維度災難的重要手段；
• 降噪：當數據受到噪聲影響時，最小特徵值對應的特徵向量往往與噪聲有關，將它們捨棄能在一定程度上起到降噪的效果；
• 特徵獨立：PCA 不僅將數據壓縮到低維，它也使得降維之後的數據各特徵相互獨立；

4. 方差的作用：咱們可以想象一下，如果一群人都堆疊在一起，我們想區分他們是不是比較困難，但是如果這群人站在馬路兩側，我們就可以很清晰的判斷出來應該這是兩伙人。所以基於方差我們可以做的就是讓方差來去判斷咱們數據的擁擠程度，在這裏我們認為方差大的應該辨識度更高一些，因為分的比較開（一條馬路給隔開啦）。方差可以度量數值型數據的，數據若是想要區分開來，他那他們的離散程度就需要比較大，也就是方差比較大。

5. 協方差的作用：

6. 計算過程：(下圖為採用特徵值分解的計算過程，若採用SVM算法，則無需計算協方差矩陣！)

為什麼我們需要協方差矩陣？我們最主要的目的是希望能把方差和協方差統一到一個矩陣里，方便後面的計算。

　　假設我們只有 a 和 b 兩個變量，那麼我們將它們按行組成矩陣 X：(與matlab不同的是，在numpy中每一列表示每個樣本的數據，每一行表示一個變量。比如矩陣X，該矩陣表示的意義為：有m個樣本點，每個樣本點由兩個變量組成！）

　　然後：

　　Cov(a,a) = E[(a-E(a))(a-E(a))], Cov(b,a) = E[(b-E(b))(a-E(a))]，因為E(b)=E(a)=0，所以大大簡化了計算！！！(這就體現了去中心化的作用！)

　　我們可以看到這個矩陣對角線上的分別是兩個變量的方差，而其它元素是 a 和 b 的協方差。兩者被統一到了一個矩陣里。

7. 特徵值與特徵向量的計算方法—--特徵值分解與奇異值分解法(SVD)(有關特徵值與奇異值可見我的博文！)

(1) 特徵值分解的求解過程較為簡單，以下圖為例子

(2) 特徵值分解存在的缺點：

• 特徵值分解中要求協方差矩陣A必須是方陣，即規模必須為n*n。
• 後期計算最小投影維度K時，計算量過大。
• 當樣本維度很高時，協方差矩陣計算太慢；

(3) SVD算法(奇異值分解)的提出克服這些缺點，目前幾乎所有封裝好的PCA算法內部採用的都是SVD算法進行特徵值、特徵向量以及K值的求解。

• 奇異值(每個矩陣都有)：設A是一個mXn矩陣，稱正半定矩陣A‘A的特徵值的非負平方根為矩陣A的奇異值，其中A‘表示矩陣A的共扼轉置矩陣(實數矩陣的共軛就是轉置矩陣，複數矩陣的共軛轉置矩陣就是上面所說的行列互換后每個元素取共軛)
• 只有方陣才有特徵值。

(4) SVD算法的計算過程：(numpy中已經將SVD進行了封裝，所以只需要調用即可)

可以發現，採用SVD算法無需計算協方差矩陣，這樣在數據量非常大的時候可以降低消耗。

• A為數據矩陣，大小為M*N(2*5)
• U是一個由與數據點之間具有最小投影誤差的方向向量所構成的矩陣，大小為M*M(2*2),假如想要將數據由M維降至K維，只需要從矩陣U中選擇前K個列向量，得到一個M*K的矩陣，記為Ureduce。按照下面的公式即可計算降維后的新數據：降維后的數據矩陣G = A.T * Ureduce. 
• sigma為一個列向量，其包含的值為矩陣A的奇異值。
• VT是一個大小為N*N的矩陣，具體意義我們無需了解。

利用python實現PCA降維(採用SVD的方法)：

 1 from numpy import linalg as la
 2 import numpy as np
 3 #1.矩陣A每個變量的均值都為0，所以不用進行“去平均值”處理。倘若矩陣A的每個變量的均值不為0，則首先需要對數據進行預處理
 4 #  才可以進行協方差矩陣的求解。
 5 #2.與matlab不同的是，在numpy中每一列表示每個樣本的數據，每一行表示一個變量。
 6 #  比如矩陣A，該矩陣表示的意義為：有5個樣本點，每個樣本點由兩個變量組成！
 7 #3.np.mat()函數中矩陣的乘積可以使用 * 或 .dot()函數
 8 #  array()函數中矩陣的乘積只能使用 .dot()函數。而星號乘（*）則表示矩陣對應位置元素相乘，與numpy.multiply()函數結果相同。
 9 A = np.mat([[-1, -1, 0, 2, 0], [-2, 0, 0, 1, 1]])
10 # A = np.mat([[-1, -2], [-1, 0], [0, 0], [2, 1], [0, 1]]).T
11 U, sigma, VT = la.svd(A)
12 print("U:")
13 print(U)
14 print("sigma:")
15 print(sigma)
16 print("VT:")
17 print(VT)
18 print("-"*30)
19 print("降維前的數據：")
20 print(A.T)
21 print("降維后的數據:")
22 print(A.T * U[:,0])

運行結果圖：與上文採用特徵值分解所得到的降維結果一致！

8.PCA的重建

 眾所周知，PCA可以將高維數據壓縮為較少維度的數據，由於維度有所減少，所以PCA屬於有損壓縮，也就是，壓縮后的數據沒有保持原來數據的全部信息，根據壓縮數據無法重建原本的高維數據，但是可以看作原本高維數據的一種近似。

 還原的近似數據矩陣Q = 降維后的矩陣G * Ureduce.T

9.採用sklearn封裝好的PCA實現數據降維(採用的是SVD算法)：

 1 import numpy as np
 2 from sklearn.decomposition import PCA
 3 # 利用sklearn進行PCA降維處理的時候，數據矩陣A的行數表示數據的個數，數據矩陣A的列數表示每條數據的維度。這與numpy中是相反的！
 4 # A = np.mat([[-1, -1, 0, 2, 0], [-2, 0, 0, 1, 1]]).T
 5 A = np.mat([[-1, -2], [-1, 0], [0, 0], [2, 1], [0, 1]])
 6 pca = PCA(n_components = 1)
 7 pca.fit(A)
 8 # 投影后的特徵維度的方差比例
 9 print(pca.explained_variance_ratio_)
10 # 投影后的特徵維度的方差
11 print(pca.explained_variance_)
12 print(pca.transform(A))

 可以發現，採用sklearn封裝的方法實現PCA與上文的方法達到的結果一致！

10.如何確定主成分數量(針對於Sklearn封裝的PCA方法而言)

PCA算法將D維數據降至K維，顯然K是需要選擇的參數，表示要保持信息的主成分數量。我們希望能夠找到一個K值，既能大幅降低維度，又能最大限度地保持原有數據內部的結構信息。實現的過程是通過SVD方法得到的S矩陣進行操作求解，

11.sklearn中封裝的PCA方法的使用介紹。

PCA的函數原型

 (1)主要參數介紹

n_components

• 這個參數類型有int型，float型，string型，默認為None。 它的作用是指定PCA降維后的特徵數(也就是降維后的維度)。 
• 若取默認(None)，則n_components==min(n_samples, n_features)，即降維后特徵數取樣本數和原有特徵數之間較小的那個；
• 若n_components}設置為‘mle’並且svd_solver設置為‘full’則使用MLE算法根據特徵的方差分佈自動去選擇一定數量的主成分特徵來降維； 
• 若0<n_components<1，則n_components的值為主成分方差的閾值； 通過設置該變量，即可調整主成分數量K。
• 若n_components≥1，則降維后的特徵數為n_components； 

copy

•  bool (default True) 
• 在運行算法時，將原始訓練數據複製一份。參數為bool型，默認是True，傳給fit的原始訓練數據X不會被覆蓋；若為False，則傳給fit后，原始訓練數據X會被覆蓋。 

whiten

• bool, optional (default False)
• 是否對降維后的數據的每個特徵進行歸一化。參數為bool型，默認是False。

（2）主要方法介紹：

fit(X,y=None) ：用訓練數據X訓練模型，由於PCA是無監督降維，因此y=None。 

transform(X,y=None) ：對X進行降維。 

fit_transform(X) ：用訓練數據X訓練模型，並對X進行降維。相當於先用fit(X)，再用transform(X)。 

inverse_transform(X) ：將降維后的數據轉換成原始數據。(PCA的重建)

 （3）主要屬性介紹：

components：array, shape (n_components, n_features) ，降維后各主成分方向，並按照各主成分的方差值大小排序。 

explained_variance：array, shape (n_components,) ，降維后各主成分的方差值，方差值越大，越主要。 

explained_variance_ratio：array, shape (n_components,) ，降維后的各主成分的方差值佔總方差值的比例，比例越大，則越主要。 

singular_values：array, shape (n_components,) ，奇異值分解得到的前n_components個最大的奇異值。

 二、LDA

1. 類間距離最大，類內距離最小(核心思想)

2. LDA的原理，公式推導見西瓜書，這裏主要講一下PCA與LDA的異同點！

• PCA為非監督降維，LDA為有監督降維PCA希望投影后的數據方差盡可能的大（最大可分性），因為其假設方差越多，則所包含的信息越多；而LDA則希望投影后相同類別的組內方差小，而組間方差大。LDA能合理運用標籤信息，使得投影后的維度具有判別性，不同類別的數據盡可能的分開。舉個簡單的例子，在語音識別領域，如果單純用PCA降維，則可能功能僅僅是過濾掉了噪聲，還是無法很好的區別人聲，但如果有標籤識別，用LDA進行降維，則降維后的數據會使得每個人的聲音都具有可分性，同樣的原理也適用於臉部特徵識別。
• 所以，可以歸納總結為有標籤就盡可能的利用標籤的數據（LDA），而對於純粹的非監督任務，則還是得用PCA進行數據降維。
• LDA降維最低可以降維到（類別數-1），而PCA沒有限制

參考資料：https://zhuanlan.zhihu.com/p/77151308?utm_source=qq&utm_medium=social&utm_oi=1095998405318430720

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

如何利用 HtmlSpanner解析 HTML格式 的字符串：

1. GitHub 下載HtmlSpanner項目 https://github.com/NightWhistler/HtmlSpanner

2. 最好是直接放在java目錄下在，這樣不需要改引用的包路徑

3.  引入需要的依賴包

    implementation 'net.sourceforge.htmlcleaner:htmlcleaner:2.21'
    implementation 'com.osbcp:cssparser:1.7'

  4. 使用方法：

 // 頁面上用於展示 html格式的文本布局
 TextView textView = findViewById(R.id.htmlSpanner);
 // 直接 new一個 HtmlSpanner對象
 HtmlSpanner htmlSpanner = new HtmlSpanner(); // 格式化
 // 解析 html得到 spannable對象
 Spannable spannable1 = htmlSpanner.fromHtml("<span style='color:red'>html格式的文字1</span>");
 // 显示到 TextView上
 textView.setText(spannable1);

 5. 在使用中遇到的問題——當富文本中顏色格式是rgb格式，解析失敗

 解決思路：

　　1. 首先我們解析的是style=’color:rgb(0，255，255)’ 這種格式，於是看源碼覺得 CSSCompiler 這個類很有問題

　　2. 找與顏色相關的於是就找到了 parseCSSColor( String colorString ) 這個方法，看起來就是轉換顏色用的

　　3. 源碼的寫法如下：(是沒有對於rgb格式的算法，所以不能解析就很合理啦)

 　　4. 想法修改：( 遇到 0rgb格式就先處理成我們的 hex格式，這樣不就完美了嘛 )

　　5. 工具類代碼如下：

package com.xxx.xxx.xxx;

public class ColorUtil {

     /**
     * rgb 格式的顏色轉 hex格式顏色
     * @param rgb
     * @return
     */
    public static String rgb2hex(String rgb) {
        int r = 0;
        int g = 0;
        int b = 0;
        int left = rgb.indexOf("(");
        int right = rgb.indexOf(")");
        if (left > -1 && right > -1 && right > left) {
            String substring = rgb.substring(left + 1, right);
            String[] split = substring.split(",");
            if (split.length == 3){
                r = Integer.valueOf(split[0].trim());
                g = Integer.valueOf(split[1].trim());
                b = Integer.valueOf(split[2].trim());
            }
        }
        String rFString, rSString, gFString, gSString,
                bFString, bSString, result;
        int red, green, blue;
        int rred, rgreen, rblue;
        red = r / 16;
        rred = r % 16;
        if (red == 10) rFString = "A";
        else if (red == 11) rFString = "B";
        else if (red == 12) rFString = "C";
        else if (red == 13) rFString = "D";
        else if (red == 14) rFString = "E";
        else if (red == 15) rFString = "F";
        else rFString = String.valueOf(red);

        if (rred == 10) rSString = "A";
        else if (rred == 11) rSString = "B";
        else if (rred == 12) rSString = "C";
        else if (rred == 13) rSString = "D";
        else if (rred == 14) rSString = "E";
        else if (rred == 15) rSString = "F";
        else rSString = String.valueOf(rred);

        rFString = rFString + rSString;

        green = g / 16;
        rgreen = g % 16;

        if (green == 10) gFString = "A";
        else if (green == 11) gFString = "B";
        else if (green == 12) gFString = "C";
        else if (green == 13) gFString = "D";
        else if (green == 14) gFString = "E";
        else if (green == 15) gFString = "F";
        else gFString = String.valueOf(green);

        if (rgreen == 10) gSString = "A";
        else if (rgreen == 11) gSString = "B";
        else if (rgreen == 12) gSString = "C";
        else if (rgreen == 13) gSString = "D";
        else if (rgreen == 14) gSString = "E";
        else if (rgreen == 15) gSString = "F";
        else gSString = String.valueOf(rgreen);

        gFString = gFString + gSString;

        blue = b / 16;
        rblue = b % 16;

        if (blue == 10) bFString = "A";
        else if (blue == 11) bFString = "B";
        else if (blue == 12) bFString = "C";
        else if (blue == 13) bFString = "D";
        else if (blue == 14) bFString = "E";
        else if (blue == 15) bFString = "F";
        else bFString = String.valueOf(blue);

        if (rblue == 10) bSString = "A";
        else if (rblue == 11) bSString = "B";
        else if (rblue == 12) bSString = "C";
        else if (rblue == 13) bSString = "D";
        else if (rblue == 14) bSString = "E";
        else if (rblue == 15) bSString = "F";
        else bSString = String.valueOf(rblue);
        bFString = bFString + bSString;
        result = "#" + rFString + gFString + bFString;
        return result;
    }
}

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?